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

По смыслу если r-й критерий предпочтительней t-го, то оценка y предпочтительней для ЛПР оценки z, поскольку по более предпочтительномукритерию значение больше в оценке y.Определим, наконец, результирующее бинарное отношение R : yRy 0 , если существует такая последовательность z 0 , z 1 , ..., z k , что y = z 0 , y 0 = z kи z 0 H0 z 1 H1 . . . Hk−1 z k , где бинарные отношения Hi ∈ {P, Srt : rA1 t, Trt :rA2 t} и при этом не все Hl = Srt .

В этом случае будем говорить, что последовательность z 0 , z 1 , ..., z k связывает векторные оценки y и y 0Лемма 1. Бинарное отношение R − транзитивноe и ацикличное.Доказательство. Транзитивность отношения R очевидна: если yRy 0 иy 0 Ry 00 , то последовательности векторных оценок, связывающие бинарнымиотношениями y с y 0 и y 0 с y 00 следует объединить. Отсюда следует, что yRy 00 .Докажем ацикличность отношения R. Предположим, что существуеттакая последовательность векторных оценок y 1 , ..., y k , что yRy 1 R...Ry k Ry.Из транзитивности отношения R вытекает, что yRy.

Поэтому существуетследующая цепочка связанных бинарными отношениями векторных оценок: yH1 z 1 H1 . . . Hk−1 z k−1 Hk y. Если среди отношений Hl встречается отношение P, то получим противоречие, так как сумма компонент вектороввдоль цепочки либо не меняется (при Hl = Srt или Hl = Trt ), либо убывает ( при Hl = P ). Пусть отношение P в цепочке не встречается. Тогдавдоль цепочки векторы получаются перестановкой компонент и обязательно встретится отношение Trt . Без потери общности можно считать, чтоH1 = Trt .

Далее, Hl = Til jl или Hl = Sil jl при l = 2, ..., k. Тогда yr > ytи rA2 t, i2 A1 (A2 )j2 , ..., ik A1 (A2 )jk .Введем множество I+ = {i ∈ I | iΦt}. По смыслу в множество I+ входятномера критериев, более важных, чем t-й критерий. Нетрудно видеть, чтоr ∈ I+ , t ∈/ I+ .

Действительно, из rA2 t следует, что rΦt, а tΦt вытекает изантирефлексивности бинарного отношения Φ.Возьмем любую пару (il , jl ), l = 2, ..., k. Если jl ∈ I+ , то il ∈ I+ , поскольку из il A1 (A2 )jl Φt следует, что il Φt. Поэтому для пары (il , jl ) возможнытолько следующие случаи:1) il , jl ∈ I+ ;2) il , jl ∈/ I+ ;3) il ∈ I+ , jl ∈/ I+ .P l−1P lВ первых двух случаяхzi =zi , поскольку вектор z l полученi∈I+i∈I+l−1из вектора zперестановкой il -й и jl -й компонент.Покажем, что в третьем случае необходимо выполнено il A2 jl .

Действительно, если il A1 jl , то из симметричности отношения A1 следует, что jl A1 il Φt ⇒jl Φt ⇒ jl ∈ I+ , что противоречит выбору jl ∈/ I+ . Но il A2 jl означает, чтоz l−1 Til jl z l . Отсюда получаем неравенствоXXzil−1 >zil .i∈I+i∈I+12Следовательно,Xi∈I+yi >Xi∈I+zi1 ≥Xzi2 ≥ ... ≥i∈I+Xyii∈I+(противоречие).Пусть P (X, W ) = {x1 , ..., xm } и P (Y ) = {y i = W (xi ), i = 1, ..., m} −соответствующие векторные оценки. Задачу сужения множества P (X, W )можно сформулировать так: требуется найти ядро C(P (Y ), R) бинарногоотношения R на множестве P (Y ). Поскольку отношение R ациклично итранзитивно, а множество P (Y ) конечно, то ядро C(P (Y ), R) не пусто.Основная задача здесь состоит в следующем.

Для двух векторных оценок y и y 0 требуется выяснить, связаны ли они отношением R. В частныхслучаях эта задача решается несложно. Рассмотрим примеры.1. Пусть все частные критерии равноценны, т.е. A1 = I × I, а A2 = ∅.Чтобы сравнить векторные оценки y и y 0 , нужно сначала упорядочить ихкомпоненты, а потом сравнить их по Парето. Более формально, определимвектор θ(y) ∈ E s , образованный из компонент вектора y, расположенных впорядке убывания:θ1 (y) ≥ θ2 (y) ≥ ... ≥ θs (y),где θ1 (y) = min yi − наибольшая компонента вектора y, а θs (y) = max yi −1≤i≤s1≤i≤sнаименьшая.Лемма 2. Если yP y 0 , то θ(y)P θ(y 0 ).Доказательство.

Заметим, что θ1 (y) ≥ θ1 (y 0 ). Предположим, что найдется номер k ∈ {1, ..., s − 1}, для которого выполнены неравенстваθi (y) ≥ θi (y 0 ), i = 1, ..., k, θk+1 (y) < θk+1 (y 0 ).Но s − k компонентам θk+1 (y), ..., θs (y) вектора y должны соответствоватьстолько же компонент вектора y 0 , не превосходящих θk+1 (y), что противоречит выбору k.

Итак, θi (y) ≥ θi (y 0 ), i = 1, ..., s, и хотя бы одно из этихнеравенств − строгое.Утверждение. Если A1 = I ×I, то yRy 0 выполнено тогда и только тогда,когда θ(y)P θ(y 0 ).Доказательство. Пусть yRy 0 . Тогда существует такая последовательность векторных оценок z 0 , z 1 , ..., z k , что y = z 0 , y 0 = z k и z 0 H0 z 1 H1 . . . Hk−1 z k ,где бинарные отношения Hi ∈ {P, Srt : rA1 t} и при этом найдется такоеs, при котором Hs = P. Из леммы 2 следует, что θ(z s−1 )P θ(z s ). Для l 6= sлибо θ(z l−1 )P θ(z l ), либо θ(z l−1 ) = θ(z l ). Отсюда θ(y)P θ(y 0 ).Пусть θ(y)P θ(y 0 ).

Тогда найдется последовательность видаyH1 z 1 H2 ...Hs−1 θ(y)P θ(y 0 )Hs+1 z s+1 ...Hk y,где Hl ∈ {Srt | rA1 t}, l 6= s. Отсюда yRy 0 .13Рассмотрим конкретный пример. Пусть s = 3, а P (X, W ) = {x1 , x2 , ..., x5 }.Соответствующие векторные оценки указаны в таблицеy1y2y3y4y5345245433233254Здесь y 1 Ry 3 , y 1 Ry 4 , y 2 Ry 5 , θ(y 1 ) и θ(y 2 ) не сравнимы по P. ПоэтомуC((Y ), R) = {y 1 , y 2 } и остаются две оптимальные по Парето стратегии x1 иx2 .2.

Пусть (X, W ) = {x1 , x2 , x3 , x4 } - ученики с оценками по четырем предметам, A1 = {(1, 3)}, A2 = {(2, 4), (2, 3)}.y1y2y3y45554544445454455Здесь y 1 T24 y 3 , y 1 T23 y 2 , y 1 T24 y 3 S13 y 4 ⇒ C(P (Y ), R) = {y 1 } и остаетсяединственный наилучший ученик x1 .Рассмотрим пример использования бинарных отношений в задаче проектирования управляемых динамических объектов.Динамический объект задается системой обыкновенных дифференциальных уравненийż = f (z, u, x), z(t0 ) = z 0 ,(1)где z ∈ Z(x) = {z ∈ E m | gj (z) ≤ wj (x), j = 1, ..., l} − вектор фазовыхпеременных, x ∈ X − вектор конструктивных параметров (стратегия ЛПР)и u ∈ U − управление.К такому классу объектов относятся летательный аппарат, робот-манипулятор,электрическая цепь и т.п. Возникает вопрос, как сравнить два варианта x иx0 конструкций динамической системы?Пусть H − множество в E m . Обозначим через convH выпуклую оболочку множества H, т.

е. пересечение всех выпуклых множеств из E m ,содержащих множество H. Выпуклая оболочка convH представляет собойkPсовокупность всевозможных выпуклых комбинаций видаλj z j , гдеj=1kXλj = 1, λj ≥ 0, z j ∈ H, j = 1, ..., k.j=1Справедливо следующее утверждение: выпуклая оболочка компакта в E mявляется выпуклым компактом.Рассмотрим множествоdefG(x, z) = convf (z, U, x) = conv{f ∈ E m | f = f (z, u, x), u ∈ U }14− выпуклую оболочку векторограммы f (z, U, x) правой части системы (1).В дальнейшем предполагается, что функция f (z, u, x) непрерывна, а U −компакт евклидова пространства. Тогда векторограмма f (z, U, x) − компакт, а G(x, z) − выпуклый компакт в E m .Определим бинарное отношениеxRx0 ⇔ G(x, z) ⊇ G(x0 , z), ∀ z ∈ Z(x0 ) ⊆ Z(x0 ).(2)Интуитивно ясно, что объект x обладает бо́льшими динамическими возможностями, чем объект x0 . Это означает, что управляя объектом x, можно получить более широкое множество траекторий, чем управляя объектомx0 .1Нетрудно видеть, что бинарное отношение R транзитивно и можно решать задачу поиска ядра C(X, R).Запишем бинарное отношение R в эквивалентном виде.

Пусть S = {s ∈E m | |s| = 1} − единичная сфера в E m . Определим на S опорную функциюмножества G(x, z):δ(s, x, z) = max (f, s).f ∈G(x,z)Отметим характерное свойство опорных функций:G(x, z) ⊇ G(x0 , z) ⇔ δ(s, x, z) ≥ δ(s, x0 , z) ∀ s ∈ S.Импликация ⇒ очевидна. Импликация ⇐ доказывается с помощью теоремыоб отделяющей гиперплоскости.Сделаем следующее предположение:Z(x0 ) ⊆ Z(x) ⇔ wj (x) ≥ wj (x0 ), j = 1, ..., l.Тогда (2) можно записать в виде(δ(s, x, z) ≥ δ(s, x0 , z), ∀ s ∈ S, ∀z ∈ Z(x0 ),wj (x0 ) ≥ wj (x), j = 1, ..., l.(3)Первая группа неравенств эквивалентна включению G(x, z) ⊂ G(x0 , z), авторая − включению Z(x0 ) ⊂ Z(x). Заметим, что первую группу неравенствможно записать в виде∆(x, x0 , z) = min(δ(s, x, z) − δ(s, x0 , z)) ≥ 0 ∀ z ∈ Z(x0 ).s∈SПример.

Рассмотрим системуż 1 = z 2 , ż 2 = P u − kz 2 , z 1 , z 2 ∈ E 3 , u ∈ U = {u ∈ E 3 | |u| ≤ 1}.Это уравнения движения точечного объекта, z 1 − пространственные координаты, z 2 − скорость. Вторая группа уравнений − уравнения сил. Здесь1 Этот факт строго формулируется и обосновывается в книге Н.Н.Красовского иА.И.Субботина "Позиционные дифференциальные игры". − М.: Наука, 1974.15P − тяга, u − вектор, задающий величину и направление вектора, k −коэффициент сопротивления.

Положимx = (k, P ) ∈ X = {x | k ≤ k ≤ k, P ≤ P ≤ P }.Отметим, что скорость движения объекта ограничена. Максимальная скорость достигается при ż 2 = 0, т.е.P u − kz 2 = 0 ⇒ z 2 =P |u|PPu, |z 2 | =≤ .kkkИтак,(Z(x) =Pz = (z , z ) | |z | ≤ w1 (x) =k12)2.Теперь построим бинарное отношение R. Положим f = (f 1 , f 2 ), где f 1 =z 2 , f 2 = P u−kz 2 . Отметим, что при нахождении выпуклой оболочки G(x, z)достаточно ее построить для вектора f 2 = P u − kz 2 , поскольку компонентаf 1 = z 2 от переменных u и x не зависит.

Поэтому возьмем S = {s ∈ E 3 | |s| =1},δ(s, z, x) = max (f 2 , s) = max (P u − kz 2 , s) = P − k(z 2 , s).u:|u|≤1u:|u|≤1Аналогично для стратегии x0 = (k 0 , P 0 ) δ(s, z, x) = P 0 − k 0 (z 2 , s). Отсюда∆(x, x0 , z) = min(P − P 0 + (k 0 − k))(z 2 , s) = P − P 0 − |k 0 − k||z 2 |.s∈SЗапишем неравенства (3), задающие бинарное отношение R : xRx0 ⇔0P − P 0 − |k 0 − k||z 2 | ≥ 0 ∀ z : |z 2 | ≤ P ,k00P ≥ Pkk0m0P − P 0 − |k 0 − k| P ≥ 0 ,k0(3)0PP ≥.kk0Найдем C(X, R) = {x0 ∈ X | xRx0 ⇒ x0 Rx}. Докажем, что C(X, R) = {x0 ∈X | P 0 = P }.Пусть x0 ∈ X и P 0 < P .