38.Решение матричных игр МхN (сведение к задаче линейного программирования).

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

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

Σ а_ij p_i>= ν

ⁱ

Обозначая далее

x_i= p_i/ ν

исходное неравенство можно переписать следующим образом

Σ а_ij х_i>=1 и Σ х_i>=1/ν

^{i i}

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

Σ х_i → min

ⁱ

Σ а_ij х_i>=1

ⁱ

Рассуждая аналогичным образом со стороны игрока В – он стремиться сделать свой гарантированный проигрыш минимальным. И вводя обозначения:

y_i= q_i/ ν

и учитывая, что Σ а_ij y_i<=1 получаем двойственную по отношению к

ⁱ

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

Σ y_i → max

ⁱ

Σ а_ij y_i<=1