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


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


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

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

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

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

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

где
Так как игрок А стремится максимизировать цену игры
,
то обратная величина
будет минимизироваться, поэтому оптимальная
стратегия игрока А определится из задачи линейного программирования следующего
вида:
найти минимальное значение функции
при
ограничениях (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
|
|
Так
как
, то седловая
точка отсутствует, и оптимальное решение следует искать в смешанных стратегиях
игроков:
и

На сайте можно заказать решение контрольной или самостоятельной работы, домашнего задания, отдельных задач. Для этого вам нужно только связаться со мной:
ВКонтакте
WhatsApp
Telegram
Мгновенная связь в любое время и на любом этапе заказа. Общение без посредников. Удобная и быстрая оплата переводом на карту СберБанка. Опыт работы более 25 лет.
Подробное решение в электронном виде (docx, pdf) получите точно в срок или раньше.
2)
Упростим платежную матрицу, отбросив стратегии, заведомо невыгодные или
дублирующие.
2-я
стратегия (2-й столбец) является невыгодной для игрока
– элементы 2-го столбца не меньше элементов
3-го.
4-я
стратегия (4-й столбец) является невыгодной для игрока
– элементы 4-го столбца не меньше элементов
3-го.
2-я
стратегия (2-я строка) является невыгодной для игрока
– элементы 2-й строки не больше элементов 1-й
4-я
стратегия (4-я строка) является невыгодной для игрока
– элементы 4-й строки не больше элементов 1-й
Получили
матрицу размером 2х2

3) Составим пару взаимно двойственных задач, эквивалентных
данной матричной игре.
Так
как платёжная матрица содержит отрицательные числа, то лучше перейти к новой
матрице с неотрицательными элементами; для этого к элементам платёжной матрицы
достаточно добавить соответствующее положительное число, в данном случае 2.
Решение игры при этом не изменится, а цена игры увеличится на 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-й объект капитальные вложения осуществлять невыгодно.