Добро пожаловать на наш портал !

Методы компьютерного моделирования экономических процессов

Решение матричных игр

Решение матричных игр методами линейного программирования. Рассмотрим некоторые способы решения матричных игр. Задача, решаемая первым игроком, (6.10) была сформулирована как максимизация наименьшей из сумм

но если определить некоторое хm+1 , для которого выполняется

то она может быть сведена к задаче линейного программирования:

при ограничениях

Проведя аналогичные рассуждения, приходим к тому, что задача минимизации наибольшего ожидаемого проигрыша, решаемая игроком II (6.12), сводится к задаче линейного программирования

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

Достаточно легко проверить, что задачи (6.16)-(6.17) и (6.18)-(6.19) образуют двойственную пару. Здесь в определенном смысле мы вернулись к проблемам, уже рассматривавшимся во второй главе, а именно к взаимосвязи между наличием решения у некоторой оптимизационной задачи и существованием седловой точки у соответствующей функции Лагранжа. В данном случае аналогичная связь прослеживается между седловой точкой игры и решением пары задач оптимизации.