Решение графическим методом игры MX2.

Решение игры с седловой точкой.

Если верхняя и нижняя цены совпадают, то эта величина называется ценой игры

Стратегии, соответствующие цене игры являются оптимальными стратегиями. Они вместе составляют решение игры.

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

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

 

Игры в смешанных стратегиях.

Если партнеры играют только 1 раз, то игрокам целесообразно придерживаться принципа минимакса в игре седловой точки, так и в игре без нее. В случае многократного повторения игры седловой точки. Когда же однократно повторяется игра без седловой точки, то постоянное использование минимакса стратегии становится не выгодным. Теорией игр доказано, что при многократно повторяемой игры без седловой точки игроку А для получения выигрыша больше, чем (альфа) следует чередовать свои стратегии,А1,А2,А3,…Аn. Подобная ситуация у игрока В.Смешанной стратегией игрока А называется применение чистых стратегий с вероятностью Р1,Р2,…Рm, причем можно записать в виде матрицы: Рi=1 и qi=1

 

SA= Sd =

 

Каждую чистую стратегию можно рассмотреть как частный случай, когда с частотой 1,а все другие,

SA=

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

Теорема Неймона каждая конечная игра имеет по крайней мере одно оптимальное решение вероятно в области смешанных стратегийà любая игра имеет цену

V < общ. случай.

Утверждение. Если 1 из игроков придерживается своей оптимальной стратегии, то выигрыш остается неизменным. Если 2 игрок не выходит за пределы своих полезных стратегий.

Это следствие Неймона.

 

2. Аналитическое решение игры 2х2. (Залеская)

Принцип доминирования.

Вектор х=(х1, х2,х3…хn)(упорядочен набор) доминирует вектор у=(у1, у2, у3…уn) если хi уi т.е все элементы вектора х соответствующих векторов у.

Про вектор у говорят, что он доминирует вектор х. Справедливо следующее утверждение:

Утверждение 1

Если в игре с платёжной матрицей А какая либо строка доминирует, над выпуклой комбинацией остальных строк, то она будет входить с нулевой вероятностью по оптимальной максимальной стратегии и её точно вычеркнут.

В частности если какая либо доминирует над другой строкой, то другую строку можно вычеркнуть.

Выпуклая комбинация векторов х1, х2,х3…хn называется выражение вида.

С1х2+С2х2+С3х2…Скх2

Утверждение 2

Если в игре с платёжной матрицей А какой либо столбец доминирует выпуклую комбинацию остальных столбцов, то он будет находиться с нулевой вероятностью в оптимальной стратегии второго игрока.

В частности если какой либо столбец доминирует над другим столбцом, то его можно вычеркнуть.

Пример:

А=( )

( 1

4. (4

Получаем новую платёжную матрицу:

( )



6.Графический метод решения игры типа 2хn и mх2.(Савицкая)
Для каждой стратегии второго игрока Вi=(i=1,2,…n) проведем прямую у.
Если первый игрок применяет свою смешанную стратегию 1, то выигрыш первого игрока, тогда второй игрок применяет стратегию Вi.

Ломаная позволяет определить минимальный выигрыш игрока А при любом поведении игрока В.
Тогда N в которой ломаная достигает max определяет решение игра.
Абсцисса (Х)(Х- вая координата) точки N определ.Р2.

Ордината точки N (игровая У) определяет цену В.

Точка N является пересечение двух прямы, а каждая прямая соответственно прямая. Пусто точка N является пересечением двух прямых Вi и Вj. Составим систему уравнений: Решение игр вида 2хn и mх2

Графо-аналитический метод.

У таких игр всегда имеется решение, содержащее не более двух активных стратегий для каждого из игроков. Если найти эти активные стратегии, то игра 2 х n или m х 2 сводится к игре 2 х 2, которую мы уже умеем решать. Поэтому игры 2 х n и m х 2 решают обычно графоаналитическим методом.
Рассмотрим решение матричной игры на примере.
Пример.


Решение.

       
  1 4 7 1
  6 3 2 2
6 4 7 2 4


a = 2, b=4, , поэтому игра не имеет седловой точки, и решение должно быть в смешанных стратегиях.
1. Строим графическое изображение игры.

Если игрок B применяет стратегию В1, то выигрыш игрока A при применении стратегии А1 равен а11 = 1, а при использовании А2выигрыш равен а21 = 6, поэтому откладываем отрезки А1В1 = 1, А2В1 = 6 на перпендикулярах в А1 и А2 и соединяем их отрезком. Аналогично для стратегий В2 и В3 строим отрезки В2 В2 и В3 В3.
2. Выделяем нижнюю границу выигрыша В1М N В3 и находим наибольшую ординату этой нижней границы, ординату точки М, которая равна цене игры.
3. Определяем пару стратегий, пересекающихся в точке оптимума М.
В этой точке пересекаются отрезки В2В2 и В1В1, соответствующие стратегиям В1 и В2 игрока B. Следовательно, стратегию В3 ему применять невыгодно. Исключаем из матрицы третий столбец и решаем игру 2 x 2 аналитически:


; ; .
Ответ: = 7/2; PA = (1/2; 1/2); QB = (1/6; 5/6; 0)

Пункт 1. [0,1]
2. Через концы проведем два перпендикуляра.
3. На левом перпендикуляре откладываем все элементы первой строки.
4. Направим перпендикуляр откладывая элементы второй строки.
5.каждую перу точек соединяем прямой.
6. Если все точки одной прямой расположены выше другой прямой, то одна стратегия доминирует.(соответственно строку вычеркиваем)
7. Находим нижнюю огибаемых отрезков, которая представляет собой выпуклую вверх ломаную .
8. На этой огибаемой находим max точку.

 

Алгоритм решения задачи. Решение графическим методом игры mx2.(Катичев) Алгоритм решения задач.

1. Берем горизонтальный отрезок [0,1];

2. Через концы этого отрезка проводим 2 перпендикуляра;

3. На левом 1(oy) откладываем все элементы матрицы А(1 строки);

4. На правом 1 элементы 2 строки

5. Каждую пару точек соединяем прямой, если все точки одной прямой располагаются выше точек другой прямой, то 1 стратегия доминирует. Соответствующую строку вычеркиваем, согласно принципу доминирования.

6. Находим нижнюю огибающую семейство отрезков, которые представляют выпуклую вверх ломанную;

7. На этой огибающей находим максимальную точку;

8. Составляем систему(2), которая соответствует указанной точке;

9. Из решения этой системы находим Р1, Р2, V;

10. Составим уравнение (3), из него находим g1.

Решение графическим методом игры MX2.

Платежная матрица имеет вид:

А=

Для каждой стратегии 1-ой строки построим прямую аi.

Ai: уравнение этой прямой Y=ai1+(ai2-ai1)x

При x=0 следует что y=ai1; при x =1 следует что y=ai2

Чтобы построить прямую ai, необходимо на оси OY отложить отрезок ai1, а на прямой проходящей через точку x=1 отложить отрезок ai2 и соединить эти 2 точки.

Необходимо провести для всех I и найти ломанную огибающую график сверху.

Рассмотрим пример.

А=

А1:Y=11-9x

A2:Y=9-3x

A3:Y=6+2x

A4:Y=10x

N:

3-5x=0

x=3/5

y=36/5=V-цена игры

x0=q2, q1=1-q2=2/5

 

Смешанная стратегия второго игрока

Для нахождения частот воспр.

9P2+6(1-P2)=36/5

3P2=6/5

P2=2\5

P3=3\5

 

5.

6. Приведение матричной игры к задачи матричного прогнозировафния. Постановка общей задачи линейного программирования. (Соколов)

7. Графический метод задачи линейного программирования. (Иванова)

Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Каждое из неравенств задачи линейного программирования (1.2) определяет на координатной плоскости некоторую полуплоскость (рис.2.1), а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (1.2) ОДР является пустым множеством.

Все вышесказанное относится и к случаю, когда система ограничений (1.2) включает равенства, поскольку любое равенство

можно представить в виде системы двух неравенств (см. рис.2.1)

 

ЦФ при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси (начальная ордината), а угловой коэффициент прямой останется постоянным (см.рис.2.1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня (см. рис.2.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора .

 

Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня , соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.

 

 

 

Рисунок 2.1 Геометрическая интерпретация ограничений и ЦФ задачи.

Методика решения задач ЛП графическим методом.

В ограничениях задачи (1.2) заменить знаки неравенств знаками точных равенств и построить соответствующие прямые. Найти и заштриховать полуплоскости, разрешенные каждым из ограничений-неравенств задачи (1.2). Для этого нужно подставить в конкретное неравенство координаты какой-либо точки [например, (0;0)], и проверить истинность полученного неравенства.

Если неравенство истинное, о надо заштриховать полуплоскость, содержащую данную точку;

иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

Поскольку и должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси и правее оси , т.е. в I-м квадранте. Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой. Поэтому необходимо выделить на графике такие прямые.

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

Если ОДР – не пустое множество, то нужно построить целевую прямую, т.е. любую из линий уровня (где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов). Способ построения аналогичен построению прямых ограничений.

Построить вектор , который начинается в точке (0;0) и заканчивается в точке . Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ. Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

Определить координаты точки max (min) ЦФ и вычислить значение ЦФ . Для вычисления координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .

 

8. Алгоритм графического решения задачи линейного программирования. (Собко)

9. (Филиппова) Симплекс метод. Многогранники.

Многогранник в – замкнутое, выпуклое, ограниченное множество с конечным числом условных точек.

Трехмерное пространство – множество упорядоченных троек чисел.

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

– множество упорядоченных ( )

Дано множество N граничная, если каждая окрестность точки содержит как точки множества M , так и точки непренадлежащие множеству М.

Множество замкнутое – если оно содержит все свои граничные точки.

Множество ограниченное – если его можно поместить в шар некоторого радиуса с центром в начале координат.

Множество выпуклое – если вместе с любыми двумя точками оно содержит отрезок, соединяющий эти точки (на плоскости). В общем случае это определение эквивалентно следующему.

 

 

Рис – 1 выпуклое Рис – 2 выпуклое Рис – 3не выпуклое

Множество выпуклое – если на ряду с двумя точками ( ) оно содержит выпуклую комбинацию этих точек +

Выпуклая комбинация 0, 0,

Угловая точка – точка, которая не является выпуклой линейной комбинацией точек этого множества.

 

 

 

 


Рис -1 Рис -2 Рис -3

На рисунке 3 условных точек бесконечное множество.

Условия:

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

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

3. Целевая функция заданных линейным программированием достигает экстремума в угловой точке ОДР. Причем если целевая функция достигает экстремума в нескольких условных точках ОДР, то она достигает экстремума в любой выпуклой линейной комбинации этих точек.

4. Угловую точку описывают с помощью опорного решения. Любое опорное решение является угловой точкой ОДР и любая угловая точка ОДР является опорным решение.

Задача линейного программирования в канонической форме.

 

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

так поступают с каждым из неравенств, получим систему ограничений формы равенства.

Задача линейного программирования в канонической форме имеет вид

F(x)=

Векторная форма

; ;


;

+

Опорным решением задачи линейного программирования такое допустимое решение =( 0…0) для которого векторы условия , ,… линейно независимы.

Линейно независимы векторы если из условия +…+ =0 – линейная комбинация векторов.

Линейная независимость означает, что линейная комбинация равна 0, только при 0 наборе.

Линейная зависимость это один из векторов равен 0.

Условие:

Каждому опорному решению соответствует угловая точка и наоборот между опорными решениями и угловыми точками существуют взаимно-однозначное соответствие.