Теория принятия решений

ГЛАВА III. ТЕОРИЯ ПРИНЯТИЯ РЕШЕНИЙ.§11. Многокритериальная оптимизация.В теории игр обычно интересуются стратегиями, оптимальными в некотором смысле для всех игроков. Например, в играх многих лиц мы рассматривали ситуации равновесия, устойчивые относительно возможных отклонений одного игрока. В данной главе предполагается, что имеется однолицо, принимающее решение (ЛПР), выбирающее стратегию x ∈ X. Приэтом возможно наличие неопределенностей. Типичным примером неопределенности является стратегия второго игрока по отношению к первомуигроку (ЛПР) в игре двух лиц. Здесь у первого игрока имеется один критерий оценки исходов − его функция выигрыша.В данном параграфе мы рассмотрим как бы противоположный случай:имеется одно ЛПР, но стратегия x ∈ X оценивается не скалярным, а векторным критерием W (x) = (W1 (x), ..., Ws (x)). При этом каждый частныйкритерий Wi (x) желательно максимизировать.

Если по смыслу этот критерий желательно минимизировать, то его можно заменить на −Wi (x). Итак,неопределенность здесь выражается неясностью цели ЛПР (несколько критериев).Задача многокритериальной оптимизации заключается в выборе x ∈ Xпри наличии векторного критерия W (x). Какую стратегию x ∈ X следует выбирать ЛПР ? Ответ на этот вопрос не прост. Дело в том, что, какправило, не существует стратегии x0 ∈ Arg max Wi (x), i = 1, ..., s.x∈XПример. Пусть X = {x1 , x2 , x3 , x4 }, s = 2 и векторные оценки стратегийрасполагаются на плоскости (W1 , W2 ), как это показано на рисунке.W621aW (x )3aW (x )4aW (x )2aW (x )- W1Рис. 11.1Здесь Arg max W1 (x) = {x2 , x3 }, Arg max W2 (x) = {x1 }.x∈Xx∈XПри решении многокритериальных задач используют стратегии, оптимальные по Парето.1Определение.

Стратегия x0 ∈ X называется оптимальной по Парето,если не существует такой стратегии x ∈ X, что Wi (x) ≥ Wi (x0 ), i = 1, ..., s,и хотя бы одно неравенство выполнено как строгое, т.е. W (x) 6= W (x0 ).Множество всех оптимальных по Парето стратегий обозначим черезP (X, W ). В рассмотренном примере P (X, W ) = {x1 , x3 }. Отметим простойспособ проверки оптимальности по Парето стратегии x. Пусть Y = W (X)− множество векторных оценок, отвечающих всевозможным стратегиямsx ∈ X. Сдвигаем неотрицательный ортант E+= {y ∈ Es | yi ≥ 0, i = 1, ..., s}sевклидова пространства E в точку W (x). Если сдвинутый ортант (включаяего границы) не содержит других векторов, кроме W (x), то x ∈ P (X, W ).Более формально условие оптимальности по Парето для стратегии x запиsсывается в виде (W (x) + E+) ∩ Y = {W (x)}.Часто используют более слабое определение оптимальности.Определение.

Стратегия x0 ∈ X называется оптимальной по Слейтеру,если не существует такой стратегии x ∈ X, что Wi (x) > Wi (x0 ), i = 1, ..., s.Множество всех оптимальных по Слейтеру стратегий обозначим черезS(X, W ). В рассмотренном примере S(X, W ) = {x1 , x2 , x3 }. Отметим, чтостратегия x тогда и только тогда является оптимальной по Слейтеру, когдаположительный ортант, сдвинутый в точку W (x), не содержит внутри себяникаких векторных оценок.Из определений следует, что P (X, W ) ⊂ S(X, W ). В приведенном примере оптимальные по Парето стратегии x1 , x3 не эквивалентны, то естьW (x1 ) 6= W (x3 ), и возникает проблема выбора x ∈ P (X, W ).Рассмотрим области приложений многокритериальных задач. Мы ужевстречались с оптимальными по Парето ситуациями в играх многих лиц.Другие примеры дает экономика.

Деятельность предприятия оцениваетсяпо нескольким показателям: прибыль, себестоимость продукции, валовойвыпуск и т.п. Активы банка оцениваются обычно по двум показателям: доходность и риск. Еще одна область приложений − проектирование сложных технических объектов. Например, конструкция автомобиля оценивается по нескольким техническим характеристикам: скорость, грузоподъемность, экономичность двигателя и т.д. В качестве простейшего примера рассмотрим задачу проектирования коробки.Имеется прямоугольник из металла размера a × b, a ≤ b. Из четырехуглов прямоугольника вырезаются квадраты со стороной x ∈ X = [0, a/2)2и материал сгибается вдоль линий, отмеченных на рис. пунктиром.xxРис. 11.2.

Развертка коробки.Пусть V (x) = x(a − 2x)(b − 2x) − объем коробки, S(x) = 4x2 − сэкономленная площадь пластины. Оба критерия желательно максимизировать.Критерий V (x) возрастает на отрезке [0, x∗ ] и убывает на полуинтервале[x∗ , a/2), где√a + b − a2 − ab + b2∗x =.6Следовательно, P (X, W ) = [x∗ , a/2).Решение многокритериальной задачи будем понимать в следующем смысле. Сначала находим множество P (X, W ) или S(X, W ).

Затем используетсякакой-либо метод сужения этих множеств, т.е. выделяются подмножестваP 0 ⊂ P (X, W ) или S 0 ⊂ S(X, W ). Окончательный выбор стратегии из P 0или S 0 производит ЛПР.Возникает вопрос: когда множество P (X, W ) не пусто?Теорема 3.1. Пусть X − компакт метрического пространства, а частные критерии Wi (x), i = 1, ..., s, непрерывны на X. Тогда множество P (X, W )не пусто.Доказательство. Рассмотрим следующую свертку векторного критерия:sPF1 (λ, x) =λi Wi (x),i=1λ = (λ1 , ..., λs ) ∈ Λ = {λ |sXλi = 1, λi > 0, i = 1, ..., s}.i=1defПокажем, что X1 (λ) = Arg max F1 (λ, x) ⊂ P (X, W ).

Заметим, что множествоx∈XX1 (λ) не пусто, поскольку функция F1 (λ, x) непрерывна на компакте X.Предположим противное, то есть ∃ x0 ∈ X1 (λ)\P (X, W ). Тогда ∃ x ∈ X :Wi (x) ≥ Wi (x0 ), i = 1, ..., s и W (x) 6= W (x0 ). Домножим каждое неравенство3на λi > 0 и сложим их. В результате получимsPλi Wi (x) >i=1sPλi Wi (x).

Этоi=1противоречит тому, что x0 ∈ X1 (λ).Таким образом, максимизируя свертку F1 (λ, x), можно получать оптимальные по Парето стратегии. Но для всякого ли x ∈ P (X, W ) ∃λ ∈ Λ : x ∈X1 (λ)? Ответ в общем случае отрицательный.Пример. Пусть s = 2, x = (x1 , x2 ) = W (x). Множество X − невыпуклыйчетырехугольник OABC − изображено на рисунке.6W2 = x2A AAAAAA BAHHHXHHHHO- W1 = x1CЗдесь ломаная ABC − множество P (X, W ). При положительных λ1 , λ2множество X1 (λ) содержится в двухточечном множестве {A, C}.Рассмотрим другую свертку F2 (λ, x) = min λi Wi (x), где λ ∈ Λ.

При ис1≤i≤sпользовании этой свертки будем предполагать, что Wi (x) > 0, ∀x ∈ X, i =1, ..., s. Это не является ограничением общности.Упражнение. Докажите, что если ко всем частным критериям добавитьположительные константы, то множество P (X, W ) не изменится.Теорема 3.2.(Ю.Б.Гермейер). Пусть все частные критерии Wi (x) непрерывны и положительны на компакте X метрического пространства. ТогдаS(X, W ) = ∪λ∈Λ X2 (λ).(1)Доказательство. Пусть λ ∈ Λ. Докажем, что X2 (λ) ⊂ S(X, W ). Предположим, что ∃ x0 ∈ X2 (λ)\S(X, W ). Тогда ∃ x ∈ X : Wi (x) > Wi (x0 ), i = 1, ..., s.Отсюда min λi Wi (x) > min λi Wi (x0 ). Это противоречит тому, что x0 ∈1≤i≤s1≤i≤sX2 (λ). Итак, доказано, что правая часть (1) содержится в левой.Обратно.

Пусть x0 ∈ S(X, W ). Найдем λ0 ∈ Λ : x0 ∈ X2 (λ0 ). Положимλ0i =Wi (x0 )1sPk=1, i = 1, ..., s.1Wk (x0 )sPТогда F2 (λ0 , x0 ) = min λ0i Wi (x0 ) =1≤i≤sk=14−11.Wk (x0 )Пусть x ∈ X, x 6= x0 .Тогда ∃ i1 : Wi1 (x) ≤ Wi1 (x0 ). ИмеемF2 (λ0 , x) = min λ0i Wi (x) ≤ λ0i1 Wi1 (x) ≤ λ0i1 Wi1 (x0 ) =1≤i≤ssX=k=11Wk (x0 )!−1= F2 (λ0 , x0 ).Отсюда следует, что x0 ∈ X2 (λ0 ).К сожалению, не всегда X2 (λ) ⊂ P (X, W ).Пример. Как и в предыдущем примере, положим W (x) = x = (x1 , x2 ) ∈X = [0, 1]2 . ЗдесьF2 (λ, x) = min[λ1 x1 , λ2 x2 ], P (X, W ) = {(1, 1)}.Рассмотрим линию уровня функции F2 (λ, x) − множество вида {x | F2 (λ, x) =C}.

На рисунке изображена линия уровня при λ1 < λ2 .6W2 = x2X2 (λ) λ1 x1 = λ2 x2Cλ2- W1 = x1OCλ1Рис. 11.3Если λ1 x1 > λ2 x2 , то линия уровня определяется уравнением F2 (λ, x) =λ2 x2 = C. Аналогично при λ1 x1 < λ2 x2 соответствующее уравнение имеетвид F2 (λ, x) = λ1 x1 = C. Это означает, что линия уровня функции F2 (λ, x)представляет собой "угол". При λ1 6= λ2 множество X2 (λ) является отрезком, содержащим оптимальную по Парето стратегию (1,1).Итак, свертка F1 (λ, x) позволяет получить лишь часть оптимальныхпо Парето стратегий, а свертка F2 (λ, x) позволяет построить множествоS(X, W ).

Однако, комбинация этих сверток F2 (λ, x) + αF1 (λ, x) позволяетстроить аппроксимации множества P (X, W ).Рассмотрим вопрос о построении множеств P (X, W ) и S(X, W ). Вначалерассмотрим случай, когда множество X конечно, то есть X = {x1 , ..., xn }.Рассмотрим способ сравнения стратегий x и x0 (в смысле Парето):Wi (x) ≥ Wi (x0 ), i = 1, ..., s, W (x) 6= W (x0 )5(1)В этом случае будем говорить, что стратегия x лучше стратегии x0 по векторному критерию W (x). Условие (1) задает бинарное отношение на множестве всех стратегий X.

Нетрудно проверить что это отношение транзитивно.Рассмотрим алгоритм построения множества P (X, W ). Пусть Π − переменное множество, состоящие из попарно несравнимых стратегий. Напомним, что X = {x1 , ..., xn }.Шаг 1. Положим Π = {x1 }.Пусть сделано k шагов по алгоритму и получено множество Π.Шаг k + 1. Берем очередную стратегию xk+1 и сравниваем ее со всемистратегиями из множества Π. Здесь могут встретится следующие случаи:а) Найдется стратегия из множества Π, которая лучше стратегии xk+1 .В этом случае стратегия xk+1 отбрасывается, множество Π не меняется ипереходим к следующему шагу.б) Стратегия xk+1 лучше некоторых стратегий из множества Π.

Всетакие худшие стратегии отбрасываем, получаем множество P 0 и полагаемΠ := Π0 ∪ {xk+1 }. Затем переходим к следующему шагу.в) Стратегия xk+1 не сравнима со стратегиями из множества Π. Тогдаполагаем Π := Π ∪ {xk+1 } и переходим к следующему шагу. В результатепосле n шагов получаем P (X, W ) = Π.Упражнение.

Покажите, что случаи а) и б) не могут выполняться одновременно.Этот алгоритм эффективен в том смысле, что не сводится к полномуперебору: если какая-то стратегия отброшена, то она не участвует в дальнейших сравнениях. Если в (1) все неравенства строгие, то алгоритм строитмножество S(X, W ).Пусть теперь множество X состоит из бесконечного числа элементов.Обычно оно задается в евклидовом пространстве ограничениями вида равенств и неравенств. На множестве X можно задать сетку из конечногочисла точек, а затем применить предложенный алгоритм.Другой подход состоит в аналитическом методе построения множестваP (X, W ), которое пытаются задать ограничениями вида равенств или неравенств. Такой подход основан на использовании условий, которым должныудовлетворять оптимальные по Парето или Слейтеру стратегии.

Приведемпример таких условий для случая вогнутых критериев на выпуклом компакте евклидова пространства E m .Определение. Пусть x0 ∈ X. Говорят, что вектор α ∈ E m задает в точкеx направление, допустимое для множества X, если найдется такое ε0 > 0,что x0 + εx ∈ X для всех ε ∈ [0, ε0 ).По смыслу, двигаясь из точки x0 в направлении α, мы некоторое времябудем оставаться в множестве X.