Лекции по "Управленческим решениям"

Будем условно обозначать конкретную партию игры в виде

g = (x, y, h)       (3.2)

Результатом партии игры является выигрыш (или проигрыш) каждого  из игроков. Этот результат не всегда имеет количественное выражение. Однако для получения количественных оценок принимаемых решений результат игры необходимо хотя бы условно, представить числом (например, выигрыш – 1, проигрыш – 0, ничья – 0,5).

Рассмотрим одну из конкретных партий игры g = (x, y, h) и обозначим через L₁ (x, y, h) и L₂ (x, y, h) величины проигрыша первого и второго игрока соответственно. Условимся проигрышу приписывать знак «+», а выигрышу –

«-», то есть выигрыши рассматривать как отрицательные проигрыши. Общая сумма L_∑ (x, y, h) проигрышей обоих игроков в партии g = (x, y, h) равна

L_∑ (x, y, h) = L₁ (x, y, h) + L₂ (x, y, h)    (3.3)

В парной антагонистической  игре общая сумма проигрышей L_∑ (x, y, h) равна нулю: проигрыш одного игрока – выигрыш другого.

Проигрыш игрока 2 в теории игр называется потерями. С их помощью оценивают результат игры. Обозначим потери как L (x, y, h). Очевидно, что

L (x, y, h) = L₂ (x, y, h) = - L₁ (x, y, h)    (3.4)

Поскольку стратегия h является случайной, то при выбранных стратегиях x и y игроков 1 и 2 потери L (x, y, h) будут случайной величиной с распределением вероятностей P(h) на множестве H случайных стратегий. Чтобы оценить выбранные стратегии x и y игроков на бесконечном множестве партий игры, прибегнем к приему усреднения потерь L (x, y, h) по всему множеству случайных стратегий H, для чего введем понятие средних потерь L_ср(x, y), определяемых по формуле для математического ожидания случайной величины:

L_ср (x, y) =     (3.5)

Функция L_ср (x, y) в теории игр называется функцией средних потерь или просто функцией потерь. Очевидно, что при многократном повторении партий игры с одними и теми же конкретными стратегиями x и y игроков суммарный проигрыш игрока 2 (а значит и суммарный выигрыш игрока 1) стремится к величине функции средних потерь L_ср (x, y). В этом смысле последняя является характеристикой качества стратегий игроков (результат игры как бы «очищается» от влияния случайных стратегий h Є H).

В теории игр принято считать, что  парная антагонистическая игра формально  определена, если перечислены все  возможные стратегии игроков 1 и 2, то есть заданы множества стратегий X и Y, и для любых конкретных стратегий x Є X и y Є Y определена функция потерь L_ср (x, y). Таким образом, мы приходим к следующему формальному определению игры:

Игра G определяется тремя элементами X, Y, L_ср, что условно можно записать в виде

G = (X, Y, L_ср)      (3.6)

Игры, в которых каждый игрок имеет конечное число стратегий (конечные игры), удобно задавать с помощью  так называемых матриц потерь. В случае игры с нулевой суммой достаточно задавать одну матрицу. Пусть G – некая конечная игра с нулевой суммой, в которой игрок 1 имеет m возможных стратегий, игрок 2 – n возможных стратегий, то есть X и Y есть конечные множества.

X = {x₁, x₂, … x_n},

Y = {y₁, y₂, … y_n}.

Тогда матрица порядка m*n

,     (3.7)

элемент которой q_ij = L_ср (x_i, y_i), называется матрицей потерь. Элемент матрицы q_ij, очевидно, имеет смысл средних потерь игрока 2 при реализации игроками стратегии x_i и y_i, иначе – среднего платежа игрока 2 игроку 1, если игрок 1 предпринимает стратегию x_i, а игрок 2 – стратегию y_i. Отсюда другое название матрицы потерь – платежная матрица.

С использованием платежной  матрицы Q конечная парная антагонистическая игра G может быть формально определена  тремя элементами X, Y, Q, что условно можно записать в виде:

G = (X, Y, Q)      (3.8)

где

X = {x_i}, i Є 1,m – m-мерное множество возможных стратегий игрока 1;

Y = {y_i}, j Є 1,n – n-мерное множество возможных стратегий игрока 2;

Q = {q_ij}, i Є 1,m j Є 1,n – платежная матрица размера m*n.

Задание игры в виде 3.6 или 3.8 определяет ее в том только смысле, что задает все возможные  стратегии обоих игроков и  определяет средний результат игры для каждого возможного сочетания  стратегий. Непосредственное же разыгрывание каждой партии игры g = (x, y, h) регламентируется правилами игры, определяющими порядок чередования ходов и признак окончания партии игры, объем информации каждого игрока о поведении других игроков, а также сведения о случайных ходах в игре и вероятностях их возможных исходов.

Основная теорема теории игр – теорема о существовании решения игры – гласит: любая конечная антагонистическая игра имеет решение, то есть оптимальные стратегии для обоих игроков и соответствующую цену игры. Решение конечной парной антагонистической игры лежит в области чистых или смешанных стратегий. Решение в чистых стратегиях имеет место в играх с седловой точкой. Если же игра не имеет седловой точки, то ее решение лежит в области смешанных стратегий.

 

3.4. Игры с седловой  точкой

 

Для того чтобы определить понятие седловой точки, необходимо определиться с тем, что понимается под максимином и минимаксом платежной матрицы.

Максимином или нижней ценой игры называется элемент платежной матрицы, равный максимуму из минимумов по строкам матрицы. Если обозначить максимин через v₁, то

      (3.9)

Минимаксом или верхней ценой игры называется такой элемент матрицы, который равен минимуму из максимумов по столбцам матрицы. Если обозначить минимакс через v₂, то

     (3.10)

Например:

	y1	y2	y3	y4	qi min
x1	3	8	2	3	2
x2	4	3	8	5	3 maxmin
x3	7	2	1	6	1
qj max	7	8	8	6 minmax

 

Очевидно, что величины максимина и минимакса связаны  соотношением

v₁ ≤ v₂       (3.11)

Стратегия игрока 1, соответствующая максимину v₁ называется максиминной стратегией. Стратегия игрока 2, соответствующая минимаксу v₂, называется минимаксной стратегией. Минимаксная и максиминная стратегии образуют пару минимаксных стратегий.

Если игрок 1 будет придерживаться своей максиминной стратегии, то он независимо от поведения противника гарантирует себе выигрыш не менее чем максимин v₁, то есть не менее нижней цены игры. Если игрок 2 будет придерживаться своей минимаксной стратегии, то он гарантирует себе, что проиграет не более чем минимакс v₂, то есть не более верхней цены игры. Минимаксные стратегии часто называют стратегиями предельной осторожности или стратегиями гарантированного результата (выигрыша или проигрыша).

Принцип осторожности, диктующий  игрокам выбор соответствующих стратегий (максиминной или минимаксной), является в теории игр одним из основных и называется принципом минимакса. Он вытекает из предположения о разумности каждого игрока, стемящегося в операции достигнуть цели, противоположной цели противника.

Существуют игры, для которых максимин равен минимаксу, то есть v₁ = v₂. Соответствующий элемент платежной матрицы называется седловой точкой. Иначе, седловой точкой называется элемент, который является одновременно минимальным в своей строке и максимальным в своем столбце.

	y1	y2	y3	qi min
x1	1	3	10	1
x2	6	4	5	4 maxmin
x3	8	3	2	2
qj max	8	4 minimax	10

 

Элемент платежной матрицы, соответствующий ее седловой точке (если она существует), называется чистой ценой игры. Обозначим ее через v. Совокупность минимаксных стратегий и чистая цена игры v являются решением игры с седловой точкой или, иначе, решением игры в чистых стратегиях (стратегия, выбираемая игроком в результате сознательного акта, без привлечения какого-либо случайного механизма).

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

 

3.5. Методы решения игр.

 

Покажем, что любая  конечная антагонистическая игра m*n может быть сведена к задаче линейного программирования и, следовательно, решена методами линейного программирования, в частности точными, например симплекс-методом.

Рассмотрим конечную игру G = (X, Y, Q) размера m*n, где множества стратегий X = {x_i}, Y = {y_i} и платежная матрица Q = |q_ij|, i Є 1,m, j Є 1,n заданы.

Поскольку в реальных ситуациях чистых стратегий не бывает, требуется найти решение игры в смешанных стратегиях (добавляется  фактор вероятности), то есть  цену игры v_p и две оптимальные смешанные стратегии P¹ = (p¹_i) и P² = (p²_i), где P¹ и P² – вероятностные векторы, компоненты которых удовлетворяют условиям:

      (3.12)

     (3.13)

Будем сначала искать оптимальную стратегию P¹ игрока 1. При ее определении будем исходить из свойств оптимальной стратегии, а именно будем учитывать, что эта стратегия должна обеспечить игроку 1 выигрыш не меньший v_p, при любом поведении противника, и равно v_p – при его оптимальном поведении.

Цена игры v_p пока неизвестна. Будем считать, что v_p > 0. Чтобы это условие выполнялось, достаточно, чтобы все элементы платежной матрицы Q = |q_ij| были неотрицательными, то есть q_ij ≥ 0. Этого всегда можно добиться, прибавляя ко всем элементам q_ij достаточно большое число M. При этом цена игры увеличится на М, а оптимальные стратегии не изменятся.

Предположим, что игрок 1 применяет свою смешанную стратегию P¹, а игрок 2 – чистую стратегию y_i. Тогда средний выигрыш игрока 1, обозначенный q¹_j, равен

q¹_j = = p¹₁q_1j + p¹₂q_2j + … + p¹_mq_mj, j Є 1,n  (3.14)

Поскольку ищется оптимальная  стратегия игрока 1, то его средний выигрыш q¹_j должен удовлетворять условию q¹_j ≥ v_p, откуда следует n условий:

     (3.15)

Введем обозначения 

L₁ = 1 / v_p;

z¹_i = p¹_i / v_p , i Є 1,m.

С использованием введенных  обозначений из (3.12) и (3.15) получаем:

 

Поскольку игрок 1 стремится максимизировать свой выигрыш (доставить максимум цене игры v_p), то это равносильно требованию  минимизировать величину L₁ = 1/v_p, то есть равносильно требованию

L₁ =      (3.19)

Аналогичным образом  можно найти оптимальную стратегию игрока 2.

 

 

 

 

 

5.1. Общая постановка многокритериальной детерминированной статистической ЗПР.

Пусть имеет место  некоторая операция, исход которой  зависит от действия ЛПР и некоторых  неслучайных фиксированных факторов, полностью известных оперирующей стороне и характеризующих условия протекания операций и свойства участвующих в ней объектов. Стратегию оперирующей стороны обозначим символом X. В частных случаях задачи X может быть скаляром, вектором, матрицей или еще более сложным образованием. Для определенности будем считать, что стратегия оперирующей стороны представляет собой n-мерный вектор, то есть X = (x₁, x₂, … , x_n) = (x_j), j Є 1,n.

Компоненты x_j вектора управления X связаны рядом ограничений, обусловленных конкртеным физическим и экономическим существом задачи. Эти ограничения можно представить в общем виде как условия

g_i = g_i (C_i, X) ≥ b_i, i Є 1,m     (5.1)

где g_i – некоторая функция; b_i – фиксированная скалярная величина; С_i – некоторая совокупность фиксированных величин (например, скаляр, вектор и т.п.).

Условия (5.1) определяют область Ω_X допустимых значений X. ЛПР управляет операцией, выбирая ту или иную стратегию из области Ω_X их допустимых значений.

Эффективность действий ЛПР оценивается совокупностью  критериев e₁, e₂, …, e_k, которые могут различаться своими коэффициентами относительной важности λ₁, λ₂, …, λ_k.

Критерии e_q, q Є 1,k образуют вектор критериев E = (e_q), а коэффициенты λ_q – вектор важности Λ = (λ_q). Критерии e_q, q Є 1,k, входящие в состав векторного критерия E, будем называть частными или локальными критериями. Каждый локальный критерий характеризует некоторую локальную цель операции.

Локальные критерии, в  свою очередь, могут быть как скалярами, так и векторами или какими-то более сложными образованиями.

Каждый локальный критерий e_q связан со стратегией, то есть

e_q = e_q (A_q, X), q Є 1,k      (5.2)

где A_q – некоторая совокупность фиксированных факторов.

Тогда векторный критерий Е будет представлять собой вектор-функцию от стратегии Х, то есть

Е = ( е_q (А_q,  Х) ) = Е (А, Х)     (5.3)

где А – совокупность констант, соответствующая совокупности локальных констант А_q, q Є 1,k.

Пусть цель ЛПР состоит  в увеличении возможных значений всех локальных критериев эффективности. Средством достижения цели операции является соответствующий выбор стратегии Х из области Ω_Х ее допустимых значений.