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

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

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

В соответствии с основной теоремой матричных игр, если платежная матрица не имеет седловой точки, то имеется пара оптимальных смешанных стратегий SA=||p1, p2, ..., pm|| и SB=||q1, q2, ..., qn||, применение которой обеспечивает игрокам получение цены игры .

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

(2.25)

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

(2.26)

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

, (2.27)

Где x1, x2, ... xm - неотрицательные переменные.

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

P1+p2+...+pm=1,

Переменные x1, x2, ... xm удовлетворяют условию

. (2.28)

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

Min L(x)=x1+x2+ ... +xm. (2.29)

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

, (2.30)

, . (2.31)

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

. (2.32)

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

, (2.33)

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

, (2.34)

Где y1, y2, ..., yn - неотрицательные переменные.

В силу того, что q1+q2+...+qn=1, переменные y1, y2, ..., yn удовлетворяют условию

. (2.35)

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

Max L(y)=y1+y2+ ... +ym. (2.36)

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

Оптимальная стратегия SB=||q1, q2, ..., qn|| игрока В определяется из решения двойственной задачи линейного программирования по формулам:

, . (2.37)

Таким образом, оптимальные стратегии SA=||p1, p2, ..., pm|| и SB=||q1, q2, ..., qn|| матричной игры Mxn с платежной матрицей ||aij|| могут быть найдены путем решения пары двойственных задач линейного программирования:

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

При этом

, (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+Х31; 2х1+Х2+3Х31; 3х1+Х2+Х31; XI0, .

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

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

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

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

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

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

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

У1=; у2=; у3=; max L (y)= .

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

;

.

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

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

Получаем x1=; x2=; x3=; max L (x)= .

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

.

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

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

< Предыдущая		Следующая >