Содержание к диссертации
Введение
Глава I. Вводные аспекты 17
1.1. Маршрутно-распределительная задача 17
1.2. Задача коммивояжера 19
1.2.1. «Натуральные порядки» 22
1.2.2. Задача коммивояжера как задача линейного целочисленного программирования 24
1.2.3. Метод динамического программирования в задаче коммивояжера 24
1.2.4. Задача курьера 26
1.2.5. Обобщенная задача коммивояжера 27
1.3. Задача распределения заданий 28
1.3.1. Задача распределения заданий как задача линейного целочисленного программирования 30
1.3.2. Метод динамического программирования в задаче распределения заданий 31
1.4. Принцип Беллмана и метод динамического программирования 32
1.4.1. Дискретные процессы и управления 34
1.4.2. Принцип оптимальности 36
1.4.3. Динамическое программирование 37
1.4.4. Вычислительные аспекты метода динамического программирования 39
1.5. Задачи последовательного управления 42
1.5.1. Управляемая система. Принцип максимума Понтрягина 45
1.5.2. Задачи последовательного управления 48
1.5.3. Последовательное управление движением самолета 49
1.5.4. Об одной дискретизации задачи последовательного управления 50
1.5.5. Задача быстродействия в классе простых движений с элементами маршрутизации 51
1.5.6. Игровые постановки 53 1.6. Устойчивость в задаче комбинаторной оптимизации 54
1.6.1. Введение 54
1.6.2. Классический подход 56
1.6.3. Реоптимизация 58
1.6.4. Шаблонные маршруты 59
1.7. Адаптивная устойчивость 60
1.7.1. Общая теория 60
1.7.2. Структура приложений адаптивной устойчивости 69
Глава II. Адаптивная устойчивость оптимального маршрута в задаче коммивояжера при изменении мноясества посещаемых вершин 73
II. 1. Введение и обозначения 73
11.2. Необходимые условия 78
11.2.1. Вопросы теории 78
11.2.2. Алгоритмические приложения 82
11.2.3. Эксперименты 85
11.3. Критерий адаптивной устойчивости 92
11.3.1. Вопросы теории 92
11.3.2. Алгоритмические приложения 100
11.3.3. Эксперименты 102
11.4. Достаточные условия 109
11.4.1. Вопросы теории 109
11.4.2. Аналитические области адаптивной устойчивости 114
11.4.3. Алгоритмические приложения 116
11.4.4. Эксперименты 120
11.5. Задачи последовательного управления 132
11.5.1. Эвристические решения 132
11.5.2. Адаптивная устойчивость 134
11.6. Некоторые замечания 135
П.6.1. Топология областей адаптивной устойчивости 135
11.6.2. Асимптотика относительной площади области устойчивости в евклидовой ЗК 136
11.6.3. Примеры, демонстрирующие новизну постановки 137
6.4. Модельный пример прикладной задачи с применением областей адап
тивной устойчивости 141
Глава III. Адаптивная устойчивость оптимального распределения при из менении множества распределяемых заданий 144
111.1. Введение и обозначения 144
111.2. Необходимые условия 147
111.2.1. Вопросы теории 148
111.2.2. Алгоритмы 151
111.3. Критерий адаптивной устойчивости 156
111.4. Достаточные условия 162
111.5. Специфика задач распределения заданий 163
111.6. Алгоритмы 173
111.7. Сравнение областей адаптивной устойчивости 184
Глава IV. Усечение схемы динамического программирования 191
IV. 1. Условия предшествования 191
IV.2. «Встречное» динамическое программирование 195
IV.2.1. Задача коммивояжера 196
IV.2.1.1. Обозначения и классическая схема 196
IV.2.1.2. Сокращенная схема 200
IV.2.1.3. Сравнение трудоемкости 203
IV.2.1.4. Заключение 205
IV.2.2. Задача распределения заданий 206
IV.2.2.1. Обозначения и классическая схема 207
IV.2.2.2. Сокращённая схема МДП 209
IV.2.2.3. Сравнение трудоемкости 214
IV.3. Кластеризация в задаче коммивояжера 217
IV.3.1. Алгоритм решения ЗК без дополнительных условий 217
IV.3.2. Дополнительные условия на маршрут 226
IV.3.3. Эксперименты 231
IV.3.4. Заключение 233
IV.4. Выводы к четвертой главе 234
Глава V. Приложения 236
V.l. Адаптивная устойчивость в управлении перемещением транспортных средств236
V.l.l. Грузоперевозки 236
V.l.2. Авиапожарное патрулирование 238
V.2. Приложения минимаксной маршрутно-распределительной задачи 240
V.2.I. Математическая постановка задачи 240
V.2.2. Оптимизация перемещений в агрессивной среде 241
V.2.3. Эволюционная изменчивость 246
V.2.3.I. Содержательная постановка 247
V.2.3.2. Эвристический алгоритм 248
V.2.3.3. Модельный эксперимент 248
V.3. Оптимизация перемещений исследователя-этолога 254
V.3.I. Перестановка камер на местности 254
V.3.1.1. Формальная постановка задачи 255
V.3.1.2. Метод динамического программирования 256
V.3.1.3. Доказательство оптимальности 257
V.3.1.4. Эксперимент 259
V.3.2. Другие постановки 260
Заключение 263
Литература 268
- Задача распределения заданий как задача линейного целочисленного программирования
- Алгоритмические приложения
- Критерий адаптивной устойчивости
- Алгоритм решения ЗК без дополнительных условий
Введение к работе
Актуальность работы. Задачи комбинаторной оптимизации (ЗКО) встречаются практически во всех областях человеческого знания, где требуется из большого числа вариантов выбрать наилучший или как минимум целесообразный. В качестве примеров таких задач можно привести планирование производства; оптимизацию коммуникационной инфраструктуры; оптимизацию загрузки параллельно работающих исполнителей (это могут быть, например, станки, рабочие или конвейеры современного вычислителя); задачи оптимальной загрузки транспортных контейнеров; оптимизацию раскроя в швейном и металлообрабатывающем производствах, задачи оптимизации расписаний. С теоретической точки зрения многие ЗКО служат в качестве своеобразных эталонов трудоемкости для задач, поддающихся алгоритмическому решению за конечное число итераций. Исследование ЗКО сыграло важную роль в становлении современной теории сложности алгоритмов и в формулировке одной из важнейших математических проблем современности, касающейся равенства классов Р и NP. Большое внимание в диссертации уделяется разработке и исследованию алгоритмов. В этой связи следует отметить труды A.V. Alio, D.E. Knuth, J. von Neumann, A.M. Turing, J.D. Ulmann, В.Л. Вереснева, Э.Х. Гимади, А.Ю. Горнова, Ю.И. Журавлева, А.В. Кельманова, А.Н. Колмогорова, ЮА. Кочетова, Н.Н. Кузюрина, А.А. Лазарева, Вл.Д. Мазурова, А.Л. Семенова, М.Ю. Хачая, оказавшие влияние на работу автора.
Основное внимание в диссертации посвящено двум ЗКО: задаче коммивояжера (ЗК) и задаче распределения заданий (РЗ) (наиболее близким аналогом, по-видимому, является задача размещения заказа). К ЗК (или к ее расширению) обыкновенно сводится всякая задача построения оптимального порядка выполнения работ (не считая более общие задачи оптимизации
расписаний). К РЗ сводятся задачи балансировки нагрузки одновременно работающих исполнителей. В настоящей диссертации исследуются как каждая из этих NP-трудных задач по отдельности, так и их важная с прикладной точки зрения комбинация: балансировка нагрузки в бригаде исполнителей осуществляющих перемещение по заданному множеству пунктов. Все исследуемые в диссертации задачи проявляют черты ЗК или РЗ и объединены общим названием «маршрутно-распределительные задачи» (МРЗ). К МРЗ сводятся многие из перечисленных выше ЗКО, например: оптимизация перемещения транспортных средств, роботизированных манипуляторов, патрулирующих устройств, оптимизация порядка выполнения заданий на конвейерных производствах и в параллельно работающих вычислителях, моделирование и анализ эволюционных деревьев и другие. В ряде перечисленных постановок, связанных с перемещениями системы, описываемой дифференциальными уравнениями, МРЗ становится непрерывной бесконечномерной задачей последовательного управления (см. работы А.А. Белоусова, Ю.И. Бердышева, М.С. Габриеляна, L.E. Dubins, Н.Ю. Лукоянова, Н.Н. Петрова, А.Г. Ченцова, А.А. Чикрия).
Исследование устойчивости найденных оптимальных решений является одним из важнейших направлений качественного анализа любой оптимизационной задачи. Не являются в этом смысле исключением и ЗКО. В связи с данными исследованиями необходимо отметить школы в ВЦ РАН под рук. основателя теории устойчивости в ЗКО В.К. Леонтьева; Белорусском ГУ под рук. В.А. Емеличева; Институте кибернетики НАН Украины под рук. И.В. Сергиенко; оригинальные работы по устойчивости алгоритмов решения целочисленных ЗКО, основанных на переборе L-структур, ведущиеся в Омском ГУ под рук. А.А. Колоколова; работы М. Либура, Польша, А. Фиакко, США и оригинальный результат В.Г. Дейнеко, связанный с критерием оптимальности шаблонного маршрута (The Master Tour Problem).
В общем случае исследование возможности конструктивного использования найденного оптимального решения при построении оптимального решения задачи с возмущенными начальными данными связано с понятием реоптимизации (reoptimization) и, в меньшей степени, онлайн-оптимизации. В области реоптимизации решений полиномиальных задач следует отметить работы P.M. Spira, F. Chin, V. King, С. Demetrescu. Сам термин «реоптими-зация» принадлежит, по всей видимости, M.W. Schaffter. Особенный интерес реоптимизация представляет в NP-трудных задачах, например в ЗК (С. Archetti, L. Bertazzi, М. С Speranza, S. Arora, H.-J. Bockenhauer, J. Hromkovic, B. Escoffier, G. Ausiello, T. Berg). В NP-трудных задачах (и в частности в ЗК) реоптимизация, как правило, оказывается также NP-трудной (A. Zych). Ситуация не меняется и в случае, когда известны все оптимальные решения исходной задачи (J. Hromkovic). Среди современных авторов, активно работающих над вопросами реоптимизации, следует отметить J. Hromkovic, H.-J. Bockenhauer, A. Zych, Т. Tamir.
В настоящей диссертации рассматривается оригинальный подход к постоптимальному анализу, цели которого близки к классической устойчивости, рассматриваемые постановки к реоптимизации, а методология исследования основана на принципе Беллмана. А именно изучаются условия, описывающие класс возмущений, к которым фиксированный алгоритм позволяет адаптировать найденное оптимальное решение. Подобная «алгоритмоспецифическая» усточивость/реоптимизация названа в диссертации адаптивной устойчивостью. Исследование адаптивной устойчивости оптимальных решений трудоемких дискретных задач представляет прикладной интерес в первую очередь как средство постоптимального анализа и отбора наиболее перспективных среди множества несравнимых между собой оптимальных решений, соответствующих различным математическим моделям исследуемого явления.
Цель диссертационной работы состоит в исследовании методов ре-
шения, постоптимального отбора решений, а также областей прикладного применения МРЗ.
Для достижения поставленной цели были решены следующие задачи:
построена единообразная теория адаптивной устойчивости оптимальных решений в ЗКО, обладающей определенной структурой, для случаев добавления, удаления или замены одного из элементов множества начальных данных; построенные теоретические схемы реализованы применительно к ЗК и РЗ; разработаны оригинальные алгоритмы проверки адаптивной устойчивости и проведена оценка их трудоемкости; численно построены области адаптивной устойчивости для ЗК на конечном подмножестве точек евклидовой плоскости с целочисленными координатами; результаты для ЗК обобщены на задачу оптимального размещения графа на своих вершинах;
для «симметричных» постановок ЗК и РЗ построены экономные в вычислительном отношении «встречные» варианты метода динамического программирования (МДП); проведена оценка снижения трудоемкости МДП в ЗК, возникающего при добавлении в задачу одного условия предшествования; построен специфический для ЗК эвристический «неметрический» метод кластеризации посещаемых вершин, позволяющий учитывать условия предшествования;
исследованы точные и эвристические решения ряда прикладных задач, в частности построен и реализован на ЭВМ МДП в задаче перестановки объектов на пересеченной местности; на основе минимаксной МРЗ (ММРЗ) [24] в постановке с общим плавающим стартом (location problem) разработана математическая модель для исследования филогенетических задач; предложен численный метод декомпозиции задачи последовательного управления в набор соответствующих по ограничениям задач управления.
Научная новизна. Все результаты, выносимые на защиту, являются новыми. В частности:
введено понятие адаптивной устойчивости; предложены определения адаптивной устойчивости оптимальных решений ЗКО при добавлении, удалении или замене одного из элементов множества начальных данных; получены соответствующие новым определениям необходимые, достаточные, а также необходимые и достаточные условия сохранения (возможности адаптации) оптимальных решений; построенная общая теория реализована для ЗК и РЗ;
предложены усеченные схемы МДП для «симметричных» постановок ЗК и РЗ; доказана корректность предложенных схем и проведена оценка их трудоемкости; проведена теоретическая оценка трудоемкости специфического МДП для ЗК с условиями предшествования; построен МДП для задачи перестановки объектов на неоднородной местности;
разработан метод иерархической кластеризации посещаемых вершин в ЗК и задаче курьера (ЗК с условиями предшествования), позволяющий понижать размерность задачи;
предложен метод использования ММРЗ в целях поиска как областей потенциального расположения филогенетического предка, так и областей вероятной гибридизации для группы организмов с заданной функцией схожести.
Практическая значимость. Результаты, изложенные в диссертации, могут быть использованы в прикладных постановках ЗК и РЗ для построения областей адаптивной устойчивости, используемых как для целесообразного постоптимального отбора среди оптимальных решений, так и для описания возмущений начальных данных, к которым известное оптимальное решение допускает адаптацию за полиномиальное от размерности задачи число операций. Такого рода «быстрая» адаптация может применяться, например, в программных комплексах, обслуживающих транспортные компании, поскольку в процессе перевозки грузов ситуация часто изменяется.
Предложенный алгоритм кластеризации позволяет понижать размерность
ЗК с сохранением условий предшествования. Алгоритм может служить самостоятельным эвристическим способом решения задачи курьера.При этом будучи остановлен на любой итерации, он может быть доведен до некого целесообразного решения исходной задачи с помощью любого другого точного, приближенного или эвристического способа решения задачи курьера. Такая «смешанная» стратегия решения может быть полезна, например, в задаче оптимизации распределения заданий и перемещения бригады исполнителей в агрессивной внешней среде, где важно найти баланс между точностью решения (опасностью для здоровья работников бригады) и временем расчета (опасностью распространения заражения). Работы в этой области ведутся совместно с кафедрой атомной энергетики УЭИ УрФУ.
Для поиска вероятного предка (либо области вероятной гибридизации) для множества «эволюционирующих объектов» в работе предлагается использовать ММРЗ, а также обобщенную «задачу мультикурьера» (посещаются не точки, а конечные множества, на которых заданы условия предшествования [2]) в постановке с плавающим стартом. Рассматриваемый подход может использоваться в случае, если известна степень схожести исследуемых объектов и целесообразно предположить, что эволюционное развитие объектов шло в рамках известного числа выраженных «русел». Работы в данной области ведутся совместно с лабораторией филогенетики и биохронологии ИЭРиЖ УрО РАН.
Построенный МДП для оптимального решения задачи перестановки объектов может применяться для оптимизации работ в ходе многократного перемещения наблюдательных устройств на пересеченной местности. Разработанные алгоритмы используются в интересах дистанционного мониторинга состояния особо охраняемых природных территорий Свердловской области.
Исследования рассматриваемых в диссертации задач проводились при поддержке грантов РНФ 14-11-00109, РФФИ 10-01-96020-р-урал-а, 10-08-484-а,
11-01-90432-Укр-ф-а, 13-04-847а, 13-01-90414-Укр-ф-а, 13-08-643а, 13-01-96022-р-урал-а, 14-08-00419; региональных целевых программ УрО РАН 13П1, 13П13; программ Президиума УрО РАН для молодых ученых 13-1-НП-1, 13-1-ТГ-779, 14-1-ИП-5.
Апробация работы. Основные результаты диссертации докладывались на следующих конференциях: всероссийской конференции «Дискретная оптимизация и исследование операций», Новосибирск, 2010; международной научно-технической конференции «Суперкомпьютерные технологии: разработка, программирование, применение», Дивноморское, 2010; 14-ой конференции «Математическое программирование и приложения», Екатеринбург, 2011; международной конференции «Анализ моделирование, развитие экономических систем», Севастополь, 2011; международной конференции «Алгоритмический анализ неустойчивых задач», Екатеринбург, 2011; 7-ой международной конференции «Безопасность АЭС и подготовка кадров», Обнинск, 2011; международной суперкомпьютерной конференции «Научный сервис в сети Интернет», 2012; всероссийской конференции «Управление в технических, эргатических, организационных и сетевых системах», Санкт-Петербург, 2012 (2 доклада); 26-th European international conference on operational research, Rome, Italy, 2013; 14th International Conference Computational and Mathematical Methods in Science and Engineering, Rota, Spain, 2014; международной конференции Алгоритмический анализ неустойчивых задач (ААНЗ-2014), Челябинск, 2014.
Кроме того, результаты диссертации докладывались на: расширенном семинаре лаборатории дискретных экстремальных задач ИМ СО РАН; семинаре сектора математических методов распознавания и прогнозирования отдела математических проблем распознавания и методов комбинаторного анализа ВЦ РАН; расширенном семинаре отдела математического программирования ИММ УрО РАН; заседании ученого совета ИММ УрО РАН; семинаре лабора-
тории дискретной оптимизации Омского филиала ИМ СО РАН; расширенном семинаре кафедры дифференциальных уравнений математического факультета УдГУ; расширенном семинаре лаборатории оптимального управления ИДСиТУ СО РАН; расширенном семинаре кафедры экономико-математических методов и статистики факультета экономики и управления ЮУрГУ; расширенном семинаре кафедры системного программирования ЮУрГУ; расширенном семинаре лаборатории интеллектуальных систем Научно-исследовательского института многопроцессорных вычислительных систем им А.В. Каляева ЮФУ; неоднократно обсуждались на расширенном семинаре отдела управляемых систем Института математики и механики УрО РАН.
Публикации. Материалы диссертации опубликованы в 28 печатных работах, из них одна монография [1], 13 статей в рецензируемых журналах [2-14], 1 статья в сборнике трудов [17], 13 публикаций в сборниках материалов конференций [15, 16, 18-28].
Личный вклад автора. Все выносимые на защиту результаты получены лично автором за исключением вспомогательных результатов, используемых в доказательствах, которые приводятся в тексте диссертации для полноты изложения и специально отмечены. В работах [2, 4, 8, 18, 19, 21-23] А.Г. Ченцову принадлежат постановки задач, общая схема исследования и некоторые идеи доказательств; A.M. Григорьеву и П.А. Ченцову принадлежит программная реализация и проведение вычислительных экспериментов; СТ. Князеву принадлежит обзор возможных приложений; конкретные доказательства основных положений, разработка алгоритмов и оценка их трудоемкости проведены автором диссертации самостоятельно.
Структура и объем диссертации. Диссертация состоит из введения, обзора литературы, 5 глав, заключения, библиографии и 1 приложения. Общий объем диссертации 365 страниц, включая 52 рисунка и 15 таблиц. Библиография включает 165 наименований на 20 страницах.
Задача распределения заданий как задача линейного целочисленного программирования
Задача коммивояжера [121] (далее TSP) является одной из актуальных вычислительно сложных (NP-трудных) задач в области современной теории алгоритмов. В простейшем варианте формулируется задача поиска оптимального обхода множества вершин при известной матрице попарных стоимостей перемещений между этими вершинами. Обычно при этом каждую вершину необходимо посетить только один раз.
Постановка задачи допускает большое количество вариаций. Например, функция стоимости перемещений, заданная на ребрах входного графа, может быть метрикой. Одним из важных приложений для такой постановки задачи является оптимизация перемещений на плоскости или в пространстве при необходимости посещения ряда фиксированных точек. В этом случае матрица попарных стоимостей перемещений может быть заменена списком координат вершин в некотором метрическом пространстве.
Вместо обхода с возвратом может быть предложена задача обхода всех вершин, начиная с некоторой вершины А и заканчивая некоторой вершиной В. В задачу могут быть введены дополнительные условия, например условие предшествования, когда некоторые из вершин должны быть посещены в определенном порядке [92]. Такая постановка характерна для класса задач, объединенных типовой задачей курьера, когда в ходе перемещений необходимо получить пакет в пункте А и доставить его в пункт В.
Задача поиска оптимального обхода вершин может быть обобщена до задачи поиска оптимального обхода множеств вершин (GTSP [92, 121]). В обобщенной задаче, также как и в исходной, могут возникать различные варианты постановок и дополнительных ограничений. Допуская перемещения вершин во время обхода, мы приходим к задачам оптимальной поимки, смежным с задачами оптимального управления [87]. Развернутый обзор различных постановок задачи коммивояжера и вариантов их решения можно найти в [64-66, 121].
Задачи, близкие по постановке к TSP, обладают широким спектром приложений. Так, к задаче коммивояжера можно свести множество прикладных проблем комбинаторной оптимизации. Кроме собственно оптимизации перемещений людей и грузов методы решения задачи коммивояжера оказываются полезны при исследовании вопросов из области генетики, при оптимальном управлении механическими роботами, производстве печатных плат, прокладке каналов связи. Например, в вычислительной генетике алгоритмы решения задачи коммивояжера используются для построения RH-карт [119, 150], характеризующих нуклеотидные последовательности. Каждая RH-карта представляет собой линейную последовательность заданных участков генетической информации. При этом биологические соображения подсказывают вероятность, с которой участок А может следовать непосредственно за участком В. Требуется по заданному набору участков выяснить наиболее вероятный порядок, в котором участки располагаются друг относительно друга. В этой задаче локальные участки RH-карт выступают в роли городов. Несимметричная в общем случае стоимость «перемещения» из «города» А в «город» В в такой задаче равна вероятности того, что участок А в глобальной RH-карте следует непосредственно за участком В.
Другим примером из области генетики является синтез кратчайшей последовательности нуклеотидов из заданных подпоследовательностей. В терминах строк, записанных над конечным алфавитом, в этой задаче требуется, чтобы каждая из заданных подстрок встречалась в искомой строке, при этом допускается перекрывание подстрок. «Городами» здесь являются исходные подстроки, а несимметричным «расстоянием» между подстроками-городами А и В является величина \А\ — over(A,B), где \А\ - длина строки А, а over(A,B) - максимальная длина подстроки, встречающейся одновременно на конце строки А и в начале строки В.
Примером задачи из области автоматики является оптимизация перемещений космических телескопов таким образом, чтобы при фотографировании заданного множества небесных тел затраты топлива были минимальны. В такой задаче «городами» являются небесные тела, которые требуется сфотографировать, а стоимостью перемещения между «городами» А и В - количество топлива, требуемое для разворота системы телескопов с позиции съемки объекта А на позицию съемки объекта В.
Производство печатных плат доставляет два примера применения методов решения задачи коммивояжера. В первом примере при сборке печатной платы требуется оптимизировать движение манипулятора, монтирующего элементы. «Городами» в этом случае являются элементы схемы, а «расстоянием» между «городами» - время, требуемое для перемещения манипулятора между позициями соответствующих элементов на плате. Второй пример связан с оптимальным расположением тестовых цепей на плате. Тестовая цепь должна проходить через все важные элементы платы. При этом из соображений экономии длина ее должна быть минимальной. В схожей задаче оптимального соединения всех элементов платы более целесообразно использовать минимальные остовные деревья [164] и паросочетания.
Существуют разнообразные подходы к решению задачи коммивояжера. Методы, обеспечивающие нахождение точного решения задачи коммивояжера, вычислительно затратны и часто оказываются непригодны в задачах, где количество входных вершин исчисляется тысячами, особенно если эти задачи осложнены разнообразными естественными для практики условиями, например, условием предшествования или ограничением сверху на длину единичного перехода между городами [92, 151].
Действительно, даже для неосложненной TSP наиболее быстрым точным алгоритмом (из тех, что гарантированно не «скатываются» к полному перебору), позволяющим находить оптимальное решение за 0(п22п) операций (где п - количество посещаемых «городов»), остается метод динамического программирования. В прикладных же задачах нередко сложность системы ограничений оставляет единственный известный вариант точного решения - полный перебор, требующий 0(п\) операций.
Алгоритмические приложения
В настоящей работе функция стоимости полагается неизменной, а возмущению (в виде добавления, удаления или замены одного из элементов) подвергается само множе ство начальных данных. Такого рода устойчивость (новая, насколько известно автору, в случае труднорешаемых ЗКО), адаптивной поскольку связана с «небольшой» пе рестройкой, адаптацией найденного решения к изменившимся начальным данным. Работа обобщает результаты [34, 35, 38-40, 42, 47, 51] и является строгой формализацией схемы исследования адаптивной устойчивости ЗКО, изложенной в первой главе [48]. Отметим, наконец, что описываемая ниже общая теория также применима к исследованию адаптивной устойчивости задачи оптимального размещения графа на своих вершинах [125].
Также большую роль будет играть дальнейшее развитие теории адаптивной устойчивости в задачах непрерывной оптимизации, в частности, в задачах последовательного управления. В связи с подобным развитием отметим прикладную постановку, связанную с перераспределением заданий в группе аппаратов, осуществляющих авиапожарное пат рулирование после снятия с патрулирования одного из аппаратов. Как правило, такие аппараты можно моделировать системами типа (1.23).
Пусть X — непустое конечное множество всевозможных «потенциальных» начальных данных некоторой исследуемой задачи комбинаторной оптимизации Z, а Лч — непустое конечное множество всевозможных «потенциальных» состояний этой задачи, реализующихся на произвольных начальных данных из множества X. Так, например, в задаче коммивояжера (ЗК) на плоскости множество X доступных для посещения городов может совпадать с множеством 1,п х 1,п для некоторого п Є N. Множество состояний-маршрутов Лч при этом состоит из всевозможных маршрутов обхода вершин из всевозможных подмножеств 1,п х 1,п. В задаче распределения заданий (РЗ) множество потенциально доступных для распределения заданий, также как и в задаче о рюкзаке (ЗР) — множество потенциально возможных для упаковки предметов, могут совпадать с множеством X = 1, п, где п Є N.
Зафиксируем исходное множество начальных данных А С X, возмущенное множество начальных данных А С X и соответствующие этим множествам множества состояний МА С Лч и МА С ЛЧ. Для ЗК состояниями из Мд являются маршруты обхода всех элементов из А, для РЗ — распределения элементов из А на заданное число групп, а для ЗР — упаковки элементов множества А.
Замечание 1.7.1. Отметим, что ранее работах [34, 35, 38-40, 4% 4 7, 48, 51] рассматривались пары (А, А ), где А є [А Є V (X) I 3Z Є X \ А, Зх є А: А є {A U {z}, A \ {x}, (A \ {x}) U {z}}} , a V (X) — множество непустых подмножеств X. Так, в ЗК добавлению, удалению или замене подвергался один из посещаемых городов, в РЗ — одно из распределяемых заданий, а в ЗР — один из упаковываемых предметов.
Для ЗК стоимостью маршрута является сумма весов его ребер, для РЗ стоимость распределения есть трудоемкость максимального среди исполнителей списка заданий, для ЗР стоимость состояния — это стоимость упаковки. Пусть далее для В є {A, A } NB есть множество оптимальных состояний, реализующихся на множестве начальных данных В: аЄМв Говоря о ЗКО Z с множеством потенциальных начальных данных X, функцией стоимости D и фактическими начальными данными А С X будем писать Z(A,D,X). Обыкновенно решением Z(A, D, X) считается нахождение хотя бы одного оптимального состояния «о Є NA И определение D(ao).
Обычно при возмущении множества начальных данных состояния задачи «не сохраняются»: МАГ\МА = 0, а значит «не сохраняются» и оптимальные состояния: NAC\NA = 0. Так, например, в ЗК при добавлении к множеству начальных данных нового города маршруты обхода исходного множества городов и расширенного множества городов будут содержать различное число ребер.
Фиксированное множество возмущенных начальных данных А далее будем называть просто возмущением. Для задачи Z(A,D,X) и возмущения А С X зафиксируем мультифункцию ставящую в соответствие всякому исходному состоянию некоторое множество возмущенных состояний. В ЗК, например, при возмущении в форме добавления вершины к множеству начальных данных результатом действия такой функции может быть множество маршрутов, получающихся из исходного размещением новой вершины «в одно из ребер» данного исходного маршрута.
Приведем несколько примеров. В ЗК оптимальный маршрут является адаптивно устойчивым к добавлению нового города, если при размещении добавленного города между некоторыми двумя последовательными городами данного оптимального маршрута получившийся маршрут также является оптимальным; в РЗ оптимальное распределение устойчиво к удалению одного из заданий, если после изъятия задания из списка работ соответствующего работника распределение остается оптимальным; в ЗР оптимальная упаковка устойчива к замене одного из доступных к упаковке предметов на новый, если после такой замены упаковка остается оптимальной (как в случае, если замену пришлось совершить внутри самой упаковки, так и в случае, когда упаковка осталась прежней).
Далее для ЗКО, обладающих определенной структурой, строится единая схема исследования адаптивной устойчивости. Рассмотрим требования к структуре задачи Z(A, D, X). Пусть Q — непустое конечное множество, элементы которого далее будем называть структурными частями; пусть есть множество всех кортежей всевозможной длины, которые можно составить из элементов множества Q (такие кортежи мы далее будем называть представлениями), тогда пусть функция каждому представлению ставит в соответствие некоторое состояние.
Для ЗК примером структурных частей могут служить дуги маршрута (каждая структурная часть есть элемент множества X2), тогда для маршрута а = (х\,... ,хп) представлением будет кортеж ((жі,ж2), (х2,х3),..., (хп-і,хп)). В РЗ структурными частями могут служить подмножества множества начальных данных, тогда представлением распределения {А\,... ,Ап} будет любой из кортежей (Av ,..., Av ), где tp: 1,п н 1,п. Для ЗР намеренно приведем несодержательный с прикладной точки зрения пример структурных частей. А именно, структурными частями могут служить подмножества упаковываемых предметов, допустимые по совокупному объему; в этом случае состояния ЗР обладают представлениями в виде одноэлементных кортежей, состоящих из единственной структурной части.
Итак, всякое представление v Є 6 1(а) С G обладает следующей структурой: v = (s\,... ,sn) Є Qn, где п Є N. Отметим, что одному состоянию могут соответствовать несколько представлений, но по представлению состояние идентифицируется однозначно.
Критерий адаптивной устойчивости
Проверка условия 11.20 требует расчета минимума по всем (х,у) Є (S \ {z}) . Очевидно \(S \ {z}) \ 15 1 IS 2) l l, а значит, при заданном оптималвном распределении «о = (a70(i),..., а70(га)) Є Ml(S), для всякого г Є 2,п— 1 целесообразно непосредственно рассчитатв стоимоств оптималвного маршрута на Mfs(S\ {СІ10(І)}) и сравнитв с ввіражени-ем D(Del(i,ao)). Учитвівая сказанное, приведенное условие представляет лишв теоретический интерес и отделвнвій алгоритм в разделе П.3.2 для случая устойчивого удаления вершинві не приводится.
Сформулируем, наконец, критерий адаптивной устойчивости оптималвного маршрута при перемещении одной из внутренних вершин. Следующая ниже теорема в общем повторяет рассуждения теоремві П.3.2, однако в отличие от последней, допускает целесообразное применение на практике в случае «болвшого» множества X.
Теорема II.3.3. Пусть заданы множество X, функция стоимости d: X2 — Е, исходное множество вершин S С X: 5 \S\ = п со, начальная и конечная вершины (s,t) Є S 2, произвольные элементы с Є S \{s,t} и z Є X \ S, тогда
Мы показали, что длина произвольного маршрута обхода (S \ {с}) U {z} не менее правой части (11.21). Покажем теперь, что найдется маршрут / є M ((Sf \ {с}) U {г}), длина которого в точности совпадает с правой частью (11.21). Пусть минимум в правой части (11.21) достигается на некоторой паре (х,у) Є (S \{c}) . Рассмотрим любой из маршрутов «о Є Ml(S,x,c,у0), на котором реализуется минимум в (11.16) при (х,у) = (х,у)
Следствие II.3.3. Пусть заданы множество X, функция, определяющая стоимость перемещений d: X2 — Е, исходное множество вершин S С X: 5 \S\ = п со, начальная и конечная вершины (s,t) Є S 2, оптимальный маршрут «о = (я7о(і) а7о(») е Ml(S), тогда для произвольных і Є 2,п — 1 и z Є X\S маршрут Mov(z,i,a0) Є M ((S,\{a7o(i)})U {z}) оптимален тогда и только тогда, когда D(Mov(z,i,a0)) = f min (6 %) + AM(z,alo{thx,y)) . (11.24) Для использования соотношения (11.24) в целях сокращения числа вычислений при проверке возможности устойчивой замены вершин с Є S\ {s,t} оптимального маршрута на элементы множества X \ S мы должны для всякого с Є S \{s,t} заранее просчитать величины Т)? 5 (S) для произвольных (х,у) Є (S \ {с}) . Построение соответствующего алгоритма для получения областей критериальной устойчивости при замещении вершины оптимального маршрута может быть проведено по аналогии со случаем добавления вершины. Формальная запись такого алгоритма не приводится.
Сформулируем теперь алгоритм, с помощью которого в следующем разделе будет построено несколько примеров оптимальных маршрутов на евклидовой плоскости с соответствующими их ребрам областями критериальной устойчивости при добавлении вершины.
Алгоритм II.3.1. (Построение области вершин, отвечающих критерию устойчивой вставки в оптимальный маршрут)
Пусть задано конечное множество X: \Х\ оо, функция стоимости d: X2 — Е, исходное множество вершин S С X: \S\ = п, начальная и конечная вершины (s,t) Є
Для всякого (х,у) Є 5 рассчитаем D J(S). Такой расчет можно провести, используя любой метод решения задачи поиска оптимального маршрута обхода множества S, выбирая при этом стоимость перехода d(x,y) достаточно маленьким отрицательным числом так, чтобы все маршруты, содержащие ребро (х,у), гарантированно имели меньшую длину, чем маршруты, это ребро не содержащие. Например, переопределим функцию d:
От полученного выражения для D 1 (5) потребуется лишь отнять величину d(x,y) и добавить исходное значение d(x, у). Следует заметить, что предложенный метод нахождения D ( (S) не единственен и неоптимален, так как мы не используем сужение области допустимых маршрутов при фиксации ребра (х,у).
Предложение II.3.1. Трудоемкость алгоритма II.3.1 ограничена сверху 0(пА2п+п2\Х\). Доказательство. На шаге 2 алгоритма П.3.1 нам потребуется вычислить Tjf HS) для всякого (х,у) Є S . Как мы показали выше, вычисление T) V(S) можно свести к решению задачи коммивояжера размерности \S\ = п. трудоемкость этой задачи не превышает 0(п22п) [123]. Мощность множества S не превосходит п2, следовательно, суммарную трудоемкость шага 2 алгоритма П.3.1 можно оценить сверху выражением 0(п42п).
На шаге За алгоритма для всякого z Є X \ S производится расчет минимума (11.25), что потребует 0(п2) операций. На шаге 36 производится перебор п—1 ребра оптимального маршрута, что потребует (учитывая известное D J(S)) 0(п) операций. Следовательно трудоемкость шага 3 можно оценить как (0(п2) + 0(п))0(\Х\) = 0(?г2Х). Суммируя тру доемкость шагов 2 и 3, имеем оценку: 0(п42п + г2Х). Следует отметить, что трудоемкость во всех оценках настоящей работы приводится с точностью до логарифмического множителя, обычного при использовании алгоритмов поиска, которые будут неизбежно возникать в явном или неявном виде при учете значений DJ S) в расчете (11.25).
Решая задачу построения области критериальной устойчивости «перебором по X» -с помощью вычисления для каждого z Є X\S оптимального маршрута за 0((п + 1)22га+1), операций, мы бы получили трудоемкость проверки адаптивной устойчивости на всем X порядка 0((п + 1)22га+1Х). Данное выражение существенно превосходит полученное в предложении П.3.1 0(п42п + гг2Х) при естественном условии Х п2 (например в экспериментах следующего раздела Х = 160000, п2 2500).
На рисунках 2.6-2.10 каждому ребру поставлена в соответствие область плоскости определенного цвета (выколотыми кружками обозначены фиксированные начало и конец маршрута). Добавление новой вершины внутрь области на позицию с целыми координатами позволяет включить добавленную вершину между началом и концом соответствующего (содержащегося в) данной области ребра существующего оптимального маршрута с сохранением оптимальности. Разные цвета областей выбираются с одной лишь целью -обеспечить разделение соседних областей.
При построении рисунка 2.6 задачи коммивояжера высокой размерности решались при помощи программы Concorde TSP Solver [164], использующей инструментарий целочисленного линейного программирования. Именно это обусловило необходимость выбора натуральных значений функции d.
Добавление вершины в область, отмеченную белым цветом приводит к «разрушению» существующего оптимального порядка. Отметим, что с формой областей критериальной устойчивости не всегда легко интуитивно согласиться. Для наглядности на рисунке 2.10 приведена последовательность экспериментов, в которых количество вершин возрастает от 6 до 10, при этом всякий раз новая вершина добавляется в дополнение до области критериальной устойчивости, построенной для существующего маршрута. Крестиком обозначается точка на плоскости, в которую на следующем шаге добавляется новая вершина. Рисунок показывает разрушение существующих оптимальных маршрутов при «адаптивно неустойчивом добавлении» новых вершин.
Алгоритм решения ЗК без дополнительных условий
Критерии сохранения оптимального маршрута в задаче коммивояжера, полученные в настоящей диссертации, имеют общие черты с методом исследования допустимых изменений (радиусов устойчивости, tolerances) при изменении веса ребра, описываемым в ряде упоминавшихся в обзоре литературы работ, например в разделе 2.4 диссертации [147]. (Допустимым считается такое изменение веса ребра, при котором существующий оптимальный маршрут остается оптимальным). Несмотря на идейное сходство, следует отметить существенное различие указанных постановок, так, например, задача исследования условий устойчивой вставки новой вершины в заданное ребро оптимального маршрута в задаче коммивояжера не сводится напрямую к задаче определения допустимого изменения веса данного ребра.
Рассмотрим два примера добавления новой вершины к известному оптимальному маршруту в задаче коммивояжера (случай добавления вершины представляет наибольший интерес как в теоретическом, так и в прикладном отношениях). Обозначая ребро с инцидентными вершинами а и 6, будем писать [а, Ь], вес этого ребра будем обозначать \а,Ь\.
Вес ребра [а, Ь] всюду будем считать евклидовым расстоянием между точками а Ь, если не сказано иное. Будем моделировать вставку новой вершины с в ребро [а, Ь] изменением веса этого ребра: \а,Ь\ — \а,с\ + \с,Ь\. Выскажем следующее предположение: вершину с можно вставить в ребро [а, Ь], получая вновь оптимальный маршрут, содержащий ребра [а, с] и [с, Ь] вместо ребра [а, Ь], если величина \а,с\ + \с,Ь\ находится в пределах допустимых отклонений для веса ребра [а, Ь]. В приведенных ниже примерах демонстрируется, что такое предположение неверно.
Рассмотрим оптимальный маршрут (рисунок 2.24а) с фиксированными началом а и концом d. Здесь \а,с\ = \c,b\ = \b,d\ = \c,d\. При увеличении веса ребра [а,с] вплоть до длины ребра [а, Ь] оптимальный маршрут (a,c,b,d) сохраняется. Добавим новую вершину е (рисунок 2.24Ь) на ребро [с, Ь] таким образом, чтобы \а,е\ + е,с \а,Ь\. Рассмотрим маршрут (a,e,c,b,d). Трактуя вставку вершины е в ребро [а,с] как замену исходного «евклидова» веса ребра [а, с] на сумму \а, е + е, с\, имеем соблюдение допустимых для сохранения оптимального маршрута изменений веса ребра [а, с] и, как следствие, ожидаемую оптимальность маршрута (а, е, с, b, d), однако очевидно, что маршрут (а, с, е, b, d) обладает меньшей длиной.
Пример недостаточности непосредственного использования допустимых изменений веса ребра известного оптимального маршрута для проверки возможности устойчивой вставки новой вершины в данное ребро (исходный порядок не нарушен)
Данный пример легко адаптировать для неметрического случая. Пусть на рисунке 2.24 \а,с\ = \c,b\ = \b,d\ = 1, а все остальные веса ребер равны 100. Очевидно, вес ребра [а, с] может быть увеличен до 100 без потери оптимальности найденного маршрута. Добавим точку е такую, что \а,е\ = 20 = е,с, \с,е\ = 0 = \е,Ь\ а веса всех остальных ребер, одной из вершин которых может быть е, равен 10000.
Рассмотренный пример демонстрирует в определенной степени различие в подходах к устойчивости, однако общий порядок обхода вершин исходного маршрута остается неизменным, отличается лишь ребро, в которое необходимо вставить новую вершину для обеспечения оптимальности. Приведем более сложный пример, в котором «разрешенная вставка вершины в ребро» (в смысле допустимых отклонений веса этого ребра) приводит к формированию неоптимального маршрута, существенно (на уровне порядка обхода исходных вершин) отличающегося от оптимального маршрута (пример подготовлен с помощью программы Concorde TSP Solver, координаты точек на рисунке 2.25 существенны).
Рассмотрим оптимальный маршрут на рисунке 2.25а. Необходимые для рассмотрения примера вершины обозначены {а,... ,д}, остальные вершины вводятся для создания общей структуры маршрута и не обозначаются отдельно. Все вершины находятся на евклидовой плоскости, длины ребер изначально совпадают с евклидовыми расстояниями между инцидентными ребрам вершинами. Отметим несколько важных моментов, связанных со структурой примера на рисунке 2.25: вершина Ъ находится несколько ближе к вершине а, чем вершина с; отрезки [d, /] и [/, е] перпендикулярны; вершина д равноудалена от вершин ей/; «новая» вершина h, вводится на рисунке 2.25Ь так, чтобы отрезки [h, d] и [d, f] были перпендикулярны, причем \h,d\ + \d, / \d,e\.
Заметим, что при увеличении веса ребра [d, /] вплоть до длины отрезка [d, е] оптимальный маршрут на рисунке 2.25а не изменится. Одним из таких изменений веса [d, /] может служить вставка в ребро [d, /] новой вершины h (с заменой самого ребра [d, /] на пару ребер [d,h] и [h, f] и соответствующим «изменением веса»: \d, / — \d,h\ + \h,f\). По построению «изменение веса» ребра [d, /] в силу вставки «новой» вершины h находится в пределах допустимого для сохранения исходного маршрута (рисунок 2.25а) отклонения, а следовательно маршрут, включающий вершину h в ребро [d, /] должен быть оптимальным, однако это не так: в оптимальном маршруте (рисунок 2.25Ь) не только вершина h добавлена в ребро [b, d] вместо ребра [d, /], но и порядок посещения вершин бис изменился.
Приведем также пример, демонстрирующий, что и задача, связанная с устойчивостью оптимального маршрута при изменении веса ребра, не может быть сведена к задаче, связанной с адаптивной устойчивостью оптимального маршрута при добавлении в это ребро новой вершины.