Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Лекции по ТПР - файл Лекция№16-тпр.doc


Лекции по ТПР
скачать (681.7 kb.)

Доступные файлы (18):

Лекция№01-тпр.doc38kb.12.11.2008 13:15скачать
Лекция№02-тпр.doc97kb.12.11.2008 13:25скачать
Лекция№03-тпр.doc179kb.12.09.2004 22:30скачать
Лекция№04-тпр.doc146kb.12.09.2004 22:31скачать
Лекция№05-тпр.doc131kb.12.09.2004 22:32скачать
Лекция№06-тпр.doc248kb.12.09.2004 22:33скачать
Лекция№09.doc177kb.03.10.2006 21:09скачать
Лекция№10-тпр.doc179kb.12.09.2004 22:49скачать
Лекция№11-тпр.doc353kb.25.11.2005 11:46скачать
Лекция№12-тпр.doc205kb.12.09.2004 22:53скачать
Лекция№13-тпр.doc191kb.12.09.2004 22:54скачать
Лекция№14-тпр.doc83kb.14.12.2004 14:25скачать
Лекция№15-тпр.doc301kb.12.09.2004 23:02скачать
Лекция№16-тпр.doc131kb.12.09.2004 23:04скачать
Лекция№17-тпр.doc542kb.12.09.2004 23:03скачать
Лекция№7-тпр.doc142kb.12.09.2004 22:38скачать
Лекция№8-тпр.doc93kb.12.09.2004 22:44скачать
Лекция№9-тпр.doc142kb.12.09.2004 22:47скачать

Лекция№16-тпр.doc

Лекция №17.

Решение и геометрическая интерпретация игры (2x2).

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

Пусть игрок А использует стратегию , а игрок В – стратегию В1. Тогда выигрыш игрока А определяется из уравнения

.

Если же игрок В будет применять стратегию В2, то выигрыш игрока А не изменится и будет определяться равенством

.

Принимая во внимание условие , можно записать систему уравнений с тремя неизвестными величинами:

,

, (1)

.

Решив эту систему уравнений, находим оптимальную смешанную стратегию игрока А, т.е. и .

Аналогично определяется оптимальная стратегия игрока В из системы уравнений:


,

, (2)

.

В результате решения системы уравнений (2) находятся вероятности и , т.е. оптимальная стратегия .

Игра (2х2) допускает простую геометрическую интерпретацию. Для этого в системе координат хОу на оси абсцисс откладывается отрезок А12, равный единице, и через концы этого отрезка проводятся перпендикулярные к оси абсцисс прямые, на которых откладываются выигрыши игрока А (рис.1).

Л
евый перпендикуляр, совпадающий с осью ординат, соответствует стратегии А1, для которой Р1=1, Р2=0, а правый равен стратегии А2, для которой Р1=0, Р2=1. При применении игроком В стратегии В1 выигрыш будет а11, если игрок А использует стратегию А1, и будет а21, если он применяет стратегию А2. Отложив отрезки, равные а11 и а21 на соответствующих перпендикулярах получим две точки: В1 соответствующий стратегии А1 и В1 соответствующий стратегии А2. Ордината любой точки отрезка В1В2 равна величине выигрыша игрока А при применении им стратегии А1 и А2 с вероятностями Р1 и Р2.

Если игрок В применяет стратегию В2, то выигрыш игрока А равен а12 при использовании стратегии А1, и а22 – стратегии А2. Ординаты точек, лежащие на отрезке В2В2, равны среднему выигрышу игрока А, если он применяет стратегии А1 и А2 с вероятностями Р1 и Р2, а противник -–стратегию В2.

Для нахождения оптимальной стратегии построим нижнюю границу выигрыша игрока А, т.е. ломаную В2NB1, отмеченную на рис.1 линией. Очевидно, что на этой ломанной лежат минимальные выигрыши игрока А при использовании им любой смешанной стратегии.

Оптимальное решение игры определяет точка N, в которой выигрыш игрока А принимает наибольшее значение (проигрыш игрока В наименьшее значение) равный цене игры . Проекция этой точки на ось абсцисс соответствует оптимальной стратегии , при этом расстояния от точки до концов единичного отрезка на оси абсцисс равны вероятностям и .

Оптимальная стратегия игрока В находится аналогично. Для этого необходимо поменять местами игроков А и В. (см. рис.2)





Н

а рис.1 и 2 решение игры определялось точкой пересечения стратегий, однако это справедливо не всегда. Так, например на рис.3 показан случай, когда нижняя граница выигрыша игрока А совпадает с отрезком В2В2, т.е. стратегия В1 для игрока В заведомо не выгодная. Здесь , игра имеет седловую точку.

На рис.4 показан случай, в котором ,. Игра имеет седловую точку.

^ Решение игры (2хn) и (mx2).

Существует теорема, которая гласит: любая конечная игра с нулевой суммой (mxn) имеет решение, в котром число активных стратегий каждого игрока не превосходит l, где l=min(m,n). Следовательно у игры (2хn) или (mx2) всегда имеется решение, содержащее не более двух активных стратегий у каждого из игроков. Если эти активные стратегии игроков будут найдены, то игра (2хn) или (mx2) превращается в игру (2х2).

Практическое решение игры (2хn) осуществляется следующим образом:

1. Строится графическое изображение игры;

2. Выделяется нижняя граница выигрыша и находится наибольшая ордината нижней границы, которая равна цене игры ;

3. Определяется пара стратегий, пересекающихся в точке оптимума. Эти стратегии являются активными стратегиями игрока В. Таким образом, игра (2хn) сведена к игре (2х2).(см. рис.5). Если в точке оптимума пересекаются более двух стратегий, то в качестве активных стратегий может быть выбрана любая пара из них. Решение игры (mx2) осуществляется а
налогично.


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

Цена игры , которая получается при решении ЗЛП (5)-(7) и (13)-(15) должна быть одной и той же величиной. Будут ли они действительно равны? Положительный ответ на этот вопрос следует из факта, что эти две задачи образуют пару двойственных ЗЛП. Теорема о таких задачах гласит: если одна из ЗЛП двойственной пары имеет решение, то другая задача также имеет решение, причем экстремальные значения целевых функций совпадают.

Покажем, что ЗЛП (13)-(15) имеет решение. Для этого необходимо, чтоб условия (13)-(14) были совместны, т.е. имели хотя бы одно решение, а максимизируемая целевая функция была ограничена сверху.

Действительно, ограничения (13)-(14) совместны, т.к. уj=0 () удовлетворяют ограничениям (13),(14). Следовательно, множество планов (13),(14) не пустое. В силу условия (13) все значения уj () ограничены сверху, а это означает ограниченность сверху целевой функции (15). Таким образом ЗЛП (13)-(15) имеет решение. Тогда на основании теоремы о двойственности ЗЛП (5)-(7) тоже имеет решение, причем

,

т.е. в обеих задачах значение цены игры  одинаковое.

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


Скачать файл (681.7 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации