Введение к работе
Актуальность темы. В диссертационной работе исследуются задачи маршрутизации последовательного обхода множеств и сечений многозначных отображений (МО). В заданном непустом множестве требуется построить путь (ломаную), выходящий из обособленного элемента множества; узлами этого пути являются элементы некоторых его подмножеств (по одному представителю от каждого), Задана функция, оценивающая затраты на переход между точками множества. Совокупные затраты на весь такой путь оцениваются либо суммой затрат по всем его звеньям (аддитивный критерий), либо наибольшими, среди всех участков пути, затратами (критерий типа "максимум"). Мы стремимся оптимизировать величину совокупных затрат посредством согласованного выбора перестановки индексов подлежащих обходу множеств, называемой далее маршрутом, и кортежа элементов множеств (по одному из каждого множества, при этом очередность задается маршрутом), именуемого далее трассой. В результате возникает дискретно-непрерывная экстремальная задача. Дискретная составляющая связана с построением маршрута, а непрерывная — с отысканием трассы. Вообще говоря, без потери качества невозможна декомпозиция задачи на две вышеупомянутые подзадачи, являющиеся дискретной и непрерывной ее компонентами.
Потребность в таких постановках возникает в задачах авиапожарного патрулирования лесов, облета архипелага, размещения компонент электронной аппаратуры на печатных платах1,2.
Первые две задачи связаны с оптимизацией посещений некоторым летательным аппаратом определенных географических областей, которыми могут быть лесные массивы, группы островов архипелага и т.д. Требуется минимизировать либо суммарный расход топлива на весь перелет, либо наибольший среди звеньев пути расход горючего (это требование может быть обусловлено необходимостью гарантировать невозможность израсходования всего запаса топлива во время перелета ио самому протяженному звену пути). В задаче размещения компонент электронной аппаратуры на печатной плате задана система токопроводящих фрагментов, на каждом из которых имеется набор точек крепления функциональных элементов электронной аппаратуры, и некоторый обособленный контакт. Требуется провести проводник с началом в данном контакте, соединяющий все фрагменты
'Коротаева Л.Н., Трухни М.П., Ченцов А.Г. К вопросу о маршрутизации соединений // А и Т. — 1997. - №12. - С. 175 - 192.
2Деньдобренко Б.Н., Малика А.С. Автоматизация конструирования РЭА. — М.: Высш. школа, 1980.
і і 'ОС. национальная]
3 ! БИБЛИОТЕКА І
| GПетербург д, (
і оэ гооЗвкт&(?М
печатной платы, минимальной длины (сопротивления) или с наименьшей протяженностью (сопротивлением) наиболее длинного звена (звена с наибольшим сопротивлением). Первое требование может быть продиктовано соображениями оптимизации общего сопротивления всего проводника, а второе — желанием минимизировать наибольшее падение напряжение среди участков проводника при прохождении по нему электрического тока.
В плане построения маршрута данная задача является обобщением известной задачи коммивояжера (ЗК)3 (имеется в виду незамкнутый ее вариант), которая относится к классу задач дискретной оптимизации: при решении ЗК осуществляется маршрутизация точечных объектов ("городов") посредством выбора очередности их посещения, а в нашей задаче помимо поиска маршрута требуется выбрать точки на множествах, образующие трассу. Для решения ЗК имеется много методов, как точных*1, так и приближенных5. Среди них отметим метод ветвей и границ6 и метод динамического программирования (ДП)7,К.
В связи с поиском трассы отметим задачи последовательного управления, в которых требуется оптимизировать перемещение динамической системы по множествам в фазовом пространстве с заданной очередностью их посещений. Отметим в этой связи подход, развиваемый свердловской школой Н.Н. Красовского, Речь идет, в частности, о построении вариантов принципа максимума Л.С. Понтрягина9, основывающихся на идеях двойственности10 линейных задач управления и задач выпуклого программирования. Данное направление связано прежде всего с работами Н.Н. Красовского, А.Б. Куржанского, Ю.С. Осипова и А.И. Субботина. На этой основе были разработаны конструкции решения задач последовательного
3Меламед И.И., Сергеев СИ., Сигал И.Х. Задача коммивояжера. Вопросы теории // А и Т. — 1989. - №9. - С. 3 - 34.
4Меламед И.И., Сергеев СИ., Сигал И.Х. Задача коммивояжера. Точные алгоритмы // А п Т. — 1989. - №10. - С. 3 - 29.
5Меламед И.И., Сергеев СИ., Сигал И.Х. Задача коммивояжера. Приближенные алгоритмы // А и Т. - 1989. - №11.- С. 3 - 26.
"Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач большой размерности. — Киев: Наукова думка, 1981. — 288 с.
7Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник, - M.: Мир, 1964. - Т. 9 - С. 219 - 228.
8Хелд М., Карп P.M. Применение динамического программирования к задачам упорядочения. // Кибернетический сборник, — М,: Мир, 1964. — Т. 9 - С. 202 - 218.
"Понтрягин Л.С, Болтянский В,Г., Гамкрелндзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. — М.: Наука, 1976. — 392 с.
'"Красовский Н.Н, Теория управления движением. — М.: Наука, 1968. — 476 с.
управления линейными системами11, логически связанные с проблемой оптимизации трасс в задаче последовательного обхода множеств (отметим вариант принципа максимума Л.С. Понтрягина для нелинейной задачи последовательного управления12, а также исследования Ю.И. Бердышева13 в области решения задач управления, связанных с посещением упорядоченной системы множеств). Рассматривались игровые варианты задач последовательного управления14. Кроме того, отметим некоторые маршрутные (по смыслу) задачи оптимизации па классе ломаных15 (использовались методы теории приближения функций).
Известен точный метод решения задачи маршрутизации последовательного обхода множеств — модификация метода ДП16. Данный метод позволяет существенно сократить объем вычислений в сравнении с полным перебором и не нуждается в специальном выборе начального приближения. Основной его недостаток связан с жесткими требованиями к доступной, для хранения массива значений функции Беллмана, памяти при реализации на ЭВМ. В работе приводится вариант данного метода, адаптированный для решения задач маршрутизации последовательного обхода сечений МО в произвольном непустом множестве. В частности, рассматривается конструкция, позволяющая сократить перебор и заключающаяся в том, чтобы просматривать не все очередное целевое множество, а лишь его часть, которая задается допуском, оценивающим разницу в затратах на перемещения в точки области по отношению к затратам на переход в "ближайший" элемент данного множества (в результате имеем обход подвижных множеств).
Основное внимание уделяется вопросам приближенной реализации метода ДП. Рассматривается построение массива значений функции Беллмана (первый этап метода ДП) по слоям с погрешностями, величина ко-
"Бердышев Ю.И., Ченцов А.Г. Оптимизация взвешенного критерия в одной задаче управления // Кибернетика. 1986. №2. С. 59 - 87.
12Бердышев ГО.И., Чепцов А.Г. О некоторых задачах последовательной оптимизации управляемых систем // Рукопись в деп. в ВИНИТИ. - 1983. - №109-83 Деп, - 99 с.
13Бердышев Ю.И. О задаче последовательного обхода нелинейным управляемым объектом совокупности гладких многообразий // Дифференциальные уравнении. 2002. Т. 38. №11. С. 1451 - 14G1.
І4Красовскнй Н.Н., Лукоянов Н.Ю. Задача конфликтного управления с наследственной информацией // ПММ, 1996. Т. 60, Вып. 6. С. 885 - 900.
15Бердышев В.И., Кондратьев В.П. О наилучшей траектории, соединяющей упорядоченный набор
множеств. Свердловск: ИММ УНЦ АН СССР, 1986.
1вКоротаева Л.Н., Сесекни А.Н., Ченцов А.Г. Об одной модификации метода динамического программирования в задаче последовательного сближения // Журнал вычислительной математики и математической физики. - 1989. - Т. 29, №8. - С. 1107 - 1113.
торых оценивается сверху (для каждого слоя). Получены оценки сверху для рассогласований значений истинной и "приближенной" функций Бел-лмана. Рассматривается формирование пары "маршрут-трасса" (второй этап метода ДП) в условиях, когда допускается отступление от принципа оптимальности (в пределах заданных доспусков) при выборе очередного элемента маршрута и узла трассы. В итоге получена оценка сверху для погрешности, возникающей при вычислении функции Беллмана и отступлении от оптимальности при формировании пары "маршрут-трасса"17.
Исследуется отклонение результата при подмене одной системы маршрутизируемых компактных множеств другими (получена оценка в терминах хаусдорфовых расстояний между множествами разных систем)18. Рассматривается замена компактов их конечными подмножествами (є-сетями) а, в случае аддитивной функции агрегирования затрат, — границами компактов1 Погрешности при вычислении экстремумов в уравнении Беллмана могут быть при этом обусловлены применением численных методов оптимизации, различных аппроксимаций функции Беллмана, а также дискретизации областей поиска узла трассы в условиях недостижимости инфимума затрат на произвольном множестве. Проведенные исследования позволяют оценить отклонение по результату при решении (на ЭВМ) задачи маршу-рутизации последовательного обхода множеств методом ДП.
Благодаря высоким требованиям к доступной памяти ЭВМ, метод ДП утрачивает возможность практического применения уже для систем, содержащих несколько десятков множеств. Разработан приближенный алгоритм решения задачи маршрутизации последовательного обхода множеств с использованием ЗК, основная идея которого — разделение в режиме итераций процесса формирования маршрута и процесса построения трассы вдоль этого маршрута. Данный алгоритм позволяет оценить сверху погрешность результата по отношению к неизвестному глобальному экстремуму. Такая возможность важна при решении практических задач, так как обычно существуют допуски на предельную величину погрешности. Для построения и обоснования метода предложен новый взгляд на исходную экстремальную задачу со связанными переменными (очередность следования точек
17Ченцов А.А., Ченцов А.Г. О решении задачи маршрутной оптимизации методом динамического программирования // Изв. Академии наук. Теория и системы управления. 1999. №3. С. 76 - 87.
18Chentsov A.A., Chentsov A.G. Dynamic Programming Method in the Generalised Traveling Salesman
Problem: The Influence of Inexact Calculations // Mathl. Comput. Modelling. — 2001. - Vol. 33, - pp. 801 -
,819.
18Ченцов А.А., Чепцов А.Г. Редукция задач маршрутной оптимизации// А и Т. 2000. №10. С. 136 -
150.
трассы задается маршрутом), как на задачу с независимыми переменными, которыми в данном случае являются система "городов" и маршрут, Доказана эквивалентность этих экстремальных задач20. Цель работы состоит в следующем:
Поиск возможностей сокращения объема перебора при решении маршрутной задачи последовательного обхода методом ДП;
Исследование влияния на результат погрешностей вычисления функции Беллмаиа и экстремумов при построении пары "маршрут-трасса" в процессе решения исходной задачи методом ДП;
Исследование зависимости экстремума при изменении целевых множеств;
Разработка приближенных алгоритмов решения исходной задачи, допускающих оценку погрешности по отношению к глобальному экстремуму;
Реализация методов решения исходной задачи в виде программ для ПЭВМ и проведение вычислительного эксперимента.
Методы исследования. В исследованиях, проводимых в диссертации, используются методы теории экстремальных задач и теории оптимального управления. Применяются метод динамического программирования и итерационные методы решения задач оптимизации.
Научная новизна.
Построена операторная версия метода ДП для решения задачи маршрутизации последовательного обхода сечений МО в произвольном непустом множестве в условиях неточных вычислений функции Беллмаиа и отступления от принципа оптимальности при формировании пары "маршрут-трасса" для двух критериев агрегирования затрат. Получена оценка отклонения по результату относительно глобального экстремума для ситуации, когда массив значений функции Беллмаиа насчитывается с погрешностями, а выбор очередных элемента маршрута и узла трассы производится с отступлением от принципа оптимальности в пределах некоторых допусков.
Для задачи маршрутизации последовательного обхода компактных множеств в конечномерном пространстве для двух критериев агрегирования затрат построены оценки рассогласования результата, которое имеет место при замене одной системы компактов другой системой, в терминах хаусдорфовых расстояний между множествами этих систем.
3. Установлена эквивалентность двух типов маршрутных задач опти
мизации: задачи последовательного обхода множеств и задачи, имеющей
20Ченцоп А.А., Ченцов А.Г. К вопросу о решении задачи последовательного обхода множеств с использованием "незамкнутой" задачи коммивояжера // А и Т. 2002. №11. С. 151 - 166.
смысл реконструкции системы "городов", используемых в ЗК. Первая задача есть задача на экстремум со связанными переменными, а вторая — задача оптимизации с независимыми переменными.
4. Построен итерационный алгоритм решения задачи маршрутизации последовательного обхода множеств, допускающий оценку погрешности по отношению к неизвестному глобальному экстремуму для каждой итерации.
Теоретическая и практическая ценность. В диссертации разработаны конструктивные методы исследования экстремальных задач, связанных с маршрутизацией перемещений по конечной системе множеств, и, на этой основе, построены алгоритмы и программы решения таких задач для двух наиболее важных способов агрегирования затрат. Результаты диссертации могут быть использованы в дальнейших исследованиях и при решении практических задач, связанных с размещениями и маршрутизацией.
Апробация работы. Результаты диссертации докладывались на областном конкурсе студенческих научных работ (Направление "Естественные науки", 3-я премия, 1995), на Всероссийской конференции "Актуальные проблемы прикладной математики и механики", посвященной 70-летию со дня рождения академика А.Ф. Сидорова (2003), конференциях молодых научных сотрудников и аспирантов ИММ УрО РАН (2001, 2002), семинарах отдела динамических систем ИММ УрО РАН, отдела управляемых систем ИММ УрО РАН, кафедры вычислительной техники Физико-технического факультета УГТУ-УПИ,
Публикации. По теме диссертации опубликовано 14 работ, список которых приводится в конце автореферата.
Структура и объем работы. Диссертация состоит из введения и 2 глав, разбитых на 12 параграфов. Объем диссертации составляет 150 страниц, набранных в текстовом редакторе LATEX. Библиография состоит из 52 наименований.
