Теория игр, рафический метод в теории игр

       - максиминная стратегия, - минимаксная стратегия

     Если    то элемент называется седловым элементом матрицы

     A=

       Теорема 4. (о разрешимости матричной игры в чистых стратегиях) Если платежная матрица A имеет седловой элемент , то матричная игра имеет решение в чистых стратегиях, при этом оптимальной стратегий первого игрока является Xi0 чистая стратегия, а для второго – Yj0 чистая стратегия, а цена игры       v = .

     Пример. Найти решение игры, заданной платежной матрицей  A=

     Решение:

     Решим игру. Пусть -оптимальная стратегия первого игрока, - оптимальная стратегия второго игрока, v – цена игры.

     Рассмотрим матрицу

                     min

           

     max  2    3

       v==2 цена игры v = 2 , существует седловой элемент =, тогда решение в чистых стратегиях имеет вид:

       оптимальная стратегия первого  игрока:

     оптимальная стратегия второго игрока:

     Ответ: оптимальные стратегии игроков ; , цена игры     v =2 .

 

     

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

     Рассмотрим  игру с платежной матрицей

     A=.

     Если  ,то говорят, что j-ая строка доминируется i-ой строкой, при этом i-ая строка называется доминирующей для первого игрока P1; j-ая строка – доминируемой строкой для P1.

     Если  , то говорят, что i-ый столбец доминируется j-ым столбцом, при этом j-ый столбец называется доминирующим для второго игрока P2; i-ый столбец – доминируемый для P2. Доминируемую для игрока P1 строку и доминируемый для  P2  столбец можно вычеркнуть (удалить).

     Пример. Упростить платежную матрицу A=, используя принцип доминирования.

     Решение.

     1 способ: , т.к. - доминирующая строка, -

     доминируемая  строка (1) 

     2 способ:, (1) 

 

     

     5.Решение матричной игры 2×2 в смешанных стратегиях

     

     Решить  игру с платежной матрицей 

     

     Платежная функция 

     

     Решить  игру с платежной матрицей   

     Положим  . Тогда  

     

     . Тогда  
 

      Если - оптимальная стратегия первого игрока, то по определению

решения матричной игры   
 

      Если игра с нулевой суммой, то (-цена игры).  
 
 

     Решая систему, получим . 
 
 
 

     

     Аналогично  для второго игрока:

     

       Тогда

     

       Тогда 

     Если  - оптимальная стратегия второго игрока.

      Если игра с нулевой суммой, то (-цена игры).  
 

     Решая систему, получим .

     Пример.  Найти решение игры заданной платежной матрицей A= .

     Решение:

     Решим игру. Пусть - оптимальная стратегия первого игрока,            - оптимальная стратегия второго игрока,-цена игры. Тогда оптимальные стратегии игроков и цену игры можно найти, решив системы:

           

          

           

           

                    

     Ответ: оптимальные стратегии игроков , цена игры . 

 

     

     Геометрическое  решение игры

     1.Решение  игр с платежной  матрицей 2×n

     Решить  игру с платежной матрицей  A=

     Алгоритм:

1. Через концы горизонтального отрезка [0;1] провести два перпендикуляра к нему: левый и правый. Каждой точке отрезка [0;1] будем ставить некоторую смешанную стратегию (x;1− x).
2. На левом перпендикуляре от точки 0 отложить элементы . На правом перпендикуляре от точки 1 отложить элементы .

     Замечание. Масштабы на левом и правом перпендикулярах  должны быть

одинаковы, не обязательно совпадающие с  масштабом горизонтального отрезка [0;1].

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

     Решить  игру с платежной матрицей  A= графически.

     Решение:

1. Через концы горизонтального отрезка [0;1] проведем 2 перпендикуляра к нему. Каждой точке отрезка [0;1] будем ставить смешанную стратегию (x; 1− x).
2. На левом перпендикуляре от точки 0 отложить элементы 2, 3, 11. На правом перпендикуляре от точки 1 отложить элементы 7, 5, 2.
3. Соединить отрезками элементы 2 и 7, 3 и 5, 11 и 2.

 

     

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

     максимальную  точку. Точка является пересечением отрезков [3;5] и [11;2]. Тогда оптимальную стратегию можно найти при помощи матрицы .

     Решим игру с платежной матрицей .

     Оптимальные стратегии игроков  и цену игры можно найти, решив системы:

     

     

     

           

          

           

     Ответ: оптимальные стратегии игроков оптимальные стратегии игроков , цена игры  

 

     

     2.Решение  игр с платежной  матрицей m×2

     Решить  игру с платежной матрицей A=.

     Алгоритм:

1. Через концы горизонтального отрезка [0;1] провести два перпендикуляра к нему: левый и правый. Каждой точке отрезка [0;1] будем ставить некоторую смешанную стратегию (y;1− y).
2. На левом перпендикуляре от точки 0 отложить элементы . На правом перпендикуляре от точки 1 отложить элементы .
3. Соединить отрезками элементы .
4. Выделить верхнюю огибающую всех построенных отрезков, и найти минимальную точку (точки). Пусть точка является пересечением отрезков Тогда оптимальную стратегию можно найти при помощи матрицы .

     Пример. Решить игру с платежной матрицей A=.

     Решение:

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

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

     

4. Выделим верхнюю  огибающую всех построенных отрезков, и найдем минимальную точку. Точка является пересечением отрезков [6;5] и [1;8]. Тогда оптимальную стратегию можно найти при помощи матрицы .

     Решим игру с платежной матрицей

         

         

     Ответ: оптимальные стратегии игроков оптимальные стратегии игроков , цена игры

 

Практическая  Часть

1. Решить Систему
1. По формулам Крамера

 

Решение.

1)Составим определитель из коэффициентов стоящих при неизвестных в системе. 
 
 
 
 
 
 
 
 

2)Тогда по теореме Крамера: 
 
 

3)Проверка: 

Ответ:

2. Методом Гаусса

 

Решение.

1)Составим расширенную матрицу системы: 

2)Преобразим расширенную матрицу к ступенчатому виду: 

 

3)Расширенная приведена к расширенному виду. Получили следующую систему уравнений: 
 
 
 
 
 
 
 
 
 

Ответ:

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