Некоторые маршрутные задачи последовательного обхода множеств тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РОССИЙСКАЯ АКАДЕМИЯ НАУК УРАЛЬСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ

На правах рукописи

ЧЕНЦОВ Алексей Александрович

НЕКОТОРЫЕ МАРШРУТНЫЕ ЗАДАЧИ ПОСЛЕДОВАТЕЛЬНОГО ОБХОДА МНОЖЕСТВ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Екатеринбург — 2003

Работа выполнена в Институте математики и механики Уральского отделения РАН.

Научный руководитель - доктор физико-математических наук,

профессор В.Н. Ушаков Официальные оппоненты - доктор физико-математических наук,

профессор А.Н. Сесекин, кандидат физико-математических наук, старший научный сотрудник В.Б. Костоусов Ведущая организация — Челябинский государственный

университет

Защита состоится ^ " _^_ 2003 года

/5

II X ^ II

часов на заседании диссертационного совета К 004.006.01

по защите диссертаций на соискание ученой степени кандидата наук в Институте математики и механики Уральского отделения РАН по адресу: 620219, г. Екатеринбург, ул. Софьи Ковалевской 16.

С диссертацией можно ознакомиться в научной библиотеке Института математики и механики УрО РАН.

Автореферат разослан октября 2003 г.

Ученый секретарь диссертационного совета

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. В диссертационной работе исследуются задачи маршрутизации последовательного обхода множеств и сечений многозначных отображений (МО). В заданном непустом множестве требуется построить путь (ломаную), выходящий из обособленного элемента множества; узлами этого пути являются элементы некоторых его подмножеств (по одному представителю от каждого), Задана функция, оценивающая затраты на переход между точками множества. Совокупные затраты на весь такой путь оцениваются либо суммой затрат по всем его звеньям (аддитивный критерий), либо наибольшими, среди всех участков пути, затратами (критерий типа "максимум"). Мы стремимся оптимизировать величину совокупных затрат посредством согласованного выбора перестановки индексов подлежащих обходу множеств, называемой далее маршрутом, и кортежа элементов множеств (по одному из каждого множества, при этом очередность задается маршрутом), именуемого далее трассой. В результате возникает дискретно-непрерывная экстремальная задача. Дискретная составляющая связана с построением маршрута, а непрерывная — с отысканием трассы. Вообще говоря, без потери качества невозможна декомпозиция задачи на две вышеупомянутые подзадачи, являющиеся дискретной и непрерывной ее компонентами.

Потребность в таких постановках возникает в задачах авиапожарного патрулирования лесов, облета архипелага, размещения компонент электронной аппаратуры на печатных платах1,2.

Первые две задачи связаны с оптимизацией посещений некоторым летательным аппаратом определенных географических областей, которыми могут быть лесные массивы, группы островов архипелага и т.д. Требуется минимизировать либо суммарный расход топлива на весь перелет, либо наибольший среди звеньев пути расход горючего (это требование может быть обусловлено необходимостью гарантировать невозможность израсходования всего запаса топлива во время перелета но самому протяженному звену пути). В задаче размещения компонент электронной аппаратуры на печатной плате задана система токопроводящих фрагментов, на каждом из которых имеется набор точек крепления функциональных элементов электронной аппаратуры, и некоторый обособленный контакт. Требуется провести проводник с началом в данном контакте, соединяющий все фрагменты

'Коротаева Л.Н., Трухни М.П., Ченцов А.Г. К вопросу о маршрутизации соединений // А и Т. — 1997. - №12. - С. 175 - 192.

2Деньдобренко Б.Н., Малика A.C. Автоматизация конструирования РЭА. — М.: Высш. школа, 1980.

печатной платы, минимальной длины (сопротивления) или с наименьшей протяженностью (сопротивлением) наиболее длинного звена (звена с наибольшим сопротивлением). Первое требование может быть продиктовано соображениями оптимизации общего сопротивления всего проводника, а второе — желанием минимизировать наибольшее падение напряжение среди участков проводника при прохождении по нему электрического тока.

В плане построения маршрута данная задача является обобщением известной ¡задачи коммивояжера (ЗК)3 (имеется в виду незамкнутый ее вариант), которая относится к классу задач дискретной оптимизации: при решении ЗК осущес1*вляется маршрутизация точечных объектов ("городов") посредством выбора очередности их посещения, а в нашей задаче помимо поиска маршрута требуется выбрать точки на множествах, образующие трассу. Для решения ЗК имеется много методов, как точных*1, так и приближенных5. Среди них отметим метод ветвей и границ6 и метод динамического программирования (ДП)7,К.

В связи с поиском трассы отметим задачи последовательного управления, в которых требуется оптимизировать перемещение динамической системы по множествам в фазовом пространстве с заданной очередностью их посещений. Отметим в этой связи подход, развиваемый свердловской школой H.H. Красовского, Речь идет, в частности, о построении вариантов принципа максимума JI.C. Понтрягина9, основывающихся на идеях двойственности10 линейных задач управления и задач выпуклого программирования. Данное направление связано прежде всего с работами H.H. Красовского, A.B. Куржанского, Ю.С. Осипова и А.И. Субботина. На этой основе были разработаны конструкции решения задач последовательного

3Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Вопросы теории // А и Т. — 1989. - №9. - С. 3 - 34.

4Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Точные алгоритмы // А п Т. — 1989. - №10. - С. 3 - 29.

5Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Приближенные алгоритмы // А и Т. - 1989. - №11,- С. 3 - 26.

"Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач большой размерности. — Киев: Наукова думка, 1981. — 288 с.

7Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник, - М.: Мир, 1964. - Т. 9 - С. 219 - 228.

8Хелд М., Карп P.M. Применение динамического программирования к задачам упорядочения. // Кибернетический сборник, — М,: Мир, 1964. — Т. 9 - С. 202 - 218.

°Понтрягин Л.С., Болтянский В,Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. — М.: Наука, 1976. — 392 с.

'"Красовский H.H. Теория управления движением. — М.: Наука, 1968. — 476 с.

управления линейными системами11, логически связанные с проблемой оптимизации трасс в задаче последовательного обхода множеств (отметим вариант принципа максимума JI.С. Понтрягина для нелинейной задачи последовательного управления12, а также исследования Ю.И. Бердышева13 в области решения задач управления, связанных с посещением упорядоченной системы множеств). Рассматривались игровые варианты задач последовательного управления14. Кроме того, отметим некоторые маршрутные (по смыслу) задачи оптимизации на классе ломаных15 (использовались методы теории приближения функций).

Известен точный метод решения задачи маршрутизации последовательного обхода множеств — модификация метода ДП16. Данный метод позволяет существенно сократить объем вычислений в сравнении с полным перебором и не нуждается в специальном выборе начального приближения. Основной его недостаток связан с жесткими требованиями к доступной, для хранения массива значений функции Беллмана, памяти при реализации на ЭВМ. В работе приводится вариант данного метода, адаптированный для решения задач маршрутизации последовательного обхода сечений МО в произвольном непустом множестве. В частности, рассматривается конструкция, позволяющая сократить перебор и заключающаяся в том, чтобы просматривать не все очередное целевое множество, а лишь его часть, которая задается допуском, оценивающим разницу в затратах на перемещения в точки области по отношению к затратам на переход в "ближайший" элемент данного множества (в результате имеем обход подвижных множеств).

Основное внимание уделяется вопросам приближенной реализации метода ДП. Рассматривается построение массива значений функции Беллмана (первый этап метода ДП) по слоям с погрешностями, величина ко-

"Бердышев Ю.И., Ченцов А.Г. Оптимизация взвешенного критерия в одной задаче управления // Кибернетика. 1986. №2. С. 59 - 87.

12Бердышев ГО.И., Чепцов А.Г. О некоторых задачах последовательной оптимизации управляемых систем // Рукопись в деп. в ВИНИТИ. - 1983. - №109-83 Деп, - 99 с.

13Бердышев Ю.И. О задаче последовательного обхода нелинейным управляемым объектом совокупности гладких многообразий // Дифференциальные уравнении. 2002. Т. 38. №11. С. 1451 - 14G1.

иКрасонскнй H.H., Лукоянов Н.Ю. Задача конфликтного управления с наследственной информацией // ПММ, 1996. Т. 60, Вып. 6. С. 885 - 900.

15Бердышев В.И., Кондратьев В.П. О наилучшей траектории, соединяющей упорядоченный набор множеств. Свердловск: ИММ УНЦ АН СССР, 1986.

1вКоротаева Л.Н., Сесекии А.Н., Ченцов А.Г. Об одной модификации метода динамического программирования в задаче последовательного сближения // Журнал вычислительной математики и математической физики. - 1989. - Т. 29, №8. - С. 1107 - 1113.

торых оценивается сверху (для каждого слоя). Получены оценки сверху для рассогласований значений истинной и "приближенной" функций Бел-лмана. Рассматривается формирование пары "маршрут-трасса" (второй этап метода ДП) в условиях, когда допускается отступление от принципа оптимальности (в пределах заданных доспусков) при выборе очередного элемента маршрута и узла трассы. В итоге получена оценка сверху для погрешности, возникающей при вычислении функции Беллмана и отступлении от оптимальности при формировании пары "маршрут-трасса"17.

Исследуется отклонение результата при подмене одной системы маршрутизируемых компактных множеств другими (получена оценка в терминах хаусдорфовых расстояний между множествами разных систем)18. Рассматривается замена компактов их конечными подмножествами (е-сетями) а, в случае аддитивной функции агрегирования затрат, — границами компактов19 Погрешности при вычислении экстремумов в уравнении Беллмана могут быть при этом обусловлены применением численных методов оптимизации, различных аппроксимаций функции Беллмана, а также дискретизации областей поиска узла трассы в условиях недостижимости инфимума затрат на произвольном множестве. Проведенные исследования позволяют оценить отклонение по результату при решении (на ЭВМ) задачи маршу-рутизации последовательного обхода множеств методом ДП.

Благодаря высоким требованиям к доступной памяти ЭВМ, метод ДП утрачивает возможность практического применения уже для систем, содержащих несколько десятков множеств. Разработан приближенный алгоритм решения задачи маршрутизации последовательного обхода множеств с использованием ЗК, основная идея которого — разделение в режиме итераций процесса формирования маршрута и процесса построения трассы вдоль этого маршрута. Данный алгоритм позволяет оценить сверху погрешность результата по отношению к неизвестному глобальному экстремуму. Такая возможность важна при решении практических задач, так как обычно существуют допуски на предельную величину погрешности. Для построения и обоснования метода предложен новый взгляд на исходную экстремальную задачу со связанными переменными (очередность следования точек

17Ченцов A.A., Ченцов А.Г. О решении задачи маршрутной оптимизации методом динамического программирования // Изв. Академии наук. Теория и системы управления. 1999. №3. С. 76 - 87.

18Chentsov A.A., Chentsov A,G. Dynamic Programming Method in the Generalized Traveling Salesman Problem: The Influence of Inexact Calculations // Mathl. Comput. Modelling. — 2001. - Vol. 33, - pp. 801 -,819.

18Ченцов A.A., Ченцов А.Г. Редукция задач маршрутной оптимизации// А и Т. 2000. №10. С. 136 -150.

б

трассы задается маршрутом), как на задачу с независимыми переменными, которыми в данном случае являются система "городов" и маршрут, Доказана эквивалентность этих экстремальных задач20.

Цель работы состоит в следующем:

1. Поиск возможностей сокращения объема перебора при решении маршрутной задачи последовательного обхода методом ДП;

2. Исследование влияния на результат погрешностей вычисления функции Беллмана и экстремумов при построении пары "маршрут-трасса" в процессе решения исходной задачи методом ДП;

3. Исследование зависимости экстремума при изменении целевых множеств;

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

5. Реализация методов решения исходной задачи в виде программ для ПЭВМ и проведение вычислительного эксперимента.

Методы исследования. В исследованиях, проводимых в диссертации, используются методы теории экстремальных задач и теории оптимального управления. Применяются метод динамического программирования и итерационные методы решения задач оптимизации.

Научная новизна.

1. Построена операторная версия метода ДП для решения задачи маршрутизации последовательного обхода сечений МО в произвольном непустом множестве в условиях неточных вычислений функции Беллмана и отступления от принципа оптимальности при формировании пары "маршрут-трасса" для двух критериев агрегирования затрат. Получена оценка отклонения по результату относительно глобального экстремума для ситуации, когда массив значений функции Беллмана насчитывается с погрешностями, а выбор очередных элемента маршрута и узла трассы производится с отступлением от принципа оптимальности в пределах некоторых допусков.

2. Для задачи маршрутизации последовательного обхода компактных множеств в конечномерном пространстве для двух критериев агрегирования затрат построены оценки рассогласования результата, которое имеет место при замене одной системы компактов другой системой, в терминах хаусдорфовых расстояний между множествами этих систем.

3. Установлена эквивалентность двух типов маршрутных задач оптимизации: задачи последовательного обхода множеств и задачи, имеющей

20Ченцоп A.A., Ченцов А.Г. К вопросу о решении задачи последовательного обхода множеств с использованием "незамкнутой" задачи коммивояжера // А и Т. 2002. №11. С. 151 - 166.

смысл реконструкции системы "городов", используемых в ЗК. Первая задача есть задача на экстремум со связанными переменными, а вторая — задача оптимизации с независимыми переменными.

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

Теоретическая и практическая ценность. В диссертации разработаны конструктивные методы исследования экстремальных задач, связанных с маршрутизацией перемещений по конечной системе множеств, и, на этой основе, построены алгоритмы и программы решения таких задач для двух наиболее важных способов агрегирования затрат. Результаты диссертации могут быть использованы в дальнейших исследованиях и при решении практических задач, связанных с размещениями и маршрутизацией.

Апробация работы. Результаты диссертации докладывались на областном конкурсе студенческих научных работ (Направление "Естественные науки", 3-я премия, 1995), на Всероссийской конференции "Актуальные проблемы прикладной математики и механики", посвященной 70-летию со дня рождения академика А.Ф. Сидорова (2003), конференциях молодых научных сотрудников и аспирантов ИММ УрО РАН (2001, 2002), семинарах отдела динамических систем ИММ УрО РАН, отдела управляемых систем ИММ УрО РАН, кафедры вычислительной техники Физико-технического факультета УГТУ-УПИ,

Публикации. По теме диссертации опубликовано 14 работ, список которых приводится в конце автореферата.

Структура и объем работы. Диссертация состоит из введения и 2 глав, разбитых на 12 параграфов. Объем диссертации составляет 150 страниц, набранных в текстовом редакторе LATEX. Библиография состоит из 52 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обосновывается актуальность темы (в том числе указывается область потенциального применения результатов работы), определяется цель работы, приводятся аналоги задачи маршрутизации последовательного обхода множеств, проводится обзор литературы по исследуемой проблематике и излагаются основные результаты и содержание работы.

Первая глава состоит из 8 параграфов и посвящена применению метода ДП для решения задачи маршрутизации последовательного обхода множеств, его адаптации для решения задачи последовательного обхода

сечений МО, а также исследованию влияния погрешностей вычисления функции Беллмана и экстремумов при построения пары "маршрут-трасса" и дискретизации целевых множеств на результат решения задачи. Серьезное внимание уделяется сокращению объема перебора при решении, данной задачи методом ДП за счет просмотра не всего очередного целевого множества, а подмножества е-ближайших к текущей позиции точек, а, в случае аддитивного критерия агрегирования затрат и компактных целевых множеств, — посредством замены множеств их границами. Для каждого из этих случаев получены оценки рассогласования результата по отношению к глобальному экстремуму полной задачи и промежуточные оценки для слоев функции Беллмана и этапов построения пары "маршрут-трасса".

Пусть заданы произвольное непустое множество X, его элемент х° € X, играющий роль начального состояния, а также кортеж операторов, являющихся МО в X:

А\: X 2х,..., Ам ■ X -ч- 2х, (1)

где 2х — семейство всех непустых подмножеств множества X.

Для оценки затрат на перемещения в X задан кортеж функционалов, имеющих смысл функций стоимости:

с\ : X х X [0,оо[, ... , См : 1x14 [0,оо[. (2)

Рассматриваются следующие перемещения в X из начальной позиции х° по сечениям МО (1):

(ж0 [хх е АЫ) ... {хц е (з)

здесь X = {¿1; ...;г/у} — перестановка номеров из 1,^, именуемая далее маршрутом, а (жо; жц ...; хц) — кортеж точек "движения" по маршруту X, называемый далее трассой. Каждое перемещение вида (3) оценивается с помощью (2) величиной:

си(х0,хг) + ... + (4)

для аддитивного критерия или

тах(с1-1(з;о,а;1), (5)

для критерия типа "максимум". Ограничимся здесь рассмотрением только аддитивного критерия агрегирования затрат, хотя в диссертации все результаты получены для обоих критериев. Мы стремимся свести к минимуму величину совокупных затрат (4) или (5) посредством согласованного выбора маршрута и трассы вдоль этого маршрута (т.е. выбора пары "маршрут-трасса").

При использовании метода ДП с этой задачей минимизации связывается функция Беллмана У, аргументами которой являются пары (ж, А"), где х е X и К — подмножество 1, N. Если, при в е О, И, рассматривать множество £>„ всех таких пар (х, К), у которых х € X, а К, К С 1, Ы, имеет мощность з, то все пространство упомянутых позиций разбивается на слои 1>о, А) •••) Ау- Функцию Беллмана можно представить в виде системы слоев (сужений) У0,\Г1,...,Ум.'ЁслаРе = {Д, [0,оо[} (з = 0,1,.... ЛГ), то построение функции Беллмана (решение уравнения Беллмана) эквивалентно преобразованию Ц>VI -4 У/у посредством операторов

Т, : -»• Я, (6)

где я £ 1, N. Каждый такой оператор определяется правилом

А-} = тщ Ы (сл(®,у) + Л(у, К \ {Л})); (7)

кбК 1/елк(®)

в итоге с помощью операторов (7) по цепочке (6) формируется "беллманов-ский" процесс построения массива значений функции Беллмана по слоям в пространстве позиций (Уо ~ О)к(У, — Т3(У^Х) Уз € 1,ЛГ), где О : Д)->К- есть функция, тождественно равная нулю.

Введем в этот процесс на основе (6) погрешности, оцениваемые сверху числами ¿1 > 0, > 0; именно, пусть функции

% 6 ^о, VI б Д, ..„ % 6 таковы, что Уо = О и для 5 £ 1, ЛГ, К) € Д, имеет место \У,(х, К) - Та(У3-1)(х, Л')| <

Тогда справедливо следующее

Утверждение 1.1. Отклонение УТ от Уг удовлетворяет оценке

г

Щх, К) - УТ(х, К")| < Уг е 17^ У(я=, К) 6 я. (8)

8=1

Таким образом, осуществляется приближенное построение массива значений функции Беллмана. При этом погрешности могут быть обусловлены использованием численных методов при вычислении экстремумов (7) или дискретизаций значений МО при поиске инфимума в (7). Оценка (8) означает, что проигрыш в результате будет определяться суммой 5\, ...,6м.

Построение пары "маршрут-трасса" ведется в обратном, по отношению к формированию массива значений функции Беллмана, направлении.

Рассмотрим сначала постановку, в которой значения операторов (1) конечные подмножества X. Именно, на первом этапе решается уравнение Беллмана

V(x°, 1, N) = min min Ых°, у) + V(y, 1, N \ {*})]; (9)

относительно элемента маршрута ii = к и узла трассы xi = у, доставляющих соответствующие экстремумы.

На произвольном j-м шаге (2 < j < N) решается уравнение Беллмана

VCxj-i, 1, iv \ {ii,.... v-x» = _min min [ck(xj-uv)+

A£l,JV\-fi|.....i} ^g)

(lTJV \ {i!.....ij-x» \ {Ä»];

и определяется из условий минимума очередной узел пары "маршрут-трасса", а именно, индекс ij и точка трассы Xj.

Пусть теперь значения операторов (1) есть произвольные непустые подмножества X, а выбор очередных элемента маршурута и узла трассы при решении уравнений вида (9) (для 1-го шага) или (10) (для последующих шагов) осуществляется так, чтобы совокупные затраты при этом отличались от экстремума не более чем на величину к5) где s — это номер шага (разумеется, в выражениях (9) и (10) внутренний минимум следует заменять на инфимум). Пусть, кроме того, вместо истинной функции Беллмана V задана аппроксимирующая ее функция V такая, что

(Vs £ TjV Va е Dn„s : |V(z) - V(z)\ < а.) к (Vг 6 £>0 : V(z) = 0), (11)

где ai > 0, ...,адг > 0. Тогда справедливо следующее

Утверждение 1.2. Для функции\> удовлетворяющей (11) справедлива при заданных наборах параметров точности (а,)а6и (Kj)äSr^ следующая оценка: для любой пары "маршрут-трасса" (Л, (а^¡g-pv) конструируемой на основе приближенного решения абстракных аналогов задач (9), (10) с точностью, характеризуемой кортежем (OseTw имеет место

N N

j-1 ä=i

Рассмотрим теперь задачу маршрутизации последовательного обхода компактных подмножеств п-мерного арифметического пространства К", т.е. случай X = К". Пусть заданы две системы компактов (Я-1')^^ 6 С

И

(H^)ieY7f e гДе ~ множество всех кортежей из N непустых компактных подмножеств R". Пусть функции затрат заданы с помощью метрики р, порожденной некоторой нормой || • ||: Vi £ 1, N V®i £ X V12 е X : Ci{xi,x2) = р{х 1,Жг) = ||жх ~ Рассматривается задача маршрутизации перемещений по каждой из двух систем множеств (будем конкретизировать систему, о которой идет речь, в квадратных скобках в обозначении функции Беллмана).

Утверждение 1.3. Для аддитивного критерия:

< VKtf^^K^MV) + 2 ¿^tffUf);

j=l

для критерия типа "максимум";

WfWK*0'1^) £ nCtffWK*0-1^) +2тахй(Я<1),яР),

iSl,N

где S) — метрика Хаусдорфа на семействе С всех непустых компактных подмножеств R".

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

Пусть для фиксированного вектора х° е К" рассматривается задача последовательного обхода непустых компактных множеств Mi,..., Mn и пространстве R" (т.е. Mi С К" при i £ 1 ,N)\ эти множества не пересекаются попарно и не содержат х° (в данном случае имеем упрощенный вариант задачи обхода МО в X = 1R" из первой главы, в котором значения МО постоянны и совпадают с множествами Mi, г € 1 ,N). Дана непрерывная функция с : К" х R" [0, оо[; ограничимся сейчас обсуждением аддитивного критерия (в диссертации результаты получены для обоих функций агрегирования затрат); маршрут J = (ij)jeT727 (перестановка 1 ,N) и трасса (^¡Х'еоТ?' гДе х° ~ х°>х1 € Mi,, ,..,Xff € MiN, оцениваются в своей совокупности суммой:

c{x0,xi) +...+c{xN_uxN). (12)

Получающаяся задача на минимум (12) в классе пар "маршрут-трасса" есть экстремальная задача Со связанными переменными. Назовем ее основной маршрутной задачей (ОМЗ). Точным методом ее решения является

метод ДП, рассмотренный выше. В связи с большим объемом перебора и, главное, высокими требованиями к объему доступной оперативной памяти компьютера при решении таких задач на ЭВМ этот метод утрачивает возможность практического применения с ростом размерности задачи.

Другая по форме задача состоит в следующем. В пределах следует, при всяком I €.1, И, выбрать "город" (элемент множества) ж'1'. Таким

н

образом требуется построить систему "городов" (ж'^^пу 6 П после

___ ¿=1_

чего следует решить ЗК с матрицей [с(: г е О, IV, $ е 1, М], где х(°) = х°; для этого допустимо использовать любые перестановки J множества 1, N. Упомянутая оптимизация критерия-суммы достигается совокупным выбором (незанумерованных) городов и маршрута 3. Мы имеем здесь экстремальную задачу с независимыми переменными: системы "городов" и перестановки в 1, ТУ". Назовем ее задачей реконструкции (ЗР). Налицо декомпозиция исходной задачи на две более простых подзадачи: задача построения системы "городов" (непрерывная компонента) и задача поиска перестановки, задающей очередность обхода "городов" (дискретная составляющая), которая есть не что иное, как незамкнутая ЗК. Встает вопрос: как связаны между собой ОМЗ и ЗР (какова зависимость между глобальными экстремумами, пространствами решений и множествами оптимальных решений). Ответ на него дает следующее

Утверждение 2.1. ОМЗ и ЗР эквиваленты: 1) их экстремумы совпадают; Ё) непустые экстремальные множества этих задач находятся во взаимно однозначном соответствии.

Утверждение 2.1 является теоретической основой для декомпозиции исходной задачи маршрутизации последовательного обхода множеств на две более простые подзадачи: построение маршрута (решение ЗК) и поиск трассы вдоль этого маршрута. Отметим, что, вообще говоря, эти две компоненты между собой жестко связаны, и нельзя без потери качества производить такую декомпозицию. Обозначим через V глобальный экстремум ОМЗ. Кратко опишем основную идею данного алгоритма на примере 1-й итерации.

Шаг 1: построение матрицы попарных сравнений.

Матрица А'1' имеет размерность (.¿V +1) х N. а ее элементы — суть наименьшие значения функции с, отвечающие паре фиксированных множеств: если г € О, Ы, э е 1, ТУ, то

тт (13)

Шаг 2: построение маршрута.

Решаем ЗК с матрицей Л'1' (13). В результате получаем маршрут а/1) и величину оптимальных (для этой ЗК) затрат V,

Шаг 3: нахождение трассы вдоль маршрута ы^.

Решаем задачу выбора точек на множествах, стремясь минимизировать затраты на перемещение по ним из начальной позиции ж0 в очередности, задаваемой маршрутом с«/1'. Для этого используем соответствующую модификацию метода ДП. В результате получаем трассу у^1' € М^цщ,..., е МЫ11)(дг) и величину оптимальных (в данной подзадаче) затрат У^ш'1'].

Шаг 4: построение системы "городов" и оценка погрешности.

Производим согласование индексов точек трассы с номерами множеств,

ш N

из которых они выбраны. В результате от трассы (у\ );6П7 е П Л^ии« с,

' ¿=1

помощью обратной, по отношению к о/1', перестановки переходим к систе-

т я

ме "городов" (а* 0,-еЩ е П М-

»=1

Оценка погрешности алгоритма на первой итерации: V < V < У[щМ], Дальнейшие итерации аналогичны 1-й с той лишь разницей, что на 2-м шаге к-й итерации (к > 2) решается ЗК по обходу системы "городов" (к 1) м

(2< " )»бТ^ € П Ми полученной на 4-м шаге (к - 1)-й итерации (соответственно по другому формируется и матрица попарных сравнений на 1-м шаге). В результате имеем следующую оценку погрешности для к-й итерации (как видно из нее, алгоритм является неухудшающим):

V < V < У[и>^>] < ... < \><2>] < У^1)]. ЗАКЛЮЧЕНИЕ

Диссертационная работа посвящена решению задач маршрутизации последовательного обхода множеств и ссгсний МО. Для двух основных типов функции агрегирования затрат (аддитивный критерий и критерий типа "максимум") построена операторная версия метода ДП для общей задачи последовательного обхода сечений МО и исследовано влияние погрешностей вычисления функции Беллмана при построении массива ее значений и экстремумов при формировании решения в виде пары "маршрут-трасса".

Это исследование важно в связи с решением вышеупомянутых задач на ЭВМ, так как при этом обычно используются различные аппроксимации функции Беллмана, дискретизация целевых множеств (замена их £-сетями) и численные методы оптимизации. Построен метод итераций и, на его основе, алгоритм решения задачи последовательного обхода множеств. Получены следующие основные результаты:

1. Проведено детальное исследование влияния погрешностей вычисления функции Беллмана при построении массива ее значений и экстремумов при формировании пары "маршрут-трасса". Получены явные оценки возможного проигрыша по результату для каждой из этих ситуаций и для их комбинации.

2. Для экстремальной задачи последовательного обхода множеств (задача со связанными переменными) построена эквивалентная экстремальная задача реконструкции с независимыми переменными и, на ее основе, метод итераций, использующий декомпозицию основной маршрутной задачи с выделением дискретной и "непрерывной" ее компонент.

3. Построен и реализован на ЭВМ итерационный алгоритм решения задачи последовательного обхода множеств, допускающий на каждой итерации возможность оценки уклонения текущего результата по отношению к неизвестному глобальному экстремуму; использование этого алгоритма позволило существенно увеличить размерность решаемых задач в сравнении с методами, применявшимися ранее.

Публикации по теме диссертации

1. Chentsov A.A., Chentsov A.G.Dynamic Programming Method in the Generalized Traveling Salesman Problem: The Influence of Inexact Calculations // Mathl. Comput. Modelling. - 2001. - Vol. 33, - pp. 801 - 819,

2. Ченцов A.A., Ченцов А,Г. О решении задачи маршрутной оптимизации методом динамического программирования // Автоматика и телемеханика. - 1998. - №9. - С. 117 - 129.

3. Ченцов A.A., Ченцов А.Г. Маршрутизация последовательного обхода системы подвижных множеств с использованием динамического программирования в условиях неточных вычислений функции Беллмана // Проблемы управления и информатики. — 1999. — №2. — С. 113 - 127.

4. Ченцов A.A., Ченцов А.Г. О решении задачи маршрутной оптимизации методом динамического программирования // Известия Академии наук. Теория и системы управления. — 1999. — №3. — С. 76 - 87.

5. Ченцов A.A., Ченцов А.Г. Редукция задач маршрутной оптимизации

// Автоматика и телемеханика. — 2000. — №10. — С. 136 - 150.

6. Ченцов A.A., Ченцов А.Г, Об одном "маршрутном" варианте процедуры динамического программирования и его реализации в условиях неточных вычислений // Информационная проблематика нечетких технологий. Управление информационных технологий Правительства Свердловской области. Екатеринбург: РУО МАИ, 1996.

7. Ченцов A.A., Ченцов А.Г. Моделирование и разработка формального и формализованного аппарата для сортировки текстов в системах знаний // Интеллектуальные информационные системы в управленческой деятельности. Екатеринбург: ИПК УГТУ, 1997. С. 24 - 27.

8. Ченцов A.A. , Ченцов А.Г. Об одном приближенном методе решения задач маршрутной оптимизации / Алгоритмы и программные средства параллельных вычислений: [Сб. науч. тр.]: Екатеринбург: УрО РАН, 2000 г., Вып. 4. С. 287 - 302.

9. Ченцов A.A. Метод итераций в обобщенной задаче коммивояжера на узкие места / Алгоритмы и программные средства параллельных вычислений: [Сб. науч. тр.]: Екатеринбург; УрО РАН, 2001 г., Вып. 5. С. 287 - 302.

10. Ченцов A.A. Метод итераций в задаче последовательного обхода множеств (обобщенная задача коммивояжера на узкие места) / Алгоритмы и программные средства параллельных вычислений: [Сб. науч. тр.]: Екатеринбург: УрО РАН, 2002 г., Вып. 6. С. 209 - 230.

11. Ченцов A.A. Об одном приближенном методе решения задач маршрутной оптимизации / Сборник научных трудов "Интеллектика, логистика, системология", №4, Челябинск, изд-во Т. Лурье, 2001 г., С. 53 - 61.

12. Ченцов A.A. Моделирование и разработка маршрутизатора на заданных топологиях объектов / Тезисы студенческих научных работ: Направление "Естественные науки". — Екатеринбург: Изд-во Урал, ун-та, 2001 г.,

13. Ченцов A.A., Ченцов А.Г. К вопросу о решении задачи последовательного обхода множеств с использованием "незамкнутой"задачи коммивояжера // Автоматика и телемеханика. 2002. № 11. С. 151 - 166.

14. Ченцов A.A., Ченцов А.Г. Маршрутные задачи последовательного обхода множеств // Тезисы всероссийской конференции "Актуальные проблемы прикладной математики и механики", посвященной 70-летию со дня рождения академика А.Ф. Сидорова - Екатеринбург: УрО РАН, 2003 г., С. 84- 85.

С. 7-9.

Ченцов Алексей Александрович

Некоторые маршрутные задачи последовательного обхода множеств

Автореферат

Подписано в печать 2.10.2003. Формат 60 х 84 1/16. Объем 1.0 п.л.

Тираж 100 экз. Заказ №91 Размножение с готового оригинал-макета в типографии УрО РАН 620219, Екатеринбург, ул. С.Ковалевской, 18.

1 5 63 6

Список сокращений.

Введение.

Глава I. Модификации метода динамического программирования в задачах последовательного обхода сечений многозначных отображений.

1. Введение.

2. Обход сечений многозначных отображений.

3. Метод ДП в условиях неточного определения функции Беллмана.

4. Построение оптимальных маршрутов и трасс.

5. Метод ДП для задач, где стоимость перехода зависит от номеров предыдущего и последующего многозначных отображений.

6. Некоторые вопросы аппроксимации целевых множеств.

7. Принцип граничных решений.

8. Некоторые результаты вычислительного эксперимента.

Глава II. Итерационные методы в задаче последовательного обхода множеств.

1. Введение.

2. Эквивалентность задачи последовательного обхода множеств и задачи реконструкции системы "городов".

3. Метод итераций в задаче последовательного обхода.

4. Некоторые результаты вычислительного эксперимента.

Предметом исследования в настоящей диссертации являются задачи последовательного обхода множеств и более общие задачи последовательного обхода сечений многозначных отображений (МО). Упомянутые дискретно-непрерывные экстремальные задачи возникают в качестве естественного развития задачи коммивояжера (ЗК) [30]. Последняя связана с оптимизацией маршрута при посещении конечной системы "городов" (под маршрутом понимается перестановка индексов "городов", соответствующая очередности их обхода) в условиях заданной матрицы затрат (каждый элемент матрицы есть величина затрат на перемещение из "города" с номером, равным индексу строки, в "город" с номером, равным индексу столбца). Для целей решения ЗК построено много алгоритмов, точных и приближенных; см. в этой связи [30]—[32]. Сейчас отметим только метод ветвей и границ [37, с. 37] и модификацию метода динамического программирования (ДП) для решения ЗК [3], [38]; последний будем активно использовать в условиях более общей задачи маршрутизации последовательного обхода множеств. Решение ЗК связано с перебором очень большого числа вариантов (АН вариантов в задаче обхода N "городов"). Поэтому большое значение имеет построение приближенных методов решения ЗК (простейший метод такого рода базируется на примитивном принципе: иди в "ближайший город").

Многочисленные потребности решения прикладных задач вынуждают рассматривать различные обобщения ЗК. В числе последних особо отмстим задачу маршрутизации последовательного обхода множеств (см., в этой связи, задачи посещения кластеров, упоминаемые в [30, с.7]; кроме того, см. исследования [28], [50], [51]). Это могут быть задачи, имеющие смысл облета островов архипелага, задачи размещения компонент радиоаппаратуры на печатных платах, простейшие модели задач авиапожарного патрулирования лесов. Упомянутые (и рассматриваемые далее) задачи маршрутизации последовательного обхода множеств являются, в отличие от ЗК (и "прямых" ее обобщений) дискретно-непрерывными экстремальными задачами: наряду с выбором нумерации элементарных задач (дискретная составляющая), требуется оптимизировать трассы движения по множествам (непрерывная компонента). Последний аспект является особенно существенным в маршрутных задачах управления, когда требуется оптимизировать перемещение динамической системы по множествам в фазовом пространстве этой системы. Особо отметим в этой связи подход, развиваемый свердловской школой H.H. Красовского. Речь идет, в частности, о построении вариантов принципа максимума JT.C. Поитрягина [35], базирующихся па идеях двойственности [25] линейных задач управления и задач выпуклого программирования. Данное направление связано прежде всего с работами H.H. Красовского, А.Б. Куржанского, Ю.С. Осипова и А.И. Субботина. На этой основе в [10], [11] были разработаны конструкции решения задач последовательного управления линейными системами, логически связанные с проблемой оптимизации трасс в задаче последовательного обхода множеств (отметим вариант принципа максимума JT.C. Понтрягина для нелинейной задачи последовательного управления в [12], [13], а также исследования Ю.И. Бердышева [Т]—[9] в области решения задач управления, связанных с посещением упорядоченной системы множеств). Игровые варианты задач последовательного управления рассматривались в работах [27], [29], [52]. Заметим, что некоторые маршрутные (по смыслу) задачи оптимизации на классе ломаных рассматривались в [5]; при этом использовались методы теории приближения функций.

В [20] был построен вариант метода ДП для решения дискретно-непрерывной задачи последовательного обхода конечной системы множеств в конечномерном пространстве. За этой статьей последовала серия работ, развивающая подход на основе метода ДП для различных классов задач дискретно-непрерывной оптимизации. Рассматривались задачи последовательного обхода сечений МО [18], [23], [39], [40], [45], [48] (особенность исследований в [39], [40], [45], [48] связана с допущением о том, что вычисления в схеме решения, использующей метод ДП, выполняются с погрешностями). В [21] была построена "сквозная" процедура решения маршрутно-распределительной задачи последовательного обхода множеств несколькими участниками, основанная на методе ДП. Развитие этих методов стимулировало исследования в области задач распределения заданий между исполнителями [22], [36], [46]. Одно из естественных возможных применений этих исследований связано с задачей нескольких коммивояжеров. Разумеется, конструкции ДП, применяемые в задачах последовательного обхода множеств, имеют своей основой обшую теорию, связанную с работами Р.Беллмана [2], [4]; абстрактные версии ДП и решения конкретных классов задач дискретной оптимизации с использованием метода ДП см. в [33]. Наконец исследования [3], [38] в области построения варианта метода ДП для ЗК послужили естественным ориентиром для разработки конструкций метода ДП для задач маршрутизации последовательного обхода множеств и сечений МО.

Данная диссертация состоит из Введения, двух глав и приложения.

1. Александрян P.A., Мирзаханян Э.А. Общая топология. — М.: Высшая школа, 1979. - 336 с.

2. Беллмаи Р. Динамическое программирование. — М.: Изд-во иностр. лит., 1974 432 с.

3. Беллман Р. Применение динамического программирования к задаче о коммивояжере // Кибернетический сборник. — М.: Мир, 1964. — Т. 9- С. 219-228.

4. Беллман Р., Калаба Р. Динамическое программирование и основы современной теории управления. М.: Наука, 1969.

5. Бердышев В.И., Кондратьев В.П. О наилучшей траектории, соединяющей упорядоченный набор множеств. Свердловск: ИММ УНЦ АН СССР, 1986.

6. Бердышев В.И., Петрак JI.B. Аппроксимация функций, сжатие численной информации, приложений. — Екатеринбург: УрО РАН, 1999.- 295 с.

7. Бердышев Ю.И. Об одной задаче последовательного сближения нелинейной управляемой системы третьего порядка с группой движущихся точек // ПММ. 2002. Т. 66. Вып. 5. С. 742-753.

8. Бердышев Ю.И. О задаче последовательного обхода нелинейным управляемым объектом совокупности гладких многообразий // Дифференциальные уравнения. 2002. Т. 38. №11. С. 1451-1461.

9. Бердышев Ю.И. Об оптимальном по быстродействию последовательном обходе нелинейной управляемой системой третьего порядка совокупности точек // Изв. Академии наук. Теория и системы управления. 2002. №3. С. 41-48.

10. Бердышев Ю.И., Ченцов А.Г. К вопросу о редукции некоторых линейных задач оптимального управления с интегральными ограничениями // Кибернетика. 1990. №4. С. 59-64.

11. Бердышев Ю.И., Ченцов А.Г. Оптимизация функционала на классе ломаных // Некоторые вопросы оптимизации разрывных функций. Свердловск, 1984. С. 29-42.

12. Бердышев Ю.И., Ченцов А.Г. О некоторых задачах последовательной оптимизации управляемых систем // Рукопись в деп. в ВИНИТИ. — 1983. №109-83 Деп. - 99 с.

13. Бердышев Ю.И., Ченцов А.Г. Оптимизация взвешенного критерия в одной задаче управления // Кибернетика. 1986. №2. С. 59-87.

14. Буслаева JI.T., Ченцов А.Г. К вопросу о декомпозиции процесса последовательного выбора вариантов // Математическое моделирование. — 1991. Т.З, т. - С. 103-113.

15. Варга Дж. Оптимальное управление дифференциальными и функциональными уравнениями. — М.:Наука, 1977.— 624с.

16. Данфорд Н.,Шварц Дж.Т. Линейные операторы.Общая теория.— М.: Изд-во иностр. лит-ры, 1962. — 895с.

17. Деньдобренко Б.Н., Малика A.C. Автоматизация конструирования РЭА. М.: Высш. школа, 1980. - 384 с.

18. Зобнин Б.Б., Коротасва JI.H., Ченцов А.Г. Об одной задаче маршрутной оптимизации и ее приложениях // Пробл. передачи информации. 1997. Т.ЗЗ. Вып. 4. С. 1-18.

19. Келли Дж.Л. Общая топология.— М.: Наука, 1981— 431 с.

20. Коротаева JI.H., Сесекин А.Н., Ченцов А.Г. Об одной модификации метода динамического программирования в задаче последовательного сближения // Журнал вычислительной математики и математической физики. 1989. - Т.29, №8. - С. 1107-1113.

21. Коротаева J1.H., Назаров Э.М., Ченцов А.Г. Об одной задаче о назначениях // Журнал вычислительной математики и математической физики. 1993. - Т.ЗЗ, т. - С. 483-494.

22. Коротаева J1.H., Трухин М.П., Ченцов А.Г. К вопросу о маршрутизации соединений // АиТ. 1997. - №2. - С. 175-192.

23. Коротаева JI.H., Ченцов А.Г. Об одном обобщении задачи коммивояжера "на узкие места"// Журнал вычислительной математики и математической физики. 1995. - Т.35, №7. — С. 1067-1076.

24. Красовский H.H. Теория управления движением. — М.: Наука, 1968. 476 с.

25. Красовский H.H. Игровые задачи о встрече движений. — М.: Наука, 1970. 420 с.

26. Красовский H.H., Лукоянов Н.Ю. Задача конфликтного управления с наследственной информацией // ПММ, 1996. Т. 60, Вып. 6. С. 885-900.

27. Лейтен А.К. Некоторые модификации задачи коммивояжера // Тр. ВЦ Тарт. ун-та, 1973. Вып. 28. С. 44-58.

28. Лукоянов Н.Ю. К вопросу вычисления цены дифференциальной игры для позиционного функционала // ПММ, 1998. Т. 62, Вып. 4. С. 586597.

29. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Вопросы теории // А и Т. 1989. - №9. - С. 3-34.

30. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Точные алгоритмы // А и Т. 1989. - №10. - С. 3-29.

31. Меламед И.И., Сергеев С.И., Сигал И.Х. Задача коммивояжера. Приближенные алгоритмы // А и Т. — 1989. — №11. — С. 3-26.

32. Мину М. Математическое программирование. М.: Наука, 1990.

33. Панасюк А.И., Панасюк В.И. Асимптотическая магистральная оптимизация управляемых систем. — Минск: Наука и техн., 1986. — 296 с.

34. Понтрягин Л.С., Болтянский В.Г., Гамкрелидзе Р.В., Мищенко Е.Ф. Математическая теория оптимальных процессов. — М.: Наука, 1976. 392 с.

35. Сабирянова К.Г., Ченцов А.Г. Динамическое программирование в задаче оптимизации покрытия. // А и Т. 1994. №3. С. 54-64.

36. Сергиенко И.В., Каспшицкая М.Ф. Модели и методы решения на ЭВМ комбинаторных задач большой размерности. — Киев: Наукова думка, 1981. -288 с.

37. Хелд М., Карп P.M. Применение динамического программирования к задачам упорядочения. // Кибернетический сборник. — М.:Мир, 1964. Т. 9 - С. 202-218.

38. Ченцов A.A., Ченцов А.Г. О решении задачи маршрутной оптимизации методом динамического программирования // А и Т. 1998. К29. С. 117 — 129.

39. Ченцов A.A., Ченцов А.Г. О решении задачи маршрутной оптимизации методом динамического программирования // Изв. Академии наук. Теория и системы управления. 1999. №3. С. 76 87.

40. Ченцов A.A., Ченцов А.Г. Редукция задач маршрутной оптимизации // А и Т. 2000. то. С. 136 150.

41. Ченцов A.A. , Ченцов А.Г. Об одном приближенном методе решения задач маршрутной оптимизации / Алгоритмы и программные средства параллельных вычислений: Екатеринбург: УрО РАН, 2000 г., Вып. 4. С. 287 302.

42. Ченцов A.A. Метод итераций в обобщенной задаче коммивояжера на узкие места / Алгоритмы и программные средства параллельных вычислений: Екатеринбург: УрО РАН, 2001 г., Вып. 5. С. 287-302.

43. Ченцов A.A., Ченцов А.Г. К вопросу о решении задачи последовательного обхода множеств с использованием "незамкнутой" задачи коммивояжера // А и Т. 2002. №11.

44. Ченцов А.А., Ченцов А.Г. Маршрутизация последовательного обхода системы подвижных множеств с использованием динамического программирования в условиях неточных вычислений функции Беллмана // Проблемы управления и информатики. 1999 - №2. - С. 113-127.

45. Ченцов А.Г., Ченцов П.А. К вопросу о построении процедуры разбиtения конечного множества на основе метода динамического программирования // А и Т. 2000. т. С. 129-142.

46. Энгелькинг Р. Общая топология,— М.: Мир,1986.— 751с.

47. Chentsov А.А., Chentsov A.G.Dynamic Programming Method in the Generalized Traveling Salesman Problem: The Influence of Inexact Calculations // Mathl. Comput. Modelling. 2001. - Vol. 33, - pp. 801-819.

48. Chentsov A.G., Korotayeva L.N. The Dinamic Programming Method in the Generalized Salesman Problem // Mathl. Comput. Modelling. — 1997. Vol. 25, No.l. - pp. 93-105.

49. Henry-Labordere A.L. The record-balancing problem: a dynamic programming solution of a generalized travelling salesman problem // R. I. R. O. 1969. V. 3 №. P. 43-49.

50. Laporte G., Nobert Y. Generalized travelling salesman problem through n-sets of nodes: an integer programming approach // INFOR. 1983. V. 21. m. P. 61-75.

51. Krasovskii A.N. and Krasovskii N.N. Control under lack of information. Berlin. Berlin etc.: Birkhauser, 1995. 322 p.