4. Решение матричной игры m×n сведением к задаче линейного программирования для игрока a.

Решение матричной игры m×n с матрицей А, элементы которой удовлетворяют условию a_ij>0 i=1,…,m j=1,…,n, эквивалентно решению пары двойственных друг другу стандартных задач линейного программирования:

Найти min ∑x_i при ограничениях

x_i≥0, i=1,…,m ∑ a_ij x_i≥1 j=1,…,n

Найти max ∑y_j при ограничениях

y_j≥0, j=1,…n ∑ a_ij y_j≤1 i=1,…,m

точнее говоря, если x⁰=(x₁⁰,…,x_m⁰) и y⁰=(y₁⁰,…,y_n⁰) – оптимальные решения задачи, то V=(∑ x_i⁰)^-1=(∑ y_j⁰)^-1 – цена игры с матрицей А, P⁰=Vx⁰=(p⁰₁= Vx⁰₁,…,p_m⁰= Vx⁰_m)- оптимальная стратегия игрока А, Q⁰=Vy⁰=(q⁰₁= Vy⁰₁,…,q_n⁰= Vy⁰_n) - оптимальная стратегия игрока B,

Необходимо определить оптимальные стратегии P⁰=(p₁⁰,p₂⁰,…,p_m⁰) и Q⁰=(q₁⁰,q₂⁰,…,q_n⁰) , где ∑ p_i⁰ =1 , ∑ q_j⁰ =1

Если игрок A применяет смешанную стратегию P⁰=(p₁,p₂,…,p_m) против любой чистой стратегии Bj игрока B, то он получает средний выигрыш

F(P,Bj)=a1j*p1+a2j*p2+…+amj*pm

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

Для оптимальной стратегии P⁰ все средние выигрыши F(P,Bj) не меньше цены игры , поэтому получаем систему неравенств:

a11*p1+a21*p2+…+am1*pm≥V

a1n*p1+a2n*p2+…+amn*pm≥V

x1=p1/V xm=pm/V при V>0

Если величинаV≤0, неравенства можно преобразовать, поменяв игроков ролями и изменив у всех элементов матрицы знак на противоположный.

a11*x1+a21*x2+…+am1*xm≥1

a1n*x1+a2n*x2+…+amn*xm≥1

x1+x2+..+xm=1/V

Цель игрока A – максимизировать свой гарантированный выигрыш, т.е. максимизировать цену игры V. Максимизация цены игры V эквивалентна минимизации величины1/V. Поэтому задача поиска оптимальной стратегии P⁰для игрока A может быть сформулирована следующим образом:

x1+x2+..+xm→min

a11*x1+a21*x2+…+am1*xm≥1

a1n*x1+a2n*x2+…+amn*xm≥1

x_i≥0

P⁰=(p₁⁰=x₁⁰*V, p₂⁰=x₂⁰*V,…, p_m⁰=x_m⁰*V)

V=1/( x₁⁰+x₂⁰+…+x_m⁰)

Пример:

-2	1	1
3	-2	3
2	2	-1

Приведем к матрице с положительными элементами, прибавив к каждому ее элементу число, больше макисмального модуля отрицательных элементов матрицы. В данном случае 3>max {│-2│, │-1│}.

1	4	4
6	1	6
5	5	2

Найти минимум целевой функции f(x₁, x_2, x₃)= x₁₊ x₂₊ x₃

x₁>0, x₂>0, x₃>0

x₁₊6 x₂₊5 x₃≥1

4 x₁₊ x₂₊5 x₃≥1

4 x₁+6 x₂₊2 x₃≥1

4. Решение матричной игры m×n сведением к задаче линейного программирования для игрока b.

Решение матричной игры m×n с матрицей А, элементы которой удовлетворяют условию aij>0 i=1,…,m j=1,…,n, эквивалентно решению пары двойственных друг другу стандартных задач линейного программирования:

Найти min ∑x_i при ограничениях

x_i≥0, i=1,…,m ∑ a_ij x_i≥1 j=1,…,n

Найти max ∑y_j при ограничениях

y_j≥0, j=1,…n ∑ a_ij y_j≤1 i=1,…,m

точнее говоря, если x⁰=(x₁⁰,…,x_m⁰) и y⁰=(y₁⁰,…,y_n⁰) – оптимальные решения задачи, то V=(∑ x_i⁰)^-1=(∑ y_j⁰)^-1 – цена игры с матрицей А, P⁰=Vx⁰=(p⁰₁= Vx⁰₁,…,p_m⁰= Vx⁰_m)- оптимальная стратегия игрока А, Q⁰=Vy⁰=(q⁰₁= Vy⁰₁,…,q_n⁰= Vy⁰_n) - оптимальная стратегия игрока B,

Если игрок B применяет смешанную стратегию Q⁰=(q₁,q₂,…,q_n) против любой чистой стратегии Ai игрока A, то он получает средний проигрыш

F(Ai,Q)=ai1*q1+ai2*q2+…+ain*qn

∑q_j=1 .

Для оптимальной стратегии Q⁰ все средние проигрыши не больше цены игры , поэтому получаем систему неравенств:

a11*q1+a12*q2+…+a1n*qn≤V

am1*q1+am2*q2+…+amn*qn≤V

y1=q1/V yn=qn/V при V>0

y1+y2+..+yn=1/V

Цель игрока B – минимизировать свой гарантированный проигрыш, т.е. минимизировать цену игры V. Минимизация цены игры эквивалентна максимизации величины 1/V. Поэтому задача поиска оптимальной стратегии Q⁰ для игрока B может быть сформулирована следующим образом:

y1+y2+..+yn→max

a11*y1+a12*y2+…+a1n*yn≤1

am1*y1+am2*y2+…+amn*yn≤1

y_j≥0

Q⁰=(q₁⁰=y₁⁰*V, q₂⁰=y₂⁰*V,…, q_n⁰=y_n⁰*V)

V=1/( y₁⁰+y₂⁰+…+y_n⁰)

Пример:

-2	1	1
3	-2	3
2	2	-1

Приведем к матрице с положительными элементами, прибавив к каждому ее элементу число, больше макисмального модуля отрицательных элементов матрицы. В данном случае 3>max {│-2│, │-1│}.

1	4	4
6	1	6
5	5	2

Найти максимум целевой функции φ(y1, y2, y3)= y1+ y2+ y3

y1>0, y2>0, y3>0

y1+4 y2+4 y3≤1

6y1+ y2+6y3≤1

5y1+5y2+2y3≤1