Использование теории игр при разработке управленческих решений»

Если игрок 1 воспользуется i-м выбором, то противник для минимизации  его выигрыша  сделает тот из своих выборов, который даст min hij. Соответственно, игрок 1 должен использовать тот выбор, который гарантирует ему выигрыш, не меньший

V⋏ =maxi minj hij , где i=1…m; j=1…n

(V⋏  – нижняя цена игры).

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

                                 V⋏= minjmaxi hij  , где i=1…m; j=1…n

(V⋏- верхняя цена игры)

Максиминная и минимаксная стратегии, соответствующие цене игры, являются оптимальными стратегиями первого и второго игроков, а их совокупность – решением игры.

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

Пара чистых стратегий (i*,j*) создает в игре ситуацию равновесия тогда и только тогда, когда в матрице выигрышей существует элемент hi*j*,  который одновременно является наибольшим в своем столбце и наименьшим в своей строке. Этот элемент (если он существует) называется седловой точкой.

Пример 1.

Седловые точки - (4, 1) и (4, 2). Цена игры = 6; оптимальный выбор для игрока 1 - четвертый, для игрока 2 равнозначны первый и второй.

Пример 2. Пусть игра определяется матрицей

Здесь равенство V1 = V2 не выполняется; оптимальной чистой стратегии для игроков нет.

При анализе игр часто  прибегают к попыткам обнаружить доминирование между строками и столбцами. Так в примере 1 элементы четвертой строки больше элементов других строк: использование выбора 4 выгоднее других выборов при любой политике противника. Противник видит, что в такой ситуации использовать выборы 3 и 4 неразумно.  Использование доминирования позволяет уменьшить размеры изучаемой матрицы исключением "невыгодных" строк и столбцов.

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

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

Стратегии игрока А | Стратегии игрока В |

| B1 | B2 | B3 |

A1 | 2 | 5 | 4 |

A2 | 3 | 1 | 4 |

A3 | 4 | 2 | 3 |

 

Введенная матрица показывает выигрыш игрока А, в зависимости от выбранного им действия и от ответного действия игрока В. Мы рассматриваем игру двух игроков, в которой выигрыш одного из них равен проигрышу другого. Внешние факторы отсутствуют. Оба игрока обладают конечным числом действий и логикой, которая определят их действия (рассмотрим ниже). Строки матрицы являются возможными действиями игрока А, столбцы матрицы - возможными действиями игрока В. Возможные действия игроков называются чистыми стратегиями.

В нашем случае, количество чистых стратегий игрока А равно 3. Количество чистых стратегий игрока В равно 3.

Игрок А имеет в своем распоряжении три чистые стратегии:

* Если  игрок А выберет стратегию A1 ,то при любом действии игрока B, он гарантирует себе выигрыш 2 ,т.е. получит не менее 2 ден.ед.

* Если  игрок А выберет стратегию A2 ,то при любом действии игрока B, он гарантирует себе выигрыш 1 ,т.е. получит не менее 1 ден.ед.

* Если  игрок А выберет стратегию A3 ,то при любом действии игрока B, он гарантирует себе выигрыш 2 ,т.е. получит не менее 2 ден.ед.

Стратегии игрока А | Стратегии игрока В | Минимальный элемент в строке |

| B1 | B2 | B3 |  |

A1 | 2 | 5 | 4 | 2 |

A2 | 3 | 1 | 4 | 1 |

A3 | 4 | 2 | 3 | 2 |

Игрок А использует логику, которая гарантирует ему максимальный выигрыш вне зависимости от поведения игрока В.

 Свой выбор, игрок А остановит на стратегии A1, которая обеспечит ему выигрыш 2, т.е. доход не менее 2 ден.ед.

Значение равное 2, называется нижней ценой игры.

V⋏ =maxi minj hij=2

Игрок В также имеет в своем распоряжении три чистые стратегии:

* Если  игрок В выберет стратегию В1 ,то при любом действии игрока B, он гарантирует себе выигрыш 4 ,т.е. получит не менее 4 ден.ед.

* Если  игрок В выберет стратегию В2 ,то при любом действии игрока B, он гарантирует себе выигрыш 5 ,т.е. получит не менее 5 ден.ед.

* Если  игрок В выберет стратегию В3 ,то при любом действии игрока B, он гарантирует себе выигрыш 4 ,т.е. получит не менее 4 ден.ед.

Стратегии игрока А | Стратегии игрока В | Минимальный элемент в строке |

| B1 | B2 | B3 |  |

A1 | 2 | 5 | 4 | 2 |

A2 | 3 | 1 | 4 | 1 |

A3 | 4 | 2 | 3 | 2 |

Максимальный элемент  в столбце | 4 | 5 | 4 |  |

Игрок В использует логику, которая гарантирует ему минимальный проигрыш вне зависимости от поведения игрока А.

Свой выбор, игрок В остановит на стратегии В1, которая обеспечит ему проигрыш 4, т.е. потерю не более 4 ден.ед.

Значение равное 4, называется верхней ценой игры.

V⋏= minjmaxi hij=4

Так как нижняя цена игры не равна верхней цене игры, то конечная игра не имеет седловой точки и решения в чистых стратегиях.

В теории игр седловая точка (седловой элемент) — это наибольший элемент столбца матрицы игры, который одновременно является наименьшим элементом соответствующей строки (в игре двух лиц с нулевой суммой). В этой точке, следовательно, максимин одного игрока равен минимаксу другого; седловая точка есть точка равновесия.

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

Смешанной стратегией игрока А называется применение чистых стратегий A1 , A2 , A3 c вероятностями p1 , p2 , p3.

Смешанную стратегию первого  игрока обозначают:

P = (p1, p2 , p3 ) , где p1+p2+p3 = 1   и   p1, p2 , p3 ≥0

Смешанной стратегией игрока B называется применение чистых стратегий B1 , B2 , B3 c вероятностями q1,q2 , q3.

 Смешанную стратегию  второго игрока обозначают:

Q = (q1,q2 , q3) , где q1+q2 + q3= 1   и   q1,q2 , q3 ≥0

Оптимальное решение игры (или просто - решение игры) - это  пара оптимальных смешанных стратегий

P* (p1*, p2*, p3* ) и Q* (q1*, q2* , q3* )

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

Выигрыш игрока А равный проигрышу игрока В , соответствующий оптимальному решению, называется ценой игры V.

Цена игры больше либо равна  нижней цены игры и меньше или равна  верхней цены игры        V⋏ ≤V≤ V⋏.

В нашем случае : 2 ≤V≤4

Стратегии игрока А | Стратегии игрока В |

| B1 | B2 | B3 |

A1 | 2 | 5 | 4 |

A2 | 3 | 1 | 4 |

A3 | 4 | 2 | 3 |

 

Если P* (p1*, p2*, p3* ) и Q* (q1*, q2* , q3*) являются оптимальным решением, то должны выполняться две следующие системы неравенств

2p1*+3p2 *+4p3*≥V

5p1*+p2 *+2p3*≥V

4p1*+4p2 *+3p3*≥V

2q1*+ 5q2*+4q3*≤V

3q1*+ q2*+4q3*≤V

4q1*+ 2q2*+3q3*≤V

Рассмотрим первую систему.

Разделим почленно первую систему на v (цену игры).

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

y1=p1*V, y2=p2*V, y3=p3*V

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

y1+y2+y3=p1*V+p2*V+p3*V=1V*p1*+p2*+p3*=1V  →min

Т.к игрок A старается увеличить  свой выигрыш, т.е. цену игры V, то выражение 1V будет стремиться к минимуму.

Мы получили задачу линейного  программирования.

Требуется найти максимум линейной функции F = y1+y2+y3 при следующей системе ограничений:

2y1+3y2+4y3≥1

5y1+y2+2y3≥1

4y1+y2+3y3≥1

Рассмотрим вторую систему.

Разделим почленно вторую систему на V (цену игры).Т.к. цена игры положительная, то знаки в неравенствах системы не изменятся.

Введем новые обозначения:

x1=q1*V, x=q2*V, x3=q3*V

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

x1+x2+x3=q1*V+q2*V+q3*V=1V*q1*+q2*+q3*=1V → max

Т.к игрок B старается уменьшить  свой проигрыш, т.е. цену игры V, то выражение  1 V  будет стремиться к максимуму.

Мы получили задачу линейного  программирования.

Требуется найти максимум линейной функции L = x1+x2+x3 при следующей системе ограничений:

2x1+5x2+4x3 ≤1

3x1+x+4x3 ≤1

4y1+2y2+3y3 ≤1

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

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

К левой части неравенства 1 системы ограничений прибавляем неотрицательную переменную x4, тем самым мы преобразуем неравенство 1 в равенство.

К левой части неравенства 2 системы ограничений прибавляем неотрицательную переменную x5 , тем самым мы преобразуем неравенство 2 в равенство.

К левой части неравенства 3 системы ограничений прибавляем неотрицательную переменную x6, тем самым мы преобразуем неравенство 3 в равенство.

2x1+5x2+4x3+x4= 1

3x1+x+4x3+ x5 =1

4y1+2y2+3y3+x6 =1

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

Определимся с начальным  опорным решением.

Наличие единичного базиса в системе ограничений позволяет  легко найти начальное опорное  решение. Рассмотрим подробнее:

Переменная x4 входит в уравнение 1 с коэффициентом 1, а в остальные  уравнения системы с коэффициентом  ноль, т.е. x4- базисная переменная.

Переменная x5 входит в уравнение 2 с коэффициентом 1, а в остальные  уравнения системы с коэффициентом  ноль, т.е. x5 - базисная переменная.

Переменная x6 входит в уравнение 3 с коэффициентом 1, а в остальные  уравнения системы с коэффициентом  ноль, т.е. x6- базисная переменная.

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

X0 = ( 0 , 0 , 0 , 1 , 1 , 1 )

Значение функции для  начального решения: L (X0) = 0

При составлении исходной симплекс таблицы, коэффициенты при  переменных функции L записываются с противоположными знаками, а свободный член со своим знаком.

Шаг 1

За ведущий выберем  столбец 1, так как -1 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем.

За ведущую выберем  строку 3, так как отношение свободного члена к соответствующему элементу выбранного столбца для 3 строки является наименьшим. Обратите внимание, что отношение мы вычисляем только для положительных элементов столбца 1.

Базисные переменные | X1 | X2 | X3 | X4 | X5 | X6 | βi | δi |

X4 | 2 | 5 | 4 | 1 | 0 | 0 | 1 | 12 |

X5 | 3 | 1 | 4 | 0 | 1 | 0 | 1 | 13 |

X6 | 4 | 2 | 3 | 0 | 0 | 1 | 1 | 14 |

L | -1 | -1 | -1 | 0 | 0 |  | 0 | - |

Разделим элементы строки 3 на 4.

Базисные переменные | X1 | X2 | X3 | X4 | X5 | X6 | βi | δi |

X4 | 2 | 5 | 4 | 1 | 0 | 0 | 1 | 12 |

X5 | 3 | 1 | 4 | 0 | 1 | 0 | 1 | 13 |

X6 | 1 | 12 | 34 | 0 | 0 | 14 | 14 | 14 |

ъL | -1 | -1 | -1 | 0 | 0 |  | 0 | - |

От элементов строки 1 отнимает соответствующие элементы строки 3 умноженные на 2.

От элементов строки 2 отнимает соответствующие элементы строки 3 умноженные на 3.

От элементов строки L отнимает соответствующие элементы строки 3 умноженные на -1.

Базисные переменные | X1 | X2 | X3 | X4 | X5 | X6 | βi | δi |

X4 | 0 | 4 | 52 | 1 | 0 | -12 | 12 | - |

X5 | 0 | -12 | 74 | 0 | 1 | -34 | 14 | - |

X6 | 1 | 12 | 34 | 0 | 0 | 14 | 14 | - |

L | 0 | -12 | -14 | 0 | 0 | -14 | 14 | - |

X1= ( 14, 0, 0, 12, 14, 0 )

Значение функции L для  данного решения: L (X1) = 14

Шаг 2

За ведущий выберем  столбец 2, так как - 12 наименьший элемент в L строке. Элемент L строки, принадлежащий столбцу свободных членов не рассматриваем.

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

Базисные переменные | X1 | X2 | X3 | X4 | X5 | X6 | βi | δi |

X4 | 0 | 4 | 52 | 1 | 0 | -12 | 12 | 18 |

X5 | 0 | -12 | 74 | 0 | 1 | -34 | 14 | - |

X6 | 1 | 12 | 34 | 0 | 0 | 14 | 14 | 12 |

L | 0 | -12 | -14 | 0 | 0 | 14 | 14 | - |

Разделим элементы строки 1 на 4.

Базисные переменные | X1 | X2 | X3 | X4 | X5 | X6 | βi | δi |

X4 | 0 | 1 | 58 | 14 | 0 | -18 | 18 | 18 |

X5 | 0 | -12 | 74 | 0 | 1 | -34 | 14 | - |

X6 | 1 | 12 | 34 | 0 | 0 | 14 | 14 | 12 |

ъL | 0 | -12 | -14 | 0 | 0 | 14 | 14 | - |

От элементов строки 2 отнимает соответствующие элементы строки 1 умноженные на - 12.