Линейное и динамическое программирование (стр. 4 из 8)

Данная задача с n переменными представляется, как многошаговый процесс принятия решений. На каждом шаге определяется экстремум функции только по одной переменной.

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

Пусть первым двум фирмам выделено ξ инвестиций. обозначим z₂(ξ) величину инвестиций 2-й фирме, при которой сумма f₂(z_2j)+f_l(ξ-z_2j), 0≤j≤ ξ максимальна, саму эту максимальную величину обозначим F₂(ξ). Далее действуем также: находим функции z₃ и F₃ и т.д. На k-ом шаге для нахождения F_k(ξ) используем основное рекуррентное соотношение: F_k(ξ)=max{f_kj(х_k)+F_(k-1)( ξ-х_k); 0 ≤ х_k ≤ ξ

xj	0	100	200	300	400	500	600	700
f1	0	28	45	65	78	90	102	113
f2	0	25	41	55	65	75	80	85
f3	0	15	25	40	56	62	73	82
f4	0	20	33	42	48	53	56	58

Таблица 1

x2	ξ-х2	0	100	200	300	400	500	600	700
	F1(ξ-x2) f2(x2)	0	28	45	65	78	90	102	113
0	0	0	28	45	65	78	90	102	113
100	25	25	53	70	90	103	115	127
200	41	41	69	86	106	119	131
300	55	55	83	100	120	133
400	65	65	93	110	130
500	75	75	103	120
600	80	80	108
700	85	85

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

ξ	0	100	200	300	400	500	600	700
F2	0	28	53	70	90	106	120	133
x2	0	0	100	100	100	200	300	300

Таблица 2

х3	ξ-х2	0	100	200	300	400	500	600	700
	F3(ξ-x3) f3(x3)	0	28	53	70	90	106	120	133
0	0	0	28	53	70	90	106	120	133
100	15	15	43	68	85	105	121	135
200	25	25	53	78	95	115	131
300	40	40	68	93	110	130
400	56	56	84	109	125
500	62	62	90	115
600	73	73	101
700	82	82

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

ξ	0	100	200	300	400	500	600	700
F2	0	28	53	70	90	106	121	135
x2	0	0	0	0	0	0	100	100

Таблица 3

x4	ξ-х4	0	100	200	300	400	500	600	700
	F4(ξ-x4) f4(x4)	0	28	53	70	90	106	121	135
0	0	135
100	20	141
200	33	139
300	42	132
400	48	118
500	53	106
600	56	84
700	58	58

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