Задача о «расшивке узких мест производства»

 

Требуется найти такое  распределение X=(х₁, х₂, x₃, х₄) капиталовложений между предприятиями, которое максимизирует суммарный прирост прибыли.

Но так же не стоит  забывать, что в данной задаче происходит распределение капиталовложений в  рамках выделенных 700 млн. руб., т.е. х₁+ х₂+ x₃+ х₄=700.

Кроме того, вкладываемые капиталы в предприятия кратны 100 млн. руб., т.е. x_j=100 * n , где n=0,1,2,…,7.

В качестве показателя эффективности  выступает суммарный прирост  прибыли 4-х предприятий: Z=f₁(x₁)+ f₂(x₂)+ f₃(x₃)+ f₄(x₄) → max.

В качестве критерия эффективности  выступает принцип максимального  результата.

Итак, требуется найти X, компоненты которого обеспечили бы максимум функции Z, при ограничении на его компоненты. Воспользуемся методом динамического программирования для решения этой задачи.

Для решения данной задачи введём параметр t, обозначающий кол-во млн. руб., выделяемых сразу k предприятиям вместе. Тогда прибыль от такого вклада составит F_k(t) при 0<= t <=700.

Представим ситуацию, что последнее, а именно k-предприятие, получит x_k млн. руб., тогда остальные (t-xk) млн. руб. должны быть распределены между предприятиями от первого до (k-1)-предприятия, причем не надо забывать, что при вложении капиталов мы должны получить максимальную прибыль.

Таким образом, приходим к рекуррентному соотношению, которое  выполняет роль критерия эффективности:

Для k=2,3,4 : F_k(t) = f_k(x_k) + F_k-1 (t-x_k)  → max при 0<=x_k<=t ;

Для k=1       : F_k(t) = f₁(t)

Функции прибыли F_k(t) и соответствующие им значения x_k табулируются в следующих таблицах:

 

	t-x2	0	100	200	300	400	500	600	700
x2	F1(t-x2) f2(x2)	0	42	58	71	80	89	95	100
0	0	0	42	58	71	80	89	95	100
100	30	30	72	88	101	110	119	125
200	49	49	91	107	120	129	138
300	63	63	105	121	134	143
400	68	68	110	126	139
500	69	69	111	127
600	65	65	107
700	60	60

 

t	0	100	200	300	400	500	600	700
F2(t)	0	42	72	91	107	121	134	143
x2	0	0	100	200	200	300	300	300

 

	t-x3	0	100	200	300	400	500	600	700
x3	F2(t-x3) f3(x3)	0	42	72	91	107	121	134	143
0	0	0	42	72	91	107	121	134	143
100	22	22	64	94	113	129	143	156
200	37	37	79	109	128	144	158
300	49	49	91	121	140	156
400	59	59	101	131	150
500	68	68	110	140
600	76	76	118
700	82	82

 

t	0	100	200	300	400	500	600	700
F3(t)	0	42	72	94	113	129	144	158
x3	0	0	0	100	100	100	200	300

 

	t-x4	0	100	200	300	400	500	600	700
x4	F3(t-x4) f4(x4)	0	42	72	94	113	129	144	158
0	0								158
100	50							194
200	68						197
300	82					195
400	92				186
500	100			172
600	107		149
700	112	112

 

 

Z_max =  197 тыс. руб., причем четвертому предприятию должно быть выделено 200 млн. руб.

x₃(700-200)=100 млн. руб.

x₂(400)=200 млн. руб.

x₁=700-200-100-200=200 млн. руб.

Итак, наилучшее вложение капитала выглядит следующим образом:

1-ому предприятию –  200 млн. руб.

2-ому предприятию –  200 млн. руб.

3-ему предприятию –  100 млн. руб.

4-ому предприятию – 200 млн. руб.

Этот план обеспечивает производственному объединению  наибольший возможный прирост прибыли  на 197 млн. руб.

В качестве проверки правильности решения задачи можно использовать равенство:

f₁(x₁) + f₂(x₂) + f₃(x₃) + f₄(x₄) = Z_max

f₁(200) + f₂(200) + f₃(100) + f₄(200)  = 58 + 49 + 22 + 68 = 197 = Z_max

Следовательно, полученные решения верны.

 

 

6. Матричная игра

Два игрока А и В  играют в матричную игру. Дана платёжная  матрица (А), отражающая выигрыш игрока А или проигрыш игрока В при  использовании ими их стратегий.

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

Попытаемся упростить матрицу А, если это возможно, за счёт выявления дублирующих и доминирующих стратегий.

Стратегия A_e дублирует стратегию A_k, если элементы e-строки равны элементам k-строки.

Стратегия B_m дублирует стратегию B_n, если элементы m-столбца равны элементам n-столбца.

В нашем случае B₁ дублирует B₄. Исключим B₄ из рассмотрения.

Стратегия A_L доминирует стратегию A_k, если элементы L-строки превышают или равны элементам k-строки. Доминируемая k-стратегия из рассмотрения исключается.

1-я стратегия доминирует 2-ую стратегию, так что 2-ую стратегию из рассмотрения исключаем.

Стратегия Bm, доминирует стратегию Bn, если элементы m-столбца меньше или равны элементам n-столбца. Доминируемая n-стратегия из рассмотрения исключается. В нашем случае такого нет.

 

Выясним, есть ли решении  игры в чистых стратегиях (проверим на оседлую точку).

A\B	B1	B2	B3	B4	αi
A1	9	-2	1	0	-2
A2	-3	4	-5	6	-5
A3	5	-7	8	-9	-9
βj	9	4	8	6

α≠β, т.е. можно сделать  вывод, что игры в чистых стратегиях нет.

 

Введём новые переменные: для игрока A P(p₁,p₂,p₃) , т.е. вероятности использования игроком А 1-ой стратегии, 2-ой стратегии и т.д. соответственно, для игрока B Q(q₁,q₂,q₃,q₄) , т.е. вероятности использования игроком B 1-ой стратегии, 2-ой стратегии и т.д. соответственно. Так же введем υ – цену игры.

Добавим к каждому  элементу матрицы значение +9, чтобы  выигрыши были неотрицательные.

 

A\B		q1	q2	q3	q4
		B1	B2	B3	B4
p1	A1	18	7	10	9
p2	A2	6	13	4	15
p3	A3	14	2	17	0

 

Пусть игрок В играет по оптимальной стратегии, а игрок  А – по чистым.

A1: 18*q₁+ 7*q₂+ 10*q₃+ 9*q₄<= υ

A2: 6*q₁+ 13*q₂+ 4*q₃+ 15*q₄<= υ

A3: 14*q₁+ 2*q₂+ 17*q₃+ 0*q₄<= υ

Поделим данные три неравенства на υ>0 и введём новую переменную x_j=q_j/ υ    при x_j=>0   j=1,2,3,4     , тогда получим:

18*x₁+ 7*x₂+ 10*x₃+ 9*x₄<= 1

6*x₁+ 13*x₂+ 4*x₃+ 15*x₄<= 1

14*x₁+ 2*x₂+ 17*x₃+ 0*x₄<= 1

x_j=>0   j=1,2,3,4

 

Так как q₁,q₂,q₃,q₄ – вероятности использования стратегий игроком В, то:

q₁+q₂+q₃+q₄=1          Делим на υ>0 и получаем:

q₁/υ +q₂/υ +q₃/υ +q₄/υ =1/υ

x₁+x₂+x₃+x₄=1/υ

 

Так как υ – проигрыш игрока В, то он хочет минимизировать, тогда 1/υ – максимизировать. Итак, приходим к постановке задачи: найти  значение вектора X=( x₁; x₂; x₃; x₄ ), которое обеспечивало бы максимальное значение функции x₁+x₂+x₃+x₄=1/υ=Z → max при следующих линейных ограничениях (*).