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

Антагонистическую матричную игру т х п (где т>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.