Решение игры с платежной матрицей 3×4 сведением

Решение игры с платежной матрицей 3×4 сведением к задаче линейного программирования

ЗАДАНИЕ.   

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

Игра имеет большую размерность, попробуем ее уменьшить, выделив невыгодные стратегии и вычеркнув их из матрицы (выполняем доминирование):

1.      Все элементы столбца В3 больше или равны элементам столбца В2, поэтому вычеркиваем столбец В3

2.      Все элементы столбца В4 больше или равны элементам столбца В2, поэтому вычеркиваем столбец В4. 

         2    4           

                           

         6    2           

                           

         3    2           

3.      Так как все элементы строки А3 меньше или равны элементам строки А2, вычеркиваем строку А3. 

         2    4           

                           

         6    2           

                           

                           

                                                                                              2    4

Получили матрицу (А1, А2, В1, В2): A =             .  

                                                                                              6    2

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

f      x( ) = +x₁      x₂ → max ,

2x₁ + 4x₂ ≤1, 

6x₁ + 2x₂ ≤1,



x x₁, ₂ ≥ 0.

g    y( ) = +y₁      y₂ → min ,

2y₁ +6y₂ ≥1, 

4y₁ + 2y₂ ≥1, 

y y₁, ₂ ≥ 0.

Решаем первую задачу симплекс-методом. Приводим к каноническому виду:

f x( ) = +x₁   x₂ → max ,

2x₁ + 4x₂ + =x₃  1,



6x₁ + 2x₂ + =x₄  1,



x x₁, ₂, x₃,x₄ ≥ 0.

Составляем симплекс-таблицу и решаем задачу преобразованием таблиц:

Находим:

1 1          3 x₁ =  , x₂ =  , f_max = . 

          10            5

1  1 y₁ = , y₂ =  ,  g_min = .

           5           10

Из решений пары двойственных задач получим цену игры и оптимальные стратегии игроков: vɶ = 1 = 10 ,  fmax 3

       10 1     1   2 1

S_A = =vY          ;         = ; ,

3  5 10   3 3

SB = vX = 10 1 ;1  = 1 2; .

3 10 5  3 3 

Оптимальные стратегии для исходной игры:

             2 1                    1 2                                    10

S_A = ;          ;0;0, S_B = ;      ;0;0,  цена игры v =  .

             3 3                    3 3                                     3