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

МОСКОВСКИЙ ОРДЕНА ЛЕНИНА II ОРДЕНА ТРУДОВОГО КРАСНОГО ЗНАМЕНИ ПЕДАГОГИЧЕСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени В. И. ЛЕНИНА

Специализированным Совет К 053.01.10

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

АЛУТИНА Елена Федоровна

МЕТОДЫ РЕШЕНИЯ ДИНАМИЧЕСКИХ МНОГОКРИТЕРИАЛЬНЫХ ЗАДАЧ

Специальность 05.13.17 — теоретические основы информатики

АВТОРЕФЕРАТ

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

Москва 1993

Работа выполнена в Московском педагогическом государственном университете им. В. И. Ленина.

доктор физико-математических наук, профессор ГОРЕЛИК В. А.

Официальные оппоненты:

доктор фнзнко-математических наук, нрофессор КОНОНЕНКО А. Ф.,

кандидат физико-математических наук, доцент ШАДРИН Г. А.

Ведущая организация: Московский технический университет связи н информации.

Защита состоится 1993 г. в ./&.'.. часов

на заседании специализированного совета К 053.01.16 по защите диссертаций на соискание ученой степени кандидата фп-зико-математическнх наук и Московском ордена Ленина и ордена Трудового Красного Знамени педагогическом государственном университете им. В. II. Ленина по адресу: 107140, Москва, Краснопрудная ул., д. 14, математический факультет МИГУ им. В. И. Ленина, ауд. 301.

С диссертацией можно ознакомиться в фундаментальной библиотеке МПГУ им. В. И. Ленина но адресу: 119882, Москва, Малая Пироговская ул., д. 1.

Автореферат разослан .Л'М^.О:!??!) 1993 г.

Ученый 1 )вета

Научный руководитель:

Э. И. КУЗНЕЦОВ

- ■ . • 1, ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

* Актуальность теш. В настоящее время в новых экономи-^¿■р ч^рких условиях вопросы комплексного решения крупных общегосударственных, межотраслевых и территориальных проблем сохраняют свою актуальность, но требуют иных подходов к их решению. Соответсвенно научные интересы в последнее время все более перемещаются от вопросов управления отдельными физическими и техническими объектами к вопросам организации взаимодействия систем различной природы и управления коллективами людей в процессе их целенаправленной деятельности, к анализу сложных систем.

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

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

На первых порах своего развития в теории многокритериальной оптимизации изучались статические задачи. Однако запросы практики вскоре потребовали изучения и динамических систем управления.

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

- г -

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

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

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

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

Целью работы является получение условий оптимальности для одного из основных понятий векторной оптимизации - парето-оп-тимальности и превде всего таких, которые обобщают на многоК-Г»и-н'риальный случай наиболее конструктивные необходимые и /.оотаточныч условия математической теории оптимальных про-.•.ч."-о}!, а так же развитие методов построения множества паре-

то-оптимальных управлений.

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

!,!ето,цологическую основу работы составляют современные методы исследования теории оптимального управления, математического анализа, выпуклого анализа, теории многокритериальной оптимизации,

Диссертация выполнена в соответствии с планом научно-исследовательской работы кафедры (номер государственной регистрации N 01.92.0005521).

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

Апробация работы. Результаты исследования докладывались на семинаре под руководством профессора, действительного члена РАО, доктора физико-математических наук Матросова В. Л в МПГУ

' \

им. Е И. Ленина, на аспирантском объединении, на научно-методическом семинаре кафедры информатики и вычислительной техники МПГУ им. В. И. Ленина, на 3-й Межвузовской конференции молодых ученых в г.Липецке (декабрь 1989 г.), на III конгрессе "Инфор-матизационные коммуникации, сети, системы и технологии" на секции "Оптимизация сложных динамических систем в экономике и

технике", проходившем в Москве в ноябре 1992 года

Структура и объем диссертации. Работа состоит из введения, трех глав, заключения, списка использованной литературы." Она содержит 129 страниц, из них 121 страницаоеновного текста, 8 страниц - список использованной литературы из 75 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ.

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

Пусть управляемый динамический процесс описывается многошаговым векторным уравнением

З-ь-'-^^.а,"^) , (1)

где фазовые переменные Ще и управления Ute. являются конечномерными векторами, • начальное состояние Л« фиксировано, на управления наложены ограничения е ££ . н

Введем управление U. = (ил г ... t и*.) , U. е X/^ ; это управление в силу (1) однозначно определяет траекторию

Качество функционирования системы описывается критериями % (U) = J; fr, (^.^lu) 4 ^ foj.

Задача оптимального управления состоит в том, чтобы, зная начально? состояние <Е© , выбрать такое допустимое управление ■ С -~ (и, , . U^) для объекта (1), которое придает функци-■H.iiHM (С) наибольшие значения.

Понятие оптимальности в теории многокритериальной оптимизации неоднозначно. Известно много различных понятий оптимальности, наиболее распространенным является - парето-оптималь-ность. Для уточнения постановки задачи вводится

ОПРЕДЕЛЕНИЕ. Управление ¿¿*е и называется паре-то-оптимальным, если не существует и. с Ц~ такого, что

3 (и) ^ % (и*), ,

и, по крайней мере для одного £ , неравенство строгое, где ^ (¿¿у определено (2) в силу уравнения (1).

Замечание: Аналогично определяется парето-оптимальность пары (ос.*) и*) , где ос* - траектория, определяемая управлением и*, (эа^ икСЬ1} Н^Т^п].

В первой главе диссертащш (§§1.1-1.4) для дискретной динамической многокритериальной задачи (1)-(2) вводится три вида свертки критериев и рассматривается связь оптимума Парето с этими свертками критериев. По теоремам Карлина и Гермейера нахождение парето-оптймальных решений задачи (1)-(2) при некоторых условиях сводится к решению задач максимизации

3 *) = Ы,,^) + Ыд) (3)

ЭО*,1*-)- (4)

Б § 1,1 устанавливаются необходимые и достаточные условия парето-оптимальности управления.

ТЕОРЕМА 1. Пусть множества выпуклы,- функции

(х> линейны по я и ^ , ~ 1, Уи , функции

^ (Ъз) и,) вогнуты по совокупности переменных ( ¿=1, т, . ). Для того чтобы решение

£сА) было парето-оптимальным, необходимо, чтобы су-

1__/г

щзствовапи числа о(± О , --1, , ~ ^ такие,

что С32-*, М*) доставляет на ^ максимум критерию (3) при ограничениях (1).

Замечание. Достаточность ' имеет место при строгой вогнутости.

ТЕОРЕМА 1 . Пусть множества выпуклы, функции

• • ^ , вогнуты по совокупности пе-

ременных и не убывают по &1. ( , I - т, ).

Для того чтобы решение (, ) сыло парето-оптимальным,

необходимо, чтобы существовали числа оС,' ^ О , т \ ¿ЦоЦ - 4- , такие, что пара (ее.*, и ) доставляет на г»/ ^

максимум критерию (3) при ограничениях (1)." 1 •

ТЕОРЕМА 2. пусть , , ¡■"¿,'п .

Для того чтобы решение {э? * Я^ б ылопарето-оптимально, небходимо, чтобы существовали числа абг О , ¿, а> , о4 - такие, что пара доставляет на % макси-

¿■ш!

мум критерию (4) при ограничениях (1).

Веодится новое понятие векторной оптимальности (интегральной парето-оптимальности).

ОПРЕДЕЛЕНИЕ 2. Пара называется локально-

парето-оптимальной (в момент ). если не существует пары (зг, и) такой, что .

причем хотя бы для одного I неравенство строгое.

ТЕОРЕМА 3. Если пара (ос*, и*) -локально парето-оптималь- • на (в момент к. ) и функции то существуют числа

сА,. >0 , * ■ такие, что

(зс*^ ) , V ,1л) & %

ОПРЕДЕЛЕНИЕ 3. Пара ^Ьс называется интег-

рально парето-оптимальной, если она доставляет на макси-

мум критерию

я**,«-)*

— ¿1/ тЛ и- аСи.

~~ Шоп-

при ограничениях (1), где определяются условиями (5).

Следует отметить, что введенное понятие справедливо только для многошаговых процессов.

В § 1.2 показывается, что к полученным в § 1.1 задачам применим метод динамического программирования, который сострит в замене динамической задачи задачей построения функции Беллмана. Для свертки Карлина

; ТЕОРЕМА 4. Пусть множество выпукло, - компак-

ты,'функции У*. «) , /эо, и.) непрерывны, функции ^¡к. С"*,строго вогнуты по совокупности переменных

, ( т. , М ). Тогда существуют числа

—————

сС, > О , 1-4-, л*- . гЕ! оС' - такие, что для

I (-V

парето-оптимальности решения необходимо и

достаточно выполнения соотношений

с тсксхх I <£/

где - функция Беллмана, определяемая стандартнш об-

разом. При этом максимальное значение критерия (3) при ограни-

чениях (1) ,• равно и)0(сс,) . Для свертки (6)

ТЕОРЕМА 5. Пусть , 1 = ж. , -е = ^ ^ ,'

■¡¿(эс, и.) 'к) . Тогда существуют числа ^¿^ > О , ¿=4,»,,

И

22с¿¡. = I . такие, что для интегральной парето-оптималь-

Нш! , .

ности решения необходимо выполнения соотношений

^ ££' ^ + ^ ^ , иг)) =

- ^ ^ + , <ч97,

где у , ,

При этом максимальное значение критерия (6), при ограничениях (1) равно

а)о(жо) ■

Для свертки Гермейера принцип оптимальности Беллмаьа в .исходном■фазовом пространстве не выполняется, но выполняется в расширенном фазовом пространстве.

ТЕОРЕМА 6. Пусть , ^ = ,

У Га* ^ ) е • Тогда существуют числа .. сС,- > О ¿=4 т- , об,- - такие, что для парето-опти-

мальности решения (за*, и*) е & необходимо и достаточно, чтобы для каддого 4., п. выполнялось соотношение

Я (ь , О, ¿с ♦ £ , и:)) =

^¡"."..смюе значение критерия (4), при ограничениях (1)

равно

Здесь дополнительные фазовые координаты

где

(*,«>)= fäbC»,").--'*^^"-))-

В §1.3 рассматриваются вычислительные аспекты метода динамического программирования для многокритериальных ■ . задач, приводятся результаты тестовых расчетов.

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

В § 2.1 для свертки Карлина (3)

ТЕОРЕМА 7.; Пусть (х,а-) линейны по ^ и U , все и.) ' вогнутые функции по совокупности переменных

а и V ( i, ы, , d, п* ± ). множества вы-

пуклы & = 4, . Для того чтобы управление и*&tf было парето-оптимальным, небходимо, чтобы существовали числа с/,О , ¿~ d, , ÜElcü и вектора такие,

м ist

что функция Гамильтона на управлении и* достигает максимума

по cjerv :

где А/, Я) - & о6 К « ^, %),

И*. Ы.,, yi! ) определяются соотношениями сслряжннш пер?ценные - уравнениями

При 32^= СЕц.* , ¿¿fc-^4. с граничными условиями. ф1 _

траектория Л:* определяется уравнением (1), при с/-С/"* .

, СЛЕДСТВИЕ. Пусть выполнены условия теоремы, тогда пара ( л^*, ) является парето-оптимальной для векторной функции Гамильтона t , > ■ • , Нн

В §2.2 для свертки Гермейера (4) выведены условия стационарности с использованием аппарата штрафных функций.

ТЕОРЕМА 8. Пусть функции j^fe+U.) . непрерывно дифференцируемы по своим' переменным, множества Uk. выпуклы для всех м - 1, ии . Пусть оптимальное управление в задаче

F(ci*) = FC"-)- ^

1 ' ¿/в v

где качество управления оценивается функционалом

^ d * t int,

%(и) задаются формулой ~

прй ограничениях (1), Ос* -соответствующая траектория с начальным состоянием ЗС^ . Тогда существуют числа А- £ О ,

и '

= l ( /5,- = О при ), а также вектора

"V......^ -гле

V = Ты, л. . ГЭ '

такие, что на управлении функции

удовлетворяют не6х'СЛкмым условиям по £/еС Здесь

В § 2.3 для задачи (1), (6) получены аналогичные условия стационарности, что и для свертки Карлина, только в этом слу-

« 0*1 I «

чае существуют числа р! ^ О . ¿Гл'=.а( . 'Л' ® 0 при * (ь) , определенным

А'ас й ^

Формулируется принцип максимума при дополнительных условиях выпуклости множеств достижимости .

5„(а,и).

/V ^

ТЕОРЕМА "9. 11усть множества 'выпуклы при

любых £ = {х?, л] * ' = 0,п-1- • Тогда на оптимальном управлении Гамильтона имеет максимальное значение, т. е.

и*.£

где

сопряженные переменные находятся из уравнений

I и -У ^ 4. [¿¿ъОь-о1^) 7 у;

Л- с*-

при ОС^ , = ^ и условии

у* = Д/ /Сл

«1+1 За^,

В §2. 4 для свертки Гермейера формулируется модифицированный принцип_ максимума, основанный на использовании модифицированной функции Гамильтона

-I-.Цосс-^«^)/!*; ¿¿о, * =

п. .

При О—О модифицированная функция--Гамильтона равна .обычной функции Гамильтона.

Модифицированный дискретный принцип максимума получен в предположении непрерывной дифференцируемости функций С^.,, и*.) . ^ ¿4*) И дважды дифференциру-

чемости о^. Ыъ) на-компактах и выполнении в

точке оптимального управления ¿4* условия

для любого либо ус-

ловия

? т э<0

для любого € ^ такого, что

Здесь к- (и*. ) - замыкание конуса допустимых направлений для 14 в точке

и:.

В третьей главе динамическая многокритериальная задача (1)-(2) решается методом подходящих ограничений-равенств, ког--да все критерии, кроме одного, обращаются в ограничения-равенства

.....' (8)

«х,., и) _-= >

где 01,..., - действительные параметры, подбираемые специальным образом. ••■

В § 3.1 динамическая многокритериальная задача с дискретным временем (1)-(2) сводится к решейию параметрической оптимизационной задачи нахождения- максимума критерия

н.

) - «2 и+(9)

«-1

при ограничениях (8),. где управления удовлетворяют ограничении — -

ям и <£~Ц~= П и к . а траектории определяются в силу (1). й,» .

Здесь же формулируются условия парето-оптимальности решения параметрической оптимизационной задачи

ТЕОРЕМА 10. Дан d°€ JP> , решение параметрической оптимизационной задачи (осР1 и") = (ос (а°), tí Са°)) является парето-оптимальным тогда и только тогда, когда -

1) °Р(л) $ cpía") для Yae $ таких, что

2) °Р(й.) < (о?) ядя Ybe-Ъ таких, что л

ср(а)= ьир { ; {ае>Ъ = \(Х^/ср(а)<<Г(а)}

' В §§ 3.2, 3.3 задача максимизации критерия (9) при ограничениях (1), (8) решается методом динамического программирования и методом принципа максимума.

Функции Беллмана для задачи (1), (8)-(9) определяется рекуррентным соотношением

cí^.j /пах. [¿¡»bbtb^jU*)*

¿A« £ c/t

где . - .

се*.„ и^) у- ¿£í)>

ТЕОРЕМА 11. . Пусть ¿/^ - оптимальное управление в задаче'(1), (8),(9) и пусть множества достижимости за один шаг «»ífcfc,"), и&хг

выпуклы при любых -Зс и /1+1 .

Тогда на оптимальном управлении справедливы равенства

/и/•/ Н

где оптимальные значения уЗ* • и /1(- удовлетворяют уравнениям

_ э&.^цО Гэ^^^/Х А. ••

с граничным условием

|л эзньысэь.) v1 л э ^

и равенствам (8). '

В § 3.4 описан метод нахождения парето-оптимальных. реше-' ний, основанный на решении вспомогательных параметрических задач вводится понятие подходящего вектора СС ■

В заоючении сформулированы основные результаты работы ' и выводы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ.

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

2) Для каждой свертки критериев установлен принцип оптимальности и выписаны уравнения Бел.таана,■ причем для свертки

Гермейера показано; что принцип оптимальности не выполняется в исходном пространстве, но выполняется в расширенном пространстве состояний. •

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

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

.Для возникающих параметрических задач развиты методы решения, »

основанные на методе динамического прграммирования и принципа максимума.

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

Основное содержание диссертации отражена в работах:

1.- Алутина Е. Ф. Динамические многокртериальные задачи. //Тезисы докладов на 3 Межвузовской конференции молодых ученых. - Липецк, 1989. - с. 102.

2. Горелик Е А., Алутина Е. Ф. Дискретные "динамические многокритериальные задачи. / Моделирование и оптимизация сложных динамических процессов. - М.: -ВЦ АН СССР, 1989. - с. 44-56.

3. Горелик В. А., Алутина Е. Ф. Дискретный принцип максимума в динамических многокритериальных задачах. /Декомпозиция и

оптимизация в сложных системах. - М : ЕЦ АН СССР, 1991.

с. 3-13.