автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Методы декомпозиции экстремума и некоторые их применения в дискретно-непрерывных задачах оптимизации

Р Г 6 од

/ В ИЮЛ 1993

нп< правах рукописи

Маркелова Елена Юрьевна

МЕТОДЫ ДЕКОМПОЗИЦИИ ЭКСТРЕМУМА И НЕКОТОРЫЕ ИХ ПРИМЕНЕНИЯ В ДИСКРЕТНО-НЕПРЕРЫВНЫХ ЗАДАЧАХ ОПТИМИЗАЦИИ

05.13.18 — теоретические основы математического моделирования, численные методы и комплексы программ

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

Челябинск 1998

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

Научный руководитель - член-корреспондент РАН А.Г. Чснцов

Официальные оппоненты - доктор физико-математических наук

Ведущая организация - Уральский государственный технический университет

Защита состоится на заседании диссертиционного совета Д.064.19.03 при Челябинском государственном университете по адресу: г. Челябинск, ул. Бр. Кашириных, 129, 1.07.98 в И00 в конференцзале.

С диссертацией можно ознакомиться в библиотеке Челябинского государственного университета.

Автореферат разослан

профессор Э.Г. Альбрехт, кандидат физико-математических наук доцент С.А. Рудаков

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

В. И. У хоботов

Актуальность темы. Работа посвящена исследованию возможности решения оптимизационных задач на основе декомпозиции .жстр«4-мума. Здесь под декомпозицией понимается процедура разделении соответствующей экстремальной операции в задаче со связанными переменными на две компоненты. При этом одна из компонент включзе теп в структуру оптимизируемой функции на основе специальных условий разложимости данной функции (критерия). Вопросы такот рода могут возникать в различных задачах оптимизации функций многих переменных, включая многокритериальные задачи и задачи оптимизации ио конусу. Необходимость таких исследований связана также с появлением большого количества прикладных оптимизационных задач, множество решений которых имеет сложную дискретно - непрерывную структуру. К таковым, в частности, относятся экстремальные задачи, связанные с маршрутизацией и распределением заданий между исполнителями в условиях, когда варианты перехода от одной элементарной задачи к другой составляют бесконечное множество. Сложность их мо--делирования обусловлена невозможностью разделения исходной задачи на дискретную и непрерывную подзадачи в силу связанности дискретных и непрерывных переменных.

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

Изначально принцип оптимальности был сформулирован Беллма-

ном для задач (включая маршрутные) с аддитивными функциями агрегирования, затем в работах Р.Беллмана, Р.СЛсмана, Р.Калабы, С.Дрсйфуса, Р.Карпа, М.Хелда для функций агрегирования, представляющих собой максимум критериев частных подзадач. Отмстим здесь же исследования А.Вальда в области последовательного анализа статистических задач. Методы, использующие динамическое программирование и попятные процедуры, широко применялись в теории оптимального управления и дифференциальных игр. (см., в частности, исследования Брайсона, Хо, Айзекса, Флеминга,Фридмана, Эллиота, Кал гона и целого ряда других специалистов в этой области.)

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

В работах Л.Миттена, Т.Морина, М.Мину, посвященных вопросам декомпозиции экстремума, был расширен класс задач, допускающих конструкцию повторной оптимизации. Однако указанные условия "разложимости" целевого функционала оказались слишком "сильными". Так, в работах А.Г.Ченцова, Л.Н.Коротаевой, А.Я.Сесекина, Э.М.Назарова были впервые получены аналоги функциональных уравнений Беллмана для некоторых задач дискретно - непрерывного характера, целевые функционалы в которых не обладают указанным свойством разложимости.

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

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

мирования, общей топологии, тео|)ии сходимости по Мору-Смиту.

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

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

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

Публикации. Основные результаты диссертации опубликованы в 6 работах.

Структура и объем работы. Диссертация состоит из введения, двух глав, приложения и списка литературы. Общий объем 110 страниц машинописного текста. Библиографический список содержит 68 наименований.

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

Во введении описывается проблематика работы и излагается краткое содержание диссертации по главам.

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

из пенсии я произвольных множеств. И сслсхнустс.я возможность iiiiecoiiiu минимума но части переменных под знак функции агрегирования.

В §1 рассмотрен модельный пример дискретно - непрерывной марш рутной задачи. Построение функциопал1,пых уравнений Беллмана при водит к проблеме повторной оптимизации иод знаком функции агреги рования. Эту проблему для целевых функционалов, действующих и: R" в R и обладающих свойством разложимости решает теорема опти малыюсти Миттена Однако целевой функционал в модельном при мерс не является разложимым но Миттену, а множество, на Ko'ropov он определен не вкладывается в МЛ

Это приводит к вопросу о возможности декомпозиции экстремум; в случае скалярного критерия на подмножестве прямого произведенш множеств произвольной природы. В §2 доказаны теоремы,в которые определены условия внесения минимума (инфимума) по части связан ных переменных под знак функции агрегирования.

Пусть А - произвольное множество и / : А —► R. Обозначим че рез MIN{f) множество всех элементов из А, на которых / достигает своего минимального значения, то есть

MIN{f) = {a G Л\ V6 G A f{b) > /(а)}.

Пусть U, V - произвольные множества, W С U х V, оператор Ф опре делен следующий образом: Ф : W —у R,

V* = («,») G W : Ф(*) = ф,фф)), (Г

где <р : U х R —» R, ф : W —► R, и V'[u] - сечение оператора ф.

Следующая теорема определяет условия, при которых минимум пс части переменных можно внести под знак функции агрегирования (р.

Теорема 2.1 Если <р - монотонно возрастает по второму аргумент} и MIN{Ф) Ф 0, то z° G MIN(Ф) тогда и только тогда, когда

Ф(*°) = v(u0,tfy>](u0)) = min v=(u, jriin^ т/>[и](и)),

где u° = pri(z°), v° = pr2(Z°), S û {и G wj™ | MIN(rlU) ф 0}

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

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

(1п( (Ф(г)) > -сю) & (Уи е : £ Ы {фф)) > -с»),

При этом определение функции <р в точках является корректным.

Тогда следующая теорема определяет условия декомпозиции экстремума:

Теорема 2.2. Пусть

1) функция (р - монотонно возрастает по второму аргументу,

2) для любого ы £ IVфункция <р(и, •) - полунепрерывна сверху в точках ¿ц = ¡пГ{*/>[и](и), и е И^]}, тогда

¡лГ ФМ = Ы <р(и, ¡пГ Л»1(«'))-

Доказана существенность условий теорем 2.1 и 2.2. Особый интерес для практики представляет случай конечного V. На основе полученных результатов построен алгоритм на функциональном уровне поиска оптимального и е - оптимального решения исходной задачи минимизации функционала Ф на множестве V/ для случая конечного II.

В §3 исследуется возможность применения процедуры "повторной" оптиыизациии при решении многокритериальных задач. Определены условия, при которых минимум (инфимум) по Парето по части переменных можно внести под знак функции агрегирования. Доказанные теоремы являются основой для построения функциональных уравнений Веллмана в случае многокритериальных задач оптимизации. Пусть частичный порядок в К"4 задан конусом Й:

К = {х 6 ИГ" | » е Т^Г: х{< 0}.

Множество минимальных по Парето точек на множестве У С К.т обозначаем Ртт(У). Пусть

Ф : -* ИГ1; ф : V/ 1Г; <р : [/ х Л" Ит,

= Ф(1У); Уиещ(и): хы = г/ы(Щи]);

я = {я 6 I Зи е 31° е Ртт(Хм) : <7 = ¥>(и,10)}.

Определим в Ита строгий частичный порядок -<:

Уо € 1Г УЬе И™ : (аЧЬ)

(У> € Т7т : а; < € 17т : о¿. < Ь;.)-

Пусть для оператора <р выполнено

Уи € У/[и) V<! € 0[ц,(^1и1), VI, б фыЩи]):

(<1^2) (*>(«, «О^Си, «а)). (2)

Это условие имеет смысл строгой монотонности <р по второму аргументу. Пусть, наконец, целевой оператор Ф представлен в виде (1).

Теорема 3.1 Пусть V? - строго монотонно возрастает по второму аргументу и множество Ртт(Р) Ф 0 и внешне устойчиво, то Ртт(Г) = Ртт»п(<Э).

В случае, когда минимум по Парето на У не достигается, определим инфимум по Парето:

Рт/(У) = Ртт(с/(Г)). Рассмотрим множество Кс - с расширение порядкового конуса К :

где "< >" - скалярное произведение. Будем говорить, что множество X С К™ ограничено по К, - конусу, если

Зе> О ЗубШт : К<(у)Г)Х = 0.

Введем обозначение:

Э = {Л € Кт | Зв € 1У[и) Зз° Е Пп/(ХЫ) : Л = ф, з0}}.

Будем считать, что для любого и 6 для любого 7 е -Х"[ц] множества Л"(7)ПХ|Ц] - ограничены. Теорема 3.2 Пусть

1) Р ограничено по некоторому «-конусу;

2) V» € 1,т Уи е ЫР : <р^(и, •) - полунепрерывны сверху в точках в Рт/(ХЫ).

3) ip строго монотонно возрастает по второму аргументу;

тогда PinJ(F) = Pinf(D).

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

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

Пусть (£, ~<е) , (Г, -<г) - предупорядоченные пространства и

Ф : W Т;' ч>: Г Т; ф : W -* Е, (3)

где Г й {(u,í) | и € Uf t 6 МЩ)}-

Тогда, если оператор агрегирования (р в разложении (1) является строго изотопным по второму аргументу и множество точек минимума (-<г —MIN){§) относительно порядка -<т на множестве Ф(1У) непусто и внешне устойчиво, то минимум по части переменных может быть внесен под знак функции агрегирования.

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

Если Х- произвольное множество, а -<п) предупорядоченное

топологическое пространство (ПТП), оснащенное топологией и> и пред-порядком -<п» то инфимум компактифицируемого оператора h : X —► ÍÍ, определяется следующим образом 3) :

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

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

(-«п -/ЛГГХЛ(Л')) й -ШЛ)(с/(Л(*))).

Обозначим через /а нижний интервал Уо 6 (Г2,о>,-<п):

/а = {х € П | х -Чп а}.

Через Т'(Л) будем далее обозначать множество всех подмножеств мно жества А.

Нас будут интересовать ПТП, обладающие свойством "устойчи вости порядка": будем говорить, что ПТП (П,ш, -<п) имеет свойствс устойчивости порядка, если многозначное отображение Ь : Л —> которое каждому значению х € П ставит в соответствие нижний ин тервал 1Х, является полунепрерывным сверху

Пусть далее (Т,т,-<т) - регулярное и согласованное ПТП, обладающее свойством "устойчивости порядка" и (Е,<т,-<е) - хауслорфово \ согласованное ПТП. Определим пространство 0 = и х Е и введем топологию в на 6:

Считаем операторы Ф, V» ^[и] определенными в (3), а внешни? оператор разложения <р : с/(Г) —» Т. Будем придерживаться следующие обозначений:

.р = Ф(И^); Уи 6 :

(2 = {(* е г| 3« е ж™ е : д = <р(«,'0)}.

Теорема 5.2 Пусть оператор Ф и операторы разложения €

являются компактифицируемыми, а оператор агрегирования •

непрерывный и строго изотопный по второму аргументу. Тогда

в й {С 6 ЯЭ) I V« е и : см 6 сг}.

и операцию замыкания на 0: если Л С 0, то

ЩА) = {(и,е) е О I V« е А(р : е € е/в(Лм)}.

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

Вторая глппа посвящена. вопросам мсуюлиропапия экстромхп.ни\ задач, связанных с маршрутизацией и распределением заданий mok. iv исполнителями. При построении моделей и их реализации испольтччч метод декомпозиции, теоретическое обоснование которого разраСччлно в главе I. Особый интерес представляют задачи с множеством решений сложной дискретно - непрерывной струк туры, не допускающие декомпозицию по дискретной и непрерывной частям.

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

1) множество, на котором определено решение исходной оптимизационной задачи, необходимо представить в виде подмножества прямой! произведения множеств (И' С (/х V), так чтобы решение исходной задачи можно было составить из решений аналогичных (частных) задач на сечениях множества IV;

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

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

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

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

В §7 метсщ декомпозиции главы I применяется для иосроеиия функциональных уравнений в маршрутной задаче дискретно - непрерывного характера: задаче размещения и функционирования временной системы радиооповещения. Временная сеть представляет собой систему и ретрансляторов. Центр - передатчик /'0 передает сигнал оповещения »1-му ретранслятору, который пересылает его ¿г-му и так далее, пока

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

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

Пусть заданы N многозначных операторов

А\ : Р Т{Р),...,Ац : Р —♦ ~Р{Р) .

Таким образом определена некоторая абстрактная динамическая система. Если р € Р - заданное состояние, а» 6 1, N - номер очередной "задачи", то А{(р) есть своеобразная область достижимости из состояния р. Процесс "управления" будет пониматься далее, как последовательная реализация переходов

Ро (Р1 € АДро)) (рг € А{,(р0) ----> {рц е А1ы(рн-0), (4)

где (|*1,...,|'лг) - суть некоторая (выбираемая исследователем) нумерация элементов 1,/У. Мы рассматриваем проблему выбора нумерации (маршрута) и "трассы" (4) в условиях, когда переходы (в (4)) оцениваются посредством критерия П : Р х Р —► [0,оо[, а общие затраты

получаются агрегированием на ослопе функции ф : [0,оо[х[0,оо[—* [0,оо[ .

Цель состоит в минимизации затрат на всем маршруте.

Ii §i) построена и исследована с помощью метода декомпозиции модель задачи маршрутизации сигнала с нелинейной функцией агрегирования затрат. Требуется передать сигнал из точки х0 в точку .г'1. Имеется п областей (компактов ) j £ 1,п, в каждой из которых можно разместить подвижный ретранслятор. 13 качестве альтернативы прямой передаче сигнала можно построить траекторию

Хо —► I/, —► ... —» Xjh —► х°

через систему к ретрансляторов, где к любое из 1, п.

Стоимость передачи из точки х в точку у может зависеть от расстояния между точками, географических особенностей местности, и гл. и задается функцией II [0,оо[. В случае передачи сигнала

из г в у через посредника z стоимость сигнала складывется из стоимости иредачи сигнала посреднику ll(x,z) и стоимости передачи сигнала V — V(z,y) от посредника в точку у (возможно через других посредников). Посредник z за свои услуги взымает плату в размере (^у) * V (коэффициент d определяется интересами и возможностями посредника). Таким образом, стоимость передачи сигнала из г в у составляет

П(*,*) + ß(V) х V, где ß(V) й (^L- + 1).

Наша задача выбрать количество к (к 6 1,п) ретрансляторов и точки х}\, i G 1 ,к, (если к ф 0) их расположения в соответствующих компактах Pj. так, чтобы стоимость передачи сигнала из г0 в х° была минимальной. Для этой задачи также получены рекуррентные соотношения Беллмана.

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

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

а) окружностью радиуса it с указанным центром О ;

б) кольцом (Л,г) с центром О ;

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

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

Публикации основных результатов

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 назв.- Рус.-Деп. в ВИНИТИ ЛП5Н-&9У, ¿5".

б{'99~ /

УРАЛЬСКОЕ ОТДЕЛЕНИЕ

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

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

УДК 519.6

Маркелова Елена Юрьевна

МЕТОДЫ ДЕКОМПОЗИЦИИ ЭКСТРЕМУМА И НЕКОТОРЫЕ ИХ ПРИМЕНЕНИЯ В ДИСКРЕТНО-НЕПРЕРЫВНЫХ ЗАДАЧАХ ОПТИМИЗАЦИИ

05.13.18 — теоретические основы математического моделирования, численные методы и комплексы программ

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель член-корреспондент РАН А.Г.Ченцов

Екатеринбург 1998

СОДЕРЖАНИЕ

Введение. з

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

экстремума.

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

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

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

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

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

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

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

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

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

Приложение

/Об

Введение

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

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

и о и ^

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

Метод декомпозиции экстремума является развитием пошагового метода решения задач применительно к задачам оптимизации. Идея пошагового решения задач анализа, оптимизации, теории дифференциальных уравнений использовалась давно и представлена в работах таких известных математиков как Ферма, Эйлер, Маклорен. Но лишь в 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ВМ РС/ АТ

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

ГЛАВА 1. ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ МЕТОДА ДЕКОМПОЗИЦИИ ЭКСТРЕМУМА

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

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

Рассмотрим задачу размещения и функционирования временной системы радиооповещения. Временная сеть представляет собой систему п ретрансляторов. Центр - передатчик Ро передает сигнал оповещения ¿1-му ретранслятору, который пересылает его ¿2-му и так далее, пока сигнал не попадет в последний пункт Р{п. Каждый ретранслятор сети может быть размещен в некоторой допустимой зоне, причем мощность

V

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

Будем называть маршрутом сигнала очередность (¿1, ¿2,..., ¿п), в которой сигнал посещает зоны (зоны пронумерованы). Трассой назовем упрядоченный набор из п точек х = (ж^, а?г2, ...,Хгп), каждая точка есть точка дислокации ретранслятора в зоне, порядок следования точек (¿1? ¿2) •••■> ¿п) соответствует маршруту. Пусть Л - множество всевозможных маршрутов (по сути это множество перестановок элементов на множестве {1,2,...,п}, X - множество всевозможных трасс, Х(А) -множество трасс, соответствующих маршруту Л £ Л. Целевая функция М(х, Л) - максимальная мощность сигнала на переходах от одного ретранслятора к другому на выбранном маршруте Л и трассе х. Наша задача состоит в нахождении такого маршрута и трассы (эту пару будем называть траекторией), при которых максимальная мощность

сигнала на переходах от ретранслятора к ретранслятору будет минимальной. Если W С X х А, то надо найти

min М(х, А).

(®,А )ew

Обратим внимание на сложность поставленной задачи. Во-первых, в ней сочетается два вида процедур оптимизации, а именно: 1-ый вид - минимизация критерия по всевозможным маршрутам А Е А, - предст�