Приведение матричной игры к задаче линейной оптимизации

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

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

Для игры размерностью m×n (табл. 6.12) при использовании нами оптимальной смешанной стратегии любая чистая стратегия оппонента приведет к нашему выигрышу не менее чем на величину цены игры , следовательно, для платежной матрицы, заданной табл. 6.12, имеем:

Таблица 6.12

			…		…
			…		…
			…		…
…	…	…	…	…	…	…	…
			…		…
…	…	…	…	…	…	…	…
			…		…
			…		…

, ,

.

Разделив эти соотношения на положительную величину , введем обозначения , и получим:

, ,

.

Так как наша цель максимизировать цену игры, то критерий – это

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

,

, .

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

Дата добавления: 2014-12-07