Решение матричной игры в смешанных стратегиях
Для игры без седловой точки оптимальные стратегии игроков
находятся в области смешанных стратегий. Смешанной стратегией игрока
называют вектор
,
компоненты которого удовлетворяют условиям
Смешанной стратегией игрока
называют вектор
где
и
– вероятности, с которыми игроки
и
выбирают свои чистые стратегии
и
.
При использовании смешанных стратегий игра приобретает случайный характер,
случайной становится и величина выигрыша игрока
(проигрыша игрока
).
Эта величина является функцией смешанных стратегий
и
и определяется по формуле:
Функцию
называют платежной или функцией выигрыша.
Смешанные стратегии
и
называются оптимальными, если они образуют
седловую точку для платежной функции
,
то есть удовлетворяют неравенству
.
Пользуются и другим определением оптимальных смешанных стратегий; стратегии
и
называют оптимальными, если
Величину
называют ценой игры.
Поиск оптимальных стратегий начинают с
упрощения платежной матрицы. Если в платежной матрице элементы
-й
строки не меньше соответствующих элементов
-й
строки, то есть
,
то говорят, что стратегия
доминирует над стратегией
.
Аналогично, если элементы
-го
столбца не превосходят элементы
-го
столбца, то есть
,
то говорят, что стратегия
доминирует над стратегией
.
Частным случаем доминирования является дублирование стратегий, когда
или
.
Исключение из платежной матрицы заведомо доминируемых стратегий (ими игрокам
пользоваться заведомо невыгодно) позволяет уменьшить ее размерность, а это
упрощает решение игры. Вероятность применения доминируемых стратегий равна
нулю.
Оптимальные смешанные стратегии
в игре с платежной матрицей
и ценой
остаются оптимальными и для игры с платежной
матрицей
(где
)
и ценой
.
На этом основании платежную матрицу можно всегда преобразовать так, что ее
элементы будут целыми неотрицательными числами, а это упрощает расчеты.
Решение матричной игры сведением к задаче линейного программирования
Пусть имеем игру размерности
с матрицей:
Обозначим через
оптимальные смешанные стратегии игроков
к
.
Стратегия
игрока
гарантирует ему выигрыш не меньше
,
независимо от выбора стратегии
,
игроком
.
Это можно записать так:
где
.
Аналогично стратегия
игрока
гарантирует ему проигрыш не больше
,
независимо от выбора стратегии
,
игроком
,
т. е.:
где
.
Поскольку элементы платежной матрицы на
основании всегда можно сделать
положительными, то и цена игры
(оптимальные смешанные стратегии
и
соответственно игроков
и
в матричной игре
с ценой
будут оптимальными и в матричной игре
с ценой
,
где
).
Преобразуем системы неравенств, разделив обе части
каждого неравенства на положительное число
,
и введем новые обозначения
;
.
Получим:
где:
и
где
Так как игрок А стремится максимизировать цену игры
,
то обратная величина
будет минимизироваться, поэтому оптимальная
стратегия игрока А определится из задачи линейного программирования следующего
вида:
найти минимальное значение функции
при
ограничениях (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 |
|
Так
как
, то седловая
точка отсутствует, и оптимальное решение следует искать в смешанных стратегиях
игроков:
и
Если по каким-либо причинам не справляетесь с решением задач, на портале можно заказать выполнение расчетной домашней работы, ИДЗ, РГР, контрольной и даже отдельных задач в разумные сроки. Чтобы вы смогли сделать заказ, я доступен по следующим каналам связи:
Контакты будут для вас
видны на территории
России и Беларуси
Общение без посредников. Удобная оплата переводом на банковскую карту. Опыт работы более 25 лет.
Подробное решение в формате электронного документа получите точно в срок или раньше.
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-й объект капитальные вложения осуществлять невыгодно.