Обложка Ченцов А.Г., Ченцов А.А., Сесекин А.Н. Задачи маршрутизации перемещений с неаддитивным агрегированием затрат
Id: 265317
499 руб.

Задачи маршрутизации перемещений с неаддитивным агрегированием затрат. Изд. 2, стереотип.

URSS. 2021. 232 с. ISBN 978-5-9710-8057-2.
  • Мягкая обложка

Аннотация

В монографии рассматриваются задачи маршрутизации перемещений с выполнением работ в пунктах посещения. Особенностью настоящего исследования является систематическое изучение неаддитивных вариантов агрегирования затрат; одним из примеров такого рода является известная задача «на узкие места». В настоящей монографии исследуются постановки, существенно более сложные в сравнении с естественным прототипом — известной задачей коммивояжера....(Подробнее) В частности, рассматриваются задачи, в которых имеют место многовариантность перемещений между пунктами посещения, усложненные функции стоимости (допускающие зависимость от списка заданий), ограничения различных типов. Упомянутые осложняющие обстоятельства мотивируются потребностями приложений, в числе которых имеет смысл отметить вопросы снижения облучаемости персонала АЭС при выполнении работ в условиях повышенной радиации, а также проблему управления режущим инструментом при листовой резке на машинах с ЧПУ. В основе исследования лежит подход, связанный с широко понимаемым динамическим программированием, разработка которого в столь общих предположениях является новым моментом в ряду многочисленных исследований, посвященных решению задачи коммивояжера.

Книга предназначена для специалистов в области многоразовых технических систем, робототехники, атомной энергетики и машиностроения. Она будет полезной для научных работников, специализирующихся на исследовании задач управления и дискретной оптимизации, преподавателей, аспирантов, магистров и студентов университетов.


Оглавление

Введение .......................................... 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]), когда доза, получаемая работником, существенно зависит от маршрута его перемещений в радиационных полях. Одна из возможных постановок здесь может быть связана с работами в условиях аварийных ситуаций, подобных Чернобылю и Фукусиме. Речь может идти о последовательной дезактивации местности, зараженной точечными источниками. Эти источники следует посетить с соблюдением всех необходимых требований и тем или иным способом демонтировать, т.е. по сути «выключить». У данной задачи, помимо условий предшествования, имеется еще одна существенная особенность: стоимости перемещений (т.е. дозы радиации) зависят от списка заданий, которые еще не выполнены на момент перемещения. Действительно, «светят» те и только те источники, которые не демонтированы на текущий момент.


Об авторах
Ченцов Александр Георгиевич
Член-корреспондент РАН, доктор физико-математических наук, главный научный сотрудник Института математики и механики им. Н. Н. Красовского УрО РАН. Профессор Уральского федерального университета. Лауреат Государственной премии СССР за цикл работ в области прикладной математики. Область научных интересов: теория управления, теория дифференциальных игр, теория меры, общая топология, дискретная оптимизация (вопросы маршрутизации перемещений и распределения заданий).
Ченцов Алексей Александрович
Кандидат физико-математических наук, научный сотрудник Института математики и механики им. Н. Н. Красовского УрО РАН. Область научных интересов: дискретная оптимизация, исследование технических систем и средств автоматизации, компьютерное моделирование.
Сесекин Александр Николаевич
Доктор физико-математических наук, профессор, заведующий кафедрой прикладной математики и механики Уральского федерального университета. Ведущий научный сотрудник Института математики и механики им. Н. Н. Красовского УрО РАН. Область научных интересов: качественная теория динамических систем с разрывными траекториями, теория импульсного оптимального управления, дискретная оптимизация с техническими приложениями.