Теория принятия решений
Конспект лекций
назад | содержание | вперед

Лекция №9. Симплексный метод решения матричных игр

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

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

При оптимальной стратегии игроку 1 обеспечен выигрыш v независимо от выбора стратегий игроком 2, то есть

Цена игры  v  неизвестна, но можно предположить v>0. Последнее условие выполняется, если элементы игровой матрицы неотрицательны, а этого можно достигнуть, прибавляя ко всем элементам матрицы некоторое положительное число. Преобразуем систему ограничений, разделив обе части неравенства на v>0 и  вводя обозначения:

Первый игрок стремится цену игры  v  максимизировать, значит, функция

должна принимать минимальное значение. Таким образом, получилась задача линейного программирования.

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

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

Пример 6.  Найти решение игры, определяемой матрицей:

Решение. Элементы платежной матрицы имеют отрицательные числа, к каждому элементу матрицы А прибавим единицу и получим следующую матрицу, все элементы которой неотрицательны:

.

Эта игра не содержит седловой точки, решением игры являются смешанные стратегии
 для определения которых составим теперь пару взаимно-двойственных задач:

Решим симплексным методом  вторую из  пары взаимно-двойственных задач на максимум (табл. 2–4), где ограничения имеют знак . Введем три дополнительные переменные, в результате чего ограничения запишутся в виде системы уравнений

Линейную функцию  F представим в виде

Из последней симплекс–таблицы, определяющей оптимальный план, следует, чтo а из соотношений двойственности следует, что .

Следовательно,  цена игры с платежной матрицей А1

а для исходной игры с платежной матрицей А:

При этом оптимальные стратегии игроков имеют вид

 

наверх


назад | содержание | вперед