Решение задачи ЛП методом Данцига-Вульфа

27 вариант

 

27(П)

9	–2	5	1
–5	0	–2	1
4	3	–1	7
8	–3	4	–2

 

Пример решения игровой задачи

Найти графическое решение (используя свойство доминирования) игры двух лиц с нулевой суммой. Строки - стратегии игрока А; столбцы  – стратегии игрока В. В приведенной ниже матрице платежи - проигрыши для игрока А.

 

	B1	B2	B3	B4
A1	9	–2	5	1
A2	–5	0	–2	1
A3	4	3	–1	7
A4	8	–3	4	–2

Решение:

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

	B1	B2	B3	B4	max
A1	9	–2	5	1	9
A2	–5	0	–2	1	1
A3	4	3	–1	7	7
A4	8	–3	4	–2	8
min	-5	-3	-2	-2	1/-2

Из этих оценок определяем:

max _i min _j(платежей) =n_н=-2 - нижняя цена игры,  
min _j max _i(платежей) =n_в =1- верхняя цена игры.

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

Решение такой задачи можно найти графически только в том случае, если у одного из игроков 2 стратегии. Применим свойство доминирования для уменьшения числа стратегий.

Из матрицы уберем те стратегии, которые ведут к худшему результату: для игрока A (большим проигрышем). В результате сравнения B₂ и B₄ видим, что стратегии B₂ менее эффективна, чем B₄ при любых стратегиях игрока A.

	B1	B3	B4
A1	9	5	1
A2	–5	–2	1
A3	4	–1	7
A4	8	4	–2

 

Далее, для игрока A стратегия A₂ эффективней, чем стратегия A₁(меньше проигрывает) при любых стратегиях игрока B

	B1	B3	B4
A2	–5	–2	1
A3	4	–1	7
A4	8	4	–2

 

В результате сравнения A₂ и A₃ видим, что стратегии A₃ менее эффективна, чем A₂ при любых стратегиях игрока B.

В результате получим следующую  матрицу:

	B1	B2	B4
A2	–5	–2	1
A4	8	4	–2

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

Для игрока A:

Оси ординат соответствуют стратегиям A2 и A4 и на них откладываются проигрыши игрока A. При фиксированной стратегии игрока B проигрыши игрока A зависит от вероятности применения его стратегий линейно.

 

Графические построения показаны на рис.1. По оси абсцисс  отложены вероятности применения стратегий. Гарантированные минимальные проигрыши игрока A лежат на верхней грани, выделенной жирной линией. Очевидно, что игрок A стремится к минимальному гарантированному проигрышу, который достигается в точке М. Найдем координаты точки М:

 

1) уравнение прямой, характеризующей проигрыши игрока A при фиксированной стратегии B2:

y=6x-2;

2) уравнение прямой, характеризующей проигрыши игрока A при фиксированной стратегии B4:

y=1-3x;

 

3) находим пересечение этих прямых:

6x - 2= 1-3x;

отсюда получаем: x=0.33 – это вероятность применения стратегии A4, (1 - x)=0,66 – вероятность применения стратегии A2; y=1-3*0.33=0 – это цена игры - n.

Следовательно, оптимальное решение игрока A, состоит в применении стратегии A4 с вероятностью P_A4=0.33 и стратегии A2 с вероятностью P_A2=0.66. Такое поведение гарантирует ему средний проигрыщ n=0 .

А теперь можно найти  решение для игрока B:

Его активные стратегии  это B2 и B4. Вероятности применения этих стратегий находятся построением графика, аналогичного вышеприведенному для игрока B, но оси ординат соответствуют активным стратегиям игрока A (рис.2).

 

Найдем координаты точки  М:

1) уравнение прямой, характеризующей выигрыши игрока B при фиксированной стратегии A2:  y=3x-2;

2) уравнение прямой при фиксированной A4: y=4-6x;

3) находим пересечение прямых:

3x-2= 4-6x,

следовательно, x=0.66 – это вероятность применения стратегии B4, (1 - x)=0,33 - вероятность применения стратегии B2;

y=3*0.66-2=0 – это цена игры n.

Гарантированные выигрыши игрока B лежат на нижней грани. Очевидно, что игрок стремится к максимально гарантированному выигрышу, который достигается в точке М. Следовательно, оптимальное решение игрока B состоит в применении стратегии B4 с вероятностью P_B4=0.66 и стратегии B2 с вероятностью P_B2=0.33. При этом его выигрыш в среднем составит  n=0