Симплекс метод в теории игр

№5.Симплекс метод в теории игр

Лабораторная работа № 5
Тема: Симплекс - метод в теории игр
Цель работы: Научиться составлять пару двойственных задач линейного программирования для матричных игр, с использованием симплекс-метода решать их.
Рассмотрим игру mn с m стратегиями A₁ ... A_m игрока A и n стратегиями B₁ ... B_n игрока B. Задана матрица игры
(5.1)
Требуется найти решение игры, т.е. две оптимальные смешанные стратегии игроков A и B:
,
где - вероятности применения чистых стратегий.
Оптимальная стратегия S_A должна обеспечить выигрыш, не меньший , при любом поведении противника, и выигрыш, равный , при его оптимальном поведении, т.е. при стратегии S_B . Т.е. для любой чистой стратегии игрока B имеем , при этом естественно желание игрока A максимизировать свой выигрыш. Таким образом, для игрока A имеем задачу:
Найти max 
при условиях
(5.2)
Для игрока B задача приобретает вид:
Найти
при условиях
(5.3)
В силу того, что игрок B стремится минимизировать проигрыш, при использовании противником любой чистой стратегии, B проиграет меньше, чем , и , если A применит свою оптимальную стратегию. Здесь  - цена игры.
Полагаем, что >0. Если это не так, то этого можно добиться прибавлением к элементам платёжной матрицы одного и того же положительного числа. Разделив каждое из соотношений задач (5.2)-(5.3) на  и положив

получим для второго игрока:


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

при условиях (5.4)
Двойственная задача (для первого игрока):.найти значения , такие что

при условиях (5.5)
Так как каждая игра имеет решение, то оптимальные решения пары двойственных задач существуют и .
Если одна из задач этой игры решена симплекс-методом, то оптимальное решение другой содержится в последней симплекс таблице исходной задачи.
Оптимальные стратегии матричной игры рассчитываются по формулам
(5.6).
Таким образом решение задачи симплекс-методом включает следующие этапы:

1. 
   Если в матрице есть отрицательные элементы, то вычесть из всех число S=min .
   

1. 
   Сформулировать задачи вида (5.4)-(5.5) для обоих игроков.
   

1. 
   Решить обе задачи симплекс-методом, т.е. найти оптимальные значения , .
   

1. 
   Найти оптимальные стратегии , по формулам (5.6) и цену игры .
   

1. 
   Найти цену исходной игры добавлением к  величины S.
   

Пример. Найти методом линейного программирования решение игры, заданной матрицей:

Найдем оптимальную смешанную стратегию S_A^*=(p₁,p₂,p₃) игрока А. Условия (5.5) примут вид:

Минимизируемая линейная функция .
Перейдем от условий-неравенств к условиям равенствам, введя переменные x₄, x₅, x₆, каждая из которых входит в одно уравнение с коэффициентом -1, в остальные с коэффициентом равным 0. Функция L принимает вид x₁+x₂+x₃+0x₄+0x₅+0x₆. Вводим базисные переменные z₁, z₂, z₃ получаем задачу:
minZ=
при условиях:


.
Здесь M - бесконечно большое число.
Заносим данные в симплекс-таблицу и находим решение задачи.
Из таблицы видно, что функция Z принимает минимальное значение min Z=1/5 при x₁=2/21, x₂=2/21, x₃=1/7. Отсюда =1/Z=3 - цена исходной игры, p₁=x_1=2/213=2/7, p₂=x_2=2/213=2/7, p₃=x_3=1/73=3/7.
Таким образом найдена оптимальная стратегия игрока А S_A^*=(2/7,2/7,3/7). Аналогично можно найти оптимальную смешанную стратегию для игрока В. S_В^*=(3/6,2/6,1/6).

Коэффициенты

базисные

свобод-

1

1

1

0

0

0

M

M

M

базисные

перемен-

ные

Переменные

ные

члены