Студопедия

КАТЕГОРИИ:


Архитектура-(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)

Приведение матричной игры к ЗЛП

Теория решения матричных игр возникла ранее линейного программирования и долгое время развивалась независимо от него. Математическое соответствие между матричными играми и линейным программированием было установлено одним из его основоположников Дж. Б. Данцигом в 1951 г. Он показал, что матричная игра может быть сведена к паре двойственных задач линейного программирования. Решение одной из них дает оптимальную стратегию игрока А, решение другой – оптимальную стратегию игрока В.

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

Платежную прямоугольную матрицу игры размерностью m ´ n можно представить в следующем виде: .

Оптимальные смешанные стратегии (максиминная и минимаксная) характеризуются векторами вероятностей:

для игрока Аp* = (p1*, p2*, …, pm*);

для игрока В q* = (q1*, q2*, …, qn*).

Поскольку стратегия игрока А оптимальна, то при любых чистых стратегиях игрока В гарантированные средние выигрыши не меньше цены игры v. Следовательно, при каждой чистой стратегии игрока В средний выигрыш (математическое ожидание) игрока А больше или равен цене игры v.

Для всех n чистых стратегий игрока В получается система неравенств: где ; . (1)

В теории игр доказывается, что оптимальные смешанные стратегии в матричной игре ½aij½m ´ n с ценой v остаются оптимальными при линейном преобразовании элементов матрицы½baij +c½m ´ n, но цена игры становится bv+c. Отсюда следует, что элементы исходной матрицы всегда можно сделать положительными, добавив ко всем элементам и цене игры подходящую величину с.

Систему неравенств (1), элементы которой приведены к положительным значениям, можно преобразовать, разделив обе части каждого неравенства на положительную величину v и обозначая p1* / v = х1, p2* / v = х2, …, pm* / v = хm.

После преобразования получается:

(2)

из следует , где .

Игрок А максимизирует свой средний выигрыш при максимуме цены игры v и минимуме 1 / v, то есть минимизируемой целевой функцией будет

f(x)= . (3)

Минимум целевой функции ищется при ограничениях, вытекающих из системы неравенств (2) и неотрицательности искомых значений хi.

ЗЛП для определения оптимальной смешанной стратегии игрока В является двойственной по отношению к рассмотренной ЗЛП для игрока А.

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



(4)

где и .

Система (4) преобразуется делением неравенств на положительную величину v, и при обозначениях q1*/v = y1, q2*/v = y2, …, qn*/v = yn получается:

(5)

, , где .

Игрок В стремится к минимизации своего среднего проигрыша, что достигается при минимуме цены игры v и, следовательно, максимуме обратной величины 1/v, поэтому в качестве максимизируемой целевой функции берется

h(у)= . (6)

Максимум целевой функции ищется при ограничениях, вытекающих из системы неравенств (5) и неотрицательности искомых значенийуj.

<== предыдущая лекция | следующая лекция ==>
| Приведение матричной игры к ЗЛП

Дата добавления: 2014-01-03; Просмотров: 326; Нарушение авторских прав?;


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



ПОИСК ПО САЙТУ:


Читайте также:



studopedia.su - Студопедия (2013 - 2017) год. Не является автором материалов, а предоставляет студентам возможность бесплатного обучения и использования! Последнее добавление ‚аш ip: 54.80.41.188
Генерация страницы за: 0.088 сек.