 |
 |
 |
 |
|
 |
 |
107
то она может быть сведена к задаче линейного программирования:
при ограничениях
Проведя аналогичные рассуждения, приходим к тому, что задача минимизации наибольшего
ожидаемого проигрыша, решаемая игроком II (6.12), сводится к задаче линейного программирования
Таким образом, мы получаем возможность применять все возможности аппарата линейного
программирования для поиска оптимальных стратегий обоих игроков.
Достаточно легко проверить, что задачи (6.16)-(6.17) и
(6.18)-(6.19) образуют двойственную пару.
Здесь в определенном смысле мы вернулись к проблемам, уже рассматривавшимся во второй главе, а
именно к взаимосвязи между наличием решения у некоторой оптимизационной задачи и
существованием седловой точки у соответствующей функции Лагранжа. В данном случае аналогичная
связь прослеживается между седловой точкой игры и решением пары задач оптимизации.
6.1.6. Графические методы решения игр. Следует отметить, что применение для решения задач
(6.16)-(6.17), (6.18)-(6.19) стандартных алгоритмов линейного программирования далеко не всегда
является рациональным. Помимо этого существуют иные методы, которые основываются на
использовании специфики данных задач. В настоящем пункте мы остановимся на очень простом
классическом способе поиска оптимальных смешанных стратегий в матричных играх, где один из
участников имеет только две стратегии (это так называемые 2 х п и т х 2 игры).
Для определенности положим, что игрок I имеет возможность выбирать между двумя стратегиями с
вероятностями x1 и x2 = 1-x1, тогда его ожидаемые выигрыши, соответствующие чистым стратегиям
игрока II, примут вид