Решение игр mхn. Эквивалентные задачи линейного программирования

Пусть имеется матричная игра mxn без седловой точки с матрицей выигрышей ||a_ij||. Допустим, что все выигрыши a_ij положительны (этого всегда можно добиться, прибавляя ко всем элементам матрицы достаточно большое число С; от этого, как уже отмечалось, цена игры увеличится на C, а оптимальные решения S_A и S_B не изменятся).

Если все aij  положительны, то и цена игры  при оптимальной стратегии тоже положительна, т.к. .

В соответствии с основной теоремой матричных игр, если платежная матрица не имеет седловой точки, то имеется пара оптимальных смешанных стратегий S_A=||p₁, p₂,..., p_m|| и S_B=||q₁, q₂,..., q_n||, применение которой обеспечивает игрокам получение цены игры .

Найдем вначале S_A. Для этого предположим, что игрок В отказался от своей оптимальной смешанной стратегии S_B и применяет только чистые стратегии. В каждом из этих случаев выигрыш игрока А будет не меньше, чем :

 

              (2.25)

 

Разделив левую и правую часть каждого из неравенств (2.25) на положительную величину v и введя обозначения:

 

       (2.26)

запишем неравенства (2.25) в следующем виде:

 

,                (2.27)

где x₁, x₂,... x_m - неотрицательные переменные.

В силу того, что

p₁+p₂+...+p_m=1,

переменные x₁, x₂,... x_m  удовлетворяют условию

.                               (2.28)

Учитывая, что игрок А стремится максимизировать , получаем следующую задачу линейного программирования: найти неотрицательные значения переменных x₁, x₂,... x_m такие, чтобы они удовлетворяли линейным ограничениям - неравенствам (2.27) и обращали в минимум линейную функцию этих переменных:

 

min L (x)=x₁+x₂+... +x_m.              (2.29)

 

Из решения задачи линейного программирования находим цену игры  и оптимальную стратегию Sa по формулам:

,                                              (2.30)

, .               (2.31)

Аналогично находим оптимальную стратегию S_В игрока В. Предположим, что игрок А отказался от своей оптимальной стратегии S_A и применяет только чистые стратегии. Тогда проигрыш игрока В в каждом из этих случаев будет не больше, чем :

.              (2.32)

Разделив левую и правую части каждого их неравенств (2.32) на положительную величину  и введя обозначения:

,        (2.33)

запишем неравенство (2.32) в следующем виде:

,             (2.34)

где y₁, y₂,..., y_n - неотрицательные переменные.

В силу того, что q₁+q₂+...+q_n=1, переменные y₁, y₂,..., y_n удовлетворяют условию

.                              (2.35)

Учитывая, что игрок В стремится минимизировать положительную цену v (свой проигрыш), получаем задачу линейного программирования: найти неотрицательные значения переменных y₁, y₂,..., y_n такие, чтобы они удовлетворяли линейным ограничениям (2.34) и обращали в максимум линейную функцию этих переменных:

 

max L (y)=y₁+y₂+... +y_m.   (2.36)

 

Эта задача является двойственной по отношению к задаче, представленной условиями (2.27) и (2.29).

Оптимальная стратегия S_B=||q₁, q₂,..., q_n|| игрока В определяется из решения двойственной задачи линейного программирования по формулам:

, .                   (2.37)

Таким образом, оптимальные стратегии S_A=||p₁, p₂,..., p_m|| и S_B=||q₁, q₂,..., q_n|| матричной игры mxn с платежной матрицей ||a_ij|| могут быть найдены путем решения пары двойственных задач линейного программирования:

 

Прямая (исходная) задача	Двойственная задача
, , ; , .	, , ; , .

 

При этом

,      (2.38)

.

 

Пример. Найти решение и цену матричной игры, платежная матрица которой имеет вид

 

Bj   Ai	B1	B2	B3
A1	1	2	3
A2	3	1	1
A3	1	3	1

 

Решение

 

1. Так как =1 не равно =3, то игра не имеет седловой точки.

2. В данной игре нет дублирующих и доминируемых стратегий.

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

Математические модели пары двойственных задач линейного программирования будут выглядеть следующим образом:

 

Прямая (исходная) задача: Найти неотрицательные переменные х1,х2,х3, минимизирующие функцию min L (x)= х 1+ х 2+ х 3, при ограничениях: х 1+3 х 2+ х 3 1; 2х 1+ х 2+3 х 3 1; 3х 1+ х 2+ х 3 1; x i 0, .

Двойственная задача: Найти неотрицательные переменные у1,у2,у3, максимизирующие функцию max L (x)=y1+y2+y3, при ограничениях:   y 1+2y2+3y3 1; 3y 1+y2+y3 1; y 1+3y2+y3 1; y j 0, .

 

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

Начальная симплекс - таблица двойственной задачи имеет вид

 

БП	у1	у2	у3	у4	у5	у6	Решение
у4	1	2	3	1	0	0	1
у5	3	1	1	0	1	0	1
у6	1	3	1	0	0	1	1
L	-1	-1	-1	0	0	0	0

ведущий столбец

 

Последующие симплекс-таблицы приведены ниже:

 

БП	у1	у2	у3	у4	у5	у6	Решение
у4	0			1		0
у1	1			0		0
у6	0			0		1
L	0			0		0

          ведущий столбец

БП	у1	у2	у3	у4	у5	у6	Решение
у4	0	0		1
у1	1	0		0
у2	0	1		0
L	0	0		0

                      ведущий столбец

 

И, наконец, получаем симплекс-таблицу, которая соответствует оптимальному решению двойственной задачи:

 

БП	у1	у2	у3	у4	у5	у6	Решение
у3	0	0	1
у1	1	0	0
у2	0	1	0
L	0	0	0

 

Оптимальное решение двойственной задачи линейного программирования следующее:

у₁= ; у₂= ; у₃= ; max L (y)= .

 

Находим оптимальную смешанную стратегию игрока В в соответствии с формулами (2.37) и (2.38):

;

.

 

Следовательно, .

 

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

 

Получаем x₁= ; x₂= ; x₃= ; max L (x)= .

 

Отсюда определим вероятности применения своих активных стратегий игроком А:

.

 

Следовательно: .

 

Таким образом, решение игры mxn сводится к решению задачи линейного программирования. Нужно заметить, что и наоборот, - для любой задачи линейного программирования может быть построена эквивалентная ей задача теории матричных игр. Эта связь задач теории матричных игр с задачами линейного программирования оказывается полезной не только для теории игр, но и для линейного программирования. Дело в том, что существуют приближенные численные методы решения матричных игр, которые при большой размерности задачи могут оказаться проще, чем симплекс - метод.

ТЕСТЫ

(В – Верно, Н – Неверно)

1. Если все элементы платежной матрицы в матричной игре положительны, то и цена игры положительна.

2. Любую матричную игру можно свести к паре двойственных задач линейного программирования.

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

4. В обратной задаче линейного программирования, к которой сводится матричная игра, ограничения получаются со знаком «».

5. Цена матричной игры, получаемая из решения прямой и обратной задач может быть различна.

 

Ответы: (1 - В; 2 - В; 3 - Н; 4 - В; 5 - Н).

 

 

ЗАДАЧИ

Решить следующие матричные игры:

1.	2	4	6	2.	-7	4	2	3.	-5	6	4
	6	2	2		0	2	1		2	4	3
	2	6	2		6	-5	-1		8	-3	1
4.	1	3	2	5.	2	1	0	6.	4	6	1
	3	1	3		1	2	1		4	4	1
	2	3	1		0	1	2		1	1	6
7.	-4	-6	-1	8.	-2	-5	2	9.	5	7	1
	-4	-4	-1		-1	1	-5		5	5	1
	-1	-1	-6		-2	-1	-2		2	2	6
10.	2	6	4	11.	3	6	9	12.	0	1	2
	6	2	6		9	3	3		2	0	0
	4	6	2		3	9	3		0	2	1