Решение матричной игры в смешанных стратегиях
Для игры без седловой точки оптимальные стратегии игроков находятся в области смешанных стратегий. Смешанной стратегией игрока называют вектор , компоненты которого удовлетворяют условиям
Смешанной стратегией игрока называют вектор где
и – вероятности, с которыми игроки и выбирают свои чистые стратегии и . При использовании смешанных стратегий игра приобретает случайный характер, случайной становится и величина выигрыша игрока (проигрыша игрока ). Эта величина является функцией смешанных стратегий и и определяется по формуле:
Функцию называют платежной или функцией выигрыша.
Смешанные стратегии и называются оптимальными, если они образуют седловую точку для платежной функции , то есть удовлетворяют неравенству . Пользуются и другим определением оптимальных смешанных стратегий; стратегии и называют оптимальными, если
Величину называют ценой игры.
Поиск оптимальных стратегий начинают с упрощения платежной матрицы. Если в платежной матрице элементы -й строки не меньше соответствующих элементов -й строки, то есть , то говорят, что стратегия доминирует над стратегией . Аналогично, если элементы -го столбца не превосходят элементы -го столбца, то есть , то говорят, что стратегия доминирует над стратегией . Частным случаем доминирования является дублирование стратегий, когда или . Исключение из платежной матрицы заведомо доминируемых стратегий (ими игрокам пользоваться заведомо невыгодно) позволяет уменьшить ее размерность, а это упрощает решение игры. Вероятность применения доминируемых стратегий равна нулю.
Оптимальные смешанные стратегии в игре с платежной матрицей и ценой остаются оптимальными и для игры с платежной матрицей (где ) и ценой . На этом основании платежную матрицу можно всегда преобразовать так, что ее элементы будут целыми неотрицательными числами, а это упрощает расчеты.
Решение матричной игры сведением к задаче линейного программирования
Пусть имеем игру размерности с матрицей:
Обозначим через оптимальные смешанные стратегии игроков к . Стратегия игрока гарантирует ему выигрыш не меньше , независимо от выбора стратегии , игроком . Это можно записать так:
где .
Аналогично стратегия игрока гарантирует ему проигрыш не больше , независимо от выбора стратегии , игроком , т. е.:
где .
Поскольку элементы платежной матрицы на основании всегда можно сделать положительными, то и цена игры (оптимальные смешанные стратегии и соответственно игроков и в матричной игре с ценой будут оптимальными и в матричной игре с ценой , где ).
Преобразуем системы неравенств, разделив обе части каждого неравенства на положительное число , и введем новые обозначения ; . Получим:
где:
и
где
Так как игрок А стремится максимизировать цену игры , то обратная величина будет минимизироваться, поэтому оптимальная стратегия игрока А определится из задачи линейного программирования следующего вида:
найти минимальное значение функции при ограничениях (1) и (2).
Оптимальная смешанная стратегия игрока определится решением задачи следующего вида:
найти максимальное значение функции при ограничениях (3) и (4).
Решив пару двойственных задач графическим (для случая двух переменных) или симплексным методом, далее определим:
Поскольку задачи (1)(2) и (3)(4) образуют пару симметричных двойственных задач линейного программирования, нет необходимости решать обе задачи. Получив решение одной из них, достаточно воспользоваться соответствием между переменными в канонических записях задач.
и из строки целевой функции последней симплекс-таблицы, содержащей компоненты оптимального вектора, выписать значения компонент оптимального вектора двойственной задачи.
При поиске оптимальных стратегий в матричных играх размерностей и целесообразно использовать графический метод решения ЗЛП и свойства оптимальных планов пары двойственных задач: если в оптимальном плане задачи переменная положительна, то соответствующее ограничение двойственной задачи ее оптимальным планом обращается в равенство; если оптимальным планом задачи ограничение обращается в строгое неравенство, то в оптимальном плане двойственной задачи соответствующая переменная равна нулю.
Задача
Отрасли и осуществляют капитальные вложения в четыре объекта. С учетом особенностей вкладов и местных условий прибыль отрасли в зависимости от объема финансирования выражается элементами платежной матрицы . Для упрощения задачи принять, что убыток отрасли равен прибыли отрасли . Найти оптимальные стратегии отраслей.
Требуется:
1) свести исходные данные в таблицу и найти решение матричной игры в чистых стратегиях, если оно существует (противном случае см. следующий пункт 2);
2) упростить платежную матрицу;
3) составить пару взаимно двойственных задач, эквивалентную данной матричной игре;
4) найти оптимальное решение прямой задачи (для отрасли ) симплекс-методом;
5) используя соответствие переменных, выписать оптимальное решение двойственной задачи (для отрасли .
6) используя соотношение между оптимальными решениями пары двойственных задач, оптимальными стратегиями и ценой игры, найти решение в смешанных стратегиях;
7) дать рекомендации по каждой отрасли.
Решение
1) Сведем исходные данные в таблицу:
/ | |||||
4 | 2 | -1 | 5 | -1 | |
3 | 1 | -1 | 3 | -1 | |
-2 | 0 | 1 | 4 | -2 | |
0 | 2 | -2 | 4 | -2 | |
4 | 2 | 1 | 5 |
Так как , то седловая точка отсутствует, и оптимальное решение следует искать в смешанных стратегиях игроков:
и
На сайте можно заказать решение задач, контрольных, самостоятельных, домашних работ (возможно срочное решение), а также онлайн-помощь на экзамене или зачете. Для этого вам нужно только связаться со мной:
Телеграм @helptask
ВКонтакте (vk.com/task100)
WhatsApp +7 (968) 849-45-98
Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту.
Подробное решение получите точно в срок или раньше.
2) Упростим платежную матрицу, отбросив стратегии, заведомо невыгодные или дублирующие.
2-я стратегия (2-й столбец) является невыгодной для игрока – элементы 2-го столбца не меньше элементов 3-го.
4-я стратегия (4-й столбец) является невыгодной для игрока – элементы 4-го столбца не меньше элементов 3-го.
2-я стратегия (2-я строка) является невыгодной для игрока – элементы 2-й строки не больше элементов 1-й
4-я стратегия (4-я строка) является невыгодной для игрока – элементы 4-й строки не больше элементов 1-й
/ | |||
4 | -1 | -1 | |
-2 | 1 | -2 | |
4 | 1 |
Получили матрицу размером 2х2
3) Составим пару взаимно двойственных задач, эквивалентных данной матричной игре.
Так как платёжная матрица содержит отрицательные числа, то лучше перейти к новой матрице с неотрицательными элементами; для этого к элементам платёжной матрицы достаточно добавить соответствующее положительное число, в данном случае 2. Решение игры при этом не изменится, а цена игры увеличится на 2. Платёжная матрица примет вид:
Обозначив и , составим две взаимно двойственные задачи линейного программирования:
Задача 1 |
Задача 2 |
|
|
4) Найдем оптимальное решение задачи для отрасли симплекс-методом. На другой странице сайта есть задача, решенная симплекс-методом очень подробно, а в этом примере, для краткости, из расчетов приведены только симплексные таблицы.
Приведем задачу к каноническому виду.
Заполняем симплексную таблицу 0-й итерации.
БП |
Симплексные отношения |
||||||
1 | 1 | 0 | 0 | ||||
0 | 1 | 6 | 1 | 1 | 0 | 1/6 | |
0 | 1 | 0 | 3 | 0 | 1 | — | |
0 | -1 | -1 | 0 | 0 |
Получаем таблицу 1-й итерации:
БП |
Симплексные отношения |
||||||
1 | 1 | 0 | 0 | ||||
1 | 1/6 | 1 | 1/6 | 1/6 | 0 | 1 | |
0 | 1 | 0 | 3 | 0 | 1 | 1/3 | |
1/6 | 0 | -5/6 | 1/6 | 0 |
Получаем таблицу 2-й итерации:
БП |
Симплексные отношения |
||||||
1 | 1 | 0 | 0 | ||||
1 | 1/9 | 1 | 0 | 1/6 | -1/18 | ||
1 | 1/3 | 0 | 1 | 0 | 1/3 | ||
4/9 | 0 | 0 | 1/6 | 5/18 |
В индексной строке все члены неотрицательные, поэтому получено следующее решение задачи линейного программирования (выписываем из столбца свободных членов):
5) Соответствие между переменными исходной и двойственной задачи:
| | | | | | | |
На основании симплексной таблицы получено следующее решение 1-й задачи:
6) Найдем решение игры в смешанных стратегиях.
Цена игры:
Находим оптимальную стратегию
Учтем, что 2-я и 4-я строка матрицы были отброшенные, как невыгодные для игрока :
Находим оптимальную стратегию
Учтем, что 2-й и 4-й столбец матрицы были отброшенные, как невыгодные для игрока :
Цена игры
7) Дадим рекомендации по каждой отрасли.
Отрасли необходимо вложить 37,5% средств в 1-й объект и 62,5% средств во 3-й объект. Во 2-й и 4-й объект капитальные вложения осуществлять невыгодно.
Отрасли необходимо вложить 25% средств в 1-й объект и 75% средств во 3-й объект. Во 2-й и 4-й объект капитальные вложения осуществлять невыгодно.