Матричная модель производственной программы предприятия

Два игрока играют в матричную игру

-9	0	3	-1	3
2	-3	2	1	-2
4	-5	8	8	-7
2	-3	2	1	-2

Требуется найти решения игры для каждого игрока, а именно пару оптимальных стратегий, при которых каждому из игроков не выгодно отступать от них, поскольку это приведёт к их проигрышу.

Проведем анализ на доменирование и получим следующую матрицу:

-9	0	-1	3
2	-3	1	-2
4	-5	8	-7

При анализе игры на седловую точку, нижняя цена игры будет a= -3, верхняяb= 4. Решения в чистых стратегиях нет, будем искать решение в смешанных.

Прибавим к каждому элементу константу, равную 9. Решение игры при этом не изменится, а цена игры возрастет на 9 и будет больше 0.

Матрица примет следующий вид:

0	9	8	12
11	6	10	7
13	4	17	2

Пусть P= (p₁,p₂,p₃) – стратегия первого игрока.Q= (q₁,q₂,q_{3 ,} p₄),V– цена игры.

Проигрыш Второго игрока будет не больше чем цена игры v

0*q₁+ 9*q₂+ 8*q₃+ 12q₄<=V

11*q₁+ 6*q₂+ 10*q₃+ 7q₄<=V

13*q₁+ 4*q₂+ 17*q₃+ 2q₄<=V

Разделим каждое неравенство на V>0 и введемq_i/V=x_i ,i=(1...4)

Поскольку q_1-4= 1, то переменныеx₁,x₂,x_{3 ,} x₄ удовлетворяют условию

x₁+ x₂+x₃+x₄<=1/V

1/Vдолжна быть максимальна, таким образом имеем слудующую задачу.

Найти вектор x= (x₁,x₂,x_{3 ,} x₄) , который обеспечивает

Z=x₁+x₂+x₃+x₄max

При ограничениях

0*x₁ + 9*x₂ + 8* x₃ + 12 x₄ <= 1

11*x₁ + 6*x₂ + 10* x₃ + 7 x₄ <= 1

13*x₁ + 4*x₂ + 17* x₃ + 2 x₄ <= 1

x₁,x₂,x_{3 ,} x₄ >= 0

Найдем оптимальное решение этой задачи симплексным методом.

			1	1	1	1	0	0	0
C	Базис	Hi	х1	х2	х3	х4	х5	х6	х7
0	х5	1	0	9	8	12	1	0	0
0	х6	1	11	6	10	7	0	1	0
0	х7	1	13	4	17	2	0	0	1
	-	0	-1	-1	-1	-1	0	0	0
0	х1	1/9	0	1	8/9	4/3	1/9	0	0
0	х6	3/9	11	0	42/9	-1	-6/9	1	0
19	х7	5/9	13	0	121/9	-30/9	-4/9	0	1
	-	1/9	-1	0	-1/9	3/9	1/9	0	0
18	х1	1/9	0	1	8/9	4/3	1/9	0	0
0	х2	3/99	1	0	42/99	-1/11	-6/99	1/11	0
19	х7	16/99	0	0	785/99	-213/99	34/99	-13/11	1
	-	14/99	0	0	38/99	24/99	5/99	1/11	0

Zmax = 14/99, X = ( 1/9, 3/99, 0 , 0)

V = 1/ Zmax = 99/14, Q = ( 11/14, 3/14, 0, 0)

Для поиска оптимальной стратегии Первого игрока производим аналогичные преобразования. Учитываем, что V– это выйгрыш первого игрока, следовательно 1/Vтребуется минимизировать. Таким образом имеем следующую задачу:

Найти вектор Y= (y₁,y₂,y₃ ) , который обеспечивает

L=y₁+y₂+y₃min

При ограничениях

0*y₁ + 11*y₂ + 13* y₃ => 1

9*y₁ + 6*y₂ + 4* y₃ => 1

18*y₁ + 10*y₂ + 17* y₃ => 1

12*y₁ + 7*y₂ + 2* y₃ => 1

y₁, y₂, y_{3 ,} y₄ >= 0

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

Lmin = Zmax = 14/99, Y = ( 5/99, 1/11, 0)

V = 1/ Zmax = 99/14, P = ( 5/14, 9/14, 0)

Возвращаемся к исходной матрице игры. Решение этой игры имеет вид:

V = 0,

P = ( 5/14, 9/14, 0, 0)

Q = ( 11/14, 3/14, 0, 0, 0)