Лекция 6. Решение матричных игр с помощью линейного программирования
План. 6.1. Связь матричных игр и линейного программирования. 6.2. Алгоритм решения матричных игр с помощью линейного программирования. Связь матричных игр и линейного программирования Теория игр находится в тесной связи с линейным программированием, так как каждая конечная игра двух лиц с нулевой суммой может быть представлена как задача линейного программирования. Г Данциг указывает, что создатель теории игр Дж. Фон Нейман, который первым ввел симплекс-метод в линейное программирование (1947 г.), установил это соотношение и в дальнейшем обосновал и развил концепцию двойственности в линейном программировании. Допустим, дана игра двух лиц, заданная платежной матрицей . Тогда оптимальная смешанная стратегия первого игрока определяется условиями , . (6.1) Эта задача может быть сформулирована в виде задачи линейного программирования. Пусть . Тогда может быть составлена математическая модель задачи для первого игрока. Исходя из чистых стратегий второго игрока целевая функция игры: (6.2) при ограничениях . Для второго игрока задача записывается в виде , . Промежуточное соотношение: . Тогда задача примет вид (6.3) при ограничениях . Задача для второго игрока (6.3) является двойственной к задаче для первого игрока (6.2). Задача для второго игрока может быть решена, например, стандартным симплекс-методом, а для первого игрока – двойственным симплекс-методом. Выбор метода определяется тем, какая из задач имеет меньше ограничений, что в свою очередь зависит от числа чистых стратегий каждого из игроков. Математическую модель задачи (6.2) можно упростить, разделив все (n + 1) ограничения на v. Это возможно при v ¹ 0. При v = 0 рекомендуется прибавить любое положительное число ко всем элементам платежной матрицы, что гарантирует положительность значения модифицированной игры. Действительное значение игры получается вычитанием из модифицированного значения этого положительного числа. Если v < 0, то надо сменить знаки неравенств. Полагая v > 0, систему ограничений можно записать: . Полагая Xi = xi / v и если v ® max, то 1/v ® min, получим задачу линейного программирования вида при ограничениях . Аналогично, исходя из чистых стратегий первого игрока или по правилам составления двойственных задач, принимая математическую модель первого игрока как исходную, математическая модель второго игрока записывается в виде при ограничениях , где S(Y)max = L(X)min = 1/v, Yj = yj/n.
Популярное: Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Организация как механизм и форма жизни коллектива: Организация не сможет достичь поставленных целей без соответствующей внутренней... Как распознать напряжение: Говоря о мышечном напряжении, мы в первую очередь имеем в виду мускулы, прикрепленные к костям ... Генезис конфликтологии как науки в древней Греции: Для уяснения предыстории конфликтологии существенное значение имеет обращение к античной... ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (924)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |