Введение
Глава 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
