Теория принятия решений, страница 2

Множество всех допустимых в точке x0направлений обозначим через L(x0 ).Для x0 , внутренней точки множества X, любое направление являетсядопустимым. Для граничной точки круга на плоскости допустимо любоенаправление, ведущее внутрь круга. Касательное направление допустимымне является.06Теорема 3.3.

Пусть все частные критерии Wi (x), i = 1, ..., s вогнуты и непрерывно дифференцируемы на выпуклом компакте X евклидовапространства E m . Тогда для того, чтобы x0 ∈/ S(X, W ) необходимо и достаточно, чтобы нашлось такое допустимое направление α ∈ L(x0 ), что(Wi0 (x0 ), α) > 0, i = 1, ..., s.(2)Доказательство. Необходимость. Допустим, что x0 ∈/ S(X, W ).

Тогда∃ x ∈ X : Wi (x) > Wi (x0 ), i = 1, ..., s. По свойству вогнутых функций(Wi0 (x0 ), x − x0 ) ≥ Wi (x) − Wi (x0 ) > 0, i = 1, ..., s,то есть условие (2) выполнено для допустимого направления α = x − x0 .Достаточность. Предположим,что для некоторого α ∈ L(x0 ) выполненоусловие (2). По определению допустимого направления найдется такое ε0 >0 , что для всехε : 0 ≤ ε < ε0 ⇒ x0 + εα ∈ X.Тогда по формуле конечных приращений ЛагранжаWi (x0 + εα) − Wi (x0 ) = (Wi0 (x0 + θi εα), εα) = ε(Wi0 (x0 + θi εα), α),где 0 < θi < 1. Пусть ε → +0. Тогда, используя непрерывность градиентаWi0 (x), получимlim (Wi0 (x0 + θi εα), α) = (Wi0 (x0 ), α) > 0, i = 1, ..., sε→+0по условию (2). Отсюда при малом ε > 0Wi (x0 + εα) − Wi (x0 ) = ε(Wi0 (x0 + εθi α), α) > 0, i = 1, ..., s.Поэтому стратегия x0 + εα строго лучше, чем стратегия x0 и x0 ∈/ S(X, W ).Отметим следующий частный случай.

Допустим, что критерии Wi (x)строго вогнуты. Тогда S(X, W ) = P (X, W ). Действительно, предположим,что ∃ x0 ∈ S(X, W ) \ P (X, W ). Тогда ∃ x : Wi (x) ≥ Wi (x0 ), i = 1, ..., s, W (x) 6=0Wi (x)+Wi (x0 )W (x0 ). Отсюда x 6= x0 и Wi ( x+x≥ Wi (x0 ), i = 1, ..., s. Это2 ) >20означает, что x ∈/ S(X, W ) (противоречие). Поэтому для строго вогнутыхкритериев теорема 3.3 дает необходимые и достаточные условия для оптимальных по Парето стратегий.

Рассмотрим пример использования полученных условий.Пример. Пусть x = (x1 , ..., xm ), K = {1, ..., m}. Для каждого подмножества J ⊂ K рассмотрим критерий:vumXXXuWJ (x) = t1 −x2k −xk +xk .k=1k∈J7k∈J/Всего 2m критериев. ПустьmX = {x ∈ E |mXx2k ≤ 1}.k=1Найдем P (X, W ). Отметим, что каждый частный критерий WJ (x)го вогнут (докажите) и P (X, W ) = S(X, W ). Условие (2) зависитс точностью до положительного множителя. Поэтому на вектор αmP|αk | = 1.

Возьмем сначалано наложить условие нормировки:k=1внутреннюю точку множества X, то естьL(x0 ) = {α ∈ E m |mPmP2k=1(x0k )строот αможx0 −< 1. В этом случае|αk | = 1}. Найдем градиент каждого частного кри-k=1терия−xkWJ (x)± 1,=sxkmP21−xkk=1где +1, если k ∈/ J и −1, если k ∈ J. Отсюда условие (2) запишется в виде(α, WJ0 (x0 )) = s−(x0 , α)1−mPk=1−(x0k )2Xαk +k∈JXαk > 0(2)k∈J/для всех J ⊂ K. Покажем, что эта система неравенств эквивалентна одномуmPнеравенству. Действительно, возьмем J = {k | αk ≥ 0}. Тогда −αk +k∈JmPαk = −k∈J/mP|αk | = −1 − наименьшее значение суммы. Отсюда из (2)k∈J−(x0 , α)s1−mPk=1− 1 > 0.(x0k )2Это одно из неравенств в (2).

Но все остальныеследуют из него. Итак, x0 ∈/smP(x0k )2 ⇔ max0 [−(x0 , α)] >S(X, W ) ⇔ ∃α ∈ L(x0 ) : −(x0 , α) > 1 −α∈L(x )k=1smP1−(x0k )2 .k=1Найдем максимум, стоящий в левой части последнего неравенства. Имеем−(x0 , α) ≤ max |x0j |1≤j≤mmXk=18|αk | = max |x0j | = |x0l |,1≤j≤mгде равенство достигается при α = (0, ..., +1 , ...0). Получили max0 [−(x0 , α)] =|{z}α∈L(x )lmax |x0j |.

Итак,1≤j≤mvumXu00tx ∈/ S(X, W ) ⇔ max |xj | > 1 −(x0k )2 .1≤j≤mk=1ОтсюдаvumXu00(x0k )2 .x ∈ S(X, W ) ⇔ max |xj | ≤ t1 −1≤j≤mk=1Это неравенство и задает множество S(X, W ) = P (X, W ) внутри X.mPЕсли x0 принадлежит границе множества X, то есть(x0k )2 = 1, тоk=10точка не будет оптимальной по Парето, так как малоеs смещение от x вдольmP(xk )2 .радиуса приведет к резкому возрастанию корня 1 −k=1Пусть m = 2. Тогда P (X, W ) задается двумя неравенствами222222(x01 ) ≤ 1 − (x01 ) − (x02 ) , (x02 ) ≤ 1 − (x01 ) − (x02 )и представляет собой пересечение двух эллипсов.Рассмотрим теперь общую задачу принятия решений. Пусть X − множество стратегий.Определение.

Бинарным отношением R на множестве X называется подмножество R ⊂ X × X.Бинарное отношение R здесь интерпретируется следующим образом: если (x, x0 ) ∈ R, то для ЛПР стратегия x лучше стратегии x0 (или не хуже,чем x0 ). Вместо (x, x0 ) ∈ R обычно используют более простую запись xRx0 .Если (x, x0 ) ∈/ R, то будем писать xRx0 .Бинарное отношение называется:а) рефлексивным, если xRx ∀x ∈ X;б) антирефлексивным, если xRx ∀x ∈ X;в) симметричным, если xRy ⇒ yRx ∀x, y ∈ X;г) асимметричным, если xRy ⇒ yRx ∀x, y ∈ X;д) транзитивным, если xRy, yRz ⇒ xRz ∀x, y, z ∈ X;г) ацикличным, если 6 ∃x1 , ..., xk ∈ X : x1 Rx2 R...Rxk Rx1 .Рассмотрим примеры. R − бинарное отношение сравнения стратегийпо векторному критерию в нестрогом смысле (по Парето) или в строгомсмысле (по Слейтеру). Это транзитивные, асимметричные отношения.Упражнение.

Докажите, что антирефлексивное транзитивное бинарноеотношение ациклично.9Определение. МножествоC(X, R) = {x0 ∈ X | xRx0 ⇒ x0 Rx}(1)называется ядром бинарного отношения R.По смыслу если x0 ∈ C(X, R) и x не хуже, чем x0 , то и x0 не хуже, чем x.Если бинарное отношение R асимметрично, то ядру можно дать эквивалентное, более удобное определение:C(X, R) = {x0 ∈ X | 6 ∃ x ∈ X : xRx0 }.(2)Докажем, что в этом случае множества (1) и (2) совпадают. Пусть x0 ∈ (1).Докажем, что x0 ∈ (2). Действительно, если ∃ x ∈ X : xRx0 , то по свойствуасимметричности x0 Rx, что противоречит определению (1). Обратно, пустьx0 ∈ (2), докажем, что x0 ∈ (1).

Но это очевидно, поскольку 6 ∃ x ∈ X : xRx0и нет посылки для импликации из (1).Для отношений сравнения по Парето и Слейтеру соответствующими ядрами являются множества P (X, W ) и S(X, W ).Упражнение. Пусть X − конечное множество, а бинарное отношение Rациклично. Докажите, что ядро C(X, R) не пусто.Пример. Пусть X = {x1 , x2 , x3 }, а бинарное отношение задано ориентированным графом:* x2 6x1YHHHHHHHH?x3Рис. 11.4Здесь отношение R не является асимметричным, так как x2 Rx3 Rx2 .

Поэтому используем первое определение ядра: C(X, R) = {x3 }. Если бы мыиспользовали второе определение, то ядро оказалось бы пустым.В качестве приложения общей задачи принятия решений поставим задачу сокращения множества оптимальных по Парето стратегий P (X, W ) наоснове экспертной информации. Подход был предложен В.В.Подиновским.Начнем с примера. Ученики x1 и x2 имеют следующие оценки по двумм лпредметам (критериям), математике и литературе: x1 3 5 . Ученикиx2 5 4не сравнимы по векторному критерию.

Однако, сравнение возможно, еслиесть экспертная информация о сравнительной важности или равноценности критериев. Если предметы равноценны, то ученик x2 учится одинаковос гипотетическим учеником x3 | 4 | 5 |, который учится лучше ученика x1 .10Поэтому ученик x2 учится лучше, чем x1 . Пусть математика важнее литературы.

Тогда x2 учится лучше x3 , так как по более важному предмету у x2пятерка. Следовательно, по транзитивности x2 учится лучше, чем x1 . Еслилитература важнее математики, то ученик x3 учится лучше x2 , но x1 и x2не сравнимы, поскольку x1 имеет пятерку по более важному предмету.Теперь проведем необходимую формализацию. Будем говорить, что частные критерии Wi (x) и Wj (x) однородны, если max Wi (x) = max Wj (x) иx∈Xx∈Xmin Wi (x) = min Wj (x), то есть критерии Wi (x) и Wj (x) имеют одинаковыеx∈Xx∈Xдиапазоны изменения.Если критерии Wi (x) и Wj (x) не являются однородными и не являютсяконстантами, то их можно сделать однородными, заменив критерий Wj (x)на критерий αWj (x) + β, где α > 0 и β соответствующим образом подобранные константы.Упражнение.

Найдите явные выражения для констант α и β.В дальнейшем будем считать, что в векторном критерии W (x) все частные критерии попарно однородны.Пусть I = {1, ..., s} − множество номеров критериев. Информация отЛПР о сравнительной важности или равноценности критериев задана множествами A1 , A2 ⊂ I ×I. Здесь A1 − множество пар (r, t) номеров равноценных критериев, A2 − множество таких пар (r, t), что критерий Wr (x) важнеекритерия Wt (x). A1 и A2 можно рассматривать как бинарные отношения наI : A1 − отношение равноценности критериев, а A2 − отношение их строгогопредпочтения. Естественно предположить, что отношение A1 симметричнои транзитивно, отношение A2 асимметрично и транзитивно.

Информация,выраженная в бинарных отношениях A1 и A2 , должна быть непротиворечивой в том смысле, что нельзя построить цепочку вида rB1 tB2 ...Bk r, гдеBi = A1 или A2 и не для всех i Bi = A1 . Например, если информациянепротиворечива, то нельзя построить цепочку вида 1A1 2A2 3A1 1.Непротиворечивость экспертной информации можно задать следующимспособом. Определим на множестве I бинарное отношение: rΦt выполненотолько в том случае, когда существует цепочка i0 B1 i1 B2 ....Bk ik , где i0 =r, ik = t, а каждое бинарное отношение Bl , l = 1, ..., k, равно либо A1 ,либо A2 и среди них есть по крайней одно отношение A2 . Нетрудно видеть,что бинарное отношение Φ транзитивно.

Непротиворечивость информациисостоит в том, что бинарное отношение Φ антирефлексивно.В евклидовом пространстве E s векторных оценок y = W (x) определимследующие бинарные отношения.Отношение Парето −P = {(y, y 0 ) ∈ E s × E s | yi ≥ yi0 , i = 1, ..., s, y 6= y 0 }.Для пары (r, t), r 6= t и вектора y введем вектор y rt , полученный из y перестановкой r-й и t-й компонент.Пусть rA1 t. Определим бинарное отношение Srt на E s : ySrt z ⇔ z = y rt .Если критерии Wr и Wt равноценны для ЛПР, то и векторные оценки y иz равноценны для него при ySrt z.11Пусть rA2 t. Определим бинарное отношение Trt : yTrt z ⇔ z = y rt , yr >yt .