Помощь студентам в учебе
Маршрутно-распределительные задачи: теория и приложения
|
Введение 6
Обзор литературы 13
Глава 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
II. 2.3. Эксперименты 85
11.3. Критерий адаптивной устойчивости 92
11.3.1. Вопросы теории 92
11.3.2. Алгоритмические приложения 100
II. 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
11.6.1. Топология областей адаптивной устойчивости 135
11.6.2. Асимптотика относительной площади области устойчивости в евклидовой ЗК 136
11.6.3. Примеры, демонстрирующие новизну постановки 137
П.6.4. Модельный пример прикладной задачи с применением областей адаптивной устойчивости 141
Глава III. Адаптивная устойчивость оптимального распределения при изменении множества распределяемых заданий 144
III. 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. !. Адаптивная устойчивость в управлении перемещением транспортных срсдств236
У.1.1. Грузоперевозки 236
У.1.2. Авиапожарпое патрулирование 238
У.2. Приложения минимаксной маршрутно-распределительной задачи 240
У.2.1. Математическая постановка задачи 240
У.2.2. Оптимизация перемещений в агрессивной среде 241
У.2.3. Эволюционная изменчивость 246
У.2.3.1. Содержательная постановка 247
У.2.3.2. Эвристический алгоритм 248
У.2.3.3. Модельный эксперимент 248
У.З. Оптимизация перемещений исследователя-этолога 254
У.3.1. Перестановка камер па местности 254
У.З.1.1. Формальная постановка задачи 255
У.З.1.2. Метод динамического программирования 256
У.З.1.3. Доказательство оптимальности 257
У.З.1.4. Эксперимент 259
У.З.2. Другие постановки 260
Заключение 263
Литература 268
Приложение
Обзор литературы 13
Глава 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
II. 2.3. Эксперименты 85
11.3. Критерий адаптивной устойчивости 92
11.3.1. Вопросы теории 92
11.3.2. Алгоритмические приложения 100
II. 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
11.6.1. Топология областей адаптивной устойчивости 135
11.6.2. Асимптотика относительной площади области устойчивости в евклидовой ЗК 136
11.6.3. Примеры, демонстрирующие новизну постановки 137
П.6.4. Модельный пример прикладной задачи с применением областей адаптивной устойчивости 141
Глава III. Адаптивная устойчивость оптимального распределения при изменении множества распределяемых заданий 144
III. 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. !. Адаптивная устойчивость в управлении перемещением транспортных срсдств236
У.1.1. Грузоперевозки 236
У.1.2. Авиапожарпое патрулирование 238
У.2. Приложения минимаксной маршрутно-распределительной задачи 240
У.2.1. Математическая постановка задачи 240
У.2.2. Оптимизация перемещений в агрессивной среде 241
У.2.3. Эволюционная изменчивость 246
У.2.3.1. Содержательная постановка 247
У.2.3.2. Эвристический алгоритм 248
У.2.3.3. Модельный эксперимент 248
У.З. Оптимизация перемещений исследователя-этолога 254
У.3.1. Перестановка камер па местности 254
У.З.1.1. Формальная постановка задачи 255
У.З.1.2. Метод динамического программирования 256
У.З.1.3. Доказательство оптимальности 257
У.З.1.4. Эксперимент 259
У.З.2. Другие постановки 260
Заключение 263
Литература 268
Приложение
Актуальность работы. Задачи комбинаторной оптимизации (ЗКО) встречаются
практически во всех областях человеческого знания, где требуется из большого числа
вариантов выбрать наилучший или как минимум целесообразный. В качестве примеров
таких задач можно привести планирование производства; оптимизацию коммуникационной инфраструктуры; оптимизацию загрузки параллельно работающих исполнителей (это
могут быть, например, станки, рабочие или конвейеры современного вычислителя); задачи
оптимальной загрузки транспортных контейнеров; оптимизацию раскроя в швейном и металлообрабатывающем производствах, задачи оптимизации расписаний.
практически во всех областях человеческого знания, где требуется из большого числа
вариантов выбрать наилучший или как минимум целесообразный. В качестве примеров
таких задач можно привести планирование производства; оптимизацию коммуникационной инфраструктуры; оптимизацию загрузки параллельно работающих исполнителей (это
могут быть, например, станки, рабочие или конвейеры современного вычислителя); задачи
оптимальной загрузки транспортных контейнеров; оптимизацию раскроя в швейном и металлообрабатывающем производствах, задачи оптимизации расписаний.
В диссертационной работе рассмотрены различные аспекты применения принципа
Беллмана и метода динамического программирования в двух известных задачах комбинаторной оптимизации: задаче коммивояжера и распределительной задаче.
В первой главе работы проводится краткий обзор классического применения принципа Беллмана в дискретных задачах, формулируются две известные задачи комбинаторной оптимизации (ЗКО) (задача коммивояжера и распределительная задача), излагается
метод динамического программирования для классических формулировок обеих задач,
рассматриваются непрерывные постановки маршрутно-распределительных задач – задачи последовательного управления. Завершается глава рассмотрением общего подхода к
адаптивной устойчивости в ЗКО. Перспективным направлением видится развитие теории адаптивной устойчивости для задач последовательного управления, имеющих как
дискретную компоненту – маршрут, так и непрерывную бесконечномерную компоненту –
управляющую программу.
Вторая глава и третья главы диссертации посвящены изложению теории устойчивости в задаче коммивояжера и задаче распределения заданий. Ранее устойчивость в задаче
коммивояжера подробно изучалась для случая изменения матрицы весов ребер и в случае master tour property. Излагаемая во второй и третьей главах теория устойчивости при
изменении множества входных данных является дополнением к существующей теории
устойчивости в задачах комбинаторной оптимизации, связанной с изменением функции
стоимости на множестве неизменных входных данных. В монографии автора [48] рассмотрен общий подход к конструированию на основе принципа Беллмана теории устойчивости
оптимальных решений при изменении множества начальных данных в абстрактной задаче комбинаторной оптимизации, удовлетворяющей ряду структурных ограничений. Однако общность излагаемых результатов не позволяет добиться достаточной математической
строгости изложения, поэтому в диссертационную работу вошли только два подробно формализованных примера построения такой теории устойчивости: для задачи коммивояжера
и распределительной задачи.
Беллмана и метода динамического программирования в двух известных задачах комбинаторной оптимизации: задаче коммивояжера и распределительной задаче.
В первой главе работы проводится краткий обзор классического применения принципа Беллмана в дискретных задачах, формулируются две известные задачи комбинаторной оптимизации (ЗКО) (задача коммивояжера и распределительная задача), излагается
метод динамического программирования для классических формулировок обеих задач,
рассматриваются непрерывные постановки маршрутно-распределительных задач – задачи последовательного управления. Завершается глава рассмотрением общего подхода к
адаптивной устойчивости в ЗКО. Перспективным направлением видится развитие теории адаптивной устойчивости для задач последовательного управления, имеющих как
дискретную компоненту – маршрут, так и непрерывную бесконечномерную компоненту –
управляющую программу.
Вторая глава и третья главы диссертации посвящены изложению теории устойчивости в задаче коммивояжера и задаче распределения заданий. Ранее устойчивость в задаче
коммивояжера подробно изучалась для случая изменения матрицы весов ребер и в случае master tour property. Излагаемая во второй и третьей главах теория устойчивости при
изменении множества входных данных является дополнением к существующей теории
устойчивости в задачах комбинаторной оптимизации, связанной с изменением функции
стоимости на множестве неизменных входных данных. В монографии автора [48] рассмотрен общий подход к конструированию на основе принципа Беллмана теории устойчивости
оптимальных решений при изменении множества начальных данных в абстрактной задаче комбинаторной оптимизации, удовлетворяющей ряду структурных ограничений. Однако общность излагаемых результатов не позволяет добиться достаточной математической
строгости изложения, поэтому в диссертационную работу вошли только два подробно формализованных примера построения такой теории устойчивости: для задачи коммивояжера
и распределительной задачи.