ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ
ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ»
КАФЕДРА ВЫСШЕЙ МАТЕМАТИКИ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ И
ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ
по курсу
«ТЕОРИЯ ИГР»
для студентов факультета
гостиничное дело
ИЗДАТЕЛЬСТВО САНКТ-ПЕТЕРБУРГСКОГО
ГОСУДАРСТВЕННОГО ЭКОНОМИЧЕСКОГО УНИВЕРСИТЕТА
2017
Цели и задачи дисциплины по направлению Гостиничное дело: Получение базовых знаний и формирование основных навыков в использования математических методов и основ математического моделирования; Развитие понятийной базы и формирование уровня подготовки, необходимых для понимания основ математического моделирования в экономике. В результате, студенты должны владеть основными математическими понятиями задачи теории игр; уметь использовать математический аппарат для решения теоретических и прикладных задач, уметь решать типовые задачи, иметь навыки работы со специальной математической литературой.
Место дисциплины в структуре ООП по направлению Гостиничное дело: задача «теория игр» относится к циклу Б.2.2 Математический и естественнонаучный цикл, Вариативная часть. Входные знания, умения и компетенции студентов должны соответствовать дисциплинам «Математика» и «Теория вероятностей и математическая статистика».
Рецензент: канд. физ.-мат. наук, доцент –
Издательство СПбГЭУ, 2017
Методические указания к решению задач «Теории игр» геометрическими методами
Задача 1. Платёжная матрица имеет вид: 
Найти цену игры и оптимальную стратегию.
Решение. Задана платёжная матрица размера (4х4). Набор чисел платёжной матрицы имеет смысл платы игрока В игроку А в зависимости от выбранных им стратегий. Стратегии игрока А – это строки матрицы. Стратегии игрока В – столбцы матрицы. Пусть стратегии игрока А нумеруются сверху вниз, а стратегии игрока В – слева направо. Задача игрока А – получить наибольший выигрыш, а задача игрока В – оказаться в наименьшем проигрыше. По правилам игры игрок А выбирает свою стратегию, не зная, какую стратегию выберет игрок В и наоборот: игрок В выбирает свою стратегию, не зная, какую стратегию выберет игрок А. В соответствии с определением, стратегия игрока А – строка чисел. Например, его вторая стратегия – это (3,5,-1,2): если при этом игрок В выбирает первую стратегию, то игрок В платит игроку А 3 ед., при выборе игроком В второй стратегии игрок А получит 5 ед., при выборе игроком В третьей стратегии игрок А платит 1 ед. и, наконец, игрок А получает 2 ед., если игрок В выбирает четвёртую стратегию. Если какая-то стратегия является предпочтительной по отношению к другой, то говорят, что та стратегия, которая более выгодная является доминирующей. Видно, что в заданной платёжной матрице вторая стратегия игрока А доминирует его первую, а третья его – доминирует четвёртую. Следовательно первую и четвёртую стратегии игрока А можно вычеркнуть. Аналогично заключаем, что четвёртая стратегия игрока В также может быть вычеркнута, так как её доминирует третья. В результате вычёркиваний приходит к платёжной матрице (2х3).
Попытаемся найти решение полученной после упрощений задачи в чистых стратегиях. Для этого справа в каждой строке выпишем гарантированный выигрыш игрока А, а внизу под каждым столбцом – максимальный проигрыш игрока В для каждой из стратегий:
4 5 5
Договоримся считать, что теперь у игрока А имеется первая и вторая стратегии, а у игрока В – первая, вторая и третья (в оговоренном ранее порядке).
Для игрока А наилучшей является первая стратегия, так как он в наихудшем случае проигрывает 1 ед.: a0 =–1 – нижняя цена игры, а для игрока В наилучшей является первая стратегия, так как он в худшем случае платит 4 ед. = b0 верхняя цена игры. Так как нижняя и верхняя цены игры не совпадают, то в чистых стратегиях задача не имеет решения.
Найдём решение задачи в смешанных стратегиях. Для этого будем считать, что игрок А с вероятностью р использует первую стратегию и с вероятностью 1 – р – вторую.
Найдём средний проигрыш игрока В.
Если игрок В выбирает первую стратегию, то он платит игроку А математическое ожидание проигрыша равное
u1=3p+4(1 – p)=4 – p
Если игрок В выбирает вторую стратегию, то он платит игроку А математическое ожидание проигрыша равное
u2=5p – 3(1 – p)=8p – 3
Если игрок В выбирает третью стратегию, то он платит игроку А математическое ожидание проигрыша равное
u3= – 1p+5(1 – p)=5 – 6p
Так как неизвестной величиной является только одна – вероятность р, то проигрыш игрока В удобно изобразить на графике в переменных (u, p).
Изучим график. Если игрок А зафиксировал вероятность р1, то игрок В имеет возможность выбора стратегии из трёх вариантов: он выберет либо первую стратегию, тогда в среднем будет платить С единиц, либо вторую стратегию, тогда в среднем он будет платить К единиц, либо третью, тогда в среднем он будет платить В единиц. Естественно он заинтересован в наименьшей плате, поэтому он выберет стратегию 2.(точка К) Понимая это, игрок А захочет получить больший выигрыш и выберет другую вероятность, например, р2. Аналогичное рассмотрение этой вероятности игрока А и выбора игроком В платежей D, E, F, заключаем, что игрок В выберет опять стратегию 2 (точка D). Но при этом ему придётся платить больше, чем если бы игрок А выбрал вероятность р1. Из приведённого исследования видно, что для разных значений вероятности игрока А, платёж ему – это нижняя огибающая (выделенная жирная линия на рисунке). Тогда наилучший выбор для игрока А – это точка G.
Найдём p0. Так как
,
то
Найдём цену игры.
Найдём стратегии игрока В.
Точка G – точка оптимальной стратегии определяется как вторая и третья стратегии игрока В, поэтому первая и четвёртая стратегии игрока В не используются.
Пусть игрок В с вероятностью q использует стратегию 2 и с вероятностью (1 – q) – стратегию три. Но цена игры известна, поэтому можно написать уравнение на q в виде:
Ответ: Оптимальная стратегия матричной игры – смешанная. Игрок А не применяет первую и четвёртую стратегии, вторая стратегия им используется с вероятность 4/7, третья стратегия используется с вероятностью 3/7. Игрок В тоже не применяет первую и четвёртую стратегии, вторую применяет с вероятность 3/7, третью – с вероятностью 4/7. Цена игры равна 11/7.
Задача 2. Платёжная матрица имеет вид: 
.
Найти цену игры и оптимальную стратегию.
Решение. Пусть как и в предыдущей задаче стратегии игрока А нумеруются сверху вниз, а стратегии игрока В – слева направо.. Видно, что в заданной платёжной матрице вторая стратегия игрока А доминирует его первую. Аналогично заключаем, что третья стратегия игрока В доминирует четвёртую и первую. В результате вычёркиваний приходит к платёжной матрице (3х2). Попытаемся найти решение задачи в чистых стратегиях. Для этого справа от каждой строки выпишем гарантированный выигрыш игрока А, а внизу под каждым столбцом – максимальный проигрыш игрока В для каждой из стратегий. В результате получим:
5 5
Договоримся считать, что теперь у игрока А имеется первая, вторая и третья стратегии, а у игрока В – первая и вторая.
Для игрока А наилучшей является первая стратегия, так как он в наихудшем случае выигрывает 3 ед. = a0 – минимальная цена игры, а для игрока В – и первая и вторая стратегии дают наибольший проигрыш 5 ед. = b0 максимальная цена игры. Так как нижняя и верхняя цена игры не совпадают, то в чистых стратегиях задача не имеет решения.
Найдём решение задачи в смешанных стратегиях. Будем считать, что игрок В первую стратегию использует с вероятностью q и с вероятностью (1-q) применяет вторую стратегию. Тогда
q 1-q
Найдём средний выигрыш игрока А.
Если игрок А выбирает первую стратегию, то получит в среднем
v1=5q+3(1-q)=3+2q
Для второй стратегии игрока А средний выигрыш будет
v2=2q+4(1-q)=4-2q
Для третьей стратегии игрока А средний выигрыш будет
v3=-3q+5(1-q)=5-8q
Так как неизвестной величиной является только одна – вероятность q, то выигрыш игрока А изобразим на графике в переменных (v, q).
Изучим график. Если игрок В зафиксировал вероятность q1, то игрок А имеет возможность выбора стратегии из трёх вариантов: он выберет либо первую стратегию, тогда в среднем будет платить С единиц, либо вторую стратегию, тогда в среднем он будет платить В единиц, либо третью, тогда в среднем он будет платить А единиц. Естественно он заинтересован в наибольшей плате, поэтому он выберет стратегию 1. Понимая это, игрок В захочет заплатить меньше и выберет меньшее q, а именно q0. В результате для различных значений q приходим к верхней огибающей как наилучшем выборе стратегии для игрока А (выделенная жирная линия на рисунке). Тогда наилучший выбор для игрока А – это точка D.
Найдём q0. Так как
,
то
Найдём цену игры.
Найдём стратегии игрока А.
Точка D – точка оптимальной стратегии определяется как пересечение второй и третьей стратегий игрока А, поэтому первая и четвёртая стратегии игрока А не используются.
Пусть игрок А с вероятностью p использует стратегию два и с вероятностью (1 – p) – стратегию три. Тогда:
Ответ: игрок А не использует первую и четвёртую стратегии, вторая и третья стратегии используется с равной вероятностью 1/2, игрок В также не использует первую и четвёртую стратегии, вторая стратегия используется с вероятностью ј, третья стратегия – с вероятностью ѕ, при этом цена игры равна 3.5.
2. Найти смешанную стратегию с помощью программы Математика задачи теории игр, если платёжная матрица имеет вид:
Решение на "Математика":
Пишем программу:
c1=\{1,1,1,1,1\};с2=\{1,1,1,1,1,1\};
b1=\{\{1,1\},\{1,1\},\{1,1\},\{1,1\},\{1,1\}\};b2=\{\{1,-1\},\{1,-1\},\{1,-1\},
\{1,-1\},\{1,-1\},\{1,-1\}\};
A=\{\{17,22,13,27,19\},\{31,23,41,32,43\},\{24,35,15,19,42\},\{32,39,24,47,35\},
\{46,52,19,39,48\},\{31,45,27,32,36\}\};
AT=Transpose[A];MatrixForm[A]
x=LinearProgramming[c2,AT, b1]
y=LinearProgramming[-c1,A, b2]
zx=c2.x
zy=c1.y
p=x/zx
q=y/zy
N[1/zx]
Получаем ответ:
33.5361
Следовательноигрок А выбирает свои стратегии с вероятностями {0,{1919/3380,0,41/1690,283/1690,813/3380}, а игрок В -- {2/169,763/2535,1199/2535,181/845,0}, при этом цена игры равна 28338/845=33.5361.
Индивидуальные задания
Вариант № 1.
Дана платёжная матрица
. Найти решение в чистых стратегиях (найти цену игры и стратегии игроков А и В). Для платёжной матрицы 
найти решение геометрическими методами (найти цену игры и стратегии игроков А и В). Для платёжной матрицы 
найти решение, используя программу «Математика». Вариант № 2.
Дана платёжная матрица
. Найти решение в чистых стратегиях (найти цену игры и стратегии игроков А и В). Для платёжной матрицы 
найти решение геометрическими методами (найти цену игры и стратегии игроков А и В). Для платёжной матрицы
найти решение, используя программу «Математика». Вариант № 3.
Дана платёжная матрица
. Найти решение в чистых стратегиях (найти цену игры и стратегии игроков А и В). Для платёжной матрицы
найти решение геометрическими методами (найти цену игры и стратегии игроков А и В). Для платёжной матрицы
найти решение, используя программу «Математика». Вариант № 4.
Дана платёжная матрица
. Найти решение в чистых стратегиях (найти цену игры и стратегии игроков А и В). Для платёжной матрицы
найти решение геометрическими методами (найти цену игры и стратегии игроков А и В). Для платёжной матрицы
найти решение, используя программу «Математика». Вариант № 5.
Дана платёжная матрица
. Найти решение в чистых стратегиях (найти цену игры и стратегии игроков А и В). Для платёжной матрицы 
найти решение геометрическими методами (найти цену игры и стратегии игроков А и В). Для платёжной матрицы 
найти решение, используя программу «Математика». Вариант № 6.
Дана платёжная матрица
. Найти решение в чистых стратегиях (найти цену игры и стратегии игроков А и В). Для платёжной матрицы
найти решение геометрическими методами (найти цену игры и стратегии игроков А и В). Для платёжной матрицы
найти решение, используя программу «Математика». Вариант № 7.
Дана платёжная матрица
. Найти решение в чистых стратегиях (найти цену игры и стратегии игроков А и В). Для платёжной матрицы 
найти решение геометрическими методами (найти цену игры и стратегии игроков А и В). Для платёжной матрицы 
найти решение, используя программу «Математика». Вариант № 8.
Дана платёжная матрица
. Найти решение в чистых стратегиях (найти цену игры и стратегии игроков А и В). Для платёжной матрицы
найти решение геометрическими методами (найти цену игры и стратегии игроков А и В). Для платёжной матрицы
найти решение, используя программу «Математика». Вариант № 9.
Дана платёжная матрица
. Найти решение в чистых стратегиях (найти цену игры и стратегии игроков А и В). Для платёжной матрицы 
найти решение геометрическими методами (найти цену игры и стратегии игроков А и В). Для платёжной матрицы 
найти решение, используя программу «Математика». Вариант № 10.
Дана платёжная матрица
. Найти решение в чистых стратегиях (найти цену игры и стратегии игроков А и В). Для платёжной матрицы 
найти решение геометрическими методами (найти цену игры и стратегии игроков А и В). Для платёжной матрицы 
найти решение, используя программу «Математика». Литература
1. етоды оптимизации. Вводный курс. – М.: Радио и связь, 1988.
2. , , Мето-дические указания по курсу “Математическое програм-мирование” для студентов вечернего и заочного факультетов. – Издат.: СПбУЭФ, 1992.
3. , , Основы линейного программирования – Издат.: СПбГУЭФ, 2006.
4. От игр к играм. Математическое введение. Москва, изд. УРСС, 2003.
МЕТОДИЧЕСКИЕ УКАЗАНИЯ И
ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ
по курсу
«ТЕОРИЯ ИГР»
для студентов факультета
гостиничное дело
Подписано в печать 19.05.17 Формат 60х84
П. л. 0,8 РТП Тираж 5 экз.
