Методы декомпозиции экстремума и некоторые их применения в дискретно-непрерывных задачах оптимизации тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат физико-математических наук Маркелова, Елена Юрьевна

  • Маркелова, Елена Юрьевна
  • кандидат физико-математических науккандидат физико-математических наук
  • 1998, Екатеринбург
  • Специальность ВАК РФ05.13.18
  • Количество страниц 129
Маркелова, Елена Юрьевна. Методы декомпозиции экстремума и некоторые их применения в дискретно-непрерывных задачах оптимизации: дис. кандидат физико-математических наук: 05.13.18 - Математическое моделирование, численные методы и комплексы программ. Екатеринбург. 1998. 129 с.

Оглавление диссертации кандидат физико-математических наук Маркелова, Елена Юрьевна

СОДЕРЖАНИЕ

Введение. з

Глава I. Теоретическое обоснование метода декомпозиции

экстремума.

§1. Модельный пример дискретно- непрерывной маршрутной 9 задачи.

§2. Принцип декомпозиции в моделях со скалярным критерием. И §3. Условия декомпозиции в многокритериальных моделях. §4. Условия декомпозиции задач оптимизации по конусу. 1,4

§5. Декомпозиция многокритериальных задач оптимизации в случае произвольных упорядоченных топологических пространств

Глава II. Модели и алгоритмы получения оптимальных решений маршрутно-распределительных задач дискретно - непрерывного характера.

§6. Исследование моделей распределительных задач на основе метода декомпозиции экстремума.

§7. Исследование моделей маршрутных задач на основе метода ** декомпозиции экстремума.

§8. Математическая модель задачи маршрутизации с конечным «г числом переходов и абстрактной функцией агрегирования затрат.

§9. Математическая модель одной задачи маршрутизации сигнала 9 ч .с неаддитивной функцией агрегирования затрат. §10. Численная реализация решения маршрутно-распределитель- 54 ных задач.

Список литературы ^0'

Приложение

/Об

Рекомендованный список диссертаций по специальности «Математическое моделирование, численные методы и комплексы программ», 05.13.18 шифр ВАК

Введение диссертации (часть автореферата) на тему «Методы декомпозиции экстремума и некоторые их применения в дискретно-непрерывных задачах оптимизации»

Введение

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

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

и о и ^

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

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

Применению идей ДП для решения задач оптимизации различных классов посвящены многочисленные работы [2, 3, 9, 13, 16, 21, 22, 33, 42, 5]. В работах Р.Калабы, С.Дрейфуса, Р.Карпа, М.Хелда метод ДП применялся к решению задач маршрутизации. Отметим также исследования А.Вальда в области последовательного анализа статистических задач. Методы, использующие динамическое программирование и попятные процедуры, широко применялись в теории оптимального

управления и дифференциальных игр. (см., в частности, исследования Брайсона, Хо, Айзекса, Флеминга,Фридмана, Эллиота, Калтона и целого ряда других специалистов в этой области.)

Большой вклад в развитие конструкций, связанных с динамическим программированием, внесли исследования H.H. Красовского, А.Б. Кур-жанского, Ю.С. Осипова, А.И. Субботина, А.Г. Ченцова. Принцип экстремального прицеливания H.H. Красовского позволил получить эффективный метод решения для широкого класса задач теории конфликтного управления на основе подхода к анализу уравнения Айзекса - Беллмана с использованием программных конструкций, восходящих к принципу максимума Понтрягина. Идеи, связанные с решением уравнения Айзекса - Беллмана с применением конструкций негладкого анализа, получили дальнейшее развитие в работах А.И.Субботина.

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

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

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

(2) Предистория системы не имеет значения для принятия будущих решений (принцип отсутствия последействия). Решение текущей задачи не изменяет решений предыдущих задач.

(3) Решение исходной задачи есть сумма решений частных задач, то есть функция агрегирования является аддитивной.

Однако вскоре появляются задачи с неаддитивными функциями агрегирования, и для них также строятся рекуррентные соотношения Беллмана [4],[57]. Так, в задаче коммивояжера на "узкие места" функция агрегирования есть максимум между решениями двух соседних частных подзадач; в задаче "надежности" [4],[47] используется муль-

ти'пликативная функция агрегирования. Поэтому встает вопрос об обобщении условий, при которых возможна декомпозиция экстремума, являющаяся основой принципа оптимальности Беллмана. В 1964 году JI. Миттен [59] доказал теорему оптимальности, в которой были сформулированы условия, допускающие декомпозицию экстремума. Была рассмотрена задача поиска минимума функции / : 1 х 1" I, обладающей свойством разложимости, а именно: функция / является разложимой, если допускает представление

f(x,y) = fi(xj2(y)),

где ж Gl, |/ £ и /i не убывает по второму аргументу. Для таких функций Миттеном доказана справедливость соотношения:

min fix, у) = min А (х. min fviy)),

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

У

вии строгой монотонности /х по второму аргументу эквивалентность достигается.

Позже в [36] был выделен класс функций, обладающих свойством разложимости:

/(¡Ei,..., хп) = fi(x1)af2(x2)a...üfn(xn),

где □ - композиция функций.

Однако уже в простейших маршрутных задачах [5],[57] целевой функционал не обладает свойством разложимости, хотя для них были выведены уравнения Беллмана. В последнее время появился новый класс маршрутных и маршрутно - распределительных задач дискретно - непрерывного характера. Впервые аналоги уравнений Беллмана для задач этого класса были получены в ИММ УрО РАН в работах Ченцова А.Г., Сесекина А.Н., Коротаевой JI.H., Назарова Э.М. Целевые функционалы таких задач не являются разложимыми. Более того, пространство решений этих задач имеет сложную дискретно-непрерывную структуру и не вкладывается в Rn. Как правило, множеством решений является прямое произведение множеств разной порядковой и топологической структуры. К таким задачам относятся, прежде всего,

различные обобщения задачи п коммивояжеров. В [25, 6, 8, 32, 44] приведен ряд таких задач: задача авиапожарного патрулирования с различными целевыми функциями, задача о сборе космического му-сора,задачи оптимальной организации радиосвязи. В каждой из задач приводятся свои доказательства справедливости рекуррентных соотношений Беллмана. В связи с этим появилась необходимость создания единого аппарата для обоснования применения метода ДП, основой которого является декомпозиция экстремума.

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

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

Вопросу численной реализации процедур динамического программирования посвящены многочисленные публикации, среди которых упомянем [19, 37, 38, 45, 50, 57, 58-61]. В главе 2 приведен пример численного решения маршрутно-распределительной задачи п коммивояжеров с помощью субоптимального метода, позволяющего " разгрузить" трудоемкую процедуру динамического программирования. Показана целесообразность применения "фрагментарного" алгоритма, позволяющего ускорить решение задачи, уменьшить объем используемой памяти и внести в процедуру динамического программирования элемент диалоговой активности.

Цель диссертационной работы: 1) определение наименее жестких

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

Перейдем к краткому описанию содержания диссертации. Работа состоит из введения, двух глав, списка литературы, приложения. Объем ее'составляет 103 страницы без приложения машинописного текста. Список литературы содержит 68 наименования. Принята сквозная нумерация параграфов. Формулы и утверждения имеют двойную нумерацию: первая цифра - номер параграфа, вторая - номер по порядку в параграфе.

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

Во втором параграфе дана постановка задачи повторной оптимиза-

и . и

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

В §3 исследуется возможность повторной оптимизации в задачах с векторным критерием. Рассмотрены случаи минимумов и инфимумов различных типов: по Парето. по Слейтеру и Джоффриону.

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

Вторая глава посвящена вопросам моделирования дискретно - непрерывных задач с помощью метода декомпозиции, рассмотренного в

главе 1. В параграфах 6,7 приводятся примеры постановок маршрутно-распределительных и маршрутных задач, для которых ранее были построены и обоснованы (в каждой задаче по-своему) уравнения Бел-лмана, и показано, как эти же результаты могут быть получены с применением единообразного математического аппарата главы 1.

Постановка абстрактной задачи маршрутизации, приведена в §8. Эта задача является обобщением многих изученных маршрутных, в том числе дискретно- непрерывных задач. Рассмотрена процедура поиска решения на основе теорем оптимальности, доказанных в главе 1.

В §9 приводится пример использования метода декомпозиции при построении модели одной сетевой задачи с неаддитивной функцией агрегирования затрат. Для этой задачи также выписаны рекуррентные соотношения Беллмана.

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

В приложении содержатся тексты исходных модулей программ, написанных на языке Си для персонального компьютера типа 1ВМ РС/ АТ

Автор выражает глубокую благодарность научному руководителю доктору ф.-м. наук члену корреспонденту РАН А.Г.Ченцову за внимание и поддержку при написании работы, сотрудникам кафедры теории управления и оптимизации Челябинского госуниверситета и сотрудникам отдела управляемых систем ИММ УрО РАН за полезные дискуссии и советы.

Похожие диссертационные работы по специальности «Математическое моделирование, численные методы и комплексы программ», 05.13.18 шифр ВАК

Список литературы диссертационного исследования кандидат физико-математических наук Маркелова, Елена Юрьевна, 1998 год

СПИСОК ЛИТЕРАТУРЫ

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

2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации . Наука ,

3. Беллман Р. Динамическое программирование. М.: ИЛ, 1960. 400с.

4. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования. М.: Наука, 1965.

5. Беллман Р., Калаба Р. Динамическое программирование и современная теория управления

6. Бердышев Б.И. Об одном быстродействующем алгоритме решения маршрутной задачи в ньютоновском поле.:В сб. Маршрутно-распределительные задачи. Екатеринбург: УГТУ. 1995. С. 9-14.

7. Бердышев Ю.И. Построение и анализ областей достижимости в ньютоновском поле.:Научные доклады. Екатеринбург: ЙММ УрО РАН, 1997. 65с.

8. Бердышев Ю.И., Савинова JI.A. Об оптимальном по быстро-

и u w м и

действию управлении нелинейной системой в маршрутной задаче обхода группы точек.: В сб. Маршрутно-распределительные задачи. Екатеринбург: УГТУ. 1995. С.14-20.

9. Болтянский В.Г. Оптимальное упраление дискретными системами. М.: Наука, 1976. 392с.

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

11. Вагнер Г. Основы исследования операций, Т. 2,3.- М.: Мир, 1973

12. Васильев Ф.П. Численные методы решения экстремальных задач. М.: Наука, 1988. 522с.

13. Габасов Р.Ф., Кириллова Ф.М. Основы динамического программирования. Минск: Изд-во БГУ, 1975. 264с.

14. Гермейер Ю.Б. Игры с непротивоположными интересами. М.: Наука, 1976. 327с.

15. Гороховик В.В. Выпуклые и негладкие задачи векторной оптимизации. Минск: Наука и техника, 1990.

16. Данфорд Н., Шварц Дж. Т. Линейные операторы. Общая теория. М.: ИЛ, 1984.

17. Ермольев Ю.М. Кратчайшие допустимые пути I // Кибернетика, 1966, 3 с. 88-95.

18. Жуковский М. Отакизция шакшй 1>м«сгйф«тЕримь»м*х¿нмт vty*wmH'A- U.iШ/Шс

19. Зарецкий JI.C. Решение задачи коммивояжера и задачи развозки методом коррекции функций состояний // Экономика и математические методы. 1979, Т.15 1 с.194-201.

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

21. Колмогоров А.Н., ФоминС.В. Элементы теории функций и функционального анализа. М.: Наука, 1989, 624с.

22. Корбут A.A., Финкелыытейн Ю.Ю. Дискретное программирование. М.: Наука, 1969. 368с.

23. Коротаева Л.Н., Назаров Э.М., Ченцов А.Г. Об одной задаче о назначениях // ЖВМ и МФ. 1993. Т. 33, 4 С.483-494.

24. Коротаева JI.H., Сесекин А.Н., Ченцов А.Г. Об одной модификации метода динамического программирования в задаче последовательного сближения // ЖВМ и МФ. 1989. Т. 29, 8 СЛ107-1113.

25. Коротаева JI.H., Ченцов ^А. Г. Метод динаического программирования в одной задаче маршрутизации с неаддитивной функцией затрат. В сб.: Маршрутно-распределительные задачи. Екатеринбург: УГТУ. 1995. С. 32-44.

26. Коршунов Ю.М. Математические основы кибернетики. М.: "Энергия". 1980. 423с.

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

28. Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир. 1978. 432с.

29. Кротов В.Ф., Лагоша Б.А. и др. Основы теории оптимального управления. М.: Высшая школа, 1990. 420с.

30. Кукушкин Н.С., Морозов В.В. Теория неантогонистических игр. М.: Изд-во МГУ, 1977.

31. Куратовский К. Топология, Т.1,2. М.: Мир. 1969.

32. Мальцев А.П., Рольщиков B.E., Ченцов А.Г. К вопросу об оптимальной маршрутизации сигнала в условиях неаддитивной функции затрат. В сб. Марпгрутно-распределительные задачи. Екатерин-

бург: УГТУ. 1995. С.54-63.

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

34. Меламед И.И., Сергеев С.И., Сиг ал И.Х. Задача коммивояжера. Точные алгоритмы. // Автоматика и телемеханика. 1989. 10. С .3~ ¿9.

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

36. Мину М. Математическое программирование. Теория и алгоритмы. М.: Наука. 1990. 485с.

37. Михалевич B.C., Кукса А.И. Методы последовательной оптимизации. M.: IIаукаю 1983. 217с.

38. Модели и методы решения задач маршрутизации на транспортной сети. // Итоги науки и техники. Сер. Оптимизация управления транспортом. М.: ВИНИТИ. 1982. Т.З. С.55-112.

39. Моисеев H.H., Иванилов Ю.П., Столярова Е.М. Методы оптимизации. М.: Наука. 1978. 352с.

40. Молодцов Д.А. Регуляризация множества точек Парето. ЖВМ и МФ. 1978. N3. с.597-602.

41. Подиновский В.В., Ногин В .Д. Парето - оптимальные решения многокритериальных задач. М.: Наука. 1982. 255с.

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

43. Пшеничный Б.Н. Выпуклый анализ и экстремальные задачи. М.: Наука. 1980. 320с.

44. Сабирянова К.Г., Ченцов А.Г. Динамическое программирование в задачах оптимизации покрытия. // Автоматика и телемеханика. 1994. N3.

45. Сихарулидзе Г.Г. Об одном обобщении задачи коммивояжера. I.II.// Автоматика и телемеханика. 1971. N8. с.116-123., N10. с.142-147.

46. Современное состояние теории исследования операций / под ред. Моисеева H.H. М.: Наука. 1979.

47. Taxa X. Введение в исследование операций: в 2-х книгах. Кн.1.

Пер. с англ.- М.: Мир. 1985. 479с.

48. Тонкой А.В, Алгоритм решения задачи последовательного движения. В сб.: Маршрутно-распределительные задачи. Екатеринбург: УГТУ. 1995. С. 32-44.

49. Удземир А.П. Динамические целочисленные задачи оптимизации в экономике. М.: Наука. 1979. 464с.

50. Финкельштейн Ю.Ю. Приближенные методы и прикладные задачи дискретного программирования. М.: Наука. 1976.

51. Хедли Д. Нелинейное и динамическое программирование. М.: Мир. 1967.

52. Ченцов А.Г. Конечно-аддитивные меры и релаксации экстремальных задач. Екатеринбург: Наука. 1993. 232с.

53. Энгелькинг Р. Общая топология. М.: Мир. 1986.

54. Bellman R. Din ami с programmm treatment of the traveling salesman problem. J.Assoc. Comput. Mach. 1962. 9. N1. p.61-63.

55. Bellman R. The theory of dinamic programming. Bull. Arner. Math. Soc. v.60. 1954. p.503-516.

56. Geoffrion A.M. Solving bicriterion mathematical programs. // Operations Research. 1967. v.15. N1. p.39-54.

57. Held M., Karp R. The traveling salesman problem and minimum spaning trees. // Operations Research. 1970. N6.

58. Lin S, Karnighan B. An effectiv heuristic algorithms for the traveling salesman problem. // Operations Research. 1973. N2.

59. Mitten L.G. Composition Principles for Synthesis of Optimal Multistage Processes, Operations Researt. 12. 1964. p.610-619.

60. Morin T.L. Marsten K.E. Branch and bound strategies for dinamic programming. // Operations Research. 1976. V.24. N4.p.611-627.

61. Paradimitrion C.H., Steiglits K. Some examples of difficult traveling salesman problem. // Operations Research. 1978. N3.

62. Tetsuzo Tanino. On Supremum of a set in a Multi-dimensional Space. // Journal of Mathematical analisis and applications, V.130,N2,1988. P.386-397.

Работы автора по диссертации

1. Маркелова Е.Ю. К вопросу о декомпозиции многокритериальных задач / Челяб. гос. ун-т. -Челябинск, 1994.- 20с.- Рус. Ден. ВИНИТИ 8.12.94, N 2828-894.

2. Маркелова Е.Ю. Некоторые алгоритмы последовательной оптимизации в маршрутно - распределительной задаче. В сб.: Маршрутно-распределительные задачи. Екатеринбург: УГТУ. 1995. С. 32-44.

3. Маркелова Е.Ю. Об одной конструкции декомпозиции экстремальной задачи / Челяб. гос. ун-т. -Челябинск, 1994.- 20с.- Рус. Деп. ВИНИТИ 16.05.94, N 1216-В94.

4. Маркелова Е.Ю. Многокритериальная оптимизация в условиях обобщенной разложимости целевой вектор-функции /Вестник ПГТУ. Математика и прикладная математика.- Пермь: ПГТУ, -1994.-N1.

5. Markelova E.Yu. Decompositions method in cone optimal problem // Inter. Workshop Nonsmooth and Discontinuous Problems of Control and Optimization.- Chelyabinsk,-1998.-P. 164-165.

6. Маркелова Е.Ю., Рольщиков B.E., Ченцов А.Г. Задача маршрутизации конечного числа переходов системы с абстрактной функцией агрегирования затрат./ Челяб.гос.ун-т.- Челябинск,1998.-17с.-Библиогр.:10 назв.- Рус.-Деп. в ВИНИТИ N 1577-В98, 25.05.98.

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