Теория принятия решений |
Конспект лекций |
Лекция №9. Симплексный метод решения матричных игр
Если у каждого из игроков больше двух возможных стратегий, то можно решение игры свести к решению задачи линейного программирования.
Рассмотрим игру, матрица которой не содержит седловой точки. Поэтому решение игры представим в смешанных стратегиях:
При оптимальной стратегии игроку 1 обеспечен выигрыш v независимо от выбора стратегий игроком 2, то есть
Цена игры v неизвестна, но можно предположить v>0. Последнее условие выполняется, если элементы игровой матрицы неотрицательны, а этого можно достигнуть, прибавляя ко всем элементам матрицы некоторое положительное число. Преобразуем систему ограничений, разделив обе части неравенства на v>0 и вводя обозначения:
Первый игрок стремится цену игры v максимизировать, значит, функция
должна принимать минимальное значение. Таким образом, получилась задача линейного программирования.
Для определения стратегии 2 игрока задача линейного программирования будет иметь после аналогичных преобразований и замены переменных следующий вид:
Таким образом, для решения игры имеем пару двойственных задач линейного программирования. Из них удобнее решать задачу на максимум с ограничениями cимплексным методом.
Пример 6. Найти решение игры, определяемой матрицей:
Решение. Элементы платежной матрицы имеют отрицательные числа, к каждому элементу матрицы А прибавим единицу и получим следующую матрицу, все элементы которой неотрицательны:
.
Эта игра не содержит седловой точки, решением игры являются смешанные стратегии
для определения которых составим теперь пару взаимно-двойственных задач:
Решим симплексным методом вторую из пары взаимно-двойственных задач на максимум (табл. 2–4), где ограничения имеют знак . Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений
Линейную функцию F представим в виде
Из последней симплекс–таблицы, определяющей оптимальный план, следует, чтo
а из соотношений двойственности следует, что
.
Следовательно, цена игры с платежной матрицей А1
а для исходной игры с платежной матрицей А:
При этом оптимальные стратегии игроков имеют вид