Задачи маршрутизации перемещений: Учебное пособие для вузов

Description

Учебное пособие посвящено исследованию задач маршрутизации с ограничениями, имеющих своим источником известную задачу коммивояжера. Рассматриваемые постановки имеют смысл задачи о посещении мегаполисов при соблюдении некоторых условий предшествования. Обосновано уравнение Беллмана, рассмотрен численный алгоритм построения функции Беллмана и алгоритм нахождения оптимального маршрута и трассы посещения мегаполисов. Получено также обобщение задачи о посещении мегаполисов в случае когда функция затрат явным образом зависит от списка невыполненных заданий. В качестве примера анализируется модельный пример задачи минимизации дозовой нагрузки при выполнении ремонтных и профилактических работ на атомных электростанциях. Учебное пособие предназначено для студентов специальности Прикладная математика, а также для студентов, аспирантов и специалистов, интересующихся методами оптимизации и исследования операций. Введение Глава 1. Предварительные построения 1.1. Общие обозначения и определения 1.2. Содержательное обсуждение используемых методов решения задач маршрутизации Глава 2. Метод динамического программирования в задаче коммивояжера 2.1. Замкнутая и незамкнутая задачи коммивояжера 2.2. Простейшие эвристические алгоритмы (примеры) 2.3 Метод динамического программирования 2.4. Решение задачи коммивояжера методом динамического программирования 2.5. Метод динамического программирования: добавление (“замкнутая задача коммивояжера) 2.6. Применение метода динамического программирования для решения задачи оптимизации дозовых затрат ремонтного персонала атомных электрических станций 2.7. Одно обобщение задачи коммивояжера: маршрутная задача последовательного обхода множеств 2.8. Метод динамического программирования в задаче последовательного обхода множеств Глава 3. Метод итераций для решения задачи последовательного обхода множеств 3.1. Постановка задачи 3.2. Эквивалентная задача реконструкции 3.3. Эквивалентное преобразование экстремальных задач и метод покоординатного спуска 3.4. Метод итераций с использованием перестраиваемой модели задачи Коммивояжера 3.5. Простейшие примеры 3.6. Более сложные варианты решения задачи о последовательном посещении множеств 3.7. Стабилизация итерационной процедуры Глава 4. Экстремальные задачи маршрутизации с ограничениями в виде условий предшествования 4.1. Содержательная постановка задачи 4.2. Математическая постановка задачи; уточнение ограничений 4.3. Задача о посещении трех множеств: иллюстративные примеры 4.4. Алгоритм на функциональном уровне 4.5. Простейший пример решения маршрутной задачи с ограничениями по методу динамического программирования 4.6. Вычислительный эксперимент Глава 5 Усложненный вариант обобщенной задачи курьера (случай, когда стоимость перемещений зависит от списка заданий) 5.1. Содержательная постановка и обсуждение задачи 5.2. Метод динамического программирования 5.3. Построение оптимального решения 5.4. Вычислительный эксперимент Заключение Литература