Автор работы: Пользователь скрыл имя, 17 Марта 2014 в 20:48, реферат
Каждый из игроков делает один ход: игрок 1 выбирает свою i-ю стратегию (i= ), 2 – свою j-ю стратегию (j= ), после чего игрок 1 получает выигрыш аij за счёт игрока 2 (если аij< 0, то это значит, что игрок 1 платит второму сумму |аij|). На этом игра заканчивается.
Каждая стратегия игрока i= ; j = часто называется чистой стратегией.
3
2
A1
Рис.1. Нахождение оптимальной стратегии игрока 1
В точках А1 и А2 восстановим перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью 0y) отложим выигрыш игрока 1 при стратегии А1, а на втором – при стратегии А2. Если игрок 1 применит стратегию А1, то выиграет при стратегии В1 игрока 2 – 2, при стратегии В2 – 3, а при стратегии В3 – 11. Числам 2, 3, 11 на оси 0х соответствуют точки В1, В2 и В3.
Если же игрок 1 применит стратегию А2, то его выигрыш при стратегии В1 равен 7, при В2 – 5, а при В3 – 2. Эти числа определяют точки В¢1, В2¢, В3¢ на перпендикуляре, восстановленном в точке А2.Соединяя между собой точки В1 и В¢1, В2 и В¢2, В3 и В¢3 получим три прямые, расстояние до которых от оси 0х определяет средний выигрыш при любом сочетании соответствующих стратегий.
Ординаты точек, принадлежащих ломанной В1MNВ¢3 определяют минимальный выигрыш игрока 1 при применении им любых смешанных стратегий. Эта минимальная величина является максимальной в точке N; следовательно, этой точке соответствует оптимальная стратегия X* = (p1*, p2*), а её ордината равна цене игры n. Координаты точки N находим как точку пересечения прямых В2B¢2 и В3B¢3.
Уравнение прямой, проходящей через две точки с координатами (x1, y1) и (x2, y2): .
Имеем прямую B2B¢2. Ее координаты (0,3) и (1,5) и уравнение имеет вид:
, отсюда y = 2x+3.
Координаты прямой В3B¢3 – (0,11) и (1,2), ее уравнение:
, отсюда y = 11-9x.
Решая совместно эти два уравнения, получим: , т.е.
Следовательно X* = ( ; ), при цене игры n = .
Из рис.1 видно, что стратегия 1 игрока 2 не войдёт в его оптимальную стратегию (вероятность ее использования равна нулю).
Таким образом мы можем найти оптимальную стратегию при помощи матрицы размером 2´2: .
С использованием этой матрицы найдем оптимальную стратегию 2-го игрока (Рис.2).
y
11
5
N
3
x
B2
Рис.2. Нахождение оптимальной
Ординаты точек, принадлежащих ломанной A2NA¢1 определяют максимальный проигрыш игрока 2 при применении им любых смешанных стратегий. Эта максимальная величина является минимальной в точке N; следовательно, этой точке соответствует оптимальная стратегия Y* = (q1*, q2*), а её ордината равна цене игры n. Координаты точки N находим как точку пересечения прямых A1A¢1 и A2A¢2.
Имеем прямую A1A¢1 . Ее координаты (0,3) и (1,11) и уравнение имеет вид:
, отсюда y = 8x+3.
Координаты прямой A2A¢2 – (0, 5) и (1,2), ее уравнение:
, отсюда y = 5-3x.
Решая совместно эти два уравнения, получим: , т.е.
Следовательно Y* = (0; ; ), при цене игры n = .
РЕШЕНИЕ ПОЛНОСТЬЮ УСРЕДНЕННЫХ МАТРИЧНЫХ ИГР РАЗМЕРОМ n´n
Как было показано выше, игры размером 2хn и mх2 сводятся к играм 2´2, которые можно решить в смешенных стратегиях графическим методом.
Рассмотрим теперь матричную игру без седловой точки размером n´n, где n>2. Имеем платежную матрицу:
Если эта игра является полностью усредненной, т.е. все чистые стратегии противника являются активными, то можно найти оптимальные смешанные стратегии путем решения системы уравнений n+1 порядка. Для n=2 мы ранее записывали такие системы и решали их аналитически (см. раздел 3).
Для нахождения оптимальной стратегии 1-го игрока и цены игры n необходимо решить систему уравнений:
Исходными данными для решения системы являются:
- Матрица коэффициентов при неизвестных
- Вектор свободных членов
В результате решения получим вектор неизвестных ,n.
Для нахождения оптимальной стратегии 2-го игрока и цены игры n необходимо решить систему уравнений:
Исходными данными для решения системы являются:
- Матрица коэффициентов при неизвестных
- Вектор свободных членов
В результате решения получим вектор неизвестных ,n.
Если будет получено осмысленное решение систем (найденные вероятности будут находиться в промежутке [0,1]), то предположение о том, что все чистые стратегии игроков являются активными, верное, и задача решена правильно. В противном случае так находить оптимальные стратегии нельзя, т.к. задача не является полностью усредненной.
Не полностью усредненные игры размером n´n, n>2 и любые игры размером m´n, где m¹n и m,n>2 можно решать приближенными методами или симплекс-методом (сведение к задаче линейного программирования).