4. Задача на динамическое программирование.

Пусть 4 фирмы образуют объединение. Рассмотрим задачу распределения инвестиций в размере 700 тыс. рублей по этим 4 фирмам. Размер инвестиций пусть будет кратен 100 тыс. рублей. Эффект от направления i-ой фирме инвестиций в размере f₁(x₁)+f₂(x₂)+f₃(x₃)+f₄(x₄) → max , где x_i – пока еще неизвестный размер x₁+x₂+x₃+x₄ ≤ 7 ; х₁,х₂,х₃,х₄ ≥ 0 инвестиций i-ой фирме.

Эта задача решается методом динамического программирования: последовательно ищется оптимальное распределение для к=2, 3, 4 фирм. Пусть первым двум фирмам выделено m инвестиций , обозначим z₂(m) величину инвестиций 2-й фирме, при которой сумма f₂(z₂(j))+f₁(m-z₂(j)) , 0 ≤ j ≤ m максимально, саму эту величину обозначим F2(m). Далее действует также : находятся функции z₃ и F₃ и т. д. На к-ом шаге для нахождения F_k(m) используют основное рекуррентное соотношение:

F_k(m)=max{f_k(j)+F_{k-1}(m-j) ; 0 ≤ j ≤ 7}.

X	0	100	200	300	400	500	600	700
f1(x)	0	20	44	55	63	67	70	70
f2(x)	0	18	29	49	72	87	100	108
f3(x)	0	25	41	52	74	82	88	90
f4(x)	0	30	52	76	90	104	116	125

Таблица 1.

	ζ-x2	0	100	200	300	400	500	600	700
x2	F1(ζ-x2) f2(x2)	0	20	44	55	63	67	70	70
0	0	0	20	44	55	63	67	70	70
100	18	18	38	62	73	81	85	88
200	29	29	49	73	84	92	106
300	49	49	69	93	104	112
400	72	72	92	116	127
500	87	87	107	131
600	100	100	120
700	108	108

Серым цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 2 предприятия.

ζ	0	100	200	300	400	500	600	700
f2(x2)	0	20	44	62	73	93	116	131
x2(ζ)	0	0	0	100	100/200	300	400	500

Таблица 2.

	ζ-x3	0	100	200	300	400	500	600	700
x3	F2(ζ-x3) f3(x3)	0	20	44	62	73	93	116	131
0	0	0	20	44	62	73	93	116	131
100	25	25	45	65	87	98	118	141
200	41	41	61	85	103	114	134
300	52	52	72	96	114	125
400	74	74	94	118	136
500	82	82	102	126
600	88	88	108
700	90	90

Серым цветом обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 3 предприятиям.

ζ	0	100	200	300	400	500	600	700
f3(x3)	0	25	45	65	87	103	118	141
x3(ζ)	0	0	100	100	100	200	100	100

Таблица 3.

	ζ-x4	0	100	200	300	400	500	600	700
x4	F3(ζ-x4) f4(x4)	25	45	65	87	103	118	141	25
0	0								141
100	30							148
200	52						155
300	76					163
400	90				155
500	104			149
600	116		141
700	125	125

Z_max=163 – максимальный суммарный эффект от выделения соответствующего размера инвестиций в 4-ое предприятие.

Сведем полученные результаты Таблицу 4.

Таблица 4.

ζ	0	100	200	300	400	500	600	700
f1(x1)	0	20	44	55	63	67	70	70
x1(ζ)	0	100	200	300	400	500	600	700
f2(x2)	0	20	44	62	73	93	116	131
x2(ζ)	0	0	0	100	100/200	300	400	500
f3(x3)	0	25	45	65	87	103	118	141
x3(ζ)	0	0	100	100	100	200	100	100
f4(x4)								163
x4(ζ)								300

Теперь f₄(700)=134 показывает максимальный суммарный эффект по всем 4-ем фирмам, а x₄(700)=300 тыс.руб. – размер инвестиций в 4-ую фирму для достижения этого максимального эффекта. После этого на долю первых 3-ех фирм остается 400 тыс.руб. и для достижения максимального суммарного эффекта по первым 3-м фирмам в 3-ью надо вложить 100 тыс.руб., во 2-ую – 100 тыс.руб., в 1-ую 200 тыс.руб. Серым цветом отмечены оптимальные значения инвестиций по фирмам и значения эффектов от них.