Некоторые задачи маршрутизации и распределения заданий: метод динамического программирования и приближенные алгоритмы

• Автор: Ченцов, Павел Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2004
• Место защиты: Екатеринбург
• Количество страниц: 147 с. : ил.

Список сокращений и обозначений

Глава I. Задачи распределения в группы

1. Введение

2. Оптимизация разбиений измеримого пространства в условиях неточных вычислений

3. Разбиение в сумму интервалов натурального ряда

4. Оценки и алгоритмы на их основе

5. Вычислительный эксперимент

Глава II. Маршрутные задачи с ограничениями

1. Введение

2. Задача коммивояжера с ограничениями

3. Задача курьера
4. Один приближенный метод решения задачи коммивояжера
5. Вычислительный эксперимент
Список литературы
А Приложение

Список сокращений и обозначений
ДП — динамическое программирование. ЗК — задача коммивояжера, п/м — подмножество, в/з — вещественнозначное N — натуральный ряд.
•М, = {0} и АГ = {0; 1; 2;
М. — множество вещественных чисел, д
= - равенство по определению
Диссертационная работа посвящена исследованию экстремальных задач, имеющих смысл распределения и упорядочения заданий. В качестве основного используется метод динамического программирования. Кроме того, рассматриваются приближенные методы. Задачи такого рода возникают, например, в приложениях, связанных с распределением потока задач в многопроцессорных вычислительных комплексах, транспортными задачами, распределением товаров и грузов по складам и хранилищам, распределением работ между исполнителями и т.д. При решении такого рода задач возникают, однако, существенные трудности с организацией вычислений. Так, например, в известной задаче коммивояжера с п городами возникает п вариантов конкретного выбора маршрута. Данная задача является ИР-полной (см. в этой связи [16]). Поэтому представляется важным построение быстродействующих приближенных алгоритмов, использующих специфику той или иной конкретной задачи. С другой стороны, представляется важным исследование структуры решения, что может, в частности, осуществляться посредством применения различных модификаций известного метода динамического программирования Р.Беллмана (см. [3], [5], [25], [40]). Отметим, в частности, применение метода динамического программирования для решения задачи коммивояжера [4], [49]. Для решения этой актуальной задачи применялись и другие методы (точные и приближенные). Отмстим, в частности, известный метод ветвей и границ [37], а также процедуры сведения замкнутой версии задачи к незамкнутой [37] в связи с конструкциями данной работы. Следует упомянуть о естественных связях задачи коммивояжера
Покажем, что Т*(Кі) = T)**(/6“) Vi Є I,п. Возьмем произвольный номер і Є 1, тг. Рассмотрим более детально значения
Т.*(КЛ = таxwj — minWj, Т.**(К?) = тахгв? — min wf
1 к ' jeKi J jeKi J г г J jeK« 1 jeK? J

Т.*(КЛ = таxw — min w, T**(K?) = max w — min w,
1 4 ' weWi tue Wi 1 4 1 ' w£W,° W&W?
где Wi = {Wl:l 6 Ki}, a Wta = {wf : l G Kf}. Ho W? = {wa(l) : l G Kf}, а так как Kf = {a_1(y) : j G Ki}, то справедливо следующее выражение W° — {wQ(a-i(p) : l G Ki}, т.е. Wf = {иц : l G К,}-, итак W{ совпадает с W°, откуда следует, что
Т*(Кг)=ТГ(К?) (1.3.33)
Итак, из (1.3.33), (1.3.31) и (1.3.28) следует, что любому разбиению
№)ієРп є А* (1,1V) можно поставить в соответствие разбиение (K?)ie^ G Д* (1, IV) так, что
Т*(№ети) = ГД(АГ?)І6І^). (1.3.34)
Напротив, любому разбиению (АТг);еГп Є Д«(1> ^0 можно сопоставить разбиение'(АГг)геу^ 6 Д*(1, IV) так, что (в упомянутых ранее обозначениях)
(КГЪе тп = (^)геТН- (1-3-35)
Именно, следует полагать при г 6 1,п, что /б, == {«(у) : у 6 /б*}. Применяя операцию
-> (*?)геТЛ> определенную ранее, получаем: при в Е 1,п
/с = (а-х(у) : у 6 бб3} = {а-х(а(у)) : У € Тб5} - /б5.