2.2. Решение матричной игры сведением к задаче линейного программирования

Пусть имеется матричная игра с платёжной матрицей A=(a_ij)_mn (m и n  произвольные). Её можно свести к следующей паре симметричных двойственных задач:

x₁+x₂+…+x_m  min,

(5.1)

y₁+y₂+…+y_n  max,

(5.2)

Переменные x_i и y_j этих задач связаны с вероятностями p_i и q_j стратегий соответственно первого и второго игроков соотношениями

x₁+x₂+…+x_m=y₁+y₂+…+y_n= (5.3)

p_i=x_i, (i=1, 2, …, m) (5.4)

q_j=y_j, (j=1, 2, …, n) (5.5)

Это означает, что для решения исходной матричной игры достаточно решить задачи (5.1), (5.2), затем по формулам (5.3) (точнее, по одной из них, так как здесь на самом деле две формулы) найти , и, наконец, по формулам (5.4) и (5.5) найти p_i (i=1, 2, …, m) и q_j (j=1, 2, …, n).

Замечание. Для решения пары двойственных задач (5.1) и (5.2) достаточно поступить следующим образом: сначала решить одну из них, например (5.2), и по её решению Y⁰=( , , …, ) с применением второй теоремы двойственности

найти решение X⁰=( , , …, ) задачи (5.1).

Пример 3. Решить матричную игру сведением её к задаче линейного программирования с матрицей .

Решение. 1) Составим пару (симметричных) двойственных задач:

x₁+x₂+x₃  min, y₁+y₂+y₃  max,

2) Решим обе задачи, например, с использованием режима «Поиск решений».

Решение первой и его сценарий  следующие:

Таким образом, x₁=0.066667, x₂=0, x₃=0.2, =0.266667, откуда =3.75, p₁=x₁=0.0666673.75=0.25, p₂=x₂=0=0, p₃=x₃=0.23.75=0.75. Таким образом, P⁰=(0.25, 0, 0.75)  оптимальная стратегия первого игрока.

Решение второй и его сценарий  следующие:

Таким образом, y₁=0.066667, y₂=0.2, y₃=0, q₁=y₁=0.0666673.75=0.25, q₂=y₂=0.23.75=0.75, q₃=y₃=0=0. Таким образом, Q⁰=(0.25, 0.75, 0)  оптимальная стратегия второго игрока.

Ответ: ((0.25, 0, 0.75), (0.25, 0.75, 0), 3.75).

2.3. Игры с «природой».

В матричных играх предполагается, что в них принимают участие два игрока, интересы которых противоположны, и играют они осознанно, каждый поступая разумно. Поэтому действия каждого игрока направлены на увеличение выигрыша (уменьшение проигрыша). Но в некоторых задачах, приводящихся к игровым, имеется неопределенность, вызванная отсутствием информации об условиях, в которых осуществляется действие (погода, покупательский спрос и т.д.). Эти условия зависят не от сознательных действий другого игрока, а от объективной действительности. Такие игры называются играми с природой. Человек (первый игрок) в играх с природой старается действовать осмотрительно, второй игрок (природа, покупательский спрос) действует случайно.

Условия игры задаются матрицей (a_ij)_mn.

Имеется ряд критериев, которые используются при выборе оптимальной стратегии. Рассмотрим некоторые из них.

1. Критерий Вальде. Рекомендуется применять максиминную стратегию. Она достигается из условия

a_ij

и совпадает с нижней ценой игры. А именно, в каждой строке A_i выбирается минимальный элемент _i= a_ij, и из выбранных элементов выбирается максимальный: = _i.

2. Критерий максимума. Он выбирается из условия

a_ij,

то есть в каждой строке A_i выбирается максимальный элемент _i= a_ij, и из выбранных элементов выбирается максимальный: = _i.

3. Критерий Гурвица. Критерий рекомендует стратегию, определяемую по формуле

max{ mina_ij +(1)maxa_ij},

где  — степень оптимизма — изменяется в диапазоне [0, 1].

При =1 критерий превращается в критерий Вальде, а при =0  в критерий максимума.

Пример 1. Применить к матричной игре с платёжной матрицей

критерии игре с «природой».

Решение. 3. Критерий Вальде: в каждой строке A_i выбирается минимальный элемент _i= a_ij:

₁= a_1j=1, ₂= a_2j=2, ₃= a_3j=3,

и из выбранных элементов выбирается максимальный: = _i=max{1, 2, 3}=3. Таким образом, первому игроку рекомендуется применить третью стратегию.

2. Критерий максимума: в каждой строке A_i выбирается максимальный элемент _i= a_ij:

₁= a_1j=6, ₂= a_2j=4, ₃= a_3j=5,

и из выбранных элементов выбирается максимальный: = _i=max{6, 4, 5}=6. Таким образом, первому игроку рекомендуется применить первую стратегию.

3. Критерий Гурвица: для определенности примем =0,4. Тогда для стратегии A₁ имеем

 minа_1j +(1)maxа_1j=0,41+(10,4)6=4;

для стратегии A₂

 minа_2j +(1)maxа_2j=0,42+(10,4)4=3,2;

для стратегии A₃

 minа_3j +(1)maxа_3j=0,43+(10,4)5=4,2;

max(49600, 56100)=56100 p.

Игроку целесообразно использовать стратегию A₃.

Ответ. В двух из трёх вариантов критериев рекомендуется принятие стратегии A₃.

Пример 4. Фирма производит медикаменты. Известно, что пик спроса на некоторые лекарственные препараты приходится на летний период (первая группа), на другие — на осенний и весенний периоды (вторая группа). Затраты на 1 усл. ед. продукции за сентябрь-октябрь составили: по первой группе — 30 р.; по второй группе — 20 р.

По данным наблюдений установлено, что фирма может реализовать в течение рассматриваемых двух месяцев в условиях теплой погоды 3100 усл. ед. продукции первой группы и 1300 усл. ед. продукции второй группы; в условиях холодной погоды  1500 усл. ед. продукции первой группы и 3500 усл. ед. второй группы.

В связи с возможными изменениями погоды ставится задача  определить стратегию фирмы в выпуске продукции, обеспечивающую максимальный доход от реализации при цене продажи 50 р. за 1 усл. ед. продукции первой группы и 35 р. — второй группы.

Решение. Фирма располагает двумя стратегиями: А₁ — в этом году будет теплая погода; А₂ — погода будет холодная.

Если фирма примет стратегию А₁ и в действительности будет теплая погода (стратегия природы B₁), то выпущенная продукция (3100 усл. ед. препаратов первой группы и 1300 усл. ед. второй группы) будет полностью реализована и доход составит

3100(5030)+1300(3520)=81500 р.

В условиях прохладной погоды (стратегия природы B₂) препараты второй группы будут проданы полностью, а первой группы только в количестве 1500 усл. ед. и часть препаратов останется нереализованной. Доход составит

1500(5030)+1300(3520)20(31001500)=17500 р.

Аналогично, если фирма примет стратегию А₂ и в действительности будет холодная погода, то доход составит

1500(5030)+3500(3520)=82500 р.

При теплой погоде доход составит

1500(5030)+1300(3520)(35001300)15=16500 р.

Рассматривая фирму и погоду в качестве двух игроков, получим платежную матрицу

	B1	B2
A1
A2

Применяем критерии игр с природой:

1. Критерий Вальде:

a_ij=max(17500, 16500)=17500 p.,

фирме целесообразно использовать стратегию A₁.

2. Критерий максимума:

max(maxa_jj)=max(81500, 82500)=82500 р.

Целесообразно использовать стратегию A₂.

3. Критерий Гурвица: для определенности примем  =0,4. Тогда для стратегии A₁ фирмы

 minа_ij +(1)maxа_ij =0,417500+(10,4)81500=49600 p.;

для стратегии A₂

 minа_ij +(1)maxа_ij =0,416500+(10,4)82500=56100 p.,

max(49600, 56100)=56100 p.

Фирме целесообразно использовать стратегию A₂.

Ответ. В двух из трёх вариантов критериев рекомендуется принятие стратегии A₂.

2.4. Упражнения. Решить геометрическим методом матричную игру с платёжной матрицей:

1. а) ; б) ;

в) ; г) .

2. а) ; б) .

3. К платёжным матрицам Упражнения 2 применить критерии игр с природой.