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

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

Рассмотрим игру двух лиц с нулевой суммой, заданной платежной матрицей

Если платежная матрица не имеет седловой точки, т.е. a<b и a≤n≤b, то решение игры представлено в смешанных стратегиях ,

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

Рассмотрим задачу оттискивания оптимальной стратегии игрока A, для которого имеют место ограничения

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

Где (1.2)

По условию Разделим обе части этого равенства на n.

Оптимальная стратегия игрока А должна максимизировать величину n, следовательно, функция

должна принимать минимальное значение.

Таким образом, получена задача линейного программирования:

найти минимум целевой функции (1.3) при ограничениях (1.1), причем на переменные наложено условие неотрицательности (1.2). Решая ее, находим значения , i= и величину 1/n, затем отыскиваются значения .

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

Рассмотрим задачу оттискивания оптимальной стратегии игрока B, для которого имеют место ограничения

матричный игра экономический

Преобразуем систему ограничений, разделив все члены неравенства на n.

Где (1.5)

По условию Разделим обе части этого равенства на n.

Оптимальная стратегия игрока B должна минимизровать величину n, следовательно, функция

должна принимать максимальное значение.

Получена задача линейного программирования: найти максимум целевой функции (1.6) при ограничениях (1.4), причем на переменные наложено условие неотрицательности (1.5).

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

Пример: найти решение игры, заданной матрицей

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

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