рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Использование линейной оптимизации при решении матричных игр

Использование линейной оптимизации при решении матричных игр - Контрольная Работа, раздел Образование, ЛЕКЦИИ ПО ТЕОРИИ ИГР Пусть Игра Не Имеет ...

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

Будем считать, что все элементы платежной матрицы неотрицательны (если это не так, то можно ко всем элементам матрицы добавить некоторое число L, переводящее платежи в область неотрицательных значений - очевидно, при этом цена игры увеличится на L, а решение задачи не изменится). Таким образом, предполагаем, что >0.

Будем искать решение игры в смешанных стратегиях

 

;

 

Применение игроком I оптимальной смешанной стратегии гарантирует ему, независимо от поведения игрока II, выигрыш, не меньший цены игры .

Пусть игрок II применяет свою активную чистую j-ю стратегию, а игрок I - свою оптимальную стратегию . Тогда средний выигрыш игрока I будет равен

 

 

Учитывая, что не может быть меньше , запишем условия:

 

Разделив левую и правую части каждого из неравенств (4.4) на цену игры >0, получим

 

(4.5)

 

При использовании обозначений

 

(4.6)

 

неравенства (4.5) примут вид

 

 

где, очевидно, все , так как .

Из равенства

 

и в силу определения (4.6) следует, что переменные () удовлетворяют условию

 

 

Учитывая, что игрок I стремится максимизировать , получаем линейную функцию

 

(4.8)

 

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

 

 

минимизирующие линейную функцию (4.8) и удовлетворяющие ограничениям (4.7).

Из решения задачи линейной оптимизации легко найти цену игры и оптимальную стратегию игрока I:

 


В свою очередь, оптимальная стратегия игрока II

 

 

может быть найдена из выражения

 

где - неотрицательные переменные задачи линейной оптимизации

 

 

которая является двойственной по отношению к задаче, представленной условиями (4.7) и (4.8).

В этой системе неравенств переменные

 

 

Таким образом, оптимальные стратегии

 

и


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

 

Исходная задача Двойственная задача

 

Цена игры и вероятности применения стратегий игроками I и II равны

 

 

2. Решение матричных игр в смешанных стратегиях с помощью Excel

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

 

Пример 1

 

В качестве примера применения информационных технологий Excel найдем решение парной игры с платежной матрицей

II I

 

Решение

Для данной задачи (седловая точка отсутствует). Запишем пару двойственных задач линейной оптимизации для решения игры.

 

 

Решим исходную и двойственную задачи с помощью Excel.

Внесем данные на рабочий лист в соответствии с Рис. 4.1.

матричный игра решение линейный


Рис. 4.1. Данные для решения исходной задачи примера 1

 

В ячейки E3:E6 введем формулы для расчета функций – ограничений, ячейки B9:D9 отведем для переменных , ячейку B15 – для расчетного значения цены игры , диапазон ячеек F12:H12 – для расчетных значений вероятностей применения стратегий игроком I, и, наконец, ячейку F9 – для расчета целевой функции. Введем все необходимые формулы в соответствующие ячейки. Установим все необходимые ограничения исходной задачи перед запуском Поиска решения. С помощью Поиска решения получим следующий ответ

 

x1 x2 x3   ЦФ    
0,020182 0,02474 0,003255   0,048177    
             
        P1 P2 P3
        0,4189 0,5135 0,0676
g          
20,75676          

 

 

 


Таким образом, оптимальная смешанная стратегия игрока I:

 

 

Решим двойственную задачу. Во избежание возможных ошибок расположим данные для ее решения на отдельном рабочем листе Excel (Рис. 4.2.).

 

Рис. 4.2 Данные для решения двойственной задачи примера 1

 

Ввод данных и формул производится аналогично предыдущему случаю. Поиск решения дает ответ:

 

U 0,0026   Q1=U1* 0,0541 ЦФ
U 0,0195   Q2=U2* 0,4054 0,048177
U 0,0000   Q3=U3* 0,0000
U 0,0260   Q4=U4* 0,5405 20,75676

 

Таким образом, оптимальная смешанная стратегия игрока II есть


.

– Конец работы –

Эта тема принадлежит разделу:

ЛЕКЦИИ ПО ТЕОРИИ ИГР

Вам нужно прочитать лекции разобраться в них и выполнить задания примеры стр в EXCEL Это и будет Ваша контрольная работа Результаты.. ЛЕКЦИИ ПО ТЕОРИИ ИГР..

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Использование линейной оптимизации при решении матричных игр

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

ЛЕКЦИИ ПО ТЕОРИИ ИГР
Теория игр в контексте теории принятия решений   Рассмотренные до сих пор задачи формулировались и решались, в основном, в предположении наличия полной информации. Их можно о

Матричные игры с нулевой суммой
  Рассмотрим парную игру с нулевой суммой. Пусть игрок I имеет стратегий (1, 2,…,m), а игрок II -

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

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

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги