Сведение матричной игры к задаче линейного программирования
Рассмотрим m n игру с платежной матрицей А=( ). Без ограничения общности будем считать, что все элементы матрицы А положительны (этого всегда можно добиться, пользуясь аффинным правилом, преобразующим заданную матрицу игры, но не изменяющим оптимальных смешанных стратегий игроков). Тогда искомая цена игры v— положительное число. Интересы игрока А. Из теоремы о свойствах оптимальных смешанных стратегий игроков вытекает, что при любой чистой стратегии В игрока В, k = 1, 2,.. . , n, оптимальная смешанная стратегия Р = { } игрока А обеспечивает его средний выигрыш, не меньший v. Иными словами, выполняются соотношения k=1,2,…,n, i=1,2,…,m, которые с учетом обозначений i=1,2,…,m, можно записать так Поскольку игрок А стремится максимально увеличить свой гарантированный выигрыш, то задача отыскания решения матричной игры сводится к следующей задаче: Интересы игрока В. Аналогичным образом заключаем, что оптимальная смешанная стратегия Q= { } игрока В при любой чистой стратегии А игрока А, i = 1,2,…,m обеспечивает его средний проитрыш, не больший v. Иными словами, выполняются соотношения i=1,2,…,m, k=1,2,…,n, которые с учетом обозначений: k=1,2,…,n можно записать так i=1,2,…,m, k=1,2,…,n. Поскольку игрок В стремится сделать свой гарантированный проигрыш минимально возможным, то задача отыскания решения матричной игры сводится к следующей задаче: i = 1,2,…,m,
(B) i=1,2,…,m, k = 1,2,…,n. При этом цена игры v = где Θ - величина, обратная общему значению оптимальных сумм, Θ = = а оптимальные значения связаны с оптимальными посредством равенств Алгоритм решения матричной игры. Пример 9. Рассмотрим 2 х 2 игру с матрицей . Решение. 1) Все элементы платежной матрицы положительны. 2) Строим решения обеих задач линейного программирования, пользуясь графическим методом. В результате получаем, что 3) 4)
Популярное: Почему двоичная система счисления так распространена?: Каждая цифра должна быть как-то представлена на физическом носителе... Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... Почему стероиды повышают давление?: Основных причин три... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (940)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |