Содержание к диссертации
Введение
Глава I. Задачи распределения в группы 18
1. Введение 18
2. Оптимизация разбиений измеримого пространства в условиях неточных вычислений 21
3. Разбиение в сумму интервалов натурального ряда 39
4. Оценки и алгоритмы на их основе 57
5. Вычислительный эксперимент. 70
Глава II. Маршрутные задачи с ограничениями 84
1. Введение 84
2. Задача коммивояжера с ограничениями 86
3. Задача курьера 100
4. Один приближенный метод решения задачи коммивояжера 108
5. Вычислительный эксперимент 117
Список литературы 124
Приложение 134
- Оптимизация разбиений измеримого пространства в условиях неточных вычислений
- Оценки и алгоритмы на их основе
- Задача коммивояжера с ограничениями
- Один приближенный метод решения задачи коммивояжера
Введение к работе
Диссертационная работа посвящена исследованию экстремальных задач, имеющих смысл распределения и упорядочения заданий. В качестве основного используется метод динамического программирования. Кроме того, рассматриваются приближенные методы. Задачи такого рода возникают, например, в приложениях, связанных с распределением потока задач в многопроцессорных вычислительных комплексах, транспортными задачами, распределением товаров и грузов по складам и хранилищам, распределением работ между исполнителями и т.д. При решении такого рода задач возникают, однако, существенные трудности с организацией вычислений. Так, например, в известной задаче коммивояжера с п городами возникает п! вариантов конкретного выбора маршрута. Данная задача является NP-полной (см. в этой связи [16]). Поэтому представляется важным построение быстродействующих приближенных алгоритмов, использующих специфику той или иной конкретной задачи. С другой стороны, представляется важным исследование структуры решения, что может, в частности, осуществляться посредством применения различных модификаций известного метода динамического программирования Р.Беллмана (см. [3], [5], [25], [40]). Отметим, в частности, применение метода динамического программирования для решения задачи коммивояжера [4], [49]. Для решения этой актуальной задачи применялись и другие методы (точные и приближенные). Отметим, в частности, известный метод ветвей и границ [37], а также процедуры сведения замкнутой версии задачи к незамкнутой [37] в связи с конструкциями данной работы. Следует упомянуть о естественных связях задачи коммивояжера со многими другими задачами дискретной оптимизации; см. в этой связи [37]. Исследованию этих задач посвящены работы многих авторов. Сейчас отметим имена только некоторых исследователей, имея в виду работы, близкие в идейном отношении к тематике данной диссертации: Р.Беллман, Е.Я.Габович, А.К.Лейтен, И.И.Меламед, Ю.М. Плотинский, С.И.Сергеев, И.X.Сигал, Г.Г.Сихарулидзе, В.Р.Хачатуров, М.Хелд, D. Applegete, R. Віх-by, V. Chv atal, W. Cook, A.L. Henry-Labordere, G. Laporte, Y. Nobert.
В задачах маршрутизации и распределения заданий конструкции метода динамического программирования использовались в работах [20], [22], [26], [27], [28], [43], [50], [51], [52], [53], [54], [55], [69], [71], где рассматривались, в частности, дискретно-непрерывные экстремальные задачи последовательного обхода множеств одним или несколькими участниками. С этими постановками можно связать задачи последовательного управления (см., например, [б], [7], [8], [10], [11], [12]), включая игровые постановки (см. [32], [34], [76]); упомянутые работы,лежат в русле исследований школы Н.Н.Красовского, используют элементы теории принципа максимума Л.С.Понтрягина, двойственность линейных задач управления и выпуклого программирования, установленную Н.Н.Красовским [33]; в этой связи отметим также исследования А.Б.Куржанского, Ю.С.Осипова, А.И.Субботина. В связи с задачами о последовательном посещении множеств отметим работу [9], в которой использовались методы теории приближения функций. Идеи маршрутизации, развиваемые в дискретной математике, находят, таким образом, свое применение и во многих задачах управления и оптимизации, включающих как дискретную, так и "непрерывную" компоненты решения.
Обстоятельный обзор методов решения задачи коммивояжера и многих других подобных задач дискретной оптимизации имеется в [37], [38] и [39]; отметим, в частности, задачу нескольких коммивояжеров (см., например, работы [35], [78]) и нескольких курьеров [36], в которых одновременно используются элементы маршрутизации и распределения заданий, а также работы [22] и [26], в которых методы маршрутизации в задачах последовательного обхода множеств сочетались с активным использованием метода динамического программирования для целей разбиения пространства заданий.
В связи с вопросами распределения потока задач в многопроцессорных вычислительных комплексах отметим исследования [15], [73], [74]; решение таких задач осложняется необходимостью в рассмотрении процесса распределения в темпе реального времени и дополнительными ограничениями на порядок поступления заданий, их приоритета и некоторыми другими особенностями.
Задачи о разбиении множеств, элементы которых можно интерпретировать как задания, и подобные им в логическом отношении задачи рассматривались в целом ряде работ как в общетеоретическом плане, так и в плане исследования конкретных задач прикладного характера. Отметим, в частности, направление, связанное с кластеризацией. Так, например, в [13] рассматривались свойства оптимальных разбиений (относительно энергии, метрического потенциала, размера). В [18] исследовался алгоритм кластеризации, результат применения которого представляется последовательностью, в которой исключаются заведомо неоптимальные разбиения. В [14] исследовалась задача реализации разбиений множеств булевых наборов асимптотически оптимальными схемами. В [47] рассматривалась задача распределения ресурсов в АСУ реального времени с элементами неопределенности; использовался игровой подход. В [46] исследовались асимптотические представления для характеристик случайных разбиений конечного множества на "блоки". В связи со стохастическими постановками задач о размещении отметим монографию [24]. В [31] рассматривалась задача о назначении работ, т.е., задача о распределении работ между исполнителями, которая в некотором смысле похожа на приводимые выше постановки задач распределения заданий между процессорами, хотя имеет несколько иную систему ограничений.
Отметим, что многие задачи, рассматриваемые в диссертации, могут быть отнесены к классу NP-полных задач (см. в этой связи монографию [16] и оригинальную работу [70]). Следуя [16, гл. 3] отметим в числе близких к исследуемым в работе NP-полных задач задачи "коммивояжер" и "разбиение" ; см. [16, с. 65-67,145]. Известно, что [16, с. 28] NP-полные задачи обычно связывают с проблемой труднорешаемости (заметим, что в теории NP-полных задач рассматриваются обычно задачи распознавания, но соответствующие выводы можно распространить и на задачи оптимизации; см. [16, с. 33]). В этой связи уместно напомнить о различии между полиномиальными ("хорошими") и экспоненциальными алгоритмами: см., например, [16, с. 19-21]. Можно, однако, отметить полезное замечание в [16, с. 21] о том, что различие между упомянутыми типами алгоритмов может принимать "совсем иной характер" , когда размеры решаемых задач невелики. Это и ряд других замечаний в [16] показывают, на наш взгляд, что и для труднорешаемых (терминология [16]) задач алгоритмы, имспуе мые экспоненциальными (см. [16, с. 19]), могут представлять значительный интерес; в этой связи полезно иметь в виду применимость алгоритма в наихудшем случае и аналогичную применимость для решения той или иной индивидуальной задачи. Эти обстоятельства нашли свое отражение в предлагаемой диссертационной работе, где параллельно с разработкой точных и "трудных" алгоритмов, связываемых с вариантами метода динамического программирования, разрабатываются приближенные (и достаточно быстрые) алгоритмы, включающие в ряде случаев элементы теоретических конструкций.
Общие вопросы, связанные с решением задач дискретной оптимизации, рассматривались в монографии [48] (отметим, в частности, само понятие задачи дискретной оптимизации большой размерности; см. [48, гл. I]). В частности, в [48] приведены некоторые методы решения задачи коммивояжера большой размерности: декомпозиция, включающая разбиение пространства заданий, связанных с посещением городов, решение подзадач, формирование приближенного решения основной задачи и аналогичных решений подзадач. Среди практических применений в [48] рассматривалась, в.частности, задача о трассировке печатных плат (см. в этой связи также работу [28], где обсуждалось применение методов последовательного обхода множеств для решения задачи о размещении компонент радиоаппаратуры на печатных платах).
Заметим, что при использовании моделей, включающих элементы задачи коммивояжера или нескольких коммивояжеров в тех или иных конкретных задачах, зачастую возникают дополнительные ограничения, приводящие к затруднениям как в процессе вычислений, так и в теоретическом отношении; в этой связи отметим известную задачу курьера [36], [42] (Dial-A-Ride Problem: [68], [75], [77]). Эти осложнения связаны с конкретными прикладными задачами.
В работе [30] рассматривалась задача коммивояжера для отрезков; рассматривается набор отрезков (с фиксированным направлением прохождения или нет), которые требуется обойти с минимальными затратами (т.е. с наименьшим количеством переходов, не являющихся отрезками). Приводится несколько быстродействующих приближенных алгоритмов и их оценок. Данная задача является задачей коммивояжера с рядом дополнительных ограничений. Такие задачи возникают при оптимизации работы графопостроителей. V Различные постановки и алгоритмы решения транспортных и рас пределительных задач приводятся в монографии [2]. Из наиболее близких постановок можно выделить задачу маршрутизации морского транспорта, которая подобна вышеупомянутой задаче курьера (основное различие — минимизация времени перевозок и увеличение частоты выхода кораблей из каждого порта для случая маршрутизации движения нескольких кораблей), задачу маршрутизации для воздушного и автомобильного транспорта. Кроме того, в этой работе можно выделить исследование таких задач, как распределение имеющихся в наличии транспортных средств по маршрутам транспортной сети, распределение потока железнодорожных составов по параллельным веткам.
Теперь перейдем непосредственно к краткому содержанию диссертации. Первая глава посвящена задаче распределения заданий между участниками. Кратко эту задачу можно проинтерпретировать следующим об разом: пусть имеется набор заданий и некоторое фиксированное количество участников. Требуется "раздать" все задания участникам так, чтобы каждое задание попало только к одному участнику и при этом некоторый критерий имел минимальное значение. lit1 Рассматривается и более общая постановка. Пусть задано непустое множество Е, оснащенное алгеброй Z подмножеств Е : (Е, Z) есть измеримое пространство с алгеброй множеств. Фиксируем п Є TV, п 2; г Є 1, п — номера участников. Для L Є Z и т Є Л/" полагаем, что Am(L, Z) есть def множество всех кортежей (разбиений) ф со свойствами: т г =1 2) Vp Є l,m \/q Є l,m \ {p} : Lpfl = 0. Если зафиксирован набор Ті : Z — • [0, оо[,..., Тп : Z —У [О, оо[, то рассматриваемая общая задача выглядит следующим образом: sup({Ti(Li) : г Є ТРИ}) — inf, (іУієм є Л"( ) В рамках этой более общей постановки могут рассматриваться задачи с Щ бесконечным множеством Е. Решать вышеупомянутую общую задачу пред лагается методом ДП, причем предполагается, что при вычислении слоев функции Беллмана могут возникать ошибки. Для реализации такого подхода предлагается ввести операторы: Am : F — F, где F множество всех функций из Z в [0, оо[, по следующему правилу: при f Єи LeZ Am(f)(L)= inf sup({/(A);Tm+1(L\A)}); AeZ,AcL здесь m Є 1, n — 1. На основе этих операторов функция Беллмана строится щ итерационным способом: v\ = Ті; Vm Є l,n — 1 : vm+i = Лт(г т) Пусть бі 0,..., бп і 0 и кортеж {ws)sy i 1,п — F удовлетворяет следующим условиям: (wi = Ti)&(Vm Є l,n- 1 УЬЄ Z : \wm+i(L) - Am(wm)(L)\ em). Легко видеть, что в данном случае вводятся огрубленные варианты действия операторов А\, .,Ап-і. Устанавливается, что g VreXnVLe Z : \wr(L) - vr(L)\ ]Гє5. Пусть v — истинная функция Беллмана, a w — какая-либо ее модель, имеющая своими слоями w\,...,wn, и при этом известно, что Vs Є I,n-1VL€ Z: \ws(L) -vs(L)\ lus.
В частности, эта модель может быть построена в рамках вышеупомянутого сценария с огрублениями операторов Лі,...,Л„ і. Кроме того, пусть разбиение построено с точностью, определяемой на каждом шаге соответ-ствующим элементом кортежа (а )вєІ =ї : 1,и-1 — [О, оо[, именно, если тб 1,п-1 и L Є Z, то полагаем, что ячейка конструируемого разбиения выбирается из множества m(wm, L, am) = {А Є Z I Л С L, sup({ium(L \ Л); Тт+і(Л)}) Am(ti7m)(L) + am}. Тогда для полученного, посредством приведенной в работе процедуры на основе метода ДП, разбиения (]Ц )гєТ7г An(E,Z) справедлива оценка (V = vn(E) — значение задачи) п—1 п—1 sup({Tfc(Lfc) : к Є ї п}) V + ]Г a,- + 2 . г=1 г=1
Далее рассматривается более частная постановка. Пусть задано чис-ло N, N 2; г Є 1, N — номера заданий. Также задано число n, п 2, где г Є 1,п — номера участников. Пусть J — {p q : р Є l,N q Є 1,N} — семейство всех промежутков Л/", содержащихся в 1, N, включая пустой промежуток. Будем полагать, что участники г Є 1,п распределяют задания из 1, N по промежуткам 4- 1, /2, 2 + 1 h, ••• К + 1 Wi гДе +ь 1\ — 0, /n+i = N. Кроме того, задан набор функций множеств
Ті : J - [0, оо[,..., Tn : J - [О, оо[.
Пусть ДП(АГ) — множество всех разбиений 1, АГ в сумму п промежутков из J вышеупомянутого типа. Рассмотрим задачу: sup({Ti(A) : і Є М}) — min, (Д)гєТ € An(N). В работе предложена быстродействующая процедура на основе метода ДП, позволяющая получать оптимальное решение такой задачи. Кроме того, рассмотрена постановка, в которой требуется строить произвольное разбиение 1, N. Пусть N — семейство всех подмножеств 1, JV, Дп(1, АГ) — множество всех разбиений множества 1, N в сумму п подмножеств. Итак, ДП(1,АГ) есть множество An(E,Z) в условиях, когда Е = 1, AT, a Z есть алгебра всех п/м множества 1, N. Пусть V К Є N \ {0} Т (К) = maxwi — min Wj, г єК jeK где Wi Є К., г Є 1, п, — некоторые числовые характеристики заданий; Г (0) = 0. В работе доказано, что задача вир({Г(Ki) : і Є hN}) —+ min, (Я&да Є Д„(М0 эквивалентна приведенной выше "интервальной" постановке с условием предварительной перенумерации W{ в порядке возрастания и набором функций критерия вида: Т\ = Г2 = ••• = Тп = Т , т.е. TAD) = Т2( ) = = Tn( ) = max - min VDeJ\ {0}, где (гу") — зависимость после перенумерации. Это позволяет использовать быстродействующий алгоритм на основе метода ДП (для задачи о разбиении l,iV в сумму промежутков) для решения задачи оптимизации произвольных разбиений 1,ЛГ с критерием, формируемым на основе Т . Рассмотрено применение этой процедуры к векторным выборкам по каждой из координат в отдельности для анализа зависимостей между заданиями.
Рассматривается также следующий вариант задачи распределения заданий между участниками. Пусть задан набор заданий, т.е. множество 1,ЛГ, и п участников. Кроме того, пусть задан набор функций множеств Гі :N-»R,...,Tn :N- R, имеющих смысл суммы (три разных набора для трех постановок, в двух из которых участвуют коэффициенты). Именно, полагаем, что в качестве данного набора используется один из трех следующих наборов функций: Ti(K) = Y xh і Є Ї7й, Л Є N; jeh Ті{К) = - х;-,геМ,Л Є N, aiJtK Ti(K) = Y Xj-ai 2xit гЄЇ ,ІГєМ, jeK 1=1 где хі Є Ш,Х{ 0,і Є 1,N, — некоторые характеристики заданий, а п а.{ 0 Vi Є l,n, Y ai — 1? — коэффициенты, задающие соотношение, t=i в соответствии с которым требуется распределить набор заданий между участниками (сумма Xj,j Є К, при К = 0 полагается равной 0). Основная задача для каждого из трех случаев имеет вид: аир({Т{(К{) : г Є М}) — inf, (/. є Д»(М0 Для этой задачи (рассматриваемой для каждого из трех наборов функций критерия) получены оценки экстремума снизу. Построен быстродействующий приближенный алгоритм, опирающийся на эти оценки и некоторые особенности исследуемой задачи.
Вторая глава посвящена маршрутным задачам с ограничениями. Задана база и набор из N городов. Стоимости переходов заданы при помощи следующей матрицы:
А = {Aij Є Ш]і Є (Щ j Є TJJ)
Пусть Р — множество всех перестановок чисел из 1, iV, т.е. множество всех биекций 1, N на себя. Для абР стоимость вычисляется следующим образом:
С(а) = Л,а(1) + 22 OVC/ +l)-І=1
Незамкнутая задача коммивояжера имеет вид:
с (а) — min, а Є Р. Через 91 обозначаем семейство всех непустых п/м множества 1, N,
D = {(s, К) Є (V/V xVl\sK}.
Фиксируем отображение
I : D —» 91,
для которого выполняется следующее условие:
/(s, ) Cif V if) Є Р.
Смысл данного отображения состоит в следующем. Пусть имеется некоторый набор городов К, который требуется обойти, выйдя из города с номером s. В задаче коммивояжера без ограничений можно было совершить переход из s в любой город из К. В данном случае на выбор маршрута наложены ограничения, реализуемые следующим образом: 7(s, К) — это множество тех городов из К, в которые переход разрешен.
Через Ро обозначаем множество всех перестановок из Р, согласованных с приведенным ограничением. Теперь можно ввести незамкнутую задачу коммивояжера с ограничениями:
с(а) — min, а Є Ро В работе построена модификация метода динамического программирования, предназначенная для решения таких задач. Эта модификация используется для решения известной [37] задачи курьера. Упомянутая задача курьера есть аналог задачи коммивояжера с ограничениями в виде условий предшествования. Для ее решения применяется приведенная выше конструкция решения задачи коммивояжера с "текущими" ограничениями. В задаче курьера фиксированы некоторые пары (pi,qi) городов, причем для каждой такой пары посещение первого города (для этой пары) должно предшествовать посещению второго (между посещением первого города и посещением второго возможно посещение каких-то других городов литературе такие пары называются перевозками (см. [36]). Фиксируем два упорядоченных набора городов: (Рі)ієТЇЇ : Мг —У 1, N, Ыгем : V" — l V-Пусть для каждого непустого множества К, К С 1,п, Зг Є К : рі ф qj Vj Є К. Если К Є N, то через [К] обозначаем множество всех і є 1, n таких, что (pi Є K)Sz(qi Є /С). Для данной задачи предложен конкретный оператор 7, удовлетворяющий всем условиям, приведенным для вышеупомянутой задачи коммивояжера с ограничениями:
7(5, К)йК\ {Qj : j Є ЦК}} V(s, К) Є D.
Установлено совпадение множеств допустимых маршрутов и на этой основе совпадение двух экстремумов: задачи курьера и задачи коммивояжера с упомянутыми ограничениями. Таким образом, данную задачу курьера можно решать при помощи модификации метода ДП для задачи коммивояжера с ограничениями.
Данная система ограничений была применена для построения приближенного алгоритма решения задачи коммивояжера с ограничениями, в идейном отношении имеющего сходство с алгоритмом "иди в ближайший", а также для построения жадного алгоритма решения задачи курьера.
Кроме того, для "обычной" задачи коммивояжера был построен приближенный алгоритм, допускающий естественные аналогии с приближенным алгоритмом решения задачи распределения первой главы (с критерием "типа суммы") и позволяющий за приемлемое время решать задачу о посещении нескольких сотен городов.,
В конце каждой из глав приводятся результаты обширного вычислительного эксперимента; рассматриваются наиболее характерные примеры и демонстрируется быстродействие алгоритмов. В частности, исследуется характер зависимости времени счета от размерности и характера выборки заданий и количества групп, либо, для задачи курьера, от количества пар городов в ограничении.
Основные результаты диссертации опубликованы в следующих рабо-тах: [21], [56], [57], [58], [59], [60], [61], [62], [63], [64], [65].
Оптимизация разбиений измеримого пространства в условиях неточных вычислений
В данном разделе мы рассмотрим одну достаточно общую задачу оптимизации разбиения заданного непустого множества Е в сумму п п/м Е. Каждое такое п/м можно оценить при помощи некоторой заданной функции множеств. Все разбиение оценивается наибольшим значением такого типа. Требуется минимизировать эту оценку качества разбиения. Учитывается то обстоятельство, что ячейки разбиения могут быть, вообще говоря, лишь множествами определенного типа (отметим, в частности, что в дальнейшем (см. раздел 3) будем рассматривать одно из таких конкретных ограничений: ячейки разбиений будут допускаться лишь в виде интервалов натурального ряда). Существует много прикладных задач, в которых возникает необходимость в упомянутой оптимизации разбиений. Уже упоминалась задача п коммивояжеров; отметим здесь же "распределительный блок" задачи о посещении конечного набора множеств несколькими участниками, которая рассматривалась в [26]. В упомянутых задачах рассматривались процедуры оптимизации разбиений конечного промежутка натурального ряда, что соответствует "дискретной" версии исследуемой далее постановки. Отметим сейчас один пример "непрерывной" версии. Пример. Рассмотрим метрическое пространство (R, р), R ф 0, и непустое уэ-ограниченное множество Е : {р(х, у) : х Є Е,у Є Е} С [0, с[, где с є]0,оо[. Каждое непустое подмножество Е измеряется диаметром [66, с. 373], пустому множеству 0 сопоставляется в качестве его оценки число 0. Тем самым на семействе всех п/м Е (а это — алгебра множеств) определена функция, посредством которой можно оценивать разбиение множества Е с целью последующей минимизации. Получаем задачу о "чебышевском" разбиении множества Е в конечную сумму п/м. Сформулируем общую постановку задачи. Будем рассматривать непустое множество Е, оснащенное полуалгеброй (см. [17], [41]) Z подмножеств (п/м) Е : (Е, Z) есть измеримое пространство с полуалгеброй множеств (в [58] в качестве Е использовался конечный "отрезок" натурального ряда, а в качестве Z — семейство всех п/м этого "отрезка"). Фиксируем п Є J\f,n 2, г Є l,n — номера участников или группы, в которые производится распределение. Здесь и ниже для р Є Af и g Є N полагаем pTg = {г Є Af (p i)8z(i g)}, допуская возможность pTg = 0. Для L Є Z и m Є N полагаем, что Am(L, Z) есть def множество всех кортежей для каждого из которых выполняются свойства: Мы ввели в рассмотрение непустое множество (конечных) Z-измеримых разбиений L, имеющих каждое порядок га. В частности, Ап(Е, Z) есть множество всех Z-разбиений "единицы" Е порядка п. Условимся обозначать через F множество всех неотрицательных вещественнозначных (в/з) функций, действующих из Z в [0, оо[. Иными словами, у нас Мы полагаем, что задан кортеж (1.2.2) означает, что Ті : Z — [0, оо[, ...,Т„ : Z — [0, оо[. Теперь мы можем ввести критерий качества: для разбиения (j)iGy Є An(E,Z): качестве основной рассматриваем задачу
Приведем пример такой задачи. Пусть Е = [0,1], Z-семейство всех конечных объединений промежутков (открытых, полуоткрытых, замкнутых) в Е; Z — алгебра подмножеств Е, на ней определена мера Л — след п меры Лебега: если L = \_\ L{ есть дизъюнктное объединение (L и Li — г=1 п промежутки), то \{L) = Y2 l{Li). Пусть функция / : Е — Ш ограничена, г=1 ai 0 и /ЗІ 0 при і Є 1, п. Пусть Tj(0) = А, при L 7 0, L Є Z. Минимизация каждой функции ТІ должна, как видно из формулы, быть взвешенной: минимизируя колебание / на L посредством выбора, в качестве L, множества малой меры, мы можем получить ощутимое возрастание второго (штрафного) слагаемого. Данную задачу можно рассматривать как вариант задач более общего вида. Для этого введем следующие обозначения. Если m Є N и (Ьг)гєГт есть некоторый кортеж (1.2.1), то Критерий задачи (1.2.3) реализуется как вариант (1.2.4). Вообще в (1.2.4) наиболее интересен случай, когда (1.2.1) есть разбиение некоторого изме римого множества. Тогда, при т Є 1,п и L Є Z мы получаем задачу Если в (1.2.5) т = п и L = Е, то реализуется задача (1.2.3). Остальные варианты (1.2.5) будем называть укороченными задачами. Если т Є 1,п, то определяем vm Є F посредством условия: при L Є Z Легко видеть, что на самом деле в (1.2.6) достигается минимум. Экстремум задачи (1.2.3) можно записать следующим образом: V = vn(E). Функции v\,...,vn можно рассматривать как слои функции Беллмана. Из (1.2.4) и (1.2.6) следует очевидное равенство Как обычно, преобразования типа Vk — Vk+\, где к 1,п— 1, характеризуются соотношениями, имеющими смысл уравнения Беллмана. Однако в данном случае, как и в [53], удобно истолковать эти преобразования как действия операторов; при этом удается охватить случай неточно исполняемых преобразований. Итак, мы рассмотрим некоторые операторы из множества {F —У }, полагая до конца настоящего раздела, что Z — алгебра подмножеств Е; см. [41, гл. 1]. Итак, далее (Е, Z) — измеримое пространство с алгеброй множеств. Введем ряд обозначений. Если L Є Z, то через ZL обозначаем семейство всех множеств Л Є Z таких, что Л С L. Если же тп Є 1, п — 1, то полагаем, что
Оценки и алгоритмы на их основе
Рассмотрим следующую общую постановку задачи оптимизации разбиения конечного множества 1, N, где N Є Л/", и iV 2. Элементы г Є 1,N здесь — номера задач или просто задачи. Обозначим через N семейство всех подмножеств 1, N. Пусть п Є TV, n 2, — количество участников, аг Є 1, гг - номера участников или просто участники. Через An(l, N) обозначаем (непустое) множество всех кортежей для каждого из которых выполняется Здесь An(l,iV) можно рассматривать как An(E,Z), где E1 = l,iV a Z — семейство всех подмножеств l,iV. Каждый кортеж (1.4.1),(1.4.2) представляет из себя разбиение 1, N. Пусть задан набор функций множеств на основе которых можно сформулировать соответствующий критерий качества разбиения {Ki)ij Є An(l, N): Теперь с помощью (1.4.4) мы можем сформулировать задачу: Экстремум данной задачи будем обозначать V. Нас интересует разбиение {КІ)ІЄТП Є An(l,iV) являющееся решением приведенной задачи. Один из возможных методов решения приведенной задачи — метод ДП раздела 2 (см., например, [56], [58]; см. также решение других комбинаторных задач по методу ДП в [4], [25], [26], [40], [43]), [49], но вычислительная реализация данного метода затруднена, что не позволяет решать задачи большой размерности. Как правило метод ДП позволяет распределять не более нескольких десятков заданий, но даже в этом случае время счета может составлять часы или дни. Характерной особенностью этого алгоритма является увеличение расхода памяти и времени счета более чем в два раза при добавлении в распределяемую выборку одного нового задания, хотя полный перебор здесь не производится. Поэтому немалый интерес представляет возможность оценить задачу, опираясь на уже построенные решения аналогичных задач. Пусть, у нас есть набор критериев участников (1.4.3) Т{(К), г Є 1, п, К С 1,N, и мы уже решили поставленную выше задачу (1.4.5). В терминах поставленной выше задачи для К Є N и m Є 1,п через ЛШ(К) обозначим (непустое) множество всех кортежей для каждого из которых выполняется Каждый такой кортеж — разбиение К. Случай, когда К. = 1,N и m = п, определяет разбиения всего множества заданий. В методе ДП используются так называемые укороченные задачи. Далее мы будем рассматривать укороченные задачи следующего вида: если К 6 N и т Є 1, п, то полагаем Предложение 1.4.1 Пусть задача решена для набора критериев ТІ(К),І Є 1, п, К Є N, и задан набор других критериев Т{(К), І Є l,n, К Є N. Пусть, кроме того, 9т(К) = тіп sup({Ti(.Kj) : і Є 1,т}) Vm Є l,n VK Є N. Пусть, наконец, ct\,...,ctn - неотрицатель7іие числа, и известно, что Т{(К) Т{(К) + оц Уі ЄЇ п УК Є N. Тогда вт{К) вт{К) + тах({аь ..., ат}) Ут Є 1 п УК Є N. Доказательство Так как формула для определения 0т(К) имеет следующий вид: где т G 1, п и Я" Є N, то справедлива оценка: т.е., мы получили неравенство, сформулированное в предложении. D Остальная часть данной главы посвящена более узкому типу задач, для которых построен ряд оценок и предложен приближенный алгоритм для их решения. Далее выделим несколько содержательных постановок. Содержательная постановка первой задачи такова. Пусть имеется набор чисел Х{ 0, г Є l,iV.
Требуется распределить эти числа в п групп, так, чтобы сумма чисел в каждой из групп была по возможности минимальной. Содержательная постановка второй задачи состоит в следующем. Пусть имеется набор чисел Х{ 0, і Є 1, N. Кроме того, задан набор коэффи п циентов оц 0, і Є l,n, Ylai = 1- Ha содержательном уровне требуется г=1 распределить эти числа в п групп так, чтобы соотношение сумм элементов по группам было максимально близко к соотношению, задаваемому приведенными коэффициентами. При ац = 1/п, і Є 1,п, данная задача связана с предыдущей. Как одну из возможных интерпретаций можно рассматривать задачу распределения заданий по процессорам. Здесь жг- может обозначать число элементарных операций, производимых при решении задачи с номером г. Мы пытаемся распределить эти задачи по процессорам так, чтобы выровнять загрузку процессоров, минимизировав тем самым общее время работы всего комплекса. В этой связи отметим работы [15], [73], [74]. Особенность задач, поставленных в данных работах, состоит в том, что распределению подвергаются либо задачи, поступающие и, соответственно, помещаемые в ту или иную группу (т.е. задачи, передаваемые на обработку тому или иному процессору) с течением времени (см. [15]), либо выборки задач с дополнительными ограничениями на порядок выполнения и приоритетность (см. [73], [74]). Другие возможные интерпретации — распределение товаров по складам, распределение жидких или сыпучих грузов по хранилищам, распределение работ между исполнителями. Коэффициенты из второй по становки позволяют учитывать различные мощности процессоров, объемов складов и т.д. Уточним постановку задачи (см. в этой связи [62] и [64]). Требуется оптимизировать разбиение конечного множества 1, N, где N Є N = {1;2;...} и N 2. Каждому индексу і Є l,iV сопоставляется некоторое положительное число Х{ О, г Є 1, N. Как и ранее, через N обозначаем семейство всех подмножеств 1, N. Число п Є N, п 2, определяет количество участников; числа г Є 1, п - номера участников или просто участники. В остальном постановка идентична приведенной выше. В качестве ТІ, і Є 1,п, будем рассматривать следующие три набора функций множеств (сумму чисел ХІ по пустому множеству 0 отождествляем с 0): где условия на выбор ОСІ,і Є 1,п, те же самые, что и в случае (1.4.9). В первом случае Т\ — ... = Тп. Для сформулированной ранее задачи (1.4.5), для каждого из трех типов функций критерия, установлены нижние оценки экстремума V. Предложение 1.4.2. Для критерия, определяемого функциями (1.4.9), где О І,І Є 1,п, удовлетворяют упомянутым в связи с (1.4.9) условиям,
Задача коммивояжера с ограничениями
В данном разделе рассматриваются версии незамкнутой задачи коммивояжера, в которой накладываются дополнительные ограничения на текущие переходы из города в город. Именно, предполагается, что из списка городов, в которые возможен текущий переход из уже достигнутого города, "вычеркивается" ряд городов. Возникают, стало быть, ограничения на текущие переходы. Такое ограничение может быть связано как с потребностями в построении приближенных алгоритмов (напомним, что задача коммивояжера является NP-полной), так и с целесообразностью сведения к данной постановке других задач. Здесь отметим совсем кратко задачу курьера, в которой требуется посетить полную систему городов в условиях, когда посещение одного фиксированного города должно предшествовать посещению другого. Такое условие может быть связано с передачей той или иной корреспонденции или доставки каких-либо грузов при движении по выбранному маршруту. Для упомянутой задачи также строится позднее модификация метода динамического программирования. Заметим, что в целом ряде задач такого рода, осложненных ограничениями, применение метода ДП затруднено (см. [4], [49]). Далее мы конструируем специальную версию ЗК с ограничениями, налагаемыми на текущие переходы из города в город (позднее будет обнаружена применимость упомянутой версии и в некоторых аналогах ЗК с "функциональными" ограничениями). Такая реализация возможна потому, что подобные ограничения хорошо согласуются с логикой метода ДП, хотя и осложняют обоснования. При этом список городов, оставшихся после реализации начального отрезка маршрута, искусственным образом сокращается до списка городов, переход в которые на данном шаге допустим. Эти содержательные рассуждения далее реализуются посредством выделения допустимых маршрутов (среди всевозможных), причем это осуществляется и в основной задаче, и в задачах, являющихся по смыслу укороченными (в качестве базы может использоваться любой город, а массив последующих городов может соответствовать любому сокращению полного списка). Получающаяся при этом система задач позволяет сформировать функцию Беллмана обычным способом, после чего мы вводим естественную, для данной системы, версию уравнения Беллмана. Конкретное построение функции Беллмана, как обычно, реализуется "в обратном времени" (от простого к сложному); на основе этой функции мы вводим "бел-лмановские" маршруты, непременно оптимальные в нашей ЗК с ограничениями. Предлагаемые здесь конструкции соответствуют, работе [60].
Полезно отметить, что конструируемая вспомогательная ЗК с ограничениями может быть полезна и для других содержательных задач маршрутизации, которые в данной работе не рассматриваются (в частности, можно исследовать вопросы компромиссного выбора очередного города, имея в .виду возможность немедленного извлечения выгоды и подготовки условий для извлечения выгоды в процессе будущих перемещений). В связи с исследованиями ЗК отметим также работы [44], [45], где, в частности, предложен подход, связанный с использованием задач управления; см. также [72] в связи с различными подходами к построению алгоритмов решения ЗК. Общие вопросы, связанные с методом ДП см. в [5] и [40]. Наконец, отметим обстоятельный обзор [37], [38], [39] в области теории и методов решения ЗК и различных аналогов ЗК; см. также обширную би блиографию [37], [38], [39]. Далее напомним понятие интервалов, введенное в разделе 3 главы 1. Если і Є Л/о и j Є Л/о, то есть промежуток Л/о с концами г, ji; мы допускаем случай, когда (2.2.1) есть пустое множество. Фиксируем N Є Л/, iV 2, и п Є Л/, а также матрицу где (здесь и ниже) R — вещественная прямая. Пусть Р — множество всех перестановок чисел из 1, N, т.е. множество всех биекций 1, N на себя. Через 91 обозначаем семейство всех непустых п/м множества l,iV; N = 9t U№ — семейство всех п/м 1, N, Далее элементы непустого множества D (2.2.2) именуем позициями. Фиксируем отображение Отметим ряд полезных свойств, связанных с (2.2.2)-(2.2.4): учтена биективиость a. Следует заметить, что в случае поиска оптимального решения задачи курьера зависимость I(s, К) от s Є 0, N нам не потребуется; возможно, однако, применение этого "механизма" к построению приближенных алгоритмов решения этой задачи, где подобная зависимость существенна. Через Ро обозначаем множество всех маршрутов а Є Р таких, что Таким образом, мы построили PQ — множество всех перестановок множества 1, N, удовлетворяющих нашим ограничениям. Но если мы хотим ре-шать задачу посредством метода ДП, то нам следует ввести и так называемые "укороченные"задачи. Если К Є N, то через \К\ обозначаем мощность К; \К\ Є О, N. При этом, конечно, 0 = 0. Для всякого множества К Є 91 через (Ы)[К] обозначаем непустое множество всех биекций [1, с. 319] "отрезка" 1, \К\ (напомним, что в нашем случае \К\ Є Л/") на К. Разумеется, (Ьг)[1, N] = Р. Если (s, К) Є В и а Є (Ьг)[К], то отображение
Один приближенный метод решения задачи коммивояжера
В конце первой главы был приведен один приближенный алгоритм решения задачи распределения заданий между участниками. Вычислительный эксперимент показал хорошее быстродействие и приемлемую точность алгоритма. Можно сделать вывод, что для многих задач, пусть для достаточно "узких" постановок, возможно строить быстродействующие и притом достаточно точные приближенные алгоритмы. Так, в ходе работы была предпринята попытка построить новый приближенный алгоритм решения обычной незамкнутой задачи коммивояжера (см. в этой связи работу [65]). Следует отметить, что данная задача является NP-трудной (см. [16, с. 145]). В упомянутой монографии [16] она включена в число шести основных NP-полных задач (заметим (см. [25, с. 837]), что для NP-полных задач не найдено полиномиальных алгоритмов их решения, но и не доказано, что таковых не существует), см. [16, с. 64-67]; она отнесена к задачам, труднорешаемость которых доказуема [16, с. 25], хотя в рассуждениях такого рода рассматривается обычно не экстремальная задача, а задача о возможности выбора маршрута с качеством не хуже заданного. Однако, как уже отмечалось во Введении, оптимизационная версия данной задачи "по крайней мере столь же сложна" (см. [16, с. 33]). Заметим, наконец, что обычно рассматривается замкнутая задача коммивояжера, а точнее, задача о построении замкнутого маршрута с возвратом на базу; см., например, [16, с. 16,17]. В [37] указан, однако, вариант редукции замкнутой задачи к незамкнутой, в которой возвращение на базу не требуется (разумеется, реализуема и "обратная" редукция). Мы останавливаемся в этой связи на последней версии, более близкой в логическом отношении другим конструкциям настоящей работы. Для решения задачи коммивояжера используются различные методы, точные и приближенные (см. [37], [38], [39], [44], [45] и др.). Если рассматривать метод ветвей и границ и метод динамического программирования, то можно сказать, что они обладают недостаточно высоким быстродействием и мощностью (наиболее сложен в вычислительном плане метод ДП, который не позволяет даже на достаточно мощных вычислительных машинах решать задачу о посещении более чем несколько десятков городов). Следует отметить один важный результат [67]: решение задачи обхода 13509 городов, что потребовало, конечно, больших затрат машинного времени. В работе [2] приведен широкий обзор различных приближенных алгоритмов решения маршрутных задач. Сформулируем общую постановку незамкнутой задачи коммивояжера. Задано натуральное число N,N 2, определяющее (число городов. Фиксируем матрицу затрат Через Р, как и ранее, обозначаем множество всех перестановок чисел из 1, N. Перестановки из Р будем называть маршрутами. Для любого р Є Р мы можем вычислить его стоимость при помощи следующего соотношения Далее рассматриваем задачу вида Перейдем непосредственно к описанию алгоритма решения этой задачи. Данный алгоритм был разработан в ходе анализа различных выборок городов и решений, полученных с использованием других методов. Для большей ясности алгоритм разбивается на ряд этапов. Этап 1. На этом этапе мы строим некоторый базовый маршрут, который далее будем стараться оптимизировать.
В качестве алгоритма поиска такого маршрута (его можно рассматривать как начальное приближение) предлагается хорошо известный метод "иди в ближайший". Хотя этот алгоритм является простым и быстрым, в ряде случаев он не дает хорошего результата в смысле качества. Суть этого простейшего алгоритма состоит в следующем. Заметим, что ближайшим городом из множества К С 1,N от города г, г . К, будем называть такой город j Є К, для которого значение Aij минимально среди всех Л , , к Є К. В этих терминах реализуются следующие действия (шаги): 1. Находим во всем наборе городов ближайший до базы, и добавляем его в маршрут как первый город конструируемого маршрута. В случае, если таких городов несколько, рассматриваем переходы в каждый (из ближайших) город по очереди с дальнейшим продолжением решения отдельно для каждого такого города. 2. В оставшемся наборе городов ищем город, ближайший к только что добавленному в маршрут, и помещаем его в маршрут следующим. Если таких городов несколько, то рассматриваем переходы в каждый ближайший город по очереди с дальнейшим решением задачи отдельно для каждого такого города. 3. Шаг 2 повторяется до тех пор, пока все города не попадут в марш
Похожие диссертации на Некоторые задачи маршрутизации и распределения заданий: метод динамического программирования и приближенные алгоритмы
