Использование линейной оптимизации при решении матричных игр

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

Будем считать, что все элементы платежной матрицы неотрицательны (если это не так, то можно ко всем элементам матрицы добавить некоторое число L, переводящее платежи в область неотрицательных значений - очевидно, при этом цена игры увеличится на L, а решение задачи не изменится). Таким образом, предполагаем, что >0.

Будем искать решение игры в смешанных стратегиях

 

;

 

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

Пусть игрок II применяет свою активную чистую j-ю стратегию, а игрок I - свою оптимальную стратегию . Тогда средний выигрыш игрока I будет равен

 

 

Учитывая, что не может быть меньше , запишем условия:

 

Разделив левую и правую части каждого из неравенств (4.4) на цену игры >0, получим

 

(4.5)

 

При использовании обозначений

 

(4.6)

 

неравенства (4.5) примут вид

 

 

где, очевидно, все , так как .

Из равенства

 

и в силу определения (4.6) следует, что переменные () удовлетворяют условию

 

 

Учитывая, что игрок I стремится максимизировать , получаем линейную функцию

 

(4.8)

 

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

 

 

минимизирующие линейную функцию (4.8) и удовлетворяющие ограничениям (4.7).

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

 

В свою очередь, оптимальная стратегия игрока II

 

 

может быть найдена из выражения

 

где - неотрицательные переменные задачи линейной оптимизации

 

 

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

В этой системе неравенств переменные

 

 

Таким образом, оптимальные стратегии

 

и

игры с платежной матрицей () могут быть найдены путем решения симметричной пары двойственных задач линейной оптимизации.

 

Исходная задача Двойственная задача

 

Цена игры и вероятности применения стратегий игроками I и II равны

 

 

2. Решение матричных игр в смешанных стратегиях с помощью Excel

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

 

Пример 1

 

В качестве примера применения информационных технологий Excel найдем решение парной игры с платежной матрицей

II I

 

Решение

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

 

 

Решим исходную и двойственную задачи с помощью Excel.

Внесем данные на рабочий лист в соответствии с Рис. 4.1.

матричный игра решение линейный

Рис. 4.1. Данные для решения исходной задачи примера 1

 

В ячейки E3:E6 введем формулы для расчета функций – ограничений, ячейки B9:D9 отведем для переменных , ячейку B15 – для расчетного значения цены игры , диапазон ячеек F12:H12 – для расчетных значений вероятностей применения стратегий игроком I, и, наконец, ячейку F9 – для расчета целевой функции. Введем все необходимые формулы в соответствующие ячейки. Установим все необходимые ограничения исходной задачи перед запуском Поиска решения. С помощью Поиска решения получим следующий ответ

 

x1 x2 x3   ЦФ     0,020182 0,02474 0,003255   0,048177                           P1 P2 P3         0,4189 0,5135 0,0676 g           20,75676

 

 

Таким образом, оптимальная смешанная стратегия игрока I:

 

 

Решим двойственную задачу. Во избежание возможных ошибок расположим данные для ее решения на отдельном рабочем листе Excel (Рис. 4.2.).

 

Рис. 4.2 Данные для решения двойственной задачи примера 1

 

Ввод данных и формул производится аналогично предыдущему случаю. Поиск решения дает ответ:

 

U	0,0026		Q1=U1*	0,0541	ЦФ
U	0,0195		Q2=U2*	0,4054	0,048177
U	0,0000		Q3=U3*	0,0000	
U	0,0260		Q4=U4*	0,5405	20,75676

 

Таким образом, оптимальная смешанная стратегия игрока II есть

.