Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Использование теорем двойственности




 

Решение ЛП-задач Получателя и Плательщика связаны между собой теоремами двойственности. Этот факт позволяет проводить трудоемкое решение только для задачи одного из игроков, а ЛП-искомые для другого игрока получить с помощью данных соотношений.

Проведем сравнение используемых ЛП-обозначений и соотношений

Получатель Плательщик
Искомые величины Xi = xi /n, где I =1... m; Gmin =1/n. Система ограничений , где . Целевая функция . Искомые величины Y j = yj /n, где j = 1... n; F max=1/n. Система ограничений , где . Целевая функция .
Теоремы двойственности в ЛП-теории (с учётом известных коэффициентов целевых функций)  
Следствия из теорем двойственности(первые уравнения умножены на n2, последнее равенство – на n) С учетом того, что xi = Xi ×n, а yi = Yi ×n.  
     

 

Решение системы уравнений значительно упрощается при учете следующего факта: произведение равно нулю, когда хотя бы один из сомножителей равен нулю. Это позволяет сформулировать следствия в терминах «игровой» задачи.

Если, при условии применения любым игроком какой-либо отдельной чистой стратегии, средний платеж не равен цене игры n, то эта чистая стратегия игроком не применяется, а соответствующая вероятность равна нулю

Средний платеж по каждой активной стратегии строго равен цене игры n

Сумма всех вероятностей (для каждого игрока) равна единице

x 1 + x 2 +…+ xm = 1 и y 1 + y 2 +…+ yn = 1,

(при неотрицательных значениях).

Замечание: для составления системы уравнений и нахождения всех искомых вероятностей достаточно знать смешанную стратегию одного из игроков. Тогда ряды, соответствующие неактивным стратегиям этого игрока, исключаются из платежной матрицы, а величина среднего платежа по каждой чистой стратегии другого игрока позволяет выявить и его активные стратегии, и цену игры, и (через решение системы оставшихся уравнений) вероятности применения активных стратегий. С другой стороны, если известен состав множества активных стратегий игроков, то исходная система требований преобразуется в систему точных равенств, соответствующим активным стратегиям, что также позволяет находить все искомые величины, решая систему уравнений.

Иногда состав активных стратегий может быть взят гипотетически. Выдвижение правдоподобных гипотез существенно облегчается предварительным фиктивным разыгрыванием (оно описано далее в разделе «Итеративный метод фиктивного разыгрывания Брауна – Робинсона»), которое позволяет сделать качественный вывод о составе множеств активных стратегий обоих игроков и приближенный – о частотности (или вероятности) использования этих стратегий. Совместность полученной системы уравнений и полная проверка полученного результата на соответствие всем требованиям, предъявляемым к решению, позволяет либо принять, либо отвергнуть выдвинутую гипотезу, уже с получением не приближенного, а точного решения игры.

Пример 6в. Требуется найти смешанные стратегии игроков и цену игры, если дана платежная матрица (она взята из примера 4б)

 

  В 1 В 2  
А 1    
А 2    
А 3    

 

Решение

1. Графически установим (пример 4б), что, при условии применения Получателем его стратегии А 3, величина среднего платежа меньше цены игры n. На основании следствия из теорем двойственности делаем вывод, что вероятность применения этой стратегии x 3 = 0. С другой стороны, отрезки, соответствующие стратегиям Получателя А 1 и А 2 проходят через точку М (y 2; n) и составляют его смешанную стратегию.

2. Смешанная стратегия Плательщика состоит из стратегий В 1 и В 2, применяемых с вероятностями y 1 и y 2 следовательно, для вероятностей применения этих стратегий получаем уравнения

Решение этой системы дает результат

Сделаем вывод (он полностью согласуется с графическим решением в примере 4б): смешанная стратегия Плательщика состоит из стратегий В 1 и В 2, применяемых с вероятностями y 1 > 0 и y 2 > 0.

3. Для обеих применяемых (yj > 0) стратегий Плательщика В 1 и В 2 по следствиям из теорем двойственности получаем уравнения, связывающие вероятности x 1 > 0 и x 2 > 0

 

Решение этой системы, дает результат

4. Проведем проверку смешанной стратегии Получателя.

x 1 + x 2 + x 3 = 5/7 + 2/7 + 0 = 1.

Предположим, что Плательщик достаточно много раз применяет свою стратегию В 1. Тогда величина среднего платежа может быть вычислена

7 x 1 + 2 x 2 + 8 x 3 = 7×5/7 + 2×2/7 + 8×0 = 39/7 = n > a = 5;

Во всех остальных случаях Плательщик применяет стратегию В 2. Тогда вычисление величины среднего платежа дает результат

5 x 1+7 x 2 + 4 x 3 = 5×5/7 + 7×2/7 + 4×0 = 39/7 = n > a.

5. Проведем проверку смешанной стратегии Плательщика.

y 1 + y 2 = 2/7+5/7 + 0 = 1.

Предположим, что Получатель достаточно много раз применяет свою стратегию А 1. Тогда величина среднего платежа может быть вычислена

7 y 1 + 5 y 2 = 7×2/7 + 5×5/7 = 39/7 = n< b = 7.

Во всех остальных случаях Получатель применяет стратегию А 2. Тогда вычисление величины среднего платежа дает результат

2 y 1+7 y 2 = 2×2/7 + 7×5/7 = 39/7 = n< b.

Если Получатель применяет стратегию А 3, то величина среднего платежа составит

8 y 1 + 4 y 2 = 8×2/7 + 4×5/7 = 36/7< n.

(что подтверждает невыгодность этой стратегии для Получателя).

Ответ

– оптимальная смешанная стратегия Получателя состоит в применении стратегии А 1 с вероятностью x 1» 0,71 и стратегии А 2 с вероятностью x 2» 0,29;

– оптимальная смешанная стратегия Плательщика состоит в применении стратегии В 1 с вероятностью y 1» 0,29 и стратегии В 2 с вероятностью y 2» 0,71;

– цена игры (средняя величина платежа, гарантированная каждому игроку при применении оптимальных смешанных стратегий) n» 5,56.




Поделиться с друзьями:


Дата добавления: 2014-12-27; Просмотров: 453; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.014 сек.