Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Тема 4. Взаимосвязь матричных игр и линейного программирования

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

Пусть игра m × n не имеет оптимального решения непосредственно в чистых стратегиях. Оптимальное решение необходимо искать в области смешанных стратегий.

Пусть смешанная стратегия х является оптимальной для игрока А

Поскольку при оптимальной стратегии средний выигрыш не меньше цены игры (q) при любой чистой стратегии Вj игрока В, то справедлива система n неравенств:

Цена игры является наибольшим из гарантированных исходов игрока А, поэтому компоненты (х 1, х 2, …, хm) оптимальной смешанной стратегии игрока А являются решением следующей задачи: найти неотрицательное решение системы линейных неравенств (1) при наибольшем возможном значении параметра q и выполнении дополнительного условия: х 1 + х 2 + … + хm = 1.

Будем предполагать, что цена игры q строго положительна. Разделим каждое из неравенств системы (1) на q > 0 и введем новые переменные:

в результате перейдем к эквивалентной системе неравенств:

При этом

Так как максимизация параметра q эквивалентна минимизации суммы X 1 + X 2 + … + Xm, то сформулированная выше задача эквивалентна следующей задаче, сформулированной в виде задачи линейного программирования:

найти min f (X 1, X 2, …, Xm) = X 1 + X 2 + … + Xm =1/ q при неотрицательных переменных X 1 ≥ 0, X 2 ≥ 0, …, Xm ≥ 0, удовлетворяющих ограничениям (2).

Найдя ее оптимальное решение X* 1, X* 2, …, X*m можно вычислить цену игры и компоненты оптимальной смешанной стратегии игрока А:

Задача определения оптимальной смешанной стратегии игрока В записывается как симметричная двойственная задача линейного программирования к задаче игрока A.

Цена игры является наименьшим из гарантированных исходов (проигрышей) игрока В, поэтому компоненты (у 1, у 2, …, yn) оптимальной смешанной стратегии игрока В являются решением следующей задачи:

найти неотрицательное решение системы линейных неравенств (3) при наименьшем возможном значении параметра q, удовлетворяющее дополнительному условию у 1 + у 2 + … + yn = 1.

Далее, при условии строго положительных значений цены игры q, вводятся дополнительные переменные:

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

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

что для рассматриваемых задач дает

что соответствует соотношениям для цены игры.

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

Решение задач линейного программирования осуществляется с помощью надстройки «Поиск решения» программного пакета MS Excel.

Отметим, что обзорная лекция дает лишь общее представление о курсе «Теория игр», тем не менее, мы Вам советуем ознакомиться с этой лекцией хотя бы еще один раз, после изучения основного материала курса. Это позволит Вам составить более целостное представление о его содержании, теоретическом обосновании и практическом применении.

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

Желаем Вам успеха! Благодарим за внимание.

 

<== предыдущая лекция | следующая лекция ==>
Тема 3. Решение игр в смешанных стратегиях | Средство накопления
Поделиться с друзьями:


Дата добавления: 2014-01-07; Просмотров: 462; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.013 сек.