Использование линейной оптимизации при решении матричных игр
Пусть игра 
не имеет оптимального решения в чистых стратегиях, т.е. седловая точка отсутствует 
.
Будем считать, что все элементы платежной матрицы неотрицательны (если это не так, то можно ко всем элементам матрицы добавить некоторое число 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 – для расчета целевой функции. Введем все необходимые формулы в соответствующие ячейки. Установим все необходимые ограничения исходной задачи перед запуском Поиска решения. С помощью Поиска решения получим следующий ответ
|
Таким образом, оптимальная смешанная стратегия игрока 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 есть
.