Сведите матричную игру к паре двойственных задач линейного программирования и найдите ее решение:15 вар. ‖341228373208‖
Заметим, что 3-я стратегия 2-го игрока является очень выгодной для него, она доминирует 2-ю и 4-ю.
Останется матрица
312330
, где 1-й столбец для 1-й стратегии игрока 2, а 2-й – для стратегии номер 3
Рассмотрим стратегию 2-го игрока (q1,0,q2,0), q1+q2=1
Пусть M- цена игры, а стратегия (q1,0,q2, 0), оптимальна, это значит, что ни одной чистой стратегией первый игрок не может добиться выигрыша больше M.
3q1+q2≤M
2q1+3q2≤M
3q1≤M
Разделим ограничения на M>0. Обозначим y1=q1M,y2=q2M
получаем задачу:
3y1+y2≤1
2y1+3y3≤1
3y1≤1
Целевая функция y1+y2=1M→max, так как 2-й игрок стремится уменьшить M
Введем базисные переменные y3,y4,y5 и решаем симплекс-методом:
БП b
y1 y2 y3 y4 y5
y3 1 3 1 1 0 0
y4 1 2 3 0 1 0
y5 1 3 0 0 0 1
_-z
0 -1 -1 0 0 0
Выводим из базиса y4, вводим y2
БП b
y1 y2 y3 y4 y5
y3 2/3 2 1/3 0 1 – 1/3 0 0,285714
y2 1/3 2/3 1 0 1/3 0 0,5
y5 1 3 0 0 0 1 0,333333
_-z
1/3 – 1/3 0 0 1/3 0
Выводим из базиса y3, вводим y1
БП b
y1 y2 y3 y4 y5
y1 2/7 1 0 3/7 – 1/7 0
y2 1/7 0 1 – 2/7 3/7 0
y5 1/7 0 0 -1 2/7 3/7 1
_-z
3/7 0 0 1/7 2/7 0
Так как z имеет вид 37-17y3-27y5 , план с y3=y4=0 оптимален
При этом M=73, q1=27M=23, q2=17M=13,
Двойственная задача:
3×1+2×2+3×3≥1
x1+3×2≥1
Целевая функция x1+x2+x3=1M→min
При этом должны получиться вероятности стратегий 1-го игрока
p1=x1M, p2=x2M, p3=x3M
Оптимальную смешанную стратегию 1-го игрока найдем по теоремам двойственности. Так как y3=y4=0, существенны строчки, соответствующие в исходной матрице 1-й и 2-й стратегиям 1-го игрока. Так как y1,y2 положительны, на стратегиях 2-го игрока 1 , 2 достигается точная цена игры, то есть оба ограничения обращаются в равенство. Решаем систему 2х23×1+2×2=1
x1+3×2=1
Вычтем из утроенной 2-й строки 1-ю
7×2=2
x1=17,×2=27,×3=0
Отсюда p1=x1M=13 , p2=x2M=23, p3=x3M=0
Решение:
цена игры 73, оптимальная смешанная стратегия 1-го игрока (13 , 23 , 0),
2-го игрока ( 23 , 0, 13 , 0)
