Метод линейного программирования

Антагонистическую матричную игру т х п (где т>3,п>3), не содержащую седловой точки, можно свести к паре двойственных задач линейного программирования. Рассмотрим игру т х п, заданную платежной матрицей А,

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

Эквивалентными преобразованиями можно привести все элементы матрицы к неотрицательным величинам а,-, > О, тогда у > 0, а игра решается в смешанных стратегиях

Применение игроком I оптимальной смешанной стратегии 5| гарантирует ему средний выигрыш не меньше цены игры, т.е. у, > у независимо от поведения игрока II. Игрок II, применяя оптимальную смешанную стратегию 5ц, гарантирует для себя минимальный проигрыш не больше у, т.е. у< у.

Если игрок II применяет свою чистую стратегию В_}, а игрок I — свою оптимальную стратегию 5|, то средний выигрыш игрока I равен

Если игрок I применяет свою чистую стратегию Л„ а игрок II — свою оптимальную смешанную стратегию 5ц, то средний выигрыш игрока II составит

Учитывая, что у, не может быть меньше у для игрока I, а у, не может быть больше у для игрока II, двойственную задачу линейного программирования можно записать следующим образом:

2) для игрока II

Смысл этих систем уравнений заключается в следующем: игрок I стремится увеличить цену игры (у —*• max), т.е. он действует так, чтобы его средний выигрыш при использовании его стратегий с вероятностямир, для любой j-й стратегии игрока II был не меньше величины у, которую он стремится увеличить. Игрок II стремится уменьшить свой проигрыш (у —*• min), т.е. он действует так, чтобы его средний проигрыш при использовании его стратегий с вероятностями qj при любой i-й стратегии игрока I ие превышал величину у, которую он стремится уменьшить.

Задача состоит в нахождении двух оптимальных смешанных стратегий S = (p_hp₂,...,р„,) и 5н = (q_u q₂,..., q„), которые дают для игрока I максимально возможный для него средний выигрыш, а для игрока II минимально возможный для него средний проигрыш.

Разделив левую и правую части неравенств (3.26) и (3.27) на цену игры у > 0, получим

Введем обозначении

Тогда неравенства (3.28) и (3.29) примут следующий вид:

m n

Из равенств X P, ⁼ 1 и X Ц ⁼ 1 и выражений (3.30) и

;=1 j=l

(3.31) следует, что переменные ж, и г/₇- должны удовлетворять условиям

Учитывая, что игрок I стремится максимизировать у, а игрок II стремится минимизировать у, переменные х,- и z/,- долж-

_ т

ны быть выбраны так, чтобы целевая функция F(X) = Ху

достигала минимума, а целевая функция Ф(У) = X У> — мак-

М

симума.

Таким образом, решение игры сводится к задаче линейного программирования. Оптимальные стратегии 5J = (р,Р2,...,р_т) и 5п = (<7ь ???> А могут быть найдены путем решения симметричной пары двойственных задач линейного программирования

Решая их, находим значения x_if yj, цену игры у и, следовательно, оптимальные стратегии S = (р_У р₂> ...» р_т) ^и ^н ⁼ = {q_b ц_ъ ...,

Пример 3.10. Найдите решение конфликтной ситуации с платежной матрицей

Решение. Математические модели пары двойственных задач линейного программирования можно записать так:

• найти минимум функции F(X) = Х + х₂ + *з при ограничениях

• найти максимум функции Ф(У) = У + У2 + Уз при ограничениях

Симплексный метод позволяет найти решение этой системы неравенств (табл. 3.10).

Тогда цена игры у = 1 : X г/. = 1 : - = а вероятности примене-

М ⁹ ^

иия стратегий игрока II будут

Таким образом, оптимальная смешанная стратегия игрока II

Поскольку решение системы неравенств (3.43) симплексным методом даст также и решение (см. табл. 3.10) двойственной задачи, то можно записать

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

Таблица 3.10

Автор: Фомин Геннадий