книги / Математические методы в системах поддержки принятия решений

Теперь для выпуклой функции <р(х) как функции, определенной на /Р, запишем необходимое условие ее минимума

Это условие при выпуклой <р(х) является и достаточным для оптималь­ ности х°; здесь допустимое множество X в точке х° аппроксимировано

обобщенным градиентным (субградиентным) множеством. Эквивалентность выражений (3) и (4) устанавливается достаточно

просто:

ЭДх°) и -Э 6(х°[Л) = Э8*(х°|*)

есть множества, но тогда для принадлежности нуля сумме этих мно­ жеств достаточно принадлежности нуля их пересечению.

Если функция Дх) дифференцируема в точке х° € X, то

ЭДх°) =Л(х°),

и необходимое условие оптимальности решения х° записывается в виде Л(х°) = Э5'(х°1А).

Выражение (3) можно записать в более развернутой форме, для этого учитывается, что

5(х°да = 8(х°1Аг1) + 8(х°|Л^> + 8(х°[Аг3) + ... + 8(х°1А;),

где Хь Хъ ..., Х„ — выпуклые множества, образованные соответственно

а также то, что Э8(х|А^), / =l,/w, — опорные функции множеств Хь Хъ ...

..., Хт в точке х однозначно определяются {Эф,(х)} — опорными функ­

циями соответствующих ограничивающих условий

Таким образом, когда Эф(х) не пусто, т.е. ф,(х) < 0, / = 1, 2,..., т, условие

(3) преобразуется к виду

Эф(х0) = Э/(х°)+^Ч,.Эф(.(х0) VX>0, таких, что Х ф (х°) = 0, / = 1 /и;

/»I

при этом необходимое условие оптимальности решения х°, 0 е Эф(х°) имеет место только в том случае, когда коэффициенты Х„ i= l,m и х®

удовлетворяют известной теореме Куна—Таккера [22;23].

Теорема. Для того чтобы вектор был вектором Куна— Таккера, о т ­ решением рассматриваемой условной экстремальной задачи, необходимо и

достаточно, чтобы пара (х°, А0) была седловой точкой функции Лагранжа

ш

L(X,x) = f ( x ) + ' £ x lф,(х). Это условие выполняется тогда и только то-

/=1

гда, когда вектор х° и компоненты вектора X удовлетворяют следующим условиям:

1) Х,ф,<х°) - 0, X,>0, фХх») < 0 ,/= 1, 2 , к;

2) Ф/С*°) = 0, / = к + 1, к + 2,..., т;

3) 0 е Э/(х°) + £ X , Э ф (х °) = Эф(х°).

/«1

Для выпуклых условных задач выбора решений имеется и двой­ ственно-сопряженная форма [23;24;20].

Задача. Найти оптимальное решение (х^х® )> Доставляющее максимальное значение

деленная: условие вогнутости выполнено.

2.Составим функцию Лагранжа

А(х,, х2, X) = -(х , - х 2)2 + Х|2х, - х2 - 6|, X > 0.

3.Выпишем необходимое условие экстремума для функции Лагранжа

0 € ЭА(х,, х2, X) « Э/Ц, х2) + ХЭф(х1, х2),

где ЭДх!, х2) = { -2(х, - х 2), 2(х, - х2)},

52

должны быть вычислены в точке (х®,х®), подозреваемой на экстремум; если щ > 0 , то

а2 < 0.

4.Согласно необходимому условию рассмотрим следующие системы:

4.1) -2(х® - х ? ) + 2Л = 0 ,2(х® - x j ) - X = 0, если 2х® - х £ - 6 > 0;

4.2) -2(х® -х® )-2Х = 0, 2(х® - х £ )+ Х = 0, если 2х® - x j - 6 < 0 ;

4.3) -2(х® -х® ) + 2Ха, =0, 2(х® -х® ) - Ха2 = 0, если 2х® -х® - 6 = 0, 2 > Oj > -2 ,

-1 < а , < 1.

Из 4.3 следует, что Oj = —2а , и, очевидйо, для систем 4.1 и 4.2 решений не существу­ ет, так как строки матриц Л41 = ^ ” 2 ) ’ / *4-2 = (2 ~2 ) лине^но зависимы; система 4.3

имеет единственное решение х® =х® =6 при а® =а® = 0 как значений компонент субгра­

диента, взятого из субдифференциала (at, <Х2)=[{—1, 1},{2, —2}].

Таким образом, в рассмотренной негладкой экстремальной задаче оптимальное ре­ шение представляется точкой (х® = х® = 6) и т а х /(х ° ,х 2) - 0 (в этой точке по терминоло­

гии (128] имеет место «слипание» функций ,Дх1(х2) и <p(xi,x2)).

Установим необходимые и достаточные условия оптимальности ре­ шения х® для условно-экстремального механизма (2), реализуемого в ва­

риационных задачах. При этом будем считать, что искомое решение У°(х), a< x< tb, должно удовлетворять ограничивающим условиям, за­

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

бор решения у°(х) посредством минимизации функционала

Ь

F(y(x)) = jf(x ,y (x ),y '(x ))d x

при ограничении в виде уравнения связи <р(х, у(х)) и граничных услови­

ях у(а)9у(Ь), то необходимое условие оптимальности решения принима­

ет вид [16]

ф(*, А х)) = 0, у(а), у(Ь).

Аналогичным образом при фиксированных у (а), у(Ь) записываются

необходимые условия оптимальности решения у°(дс) и при ограничениях

53

в виде дифференциальных связей <р(х, у(х), /(х )) = 0 или в виде диффе­

ренцируемого функционала

Ь

G(y(x)) = Jg(x,y(x),y'(x))dx = l,

а

где / — заданная константа.

Для задачи выбора решения с подвижными левой и правой граница­ ми, описываемыми функциями у(х, у(х)) = 0U , и 0(х, у(х)) = ОU , необ­

ходимое условие оптимальности решения у°(х) записывается в виде дифференциального уравнения Эйлера

с граничными условиями, называемыми условиями трансверсальности,

/ ( w o - 0 ', - ' i o / ; v „ =о,

f( x ,y ,y ') - ( y '- Q ') f; ,lxmi = 0,

согласно которым определяются постоянные интегрирования решения из уравнения Эйлера.

Проиллюстрируем применение условий трансверсальности в кон­ кретной простой за д а ч е: найти минимальное расстояние между двумя непересекающимися выпуклыми множествами с гладкими границами

У = Л(х) и у = / 2(х).

Очевидно, соответствующее расстояние есть

minJ-y/l + j/ 2dx, если у0 =/,(хо) и у { = / 2(х,).

*0

Искомое решение следует из уравнения Эйлера

/ уУ (у Г у " = 0= *у " = 0, / , у ( / ) * 0 =>;у'' = 0 =>;у = С *+А

т.е. минимальное расстояние есть длина отрезка прямой , соединяюще­ го заданные множества. Неизвестные константы С и /) определяются из условий трансверсальности, которые в рассматриваемой задаче записы­ ваются в виде

y 'J u = ~ 1 и y ' f 2'x = - 1,

где у ', / ,' , f 2'x — угловые коэффициенты отрезка прямой , соединяю­

щего множества и касательных к множествам в точках их соединения.

54

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

к

J K(x,y)u(y)dy = /(* ), с < x £ d , a < y< b ,

в котором К (х,у) — заданная функция, а функция Дх) установлена не­

точно — по результатам эксперимента с погрешностью. Поэтому задача вычисления функции и(х) некорректна в смысле Тихонова. Для ее ре­

шения перейдем к регуляризованной задаче

цией pk(y) = 1 .

Регуляризованная задача корректна, и для отыскания ее решения

необходимо приравнять нулю первую вариацию 5А(и(у)) по и(у), т.е.

воспользоваться выражением

а Г»

8Л(м(у)) = 2 |- jK (x ,y )u (v )d v -f(x ) | K(x,y)&u(ydy) ■dx+

1к

+2a X j « (*, (y)8« w (y)rfy=0.

М а

Проинтегрировав в этом выражении интегралы под знаком суммы по частям, получим интегродифференциальное уравнение Эйлера [117]

Это уравнение относится к классу интегродифференциальных, не со­ держащих производных под знаком интеграла. Его решение отыскива­ ется при заданных краевых условиях и(а), и(Ь), и'(а), и\Ь), например

при помощи преобразования Фурье-Лапласа [118].

55

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

в динамических задачах

Условно-экстремальный механизм в динамических задачах вводится для выбора лучшего решения ы0(0 € U по функционалу качества инте­

грального вида

т

/(«(О) = j f a(t,x(t),u(t))dt+4Kx(T),T),

'о

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

МО = f(t,x (0 A 0 ), t0< t< T , и{0 € U, МО е R"

и недифференциальных

x(t0) € G(t0), х(7) е Д 7 ),

где Г0, Т могут быть фиксированными или неизвестными моментами

времени и подлежат определению; и(0 — кусочно-непрерывная функция на [/„, Т\, или это элементы

замкнутого множества U, или непрерывные функции на [/„, 7], — эле­

менты открытого множества допустимых управлений

U -C ([tо, 71, Я"), т < п ;

МО — фазовая переменная.

Механизмы выбора лучшего решения

А. При открытом м нож естве управлений и°(/) = aig min/(«(/)), tied

и условиях

56

Необходимые условия оптимальности решения согласно этому меха­ низму представляются (пусть t0= const) соотношениями [19; 25; 26]

dH (t,x(t),u(t)M 0 ) = 0, если и е int U, ди

— функция Гамильтона, в которую вектор управления u(t) не входит ли­

нейным членом, т.е. предполагается, что - — зависит от и((), иначе ва­

ди риационная задача принятия решений не может быть решена при

открытом множестве управлений, когда вектор управления н(Г) входит в функцию Щ , x(t), u(t), \|f(/)) линейно;

ц — векторы множителей Лагранжа;

\|f(t) — вектор функций множителей Лагранжа.

Необходимые условия непосредственно выписываются из выражения для первой вариации функционала Лагранжа

т

K{x(t),u(t),y(t),t) = v)/# I(u(t))+ 1(\|/г(t),f(t, x(t) ,u(t))) - x(t))dt + *0

+oi T,g(x,t0) ) + a r M x ,T »

при приравнивании ее нулю для произвольных вариаций &с, 5\|Г, 5и, 5ц,

5Х, Sg и 5Л; у 0 - —1.

Если в рассматриваемой задаче множество допустимых управлений замкнуто и включает только непрерывные функции u(t) и оптимальное

57

управление может быть на границе U, то условие — = 0 должно быть

Эи

заменено на условие вида (gгad((Я ,и - и 0)> 0 , где и — и# — направление, не выводящее из U С([/0) 7], очевидно при этом, что когда и0 —

внутренняя точка U, условие - — =0 сохраняется.

Эи Выражения, указанные звездочкой, составляют условия трансвер­

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

трансверсальности имеют вид

* ('.)= *о, х (Т )= х т, Н(Т, х(Т), и(7), у(7)) + ЭФ^ 2 ,Г) = °-

М Т )

В названных и всех других случаях условия трансверсальности пред­ ставляют дополнительные условия для интегрирования системы диффе­ ренциальных уравнений относительно основной x(t) и сопряженной \у(0 переменных, а также для определения оптимального времени Т.

Они имеют достаточно простую геометрическую интерпретацию: векто­ ры у(/0) и \у(7) ортогональны к плоскостям многообразий соответствен­ но на моменты времени t0 и Т и направлены во внутрь этих многообра­

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

Б. П р и з а м к н у т о м м н о ж е с т в е U и содержащем кусочно­ непрерывные функции u(t), ta< t< ,T, вид механизма выбора лучшего

решения формально не изменяется по сравнению с приведенной записью в а), но необходимые условия оптимальности^решения

где Н — функция Понтрягина—Гамильтона.

В. Приведем здесь упрощенные варианты принципа максимума. Пусть

N

I(u(t)) = ^ a lul + 0 О где Ф0 — const.

/=1

Требуется найти и0, доставляющее m ax/(«(/)) при ограничениях \и\ < С/. В этом варианте выражение для функции Понтрягина—Гамиль­

тона представляется первым слагаемым заданной критериальной функ­ ции и оптимальное управление и® = с,.signa,.

58

Если же требуется найти u°(t), при котором

т

max/(«(/)) = max f/ , (t,u(t))dt,

u(t) J

где /(«(/)) принадлежит пространству непрерывных функций на [/„, Л . а f 0(t, u(t)) — непрерывно дифференцируемая функция и -во < u(f) < °°, то

необходимое условие принципа максимума для отыскания искомого

Эи Отметим, что выписанные в А и Б необходимые условия для выпук­

лых задач выбора наилучших решений являются и достаточными. Однако при этом в общем случае решения, полученные согласно изло­ женным необходимым условиям могут быть оптимальными или неоп­ тимальными в зависимости от свойств исходных функций и данных, со­ ставляющих механизм выбора решений. Имеют место также задачи, для которых такие решения совсем не могут быть получены, это задачи с так называемыми (см.[28;29]> особыми (сингулярными), скользящими оптимальными управлениями и с четеринг-режимами. Соответствую­ щие им необходимые условия оптимальности изложены также вJ28;29].

Так, в скалярном по управлению случае при особом режиме — = 0 и Эи

э2н

— — = 0 на некотором промежутке времени из [Г0, 7], т.е. функция Га- Эи 2

мильтона стационарна и при этом ее второй дифференциал по управле­ нию не является отрицательно определенным; максимум функции раз­ мыт на допустимом множестве U. Это характерно для задач

оптимального управления, в которых - — явно не зависит от u(t), функ-

Эи

ции / 0(х(0, u(t), t) и Дх(/), «(0. 0 — линейные от управления и условие

max Н не позволяет вычислить оптимальное особое управление. Дока- u(t)eU

зано, например в [25], что необходимое условие оптимальности особого управления представляется обобщением условия Лежандра-Клебша и

Заметим, что в математической экономике особые решения называ­ ют магистральными.

Рассмотрим задачу, при решении которой возникает особый режим.

Задача 1. Найти оптимальное управление u{t) е [-1, 1] и соответствующую ему траек­ торию движения системы из начального состояния х(/0) * *i в конечное х(Т) * х2, при ко­

о

жение системы описывается уравнением x(t) = u(t)t 0

59

Р е ш е н и е . Согласно изложенным необходимым условиям поступаем следующим образом:

1.Составим гамильтониан

#М 0, «(/), 0 = *2(0 + V(0w(r).

2.Найдем оптимальное управление u°(t) из min Я:

l«l$i

« °(0 ■» sign у (0 при у (0 0.

Если же у(/) = 0 , то конкретное w°(0 € (-1 ,1 ) по функции Гамильтона не определяется — имеет место режим особого управления. В этом случае воспользуемся отмеченным выше условием оптимальности такого режима:

(известны и другие подходы к исследованию режима особого управления, изложенные в [129, 135]).

При этом из сопряженной системы уравнений принципа максимума на отрезке времени, соответствующем режиму особого управления, имеем

у(0 =М . а»у =2JC=0 =*х= О

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

ди dt2 V <*и )

образом, вычислено оптимальное управление

60