5. Динамическое программирование. Распределение капитальных вложений

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

Рассмотрю нелинейную задачу распределения ресурсов между предприятиями отрасли. Предположу, что указано n пунктов, где требуется построить или реконструировать предприятия одной отрасли, для чего выделено b рублей. Обозначу через f_j(x_j) прирост мощности или прибыли на j-том предприятии, если оно получит x_j рублей капитальных вложений. Требуется найти такое распределение (х₁, х₂, ..., х_n) капитальных вложений между предприятиями, которое максимизирует суммарный прирост мощности или прибыли

Z=f₁(x₁)+f₂(x₂)+...+f_n(x_n)

при ограничении по общей сумме капвложений х₁ + х₂ +...+х_n = b, причём буду считать, что все переменные x_j принимают только целые неотрицательные значения x_j =0,1,2,...

Функции f_j(x_j) я считаю заданными, заметив, что их определение -довольно трудоёмкая экономическая задача.

Воспользуюсь методом динамического программирования для решения этой задачи.

Введу параметр состояния и определю функцию состояния. За параметр состояния  примем количество рублей, выделяемых нескольким предприятиям, а функцию состояния F_k() определим как максимальную прибыль на первых k предприятиях, если они вместе получат  рублей. Параметр  может меняться от 0 до b. Если из  рублей k-ое предприятие получит Х_к рублей, то каково бы ни было это значение, остальные -Х_к рублей естественно распределить между предприятиями от 1-го до (к-1)-го предприятия, чтобы была получена максимальная прибыль F_k-1(-x_k). Тогда прибыль k предприятий будет равна f_k(x_k) + F_k-1(-x_k). Надо выбрать такое значение x_k между 0 и , чтобы эта сумма была максимальной, и я прихожу к рекуррентному соотношению:

F_k() = max {f_k(x_k) + F_k-1(-x_k)}

0  X  

для k=2,3,....,n .Если же k=1 ,то

F₁()=f₁().

В моем случае производственное объединение состоит из 4-х предприятий (k=4).Общая сумма капитальных вложений равна 700 тыс. рублей (b=700) , выделяемые предприятиям суммы кратны 100 тыс. рублей.

Значения функций f_j(x_j) приведены в таблице 1, где, например, число 29 означает, что если 3-е предприятие получит 600 тыс. руб. капитальных вложений, то прирост прибыли на этом предприятии составит 29 тыс. руб.

Таблица 1

xj	0	100	200	300	400	500	600	700
f1(xj)	0	5	10	14	17	19	21	22
f2(xj)	0	8	13	18	21	23	21	17
f3(xj)	0	10	16	21	24	27	29	30
f4(xj)	0	11	19	26	30	33	35	36

Прежде всего заполняю таблицу 2. Значения f₂(x₂) складываю со значениями F₁(-x₂)=f₁(-x₂) и на каждой северо-восточной диагонали нахожу наибольшее число, которое помечаю звёздочкой и указываю соответствующее значение x₂(). Заполняю таблицу 3. Продолжая процесс, табулирую функции F₃(), x₃() (см. табл.4 и 5) и т.д. В таблице 6 заполняю только одну диагональ для значения =700.

Таблица 2

 -х2		0	100	200	300	400	500	600	700
X2	F(-x2) f2(x2)	0	5	10	14	17	19	21	22
0	0	0	5	10	14	17	19	21	22
100	8	8*	13*	18*	22	25	27	29	---
200	13	13*	18*	23*	27	30	32	---	---
300	18	18*	23*	28*	32*	35*	---	---	---
400	21	21	26	31	35*	---	---	---	---
500	23	23	28	33	---	---	---	---	---
600	21	21	26	---	---	---	---	---	---
700	17	17	---	---	---	---	---	---	---

Таблица 3

	0	100	200	300	400	500	600	700
F2()	0	8	13	18	23	28	32	35
x2()	0	100	100	100	200	300	300	300
x2() x2()	0 0	100 100	200	200 300	300	300 300	300 300	400

Таблица 4

 -х3		0	100	200	300	400	500	600	700
Х3	F(-x3) f2(x3)	0	8	13	18	23	28	32	35
0	0	0	8	13	18	23	28	32	35
100	10	10*	18*	23	28	33	38	42	---
200	16	16	24*	29*	34*	39*	44*	---	---
300	21	21	29*	34*	39*	44*	---	---	---
400	24	24	32	37	42	---	---	---	---
500	27	27	35	40	---	---	---	---	---
600	29	29	37	---	---	---	---	---	---
700	30	30	---	---	---	---	---	---	---

Таблица 5

	0	100	200	300	400	500	600	700
F3()	0	10	18	24	29	34	39	44
X3()	0	100	100	200	200	200	200	200
X3()	0	100	100	200	300	300	300	300

Таблица 6

 -х4		0	100	200	300	400	500	600	700
Х4	F(-x4) f2(x4)	0	10	18	24	29	34	39	44
0	0								44
100	11							50	---
200	19						53	---	---
300	26					55	---	---	---
400	30				54	---	---	---	---
500	33			51	---	---	---	---	---
600	35		45	---	---	---	---	---	---
700	36	36	---	---	---	---	---	---	---

Наибольшее число на этой диагонали:

Z_max = 55 тыс. руб.,

причем четвертому предприятию должно быть выделено

х₄* = х₄(700) = 300 тыс. руб.

На долю остальных трех предприятий остается 400 тыс. руб. Из Таблицы 5 видно, что третьему предприятию должно быть выделено

х₃* = х₃(700 - х₄*) = х₃(400) = 200 тыс. руб.

Продолжая обратный процесс, нахожу

х₂* = х₂(700 - х₄* - х₃*) = х₂(200) = 100 тыс. руб.

На долю первого предприятия останется

х₁* = 700 - х₄* - х₃* - х₂* = 100 тыс. руб.

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

х1* = 100;	Zmax = 55
х2* = 100;
х3* = 200;
х4* = 300

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

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

f₁(100) + f₂(100) + f₃(200) + f₄(300) = 5 + 8 + 16 + 26 = 55 = Z_max

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