книги / Математические методы в системах поддержки принятия решений
..pdfДействительно, если х° — слабоэффективная альтернатива, то в свя зи с противоречивостью критериев-функций, подлежащих минимиза ции, необходимые условия оптимальности, т.е. необходимые условия их минимума,
(V/X*0), х) > 0, / = 1, 2, .... т, (Vgj(x°), х) > 0, j е У(х°)
должны составлять несовместную систему; иначе, по определению, х° не будет слабоэффективной. Но тогда, распространив утверждение из вестной теоремы Фана (см. [20]) и доказательство принципа Лагранжа на рассматриваемый случай, приходим к выводу о справедливости соот ношения (**) как необходимого условия слабой эффективности альтер нативы х°.
Для выпуклых задач (D — выпуклы, F(x) — выпуклы и g(x) — вогну
ты) это условие является и достаточным.
П р и м е ч а н и е . Условие регулярности означает то, что из граничной точки х° как оптимальной альтернативы, не имеется направления убывания компонент критериальной функции, не выводящего из допустимого множества.
Таким образом, для построения множества Парето необходимо най ти х°(р“) — совместное решение системы уравнений (**) при каждом за данном ц“, а = 1, 2, ..., к с учетом условий дополняющей нежесткости
(они обусловливаются неравенством (*)), и затем выполнить операцию объединения решений х°(д“) по всем а = 1, 2, ..., к.
Изложим применение теоремы конкретно.
Задача. На выпуклом множестве D =• {* е £ 2 | -1 < х, < 0, - 2 S x 2 < 2} заданы крите
рии
(дс,,ж2) = xt2 + (х2 - 1)2, F2(xl,x2) = (x2 - 2 ) 2 + 4(х2 + I)2,
которые необходимо минимизировать. Найти оптимальное по Парето множество {х°} с D. Р е ш е н и е . 1. Запишем необходимое условие
2 |
4 |
|
£ |
V/Kxj.Jtj)- X, + ^ V g |
= 0 |
<=i j-1
и условия дополняющей нежесткости: множители Лагранжа, соответствующие пассивным ограничениям, должны обращаться в ноль
ц,дс® = 0, М - 1 - Х ® ) ® 0, Цз(*2 - 2 ) = 0, ц 4( - 2 - х ®)= 0.
Заметим, что в теореме X £ 0, + Х2 “ Ь Ц- * 0 с компонентами
ц,£0, М-2 £ 0, Цз* 0, ц4£0, Щ+ Цг + Цз + Ш^!-
В процессе поиска множества Парето должны быть проанализированы все допустимые значения компонент вектора ц совместно с искомыми дс° € D.
231
2. Составим систему
X, •2JC|0 + X,2-2(XI0-2 )+ H1-Ц2=0,
^1 -2(х2 - 1)+ Х2 ' 8(*2 + 1) + Ц з - Н4 = 0>
HiJf,0 =■0, ц2(-1-х1°) = 0,
Мх2#-2) = 0 ,М - 2 - де2°) = 0,
ц, + HJ + Из + ц4 = 1,
И,гО, (ijSO, Из^О, щ £ 0.
Имеем:
а) X, -2JC® + 2Х2(х® - 2 ) + ц , - ц 2 = 0, Hix® = О, ц 2(—1—дс®) = О,
|Х|^ О, |i2 > О, Х| ^ О, Я»2^ О, Я.] + Х2 “ 0}
б) X, -2(4 - 1)+ Х2 •8(х? + 1)+ Из - ц4 = О, Из(х2° -2) = О, ц4(-2 - х?) = 0;
И3 + И 4 = 1 - Ц 1 - ^ 2 . И1,Ц2. И з . Ш * 0, Хз ^ О, X, + Хз = 1.
Из а) находим
*1°=-4--^ 1+^ , И|Х® —0 и2(-1-х,°)=0.
Если \LX* О И Ц2 * °» ТО *,° = 0 либо X®= “ 1,
но это решение неоднозначно и противоречит теореме, поэтому исключаем его из даль нейшего рассмотрения.
Пусть Ц) = О, \L2 - 0 ; тогда х® = 2Я.2 и х® > 0, так как Я^ > 0:
исходная задача не вырождается в однокритериальную; х® > 0 — недопустимое решение, так как х® е [ - 1, 0].
Пусть |Х| = 0 и |х2 ^ 0; тогда х® = (4Я.2 + р 2) / 2 и необходимо, чтобы -1 - х® = 0. Но
при этом - 2 - 4Я.2 - ц2 = 0 и М-2 < 0, что противоречит теореме, поэтому р2 > 0- Рассмот рим р.] Ф0 и \12 = 0; имеем
= О, (4Х2 - Hi)/2 = 0 => Hi > 0.
Теперь из б) имеем:
то _ 2Х, - 8Х2 - и , + ц д
2 2Х, + 8Х2
Из+ ^4= l - ^ i. Ц|*0, И з * 0. Щ *° , Х ^ Х ^ О , X, + Х2 = 1.
232
Пусть ц3 * 0, и4 ф 0; тогда х® = 2 либо х® = -2 , но такое решение противоречит тео реме.
Пусть Из = О, И4 * 0; тогда
- 2 - х ? = 0 , - 2 - 2 Х 1 ~ 8 Хг - й з + И 4 = 0
2 2 Х , + 8 Х2
откуда И4 = - 6Xj - 8X2 < 0 , но это недопустимо. Пусть Из * 0, И4 = 0; тогда х® - 2 = 0 и
2Х] —8Я^ —Из —4A.J —16^2 —0 ^ Из ^ 0,
что также недопустимо.
Рассмотрим случай, когда Из~ 0, И4 = 0; при этом получаем
д.о _ 2Х\ —8Л.2 |
_ 2 Х| - 8(1- Я.|) |
2 2Xi -h8Х2 |
2A.J + 8(1 - Х{)' |
где 0 < Я.| й 1. Отсюда видно, что х® е [-1, 1].
3. Обобщая полученные результаты, приходим к выводу, что множество Парето пред ставляется отрезком, соединяющим точки
(*“ = о, Х2° -----1), (X® = 0, х2° = 1) из Л/0.
На рис. 4 приведена геометрическая интерпретация теоремы.1
Рис. 4. Геометрическая интерпретация теоремы для задачи принятия решения на основе минимизации критериев на замкнутом множестве:
1 — линии уровней; 2 — минимальные значения критериальных функций F\(x) и F2(x)
233
На рисунке 4 также обозначено:
D = {хе E l/g\(x) > 0 , g2(x) > 0, g}(x) SO} — множество, на котором отыскивается минимум одновременно по критериям F{(x) и F2(x);
ДО — допустимая область решений; ВКВН — выпуклый конус возможных направлений из точки
*° = (*|, *2);
V, — градиент ограничения £,(х°) > 0 в точке х°, Vg-,(jc°); V2 — градиент ограничения g2(x°) > 0 в точке х°, Vg2(x°);
х — направление смещения, х = X JVgj (х°), S 0, /(х°) = {/= 1,
7 = 2};
-V , = - ^ ц ,У /; .(х 0) = - p 1V/'1(x ° ) - p 2V/:’2(x0), р, + ц2 = 1, р„ р2 > 0; /-1
-V 4 — антиградиент критерия Ft(x) в точке х°, -VF,(x°); —Vs — антиградиент критерия F2(x) в точке х°, -V /^ x 0).
При таких обозначениях непосредственно из рисунка выписывается выражение для равновесного состояния системы векторов в точке х° в виде -V 3 = х, которое есть ничто иное, как искомое необходимое усло
вие оптимальности по Парето точки х° — граничной точки ДО. Рисунок построен для случая, когда при D = Е 1 множество Парето представляет ся линией, соединяющей точки абсолютных минимумов критериев Ft(x)
и F2(X ), проходящей через точки касания линий равных уровней этих критериев и непересекающейся с множеством D за исключением только
одной его точки х°. Непосредственная проверка выполнения определе ния эффективности по Парето решений относительно альтернатив из D
приводит к тому, что граничные точки, составляющие Ах°В, есть мно жество Парето — ядро множества D. Становится также очевидным факт
несовместности систем неравенств
(-V F ,(x°),x)>0, / = 1,2 ,
(Vsy(x°),x)> 0, VJe J(xЛ) = {1,2},
т. е. факт несуществования возможного направления из точки х° во внутрь ВКВН, вдоль которого убывали бы значения критериев F,(x) и
F2(X).
Действительно, в точке х° два ограничивающих условия (g,(x°) > 0 и &(х°) > 0) являются активными. С этой точкой связана допустимая об ласть направлений, она находится в выпуклом конусе градиентов актив ных ограничений с вершиной в х°. Видно, что при любом перемещении из х° в допустимом направлении х значения критериев одновременно не уменьшатся, так как из выражения
F,(x° +ax) = ^/ (x°)+a(V7r (x o),x+ 0(a,x), a > 0 , / = 1 ,2 ,
следует, что приращение каждого критерия представляется скалярным произведением его градиента в точке х° на направление перемещения х, а
234
оно (приращение) положительно для F2(x) и отрицательно для F,(x). В ре
зультате будет установлена другая эффективная по Парето точка и, оче видно, в ней будет иметь место только одно активное ограничение g2(x) = 0. Такая точка будет находиться в подмножествемножества Ах°В,
которое (подмножество) будет образовано в Ах°В линиями равных уров ней критериев, проходящими через точку х° +ах.
Используемое в теореме выражение для условия регулярности ока зывается справедливым. Отметим, что возможно и обратное утверж дение: если в какой-то точке множества D выполняется условие ре
гулярности, то в этой точке справедлива коническая аппроксимация допустимого множества. Для сравнения рассмотрим точку С е D; в этой
точке условие регулярности не выполняется — конус градиентов актив ных ограничений g2(C) = 0 и gy(Q = 0 не выпуклый.
7.4.Построение множества Парето для динамических задач
Изложенные в п. 7.1 методы переводятся и на динамические задачи
П
выбора решений, когда на допустимом множестве U = Y [U , C E N опре-
|
/=1 |
|
делены N функционалов |
|
|
//(и) =4(И|, |
т |
___ |
«2.......Иаг) = Ф ,(Т,х(Т)) + f F,(t,x(t),u)dt, |
/ = 1 Д . |
|
|
10 |
|
Каждый из функционалов максимизируется по щ е Ut при условии вы
полнения ограничений на движение управляемой системы, которое описывается уравнением
х(0 = f(t, X, и ,, и2, ...,uN), t0< t< T ,
с заданным начальным состоянием x(ta) - х0 и конечным множеством G, на котором заканчивается траектория движения системы в момент Т,
т.е. х (7 )е G.
Обозначим через P{U) множество оптимальных по Парето решений. Решение и 0 =(и®,и^,...,и^) называется эффективным по Парето, если
для любого и € U, д ля которого 1,{и) > /,(и°), » = 1,7V справедливы равен ства 1,(и) = / ((и°), / = 1 ,N.
Если U„ i = Т Д выпуклы, функционалы /,(и), / = ТД, вогнуты, то
решение и° эффективно тогда и только тогда, когда существует вектор
|
|
N |
Ха =(Х“,...,XaN), |
>0, |
=1, при котором |
У Х “/,(и°) = тахУА.“/((и), о - 1, 2, ..., к.
ие(/ .-1
235
Отсюда вытекает следующая структура алгоритма построения мно жества Р(Ц).
Ал г о р и т м |
|
|
|
1. Задать вектор Ха для каждого а = 1, 2, ...» к. |
|
||
2. Вычислить оптимальное решение |
из условий |
|
|
шах Я 1а (/,*(/),«(/)) = О, |
|
||
и ( \ а ) |
|
|
|
N |
|
|
|
У (Т ,х(Т ;и°(\а ))) = ^Ф ,(Г,х(Г;и°(Х .а ))), |
а = 1, 2...... к, |
x(T,ifl(k*)) е G, |
|
<=1 |
|
|
|
где H x« (tX O X O ) = ^ tfF i U ,x ,u ) + ^ £ ? l + |
j ^ ’/ j Функцию У М О ) задать разло- |
||
жением в конечномерном базисе векторных одночленов 1, х, х2, |
Xй, где л-порядок од |
||
ночлена, например, в виде V(tjc(t)) |
у ^u (t)x. Матрица у ха подлежит определению при |
решении дифференциального уравнения для Я.
к
3. Построить P((J)= jJ« °(X a ). a=l
N
В случае невыпуклого множества U = П ^ ' искомое множество Па-
/=i
рето может быть построено посредством отыскания
шах min Xa,JA u) Va е \,к.
ueU liiS N 1 '
Тогда в изложенной структуре алгоритма должно быть изменение толь ко оп. 2, а именно оп. 2 должна быть сведена к вычислению для каждо
го Xе |
a е 1 ,к, оптимального решения |
|
|
и#(Х.“) = ащтах[ min Ха,Н , (t,x(t),u(t))] |
|
||
|
|
f ^ ^ А/ |
|
при выполнении |
условий |
V,(T,x(T;u°(Xa))) = Ф<(7’гх(Г;м°(А,“))), |
где |
= dV{t: x{t)) f(t) + ЭК(/’*(/)) + Х“F, (x(t),u(t)), при этом |
пред- |
||
дх |
|
__ Эt |
|
полагается, что //и ) > 0 V/ е |
1 ,N. |
|
|
7.5. Методы сужения множества Парето |
|
Сужение принципиально осуществимо только при получении ин формации от ЛПР либо для упорядочения по важности однородных ча стных критериев, либо для утверждения их равноценности.
Критерии называются однородными, если их значения принадлежат
одному и тому же множеству.
236
Равноценными критериямипсчитаются те, для которых весовые коэф фициенты Х„ /= 1,л, A,SO, ]STA,( =1 равны и агрегированный критерий
записывается в виде
где х е X<z Е*, X, = Xj = ... = h t = 1/п.
При этом эффективное решение
где Р{Х) — множество Парето.
Рассмотрим некоторые методы [41; 98; 99; 100].
Метод выделения главного критерия. Сущность его состоит в опти мизации одного наиболее важного из рассматриваемых частных кри териев при условии удовлетворения всеми оставшимися частными критериями установленных для них соответствующих ограничений (уровней), т. е. исходная многокритериальная задача становится одно критериальной условной задачей, в которой роль введенных ограниче ний (условий) становится решающей при поиске оптимальной альтер нативы.
Показатель важности критерия можно установить следующим обра зом.
Пусть каждая альтернатива из рассматриваемой их совокупности ха рактеризуется одним и тем же вектором частных независимых свойств, а значит, и критериев, например надежностью, стоимостью, доходно стью, живучестью, безопасностью, удобством эксплуатации, адаптируе мостью к изменению условий функционирования, весом, габаритами, помехозащищенностью, управляемостью и др. Тогда по каждому из этих свойств каждый эксперт, руководствуясь только своей системой предпочтений, может восстановить профиль предпочтений на альтерна тивах и оценить их ранги. Затем восстанавливается групповой профиль предпочтений по каждому свойству, и по всей их совокупности можно вычислить суммарные ранги каждой альтернативы, соответствующие «своим» критериям. В результате восстанавливается полный групповой ранжированный профиль, по которому легко упорядочить критерии. Для этого каждому критерию следует поставить в соответствие макси мальный ранг альтернативы и упорядочить эти ранги в порядке невоз растания. Заметим, что для упорядочения частных критериев можно воспользоваться и методом п. 1.7, основанным на применении логиче ского определителя г-го ранга.
Рассмотрим применение метода выделения главного критерия.
237
З а д а ч а . Выбрать оптимальный по Парето портфель ценных бумаг: акций, облига ций, казначейских обязательств государства, сберегательных и депозитных сертификатов, векселей, варрантов, опционов, фьючерсов, приватизационных чеков, брокерских мест. Точнее, будем исходить из того, что формирование портфеля осуществляется при извест ном полном списке ценных бумаг. Пусть /= 1, 2, ..., п означает тип ценной бумаги, из вестны начальные цены единицы каждой из них и доходности по ним г, как случайные величины. При этом считается также заданным класс допустимых портфелей, обуслов ленный финансовыми условиями, и что для портфелей выполняется ограничение
|
п |
|
]£■*/ =(х,е), |
|
/=| |
где JC = (Х|, х2, ..., х„) — вектор, |
определяющий состав портфеля, х ,> 0, /= 1, 2, ..., и, |
х = {ххех + х2е2 + —+ хпеп)» ei = (°> |
..., О, 1,0,..., 0). По таким исходным данным вычис |
ляются характеристики портфеля: |
|
—ожидаемая доходность M[r\ = (х,т), где т = (ть т2, ..., т„) — вектор ожидаемых доходностей ценных бумаг, /и, = М[г,],
—ковариационная матрица доходностей
f с\\ с12—с1п> С = с2\ с22 —с2п
<сп\ сп2 ••• ст>
с элементами Сл = cov^/y), /, у = 1, 2, ..., л,
пп
—риск портфеля V(r) = (Cxjc) = ^ с,ух,хуили а(г) = Л/к (г ) — среднеквадратиче-
/=1 м
ское значение.
Требуется сформировать оптимальный портфель, т.е. портфель, характеризующийся
наилучшими значениями риска V °(r)= min^(r) и доходности М 0[г] = maxМ [г] при X X
условиях-ограничениях (х,е) ~ 1, х > 0. Очевидно, что единственного портфеля с наилуч шими доходностью и риском в общем случае не существует и его выбор следует осуществ лять из множества Парето в пространстве значений частных критериев V(r) и М[г].
Ре ш е н и е .
1.Выберем в качестве главного критерия риск V(r), а доходность портфеля М[г] пере
ведем в ограничения задачи и зададим ее значение из допустимого множества [ min mh
т а хт Л . |
\&<N |
2. Составим оптимизационную задачу K(r)- ) mi n - » х |
п |
при условиях (x,m) = Щг], |
|
X |
|
(х,е) = 1, х> 0 . Это общая модель Марковица [137, 138], она представлят гладкую задачу выпуклого программирования при ограничениях в виде равенств и неравенств. Для ее ре шения воспользуемся теоремой Куна—Таккера [18—21, 23].
3. Составим необходимые условия минимума риска портфеля: запишем функцию Ла гранжа
Л(х, X, ц, V, и) = V(r) + Х(М[г] - (х, т)) + р(1 - (х, ё)) + (v, и2 - х),
где X, ц. — скалярные множители Лагранжа;
V - iY\> *2>•••» К) — вектор множителей Лагранжа;
и2 — ослабляющая переменная (и2 > 0), ее введение обеспечивает перевод ограни чений-неравенств х 't 0 в равенства;
238
выпишем условия стационарности по х, X, р, V, и
ЭЛ О
Эи
или, в развернутом виде, имеем
grader) - X i w - p e - v « 0 , grader) = Ос, (х,/и) = M[r], (jc,e) - 1, (v^c) = 0; |
(*) |
пятое равенство есть условие дополняющей нежесткости, оно непосредственно следует из условия
— = 0 -» 2(v,«) = 0 -* 2(v,«2) = 0 -» (v,«)= 0,
Эи
X, р, v £ 0 — условия неотрицательности множителей Лагранжа.
4. Вычислим х° из первого уравнения алгебраической системы (*)
*° - АС~1т + \lC~le + vC"1.
5. Подставим JC° в третье, четвертое и пятое равенства системы (*); получим
ТКС-Че) + p(C-'e,e) + (v,C-!e) = 1,
ХССН/и,/») + р(С~1е,л|) + (v,C“lm) = А/[г],
vfXC-1/» + рС-1* + vC"1) = 0,
X, р, v £ 0.
6. Проанализируем условия дополняющей нежесткости (третье равенство п. 5). Из него следует
j V“ ^* |
. |
(1) или | v ~®* |
. |
. |
(2) |
[ХС“ /и + рС “ е * 0, |
{ХС”1!» + рС "!е + vC“ |
|
=0. |
Если принять (2), то, очевидно, портфель будет характеризоваться нулевыми риском и доходностью - это вырожденный портфель, он исключается из рассмотрения. Условия (1) дополняющей нежесткости приводят к системе уравнений
X(C”1w,e) + \i(C-{e,e) = 1, \(С~1т9т) + р (C~letm) - Af[r], |
(**) |
сусловиями неотрицательности X, р £ 0.
7.Вычислим X и р из системы (**):
( 1 |
(С- |е,е)'| |
|
( (С - 'т ,е ) |
1 'l |
Д М И (С~'е,т )) |
Щ г]) |
^(C~‘m,w) |
Af[r]J |
|
((С~'е,т) |
(С- |е,е) I |
|
|
Р(А/[г]). |
|
(C-Im,e) |
« Г ,е,е)'| |
||
(С~'т,т) |
(С~'е,т)) |
|
(С~1т,т) (С~'е,т)) |
Отсюда видно, что X и р линейно зависят от доходности портфеля; при этом
х° = а (Щг])С~1т + Р(М[/])С-1е.
239
Теперь полученные результаты подставим в выражение для х°, а последнее - в выра жение для риска V \r) при заданной доходности. Итак, получено искомое значение мини мального риска
V °(r) = min V (r )- (Сх°,х° ) = (C(a(Af[r])C_l т + Ъ{М\г\уС~' е \
X
« (Л /М Х Г 'и + Р(Л/[г])С- ,е).
Если теперь доходность изменять, то в зависимости от доходности риск будет пред ставляться квадратичной функцией — положительно определенной параболой с верши ной в точке (Кв(/*), Л/вИ ) Ф0; Ув(г) вычисляется при известном значении Мв[г], а Мв[г\ можно вычислить по выражению Мв[г] - (х°, /и).
Правая часть этой параболы (рис. 5) есть множество Парето, которое и сужается изложенным методом до единственной точки при каждом заданном значении доход ности.
Если в состав портфеля ввести безрисковые ценные бумаги (казначейские ценные бумаги, выпущенные государством), то множество Парето будет представляться гладким сплайном двух линий, одна из которых — отрезок MQA прямой, выходящий из точки, со ответствующей начальному доходу безрисковой ценной бумаги, и касающийся построен ного множества Парето. Является (естественная доходность безрисковой ценной бумаги должна быть всегда меньше доходности рискового портфеля), вторая - это вся правая часть множества Парето, начинающаяся от точки касания первой линии АС.
Это утверждение доказывается достаточно просто с учетом того, что операция соеди нения безрисковых активов не должна приводить к выходу из нового эффективного мно жества — множества Парето.
Рассмотрим в связи с этим портфель А (см. рис. 5) из исходного множества Парето, содержащий п рисковых ценных бумаг, и сформируем новый портфель из у, 0 й уй 1, час тей безрисковых ценных бумаг и 1 - у частей рисковых портфеля А. Очевидно, доходность этого нового портфеля М = уМ0+ (1 - у)МА, а его риск V - (1 - y)2VA. Из последнего име-
ем |
1 |
V* |
1- у = —р но тогда |
240