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

Пусть задана платежная матрица игры

Для оптимальной стратегии первого игрока и цены игры u выполняется неравенство или (разделив на u) обозначая получим:

Так как первый игрок стремится получить максимальный выигрыш, то он должен обеспечить минимум величине 1/u. Ñ учетом этого определение оптимальной стратегии сводится к нахождению минимума функции при условиях

(j = 1..n); yi³0 (i = 1..m).

Аналогично определение оптимальной стратегии второго игрока сводится к нахождению максимума функции при условиях

(i = 1..m); xj³0 (j = 1..n), где = zj /u.

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

Прямая задача Двойственная задача

Используя решения пары задач, можно выявить оптимальные стратегии и цену игры:

Итак, решение игры с использованием методов линейного программирования включает этапы:

составляют пару двойственных задач, эквивалентных данной игре;

определяют оптимальные планы двойственных задач;

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

Пример 9.9

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

Решение.

Пара двойственных задач:

Из решения пары задач:

u0= (1/3; 2/3; 0);

z0= (0; 1/3; 2/3).

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

Пусть задана симметричная пара двойственных задач:

.

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

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

Пример 9.10

L0= 19,71.

Решение.

Тогда матрица игры будет