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

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

Если верхняя и нижняя цены совпадают, то эта величина называется ценой игры Решение графическим методом игры MX2. - student2.ru

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

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

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

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

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

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

SA= Решение графическим методом игры MX2. - student2.ru Sd = Решение графическим методом игры MX2. - student2.ru

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

SA= Решение графическим методом игры MX2. - student2.ru

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

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

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

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

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

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

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

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

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

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

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

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

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

С1х22х23х2…Скх2

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

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

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

Пример:

А=( Решение графическим методом игры MX2. - student2.ru )

( 1 Решение графическим методом игры MX2. - student2.ru

4. (4 Решение графическим методом игры MX2. - student2.ru

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

( Решение графическим методом игры MX2. - student2.ru )



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 решают обычно графоаналитическим методом.
Рассмотрим решение матричной игры на примере.
Пример.

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


Решение.

        Решение графическим методом игры MX2. - student2.ru
  1 4 7 1
  6 3 2 2
Решение графическим методом игры MX2. - student2.ru 6 4 7 2 4


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

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

Если игрок 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 аналитически:

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


Решение графическим методом игры MX2. - student2.ru Решение графическим методом игры MX2. - student2.ru ; Решение графическим методом игры MX2. - student2.ru ; Решение графическим методом игры MX2. - student2.ru .
Ответ: γ = 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.

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

А= Решение графическим методом игры MX2. - student2.ru

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

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

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

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

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

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

А= Решение графическим методом игры MX2. - student2.ru

А1:Y=11-9x

A2:Y=9-3x

A3:Y=6+2x

A4:Y=10x

N: Решение графическим методом игры MX2. - student2.ru

3-5x=0

x=3/5

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

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

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

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

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

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

3P2=6/5

P2=2\5

P3=3\5

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

5.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Построить вектор , Решение графическим методом игры MX2. - student2.ru который начинается в точке (0;0) и заканчивается в точке Решение графическим методом игры MX2. - student2.ru . Если целевая прямая и вектор Решение графическим методом игры MX2. - student2.ru построены верно, то они будут перпендикулярны.

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

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

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

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

Многогранник в Решение графическим методом игры MX2. - student2.ru – замкнутое, выпуклое, ограниченное множество с конечным числом условных точек.

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

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

Решение графическим методом игры MX2. - student2.ru – множество упорядоченных ( Решение графическим методом игры MX2. - student2.ru )

Дано множество N Решение графическим методом игры MX2. - student2.ru граничная, если каждая окрестность точки содержит как точки множества M , так и точки непренадлежащие множеству М.

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

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

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

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

Множество выпуклое – если на ряду с двумя точками ( Решение графическим методом игры MX2. - student2.ru ) оно содержит выпуклую комбинацию этих точек Решение графическим методом игры MX2. - student2.ru + Решение графическим методом игры MX2. - student2.ru

Выпуклая комбинация Решение графическим методом игры MX2. - student2.ru ≥0, Решение графическим методом игры MX2. - student2.ru ≥0, Решение графическим методом игры MX2. - student2.ru

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

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

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

Условия:

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

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

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

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

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

Каждое ограничение задач линейного программирования записано в виде неравенства, Решение графическим методом игры MX2. - student2.ru , его можно обратить в равенство, добавляя новые неизвестные в левую часть ( Решение графическим методом игры MX2. - student2.ru ).

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

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

F(x)= Решение графическим методом игры MX2. - student2.ru

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

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

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

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


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

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

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

Линейно независимы векторы если из условия Решение графическим методом игры MX2. - student2.ru +…+ Решение графическим методом игры MX2. - student2.ru =0 – линейная комбинация векторов.

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

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

Условие:

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

Наши рекомендации