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

Если v_j>0 – выигрыш;

        v_j<0 – проигрыш;

        v_j=0 – ничейный исход (j= ).

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

v₁+ v₂+…+v_n=0.,

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

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

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

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

Простейшими являются игры 2 лиц с нулевой суммой. Пусть  в такой игре игрок 1 имеет m выборов и игрок 2 - n выборов. Если игрок 1 делает свой i-й выбор, а игрок 2 - свой j-й выбор, то выигрыш игрока 1 (проигрыш игрока 2) равен . Такая игра называется матричной и матрица H= [ / i=1..m , j=1..n ] называется матрицей выигрышей (платежной матрицей).

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

, где i=1…m; j=1…n

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

Противник, рассуждая аналогично, приходит к выводу о гарантированном  проигрыше, не превышающем              
                                   , где i=1…m; j=1…n

(

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

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

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

Пример 1.

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

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

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

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

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

 

 

 

 

 

 

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

 

	2	5	4
	3	1	4
	4	2	3

 

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

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

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

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

				Минимальный элемент  в строке
	2	5	4	2
	3	1	4	1
	4	2	3	2

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

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

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

 

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

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

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

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

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

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

 

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

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

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

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

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

P = (, , ) , где ++ = 1   и   , , 0

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

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

Q = (, , ) , где + + = 1   и   , , 0

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

P* (, , ) и Q* (, , )

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

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

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

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

	2	5	4
	3	1	4
	4	2	3

 

Если P* (, , ) и Q* (, , )

  являются оптимальным решением, то должны выполняться две следующие системы неравенств

 

 

 

 

 

 

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

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

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

 

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

→min

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

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

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

 

 

 

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

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

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

 

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

   →max

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

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

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

 

 

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

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

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

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

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

 

 

 

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

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

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

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

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

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

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

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

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

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

Шаг 1

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

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

Базисные переменные
	2	5	4	1	0	0	1
	3	1	4	0	1	0	1
	4	2	3	0	0	1	1
L	-1	-1	-1	0	0		0	-