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

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

Соотношения между и ценой игры можно формализовать в виде системы неравенств:

(13.1)

причём и

Аналогично соотношения между и ценой игры можно формализовать в виде системы неравенств:

(13.2)

и

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

и

разделим неравенства системы (13.1) и (13.2) на Получим следующие соотношения (табл. 13.1).

Таблица 13.1

Игрок А	Игрок В
Стремится максимизировать выигрыш	Стремится минимизировать проигрыш

Очевидно, в левом столбце табл. 13.1 записана стандартная задача минимизации линейного программирования, а в её правом столбце − стандартная задача максимизации линейного программирования. Кроме того, представленные в табл. 13.1 задачи линейного программирования образуют пару симметричных взаимодвойственных задач. Решив данные задачи линейного программирования (см. пункт 9) симплекс-методом, получим и решение матричной игры:

− цену игры ;

− оптимальные смешанные стратегии и

Поиск по сайту: