|
Оглавление
 Введение .......................................... 5 1. Последовательные перемещения и агрегирование стоимостей: содержательное обсуждение, примеры 18 1.1. Последовательные перемещения............... 18 1.2. Обозначения и определения общематематического характера ............................... 24 2. Задачи маршрутии «на узкие места» 31 2.1. Введение............................ 31 2.2. Простейший вариант задачи коммивояжера «на узкие места».............................. 31 2.3. Расширение (незамкнутой) задачи коммивояжера «на узкие места»; уравнение Беллмана.............. 34 2.4. Построение оптимального маршрута: алгоритм на функциональном уровне...................... 46 2.5. Простейший пример построения оптимального маршрута 59 3. Обобщенная задача курьера «на узкие места» 67 3.1. Введение............................ 67 3.2. Постановка задачи ...................... 68 3.3. Расширение основной задачи ................ 75 3.4. Построение слоев функции Беллмана ........... 84 3.5. Построение оптимальных решений............. 92 3.6. Обсуждение вариантов вычислительного эксперимента . 97 4. Маршрутизация с абстрактной функцией агрегирования затрат 99 4.1. Введение............................ 99 4.2. Обсуждение задачи...................... 100 4.3. Постановка задачи ...................... 103 4.4. Динамическое программирование.............. 108 4.5. Усечённая реализация функции Беллмана......... 120 4.6. Оптимальность «беллмановских» решений........ 126 4.7. Построение оптимального допустимого решения..... 139 4.8. Один вариант неаддитивного агрегирования затрат ... 147 5. Обобщенный вариант задачи «на узкие места»: маршрутная задача с параметром 152 5.1. Введение............................ 152 5.2. Постановка задачи и схема решения на основе динамического программирования .153 5.3. Построение слоев функции Беллмана ........... 160 5.4. Построение оптимального решения............. 162 5.5. Вычислительный эксперимент (постановка, обсуждение задачи, описание программы)................. 175 5.6. Результаты вычислительного эксперимента......... 177 5.7. Вычислительный эксперимент (продолжение): задача курьера............................... 213 5.8. Обсуждение результатов.................... 218 Приложение Литература........................................ 224
Введение
В монографии рассматриваются задачи маршрутизации перемещений с возможным выполнением тех или иных работ в пунктах посещения. Эти задачи возникают в самых различных сферах человеческой деятельности; они играют важную роль в производстве, на транспорте, в энергетике (в том числе в атомной энергетике). Так, в частности, в задачах машиностроения, связанных с раскроем, возникает необходимость в управлении движением режущего инструмента при использовании машин с ЧПУ. Данное движение требуется организовать так, чтобы инструмент последовательно посещал некоторые окрестности контуров вырезаемых деталей при соблюдении большого числа разнообразных ограничений. При этом желательно оптимизировать тот или иной критерий, например, суммарное время резки. Одним из вариантов ограничений в этой постановке являются так называемые условия предшествования (условия типа «одно после другого»), которые, в частности, предписывают вырезать у деталей (после раскроя) сначала внутренние контура и лишь после этого — внешний контур. Эта особенность связана с технологией машиностроительного производства (см. [22, 72]). Имеются и другие ограничения технологического характера (условия жесткости листа и деталей, тепловые допуски). Отметим в этой связи исследования [3, 4, 21, 23, 29, 64, 69, 79], посвященные решению упомянутой прикладной задачи. Другая практическая задача, в которой маршрутизация может сыграть важную роль, связана с атомной энергетикой, а, точнее, с проблемой снижения облучаемости персонала АЭС при выполнении комплекса работ в условиях повышенной радиации (см. [13]), когда доза, получаемая работником, существенно зависит от маршрута его перемещений в радиационных полях. Одна из возможных постановок здесь может быть связана с работами в условиях аварийных ситуаций, подобных Чернобылю и Фукусиме. Речь может идти о последовательной дезактивации местности, зараженной точечными источниками. Эти источники следует посетить с соблюдением всех необходимых требований и тем или иным способом демонтировать, т.е. по сути «выключить». У данной задачи, помимо условий предшествования, имеется еще одна существенная особенность: стоимости перемещений (т.е. дозы радиации) зависят от списка заданий, которые еще не выполнены на момент перемещения. Действительно, «светят» те и только те источники, которые не демонтированы на текущий момент.
Об авторах
 Ченцов Александр Георгиевич Член-корреспондент РАН, доктор физико-математических наук, главный научный сотрудник Института математики и механики им. Н. Н. Красовского УрО РАН. Профессор Уральского федерального университета. Лауреат Государственной премии СССР за цикл работ в области прикладной математики. Область научных интересов: теория управления, теория дифференциальных игр, теория меры, общая топология, дискретная оптимизация (вопросы маршрутизации перемещений и распределения заданий).
 Ченцов Алексей Александрович Кандидат физико-математических наук, научный сотрудник Института математики и механики им. Н. Н. Красовского УрО РАН. Область научных интересов: дискретная оптимизация, исследование технических систем и средств автоматизации, компьютерное моделирование.
 Сесекин Александр Николаевич Доктор физико-математических наук, профессор, заведующий кафедрой прикладной математики и механики Уральского федерального университета. Ведущий научный сотрудник Института математики и механики им. Н. Н. Красовского УрО РАН. Область научных интересов: качественная теория динамических систем с разрывными траекториями, теория импульсного оптимального управления, дискретная оптимизация с техническими приложениями.
|