Контрольная работа по дисциплине "Теория игр"

 

 
4. Пересчет симплекс-таблицы. 
Выполняем преобразования симплексной таблицы методом Жордано-Гаусса.

Базис	B	x1	x2	x3	x4	x5	x6
x3	1/11	9/11	0	1	0	0	-1/11
x2	1/9	2/9	1	0	0	-1/9	0
x4	4/99	80/99	0	0	1	-2/9	-9/11
F(X2)	-20/99	-4/99	0	0	0	1/9	1/11

 

 
Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
7/81-(-4/81 • -1/9):-12/9	59/81-(-80/81 • -1/9):-12/9	0-(0 • -1/9):-12/9	1-(0 • -1/9):-12/9	-1/9-(-12/9 • -1/9):-12/9	2/81-(22/81 • -1/9):-12/9	0-(1 • -1/9):-12/9
1/9-(-4/81 • 0):-12/9	2/9-(-80/81 • 0):-12/9	1-(0 • 0):-12/9	0-(0 • 0):-12/9	0-(-12/9 • 0):-12/9	-1/9-(22/81 • 0):-12/9	0-(1 • 0):-12/9
-4/81 : -12/9	-80/81 : -12/9	0 : -12/9	0 : -12/9	-12/9 : -12/9	22/81 : -12/9	1 : -12/9
-16/81-(-4/81 • 1/9):-12/9	4/81-(-80/81 • 1/9):-12/9	0-(0 • 1/9):-12/9	0-(0 • 1/9):-12/9	1/9-(-12/9 • 1/9):-12/9	7/81-(22/81 • 1/9):-12/9	0-(1 • 1/9):-12/9

 

 
В базисном столбце все элементы положительные. 
Переходим к основному алгоритму симплекс-метода. 
Итерация №0. 
1. Проверка критерия оптимальности. 
Текущий опорный план неоптимален, так как в индексной строке находятся отрицательные коэффициенты. 
2. Определение новой базисной переменной. 
В качестве ведущего выберем столбец, соответствующий переменной x1, так как это наибольший коэффициент по модулю. 
3. Определение новой свободной переменной. 
Вычислим значения Di по строкам как частное от деления: bi / ai1 
и из них выберем наименьшее: 
min (1/11 : 9/11 , 1/9 : 2/9 , 4/99 : 80/99 ) = 1/20 
Следовательно, 3-ая строка является ведущей. 
Разрешающий элемент равен (80/99) и находится на пересечении ведущего столбца и ведущей строки.

Базис	B	x1	x2	x3	x4	x5	x6	min
x3	1/11	9/11	0	1	0	0	-1/11	1/9
x2	1/9	2/9	1	0	0	-1/9	0	1/2
x4	4/99	80/99	0	0	1	-2/9	-9/11	1/20
F(X1)	-20/99	-4/99	0	0	0	1/9	1/11	0

 

 
4. Пересчет симплекс-таблицы. 
Формируем следующую часть симплексной таблицы. 
Вместо переменной x4 в план 1 войдет переменная x1. 
Строка, соответствующая переменной x1 в плане 1, получена в результате деления всех элементов строки x4 плана 0 на разрешающий элемент РЭ=80/99 
На месте разрешающего элемента в плане 1 получаем 1. 
В остальных клетках столбца x1 плана 1 записываем нули. 
Таким образом, в новом плане 1 заполнены строка x1 и столбец x1. 
Все остальные элементы нового плана 1, включая элементы индексной строки, определяются по правилу прямоугольника. 
Для этого выбираем из старого плана четыре числа, которые расположены в вершинах прямоугольника и всегда включают разрешающий элемент РЭ. 
НЭ = СЭ - (А*В)/РЭ 
СТЭ - элемент старого плана, РЭ - разрешающий элемент (80/99), А и В - элементы старого плана, образующие прямоугольник с элементами СТЭ и РЭ. 
Представим расчет каждого элемента в виде таблицы:

B	x 1	x 2	x 3	x 4	x 5	x 6
1/11-(4/99 • 9/11):80/99	9/11-(80/99 • 9/11):80/99	0-(0 • 9/11):80/99	1-(0 • 9/11):80/99	0-(1 • 9/11):80/99	0-(-2/9 • 9/11):80/99	-1/11-(-9/11 • 9/11):80/99
1/9-(4/99 • 2/9):80/99	2/9-(80/99 • 2/9):80/99	1-(0 • 2/9):80/99	0-(0 • 2/9):80/99	0-(1 • 2/9):80/99	-1/9-(-2/9 • 2/9):80/99	0-(-9/11 • 2/9):80/99
4/99 : 80/99	80/99 : 80/99	0 : 80/99	0 : 80/99	1 : 80/99	-2/9 : 80/99	-9/11 : 80/99
-20/99-(4/99 • -4/99):80/99	-4/99-(80/99 • -4/99):80/99	0-(0 • -4/99):80/99	0-(0 • -4/99):80/99	0-(1 • -4/99):80/99	1/9-(-2/9 • -4/99):80/99	1/11-(-9/11 • -4/99):80/99

 

 
 
Получаем новую симплекс-таблицу:

 

 

Базис	B	x1	x2	x3	x4	x5	x6
x3	1/20	0	0	1	-81/80	9/40	59/80
x2	1/10	0	1	0	-11/40	-1/20	9/40
x1	1/20	1	0	0	99/80	-11/40	-81/80
F(X1)	-1/5	0	0	0	1/20	1/10	1/20

 

 
1. Проверка критерия  оптимальности. 
Среди значений индексной строки нет отрицательных. Поэтому эта таблица определяет оптимальный план задачи. 
Окончательный вариант симплекс-таблицы:

Базис	B	x1	x2	x3	x4	x5	x6
x3	1/20	0	0	1	-81/80	9/40	59/80
x2	1/10	0	1	0	-11/40	-1/20	9/40
x1	1/20	1	0	0	99/80	-11/40	-81/80
F(X2)	-1/5	0	0	0	1/20	1/10	1/20

 

 
Оптимальный план можно записать так: 
x3 = 1/20 
x2 = 1/10 
x1 = 1/20 
F(X) = 1•1/20 + 1•1/10 + 1•1/20 = 1/5 
Анализ оптимального плана. 
Значение 0 в столбце x1 означает, что использование x1 - выгодно. 
Значение 0 в столбце x2 означает, что использование x2 - выгодно. 
Значение 0 в столбце x3 означает, что использование x3 - выгодно. 
Значение 1/20 в столбце x4 означает, что теневая цена (двойственная оценка) равна 1/20. 
Значение 1/10 в столбце x5 означает, что теневая цена (двойственная оценка) равна 1/10. 
Значение 1/20 в столбце x6 означает, что теневая цена (двойственная оценка) равна 1/20.

 

4.Найти р1, р2, q1,q2,v оптимальной стратегии.

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

Рассмотрим игру двух лиц, интересы которых противоположны. Такие игры называют антагонистическими играми двух лиц. В этом случае выигрыш одного игрока равен проигрышу второго, и можно описать только одного из игроков. 
Предполагается, что каждый игрок может выбрать только одно из конечного множества своих действий. Выбор действия называют выбором стратегии игрока. 
Если каждый из игроков выбрал свою стратегию, то эту пару стратегий называют ситуацией игры. Следует заметить, каждый игрок знает, какую стратегию выбрал его противник, т.е. имеет полную информацию о результате выбора противника. 
Чистой стратегией игрока I является выбор одной из n строк матрицы выигрышей А, а чистой стратегией игрока II является выбор одного из столбцов этой же матрицы. 
1. Проверяем, имеет ли платежная матрица седловую точку. Если да, то выписываем решение игры в чистых стратегиях. 
Считаем, что игрок I выбирает свою стратегию так, чтобы получить максимальный свой выигрыш, а игрок II выбирает свою стратегию так, чтобы минимизировать выигрыш игрока I.

Игроки	B1	B2	B3	a = min(Ai)
A1	7	2	9	2
A2	2	9	0	0
A3	9	0	11	0
b = max(Bi)	9	9	11

 

 
Находим гарантированный выигрыш, определяемый нижней ценой игры a = max(ai) = 2, которая указывает на максимальную чистую стратегию A1. 
Верхняя цена игры b = min(bj) = 9. 
Что свидетельствует об отсутствии седловой точки, так как a ≠ b, тогда цена игры находится в пределах 2 ≤ y ≤ 9. Находим решение игры в смешанных стратегиях. Объясняется это тем, что игроки не могут объявить противнику свои чистые стратегии: им следует скрывать свои действия. Игру можно решить, если позволить игрокам выбирать свои стратегии случайным образом (смешивать чистые стратегии). 
2. Проверяем платежную матрицу на доминирующие строки и доминирующие столбцы. 
Иногда на основании простого рассмотрения матрицы игры можно сказать, что некоторые чистые стратегии могут войти в оптимальную смешанную стратегию лишь с нулевой вероятностью. 
Говорят, что i-я стратегия 1-го игрока доминирует его k-ю стратегию, если aij ≥ akj для всех j Э N и хотя бы для одного j aij > akj. В этом случае говорят также, что i-я стратегия (или строка) – доминирующая, k-я – доминируемая. 
Говорят, что j-я стратегия 2-го игрока доминирует его l-ю стратегию, если для всех j Э M aij ≤ ail и хотя бы для одного i aij < ail. В этом случае j-ю стратегию (столбец) называют доминирующей, l-ю – доминируемой. 
В платежной матрице отсутствуют доминирующие строки. 
В платежной матрице отсутствуют доминирующие столбцы. 
Так как игроки выбирают свои чистые стратегии случайным образом, то выигрыш игрока I будет случайной величиной. В этом случае игрок I должен выбрать свои смешанные стратегии так, чтобы получить максимальный средний выигрыш. 
Аналогично, игрок II должен выбрать свои смешанные стратегии так, чтобы минимизировать математическое ожидание игрока I. 
3. Находим решение игры в смешанных стратегиях. 
Запишем систему уравнений. 
Для игрока I 
7p1+2p2+9p3 = y 
2p1+9p2 = y 
9p1+11p3 = y 
p1+p2+p3 = 1 
Для игрока II 
7q1+2q2+9q3 = y 
2q1+9q2 = y 
9q1+11q3 = y 
q1+q2+q3 = 1 
Решая эти системы методом Гаусса (решение см. ниже), находим: 
y = 5 
p1 = 1/4 (вероятность применения 1-ой стратегии). 
p2 = 1/2 (вероятность применения 2-ой стратегии). 
p3 = 1/4 (вероятность применения 3-ой стратегии). 
Оптимальная смешанная стратегия игрока I: P = (1/4; 1/2; 1/4) 
q1 = 1/4 (вероятность применения 1-ой стратегии). 
q2 = 1/2 (вероятность применения 2-ой стратегии). 
q3 = 1/4 (вероятность применения 3-ой стратегии). 
Оптимальная смешанная стратегия игрока II: Q = (1/4; 1/2; 1/4) 
Цена игры: y = 5