Решение матричной игры в смешанных стратегиях

Краткая теория

Для игры без седловой точки оптимальные стратегии игроков находятся в области смешанных стратегий. Смешанной стратегией игрока  называют вектор , компоненты которого удовлетворяют условиям

Смешанной стратегией игрока  называют вектор  где

 и  – вероятности, с которыми игроки  и  выбирают свои чистые стратегии  и . При использовании смешанных стратегий игра приобретает случайный характер, случайной становится и величина выигрыша игрока  (проигрыша игрока ). Эта величина является функцией смешанных стратегий  и  и определяется по формуле:

Функцию  называют платежной или функцией выигрыша.

Смешанные стратегии  и  называются оптимальными, если они образуют седловую точку для платежной функции , то есть удовлетворяют неравенству . Пользуются и другим определением оптимальных смешанных стратегий; стратегии  и  называют оптимальными, если

Величину  называют ценой игры.

Поиск оптимальных стратегий начинают с упрощения платежной матрицы. Если в платежной матрице элементы -й строки не меньше соответствующих элементов -й строки, то есть , то говорят, что стратегия  доминирует над стратегией . Аналогично, если элементы -го столбца не превосходят элементы -го столбца, то есть , то говорят, что стратегия  доминирует над стратегией . Частным случаем доминирования является дублирование стратегий, когда  или . Исключение из платежной матрицы заведомо доминируемых стратегий (ими игрокам пользоваться заведомо невыгодно) позволяет уменьшить ее размерность, а это упрощает решение игры. Вероятность применения доминируемых стратегий равна нулю.

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

Решение матричной игры сведением к задаче линейного программирования

Пусть имеем игру размерности   с матрицей:

Обозначим через  оптимальные смешанные стратегии игроков  к . Стратегия  игрока  гарантирует ему выигрыш не меньше , независимо от выбора стратегии , игроком . Это можно записать так:

где .

Аналогично стратегия  игрока  гарантирует ему проигрыш не больше , независимо от выбора стратегии , игроком , т. е.:

где .

Поскольку элементы платежной матрицы на основании  всегда можно сделать положительными, то и цена игры   (оптимальные смешанные стратегии  и  соответственно игроков  и  в матричной игре     с ценой  будут оптимальными и в матричной игре      с ценой   , где ).

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

где:

 и

где

Так как игрок А стремится максимизировать цену игры , то обратная величина  будет минимизироваться, поэтому оптимальная стратегия игрока А определится из задачи линейного программирования следующего вида:

найти минимальное значение функции  при  ограничениях (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-й объект капитальные вложения осуществлять невыгодно.