Исследование операций. Линейное, динамическое программирование


Исследование операций - часть 157


Заставим противника (В)

отступать от своей оптимальной стратегии, пользуясь чистыми стратегиями В1, B2, ..., Вn (а мы тем временем упорно держимся стратегии

). В любом случае наш выигрыш будет не меньше, чем v:

 

                (27.2)

Разделим неравенства (27.2) на положительную величину v

и введем обозначения:

      (27.3)

 

Тогда условия (27.2) примут вид

 

           (27.4)

 

где x1, x2,..., xm — неотрицательные переменные. В силу (27.3) и того, что p1 + р2 + ... + рm = 1, переменные x1, x2,..., хm удовлетворяют условию

 

х1, + х2, + ... + xm =

.            (27.5)

Но v есть не что иное, как наш гарантированный выигрыш, естественно, мы хотим сделать его максимальным, а значит, величину

 — минимальной.

Таким образом, задача решения игры свелась к математической задаче: найти неотрицательные значения переменных х1, х2, ..., xm такие, чтобы они удовлетворяли линейным ограничениям-неравенствам (27.4) и обращали в минимум линейную функцию этих переменных:

 

L = х1, + х2, + ... + xm => min.       (27.6)

«Ба! — скажет читатель, — что-то знакомое!» И точно — перед нами не что иное, как задача линейного программирования. Таким образом, задача решения игры т×п свелась к задаче линейного программирования с n ограничениями-неравенствами и т переменными. Зная x1, x2, ..., xm, можно по формулам (27.3) найти p1, р2, ..., рm и, значит, оптимальную стратегию

 и цену игры v.

Оптимальная стратегия игрока В находится совершенно аналогично, с той разницей, что В

стремится минизировать, а не максимизировать выигрыш, а значит, обратить не в минимум, а в максимум величину

, а в ограничениях-неравенствах вместо знаков ? будут стоять ?. Пара задач линейного программирования, по которой находятся оптимальные стратегии
, называется парой двойственных задач линейного программирования (доказано, что максимум линейной функции в одной из них равен минимуму линейной функции в другой, так что все в порядке — разных значений цены игры мы не получим).




Начало  Назад  Вперед



Книжный магазин