Помощь студентам - решение задач и контрольных работ

Помощь в решении ваших задач вы можете найти, отправив сообщение WhatsApp, ВКонтакте или Viber. Заполнение формы с личными данными и регистрация на сайте не нужна. Мгновенная связь через в любое время и на любом этапе заказа. Общение с автором студенческих работ без посредников.
Опыт работы более 20 лет.
Оплата на карту Сбербанка (другие распространенные способы оплаты по договоренности).
Стоимость решения домашней работы начинается от 50 р. за задачу (но не менее 300 р. за весь заказ). Подробное оформление с выводами. Стоимость помощи на экзамене онлайн (в этом случае необходима 100% предоплата) - от 1000 р. за решение билета.

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

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

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

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

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

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

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

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

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

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

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

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

где .

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

где .

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

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

где:

 и

где

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

найти минимальное значение функции  при  ограничениях (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

Так как , то седловая точка отсутствует, и оптимальное решение следует искать в смешанных стратегиях игроков:

 и

 

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-й объект капитальные вложения осуществлять невыгодно.

 

Сохранить ссылку на страницу в социальной сети:

Помощь в решении ваших задач по этому предмету вы можете найти, отправив сообщение в ВКонтакте, WhatsApp, на Viber или заполнив форму.
Оплата на карту Сбербанка (другие распространенные способы оплаты по договоренности).
Стоимость решения домашней работы начинается от 150 р. за задачу (но не менее 300 р. за весь заказ). Подробное оформление. Стоимость помощи на экзамене онлайн (в этом случае необходима 100% предоплата) - от 1000 р. за решение билета. Подробнее...

@100task.ru 2009-2018 Москва Спб Екатеринбург Сургут Самара Краснодар Омск