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

Гл а в а т р е т ь я

Необходимые и достаточные условия оптимальности выбора решений при целевой неопределенности

3.1.Определения оптимальности решений

вмногокритериальных механизмах при целевой неопределенности

Многокритериальный механизм вводится для выбора недоминируе­ мых лучших решений по достижении нескольких целей посредством одновременной максимизации (или минимизации) компонент f , /= 1,/я, векторного критерия fix), заданного на множестве допустимых решений X. Здесь совокупности целей и компонент векторного крите­

рия находятся во взаимно однозначном соответствии, причем компо­ ненты векторного критерия как частные критерии чаще всего противо­ речивы и выбор оптимальных решений не может быть основан только на оценках частных критериев. Поэтому так сформулированный меха­ низм требует доопределения — необходимость в этом исходит из неяс­ ности понятия одновременного максимума (минимума) всех компонент векторного критерия. В связи с этим на допустимом множестве реше­ ний X c R " (или X = R") вводят отношения доминирования, а затем на­

ходят такие решения, которые составляют соответствующие множест­ ва — ядра отношений доминирования С(Х) с X недоминируемых

решений, т.е. неулучшаемых решений одновременно по всем частным критериям. К отношениям доминирования относятся [38; 76; 39; 40]:

доминирование по Слейтеру, Парето, Борвейну, Джофриону, лексикогра­

фическое доминирование — lex; последнее вводится на конечном мно­ жестве X.

Определение 1. Решение х° е X называется оптимальным по Слейтеру или слабоэффективным, если не существует такого другого решения х е X, что

f,(x) >/{х°), / = 1,/и.

Определение 2. Решение х° G X называется оптимальным по Парето или эффективным, если не существует такого другого решения х е X, что

f,(x) >/(х°), / = 1 ,т и fix) *Лх°).

71

Отметим, что Р(Х) с S(X), где Р(Х), S{X) — множества оптимальных

стратегий по Парето и Слейтеру соответственно, и что два эффектив­ ных решения либо эквивалентны, либо не сравнимы по критериюДх).

Определение 3. Решение х° е X называется оптимальным по Борвейну или подлинно эффективным, если оно оптимально по Парето и пересечение касательного конуса к множеству X в точке х° с множеством R" (неотри­

цательным октантом) представляется нулевым элементом {0(я)}. Касательный конус здесь есть аппроксимация множества X в точке

х° и что В(Х) с Р(Х) с S(X), где В(Х) — множество оптимальных реше­

ний по Борвейну.

Определение 4. Решение х° называется оптимальным по Джофриону или собственно эффективным, если оно оптимально по Парето и Борвейну и существует такое положительное число 0, что для любых / е [1, т],

х е	X для которых выполняется неравенство Д х) >/(х°), и некоторого
j е	[1, m ] ,j* i такого, что/рс) <Дх°), выполняется неравенство
		Ш	- f i x °) ^
		f j ( x ° ) - f j ( x )
	Множество таких решений — G(X), G(X) с В(Х) Q Р(Х) Q S(X).
	Определение 5. Решение называется х° е X лексиграфически оптималь­
ным,		если Дх°) > /ех Д х) Vx € X,	х*х°, или, что то же самое, решение
х° >		kx х, х°, х е X, если выполняется одно из следующих условий:

/,(*°) >/.(*);

/ , ( ^ ) = / . ( X) , / 2(X° ) > / 2(X );

/,(*°) = М х), / 2(*°) = /(* ), / 3(х°) > /3(х);

/.(*°) =/,(х), / 2(х°) = / 2(х) = ... = / м_,(х°) = /т_,(х), / т(х«) >/„(х);

Л*0) =Лх).

При этом компоненты векторного критерия упорядочены в невоз­ растающем порядке по их важности, пусть

А(Х) > / 2(х) >Л(х) > ... >/„(х).

Лексиграфически оптимальное решение является оптимальным по Парето [48; 49; 50].

Очевидно, что из приведенных определений не вытекают какиелибо положения для непосредственного формулирования необходимых и достаточных условий оптимальности выбора решений. Такие условия зависят от свойств критериев /(х ), / = 1,/я, и множеств допустимых ре-

72

шений х б X. Однако из отмеченных взаимосвязей между множествами оптимальных решений следует, что необходимые условия для слабоэф­ фективных решений (решений, оптимальных по Слейтеру) будут необ­ ходимыми для всех других понятий эффективности решений (по Паре­ то, Борвейну, Джофриону).

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

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

В1. Выпуклая задача. Множество допустимых решений X — выпуклый компакт, частные критерии — вогнутые функции Д х), х е X, i — 1, т. Тогда для того чтобы решение х° € X было эффективным — оп­

тимальным по Парето, необходимо и достаточно, чтобы существовал

___ т вектор А = (А,„ Х-2, Хт) с компонентами Х,>0, / = 1,/и, ^ГА,, =1, при

/=1

котором для агрегированного критерия

А*-) = Х *■///(*)> х е Х > К е А,

	/=1
выполнялось бы неравенство
	Vx е X,
/=1	/=1
или, что то же,
шаххеХ	5>,/,w =2>,/д*°),
	««I

а для того чтобы решение х° е X было собственно эффективным -опти ­

мальным по Парето, необходимо и достаточно, чтобы существовал век­

тор X = (Х|, Х2, ..., Х„) со строго положительными компонентами X > О /И

*= 1,т>	= Ъ при котоРом ДляДА ) выполнялось бы то же неравен-
ство.	/=1

73

В2. Локально выпуклая задача. Множество допустимых решений X< zRk составлено из непрерывных _и_ непрерывно дифференцируемых функций-ограничений фу(х) < 0, j = 1,/, и <р/х) = 0, у = / + 1 ,т (рис. 2); оно аппроксимируемо вблизи точки-решения х° е X выпуклым кону­

сом. Частные критерии — вогнутые непрерывные и непрерывно диффе­ ренцируемые или дифференцируемые в точке функции f( x ) , / = 1 ,п,

хе X. В любой точке могут быть установлены направления неубывания

ивозрастания частных критериев, а также активные и неактивные огра­ ничения из общего количества функций-ограничений. При этом пред­ полагается, что градиенты ограничений линейно независимы, т.е. имеет место условие регулярности [20], иначе задача может стать триви­ альной.

Рассмотрим два случая: первый — решение х° является внутренней точкой, т.е. х? е inLY, и второй — решение х° находится на границе X.

В первом случае, очевидно, можно считать X = R k. Тогда по анало­

гии с однокритериальной безусловно экстремальной гладкой задачей можно [38; 42; 7] утверждать, что решение х° е int X будет локально сла­

бо эффективным — оптимальным по Слейтеру, если

Рис. 2. Касательный конус и конус возрастания функции f i x ) на множестве ДГ:

I — касательный конус в точке зР; 2 — реш ение, оптимальное по Слейтеру; 3 — абсолютно максималь­ ное значение функции т т (/|(к ),У 2 (*)); 4 — фрагмент линий равных уровней ф ункции/[(х); 5 — конус возрастания функции пип(/|(дс),^(дс)} в точке х®; 6 — фрагмент линий равных уровней функции/ 2 (х); 7 — активные ограничения ф|(х), ф3(х) в точке зР\ 8 — множество допустимых значений

74

X w , ( * )—®(*>>	А,—(A,], Aj,	A„), У 'A, —1,
/=i		,
m inC V 7,(*°K <0 v Cetf<x°),
В Д = К e	# |(V /X ^ .O > 0 ,	/ = M },

где первое выражение есть необходимое условие и представляет равен­ ство нулю линейной части критериальной вектор-функции в точке х°, а второе — достаточное условие, представляющее отрицательную опреде­ ленность матрицы, составленной из вторых частных производных кри­ териальной вектор-функции Дх) в рассматриваемой точке х°. Для необходимого условия возможна и другая, эквивалентная форма запи­ си: для того чтобы х° е int X было оптимальным решением, необходимо,

чтобы выпуклая оболочка, натянутая на концы векторов-градиентов ча­ стных критериев Д х0), * = 1,и, в точке х°, включала точку {0да} — начало системы координат.

Во втором случае, когда х° принадлежит границе Х с . /{*, будем исхо­ дить из того, что множество X допускает аппроксимацию в точке х° ка­

сательным выпуклым конусом и векторы — градиенты частных крите­ риев /,(х°), / 2(х®), ..., /„(х°) в точке х° представляют (см. рис.) конус направлений возрастания вектор-функции Д х). Тогда решение х° е X

будет локально слабо эффективным — оптимальным по Слейтеру, если пересечение касательного конуса и конуса направлений возрастания со­ ставляет одну единственную точку {0} или, что то же, линейная часть критериальной функции и активных функций-ограничений в точке х° равна нулю [43; 7; 38], т.е.

X A ;V/,(X°)+ ]ГцуУ<р,(х°) = 0,

'=1 УеУ(дс°)

где J(x°) — множество индексов активных ограничений. Это условие достаточное для вогнутой Дх). Точка {0} является вершиной конусов.

Действительно, пусть решение х° оптимально в достаточно малой окре­ стности U, g — направление неубывания критериальной функции Дх) и а > 0 — произвольное число. Тогда ag также будет направлением не­

убывания функции Дх), так как можно выбрать новую окрестность

a U = {а£|£ е U) и шаг	v перемещения по направлению £, равный
v = v/ct и такой, что v е	(0,v), где v > 0. Непосредственно отсюда следу­

ет, что конус направлений неубывания имеет вершину в точке {0} и включает конус направлений возрастания функции Дх). Аналогичное рассуждение можно провести и относительно касательного конуса в точке х °е X.

Достаточное условие локальной оптимальности точки х °е X форми­

руется, как и в предыдущем случае [7; 43].

75

ВЗ. Невыпуклая задача. Множество допустимых решений X — невы­

пуклый непустой компакт, частные критерии — неотрицательные^ не­ прерывные функции,/(х) > 0, / = 1,л, Х€ X (условие /<х) > 0, /= 1 ,л, не

является принципиальным; оно всегда реализуемо при добавлении не­ которой константы к тем исходным fix ) , которые оказались меньше нуля). Чтобы решение х° е X было эффективным по Слейтеру, необхо­

димо и достаточно существования вектора А. = (А,,, Aj, ..., А„) со строго
	__	П
положительными компонентами А > 0,	/'= 1,л,	^ А ., =1, при котором
выполнялось бы неравенство		/»1
m.tn А.,/Их#)> min А.,f	(х) Vx е X,

или

max min X ,/. (х) = min A.J , (х°).

При этом заметим, что:

1.Поскольку, в рассматриваемой задаче множество X невыпукло, то

получающиеся решения х° не все будут оптимальными по Парето, а оп­ тимальные по Парето решения будут оптимальными по Слейтеру.

2.Если частные критерии — полунепрерывные сверху ограничен­ ные функции на X, то сформулированные необходимое и достаточное

условия оптимальности решения сохраняются.

3.При заданном векторном критерииДх) = (/i(x),/2(x), ...,/я(х)) зада­ ча выбора решения сводится к задаче выбора решения по одному крите­

рию ттА ^ /Д х) с неопределенным параметром А = (А„ А,, ..., Х„), т.е. к

1£/£/?

максиминной задаче, иначе, — к игровой задаче.

В4. Негладкая выпуклая или локально выпуклая задача. Множество допустимых решений X составлено из функций — ограничений, удовле­

творяющих локальному условию Липшица; критериальная векторфункция также взята из класса локально-липшицевых функций, т.е. ог­ раничения и частные критерии — негладкие непрерывные функции; они охватывают достаточно широкий класс задач принятия решений — класс условных экстремальных негладких выпуклых задач. Для установ­ ления необходимых условий оптимальности решения таких задач в отличие от гладких выпуклых и локально выпуклых вводится обобщен­ ный градиент — субградиент. При этом критериальные функции рас­ сматриваются как почти дифференцируемые функции, а множество X,

на котором они определены,— как обобщенные градиентные множества или как выпуклое замыкание субградиентного множества [44; 45; 38]. Поэтому необходимое условие слабой эффективности решения х° € X

можно сформулировать на основе непосредственного обобщения схемы вывода и структуры необходимых условий, изложенных в п.2.2 для од­ нокритериального условно-экстремального механизма и в В.2 настоя-

76

щего параграфа (второй случай). Таким образом, для того, чтобы реше­ ние х® € X было слабоэффективным — оптимальным по Слейтеру,

необходимо существование векторов

\ = (А„ А,, ..., А*) и ц = (ц„ ц2, ..., цт),

А,>0, / = Т Я	£>.,=1, (К,р.)> О,
	Ы1

и обобщенных градиентов Э/-(х°), Э<р/х®) в точке х® соответственно кри­ териальных функций и функций-ограничений, таких, что

п

и при этом для того чтобы выполнялось условие А > О обобщенные гра­ диенты Эфу(х°), j е /(х°), функций-ограничений в точке х® должны быть

линейно независимыми. Здесь У(х°) — множество индексов активных ограничений в точке х®. Условие (*) для рассматриваемой выпуклой или локально выпуклой задачи является и достаточным для слабой эффек­

тивности решения х® е X.		П
В5. Дискретная задача. Множество I	=	допустимых решений
	/=i
конечно; на этом множестве задан векторный критерий
А х) = (fi(x), f 2(x), ..., f„(x)),		х € Х ь
X = (х„ хг, ..., х„), X €	Х„	/ = 1,/1.

Выбор решения х е X осуществляется в результате максимизации

каждого частного критерия Д х) независимо от максимизации всех дру­ гих, т.е. возможен децентрализованный способ выбора решения по компонентам векторного критерия. В итоге такого выбора решений складываются ситуации х = (х,, х2, ..., х„), среди которых могут быть наилучшие — оптимальные.

Для децентрализованного способа выбора оптимального решения х° = (х®, х®,..., х®) принципом оптимальности является принцип Нэша,

называемый принципом равновесности по Нэшу [47; 40]. Решение х® е X равновесно по Нэшу, если для всех из х, е Х„ i = 1,л, выполняется

условие

Дх») >Дх°||х,),

где (х° IX,) = (X ® .... х®_,, X,, Х®+|,.... X® ).

77

Решение х? е Х { по критерию f(x ) равновесно, если оно входит в

какую-либо ситуацию равновесия. Эффективность этого решения не

меньше значения maxmin/] (х), т.е. не меньше эффективности осторож-

Xj Х \ Х ф

ного — гарантирующего решения. Действительно,

ft (*°) > /, (х°||х,) > m in/( (х), Ух, е Х„

X \ X j

непосредственно отсюда следует, что

/Д х ° ) > т а х т ш / ,( х ) .

Л/ Х \ Х /

Для нахождения равновесного решения требуется [47; 40] в общем слу­ чае расширение множеств X , / = 1 ,п. Соответствующее расширение свя­ зано с введением на Х„ <= 1,я, распределения вероятностей F,(X,). Тогда для того чтобы существовала хотя бы одна ситуация равновесия х° е X, необходимо и достаточно, чтобы для любого f,(x) и любого исходного (детерминированного) решения х, е X, выполнялось неравенство

f,(P(X) > Г (П Х )Ы , i = ~ n ,

где F(X) = (F,(X,), F2(X2) , ..., F„(X„)) — смешанное расширение конечного множества X = П * . исходных решений.

В связи с этим отметим характерные особенности о п т и м а л ь н о ­ го п о Н э ш у р е ш е н и я :

—против равновесного решения не имеется «угроз» с позиции какого-либо частного критерия; однако изменение решения с позиции какого-либо частного критерия возможно, если имеют место изменения решений с позиций других критериев;

—может существовать несколько ситуаций равновесия, не эквива­ лентных и не взаимозаменяемых; при этом комбинации равновесных решений х?, составляющих разные ситуации равновесия, не приводят к

ситуациям равновесия.

Если допустим централизованный способ выбора решения, то его оптимальность устанавливается согласно принципу Парето.

Вб. Лексикографическая задача — lex-задача. Множество допусти­ мых решений ^-конечное; векторный критерий

Ах) = (/!(*), fiix), .... / я(х)), х € X,

задается с упорядочением по возрастанию важности его компонент — частных критериев /(х), / = 1,л, что означает введение на X бинарного отношения предпочтения. Решение х° е X будет лексикографически оп­

тимальным, если

/,(*°) >/,<*)

78

или

/|(*°) =/l(*)> /гС*0) > fl(x),

или

/,(*°) = т , u A = т , .... /„_,(*») = / п_,(х), / я(х°) >/„(х).

Отсюда непосредственно следует необходимость решения задач опти­ мизации вида

	х° = arg max / , (х),	/ = 1,л,
	x*Xj_,
где	. = Arg шах/, (x), / = Т|я, и для / =	1, Х0 = X
	Х|_2

При этом X, выделяется из Х0 в результате максимизации наиболее важного частного критерия /,(х) на Х0, Х2 выделяется из Х { максимиза­ цией^^) на Х{, если Х { состоит из не единственного решения, и далее до Х„_ь которое выделяется из Х„_2 максимизацией предпоследнего по

важности критерия /^,(х). В результате находится Схкх — ядро лексико­ графического отношения предпочтения, которому И"принадлежит х°. Из построения ядра С>1я непосредственно следует, что оно содержит толь­

ко оптимальные по Парето решения, необходимыми условиями сущест­ вования которых является компактность исходного множества X и не­

прерывность или полунепрерывность сверху (снизу) на нем частных критериевf(x ), i — 1,л.

В7. Динамическая задача. Обобщенно многокритериальную динами­

ческую задачу здесь представим в виде
			(U, F(u), х(0), R),
где	U — множество кусочно-непрерывных вектор-функций							u(t) е U
с конечным		числом	точек	разрыва первого			рода, определенных
на	отрезке	времени	{Г0, Т\	и	принимающих		значения в	U € Е",
и ** (и„ и2, ..., um) е Uxх			U2х ... х V;
	F(u) : U £*’ — отображение, которое определяется выражениями
		Т					____
		Fl (u) = j f i(t,x(t),u(t))dt+0i (x(T),T),					/ = 1,/и;
		'О
	F(u) — (F,(u), F2(U), ..., Fm(u));				F,{u)	— частный критерий эффектив­
ности решения и е О;
	х(0 е Е”, x(t) = (х,(0, х2(/), ...,хя(0)					— вектор из фазового простран­

ства £ ”, однозначно определяемый по u(t) согласно дифференциальному

уравнению

Xj(t) = <pj(t,x(t),u(t)), j = 1 ,п, x fa ) = xfi, Xj(T) = xJT;

79

R — бинарное отношение предпочтения, заданное на Е ”, по которо­ му сравниваются различные функции-управления и \ иц е U.

Решение задачи сводится к отысканию решения-управления и°(0>

t0< t< T , обеспечивающему maxF,(и), i = 1 ,т, при ограничении в виде

и би­

вектора дифференциальных связей x(t) = q>j(t,x(t),u(t)), *о, х т-

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

		и°(и°,и20,	: F(u°) = ш ах/’(и°||и,),		/= 1 ,/я.
			и, eU,
	Для того чтобы решение и0 = (и,0,и®,...,и®) было равновесным, не­
обходимо		существование	т непрерывных	на	[Г0, 7] х Е функций
6,(0 x(t)),		/ = 1,/я, и непрерывно дифференцируемых на [/Q, Т \х Е всю­
ду,	за	исключением	конечного числа	гиперплоскостей__{/*},
tk е	[Г0, 7] х Е , на которых производные функций б,(/, х(0)> / = 1,/я, по

времени	и координатам вектора x(t) могут иметь разрывы первого рода,
и таких,	что для и°(Г)
	+ ( g n d m x(t)), <р(/, x(t)), u \t))) +/</, х(Г), и®(0) = 0,

а для (и°||и,)

+ fe/addXr, 4 0 ) , <p(f, 4 0 ), «®|k(0)) + /4 , 4 0 , «*N 0) < 0,

при условии &,(Г, x(T)) = Ф,(7’ х(()), i =	1,/я.
Если в рассматриваемой задаче отрезок времени [Г0, 7] представля­
ется дискретными равноотстоящими	на	Д/ моментами времени
?0, Г,,..., /ЛГ= 71 4+1 — tk = At, к = 0,N — 1, то необходимое			и достаточное
условия равновесности решения и® = (и®0,и®, ...,и^_,),			/' = 1,/я, можно

сформулировать с учетом принципа оптимальности Веллмана либо в более общем случае — с использованием функции Кротова [19; 53; 21]. Здесь воспользуемся только п р и н ц и п о м о п т и м а л ь н о с т и В е л л м а н а ; предварительно выполним преобразование исходной по­ становки задачи выбора решения и0 е U:

max F, (и), i — 1,/я,

И/ €*//

4 0 = фО,4 0 , и(0), t0< t< T , x(t0), x(t) е G, x(T )eg < zC ,

где G — допустимое множество координат в фазовом пространстве Е .

so