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


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


Таким образом, решение игры m×п

эквивалентно решению задачи линейного программирования. Нужно заметить, что и наоборот, — для любой задачи линейного программирования может быть построена эквивалентная ей задача теории игр (на том, как это делается, мы останавливаться не будем). Эта связь задач теории игр с задачами линейного программирования оказывается полезной не только для теории игр, но и для линейного программирования. Дело в том, что существуют приближенные численные методы решения игр, которые в некоторых случаях (при большой размерности задачи) оказываются проще, чем «классические» методы линейного программирования.

Опишем один из самых простых численных методов решения игр — так называемый метод итераций (иначе — метод Брауна — Робинсон). Идея его в следующем. Разыгрывается «мысленный эксперимент», в котором стороны А

и В поочередно применяют друг против друга свои стратегии, стремясь выиграть побольше (проиграть поменьше). Эксперимент состоит из ряда «партий» игры. Начинается он с того, что один из игроков (скажем, А) выбирает произвольно одну из своих стратегий Ai. Противник (В) отвечает ему той из своих стратегий Bj которая хуже всего для А, т. е.

обращает его выигрыш при стратегии 4, в минимум. Дальше снова очередь А —он отвечает В той своей стратегией Аk, которая дает максимальный выигрыш при стратегии Вj противника. Дальше — снова очередь противника. Он отвечает нам той своей стратегией, которая является наихудшей не для последней, примененной нами, стратегии Аk, а для смешанной стратегии, в которой до сих пор примененные стратегии Ai, Ak встречаются с равными вероятностями. И так далее: на каждом шаге итерационного процесса каждый игрок отвечает на очередной ход другого той своей стратегией, которая является оптимальной для него относительно смешанной стратегии другого, в которую все примененные до сих пор стратегии входят пропорционально частотам их применения. Вместо того чтобы вычислять каждый раз средний выигрыш, можно пользоваться просто «накопленным» за предыдущие ходы выигрышем и выбирать ту свою стратегию, при которой этот накопленный выигрыш максимален (минимален).


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