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

Динамическое программирование - это вычислительный метод для решения задач управления определённой структуры. Данная задача с 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 =1,2,...

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

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

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

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

0 £ X £ x

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

F₁(x)=f₁(x).

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

Значения функций f_j(x_j) приведены в таблице 1.

Таблица 1

xj
f1(xj)
f2(xj)
f3(xj)
f4(xj)

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

Таблица 2

x-х2
X2	F(x-x2) f2(x2)
			15*
		15*	30*	41*	52*	61*			---
					61*	70*	77*	---	---
							---	---	---
						---	---	---	---
					---	---	---	---	---
				---	---	---	---	---	---
			---	---	---	---	---	---	---

Таблица 3

x
F2(x)
x2(x)
x2(x)

Таблица 4

x-х3
Х3	F(x-x3) f2(x3)
			15*	30*
									---
		30*	45*	60*	71*	82*	91*	---	---
							---	---	---
						---	---	---	---
					---	---	---	---	---
				---	---	---	---	---	---
			---	---	---	---	---	---	---

Таблица 5

x
F3(x)
X3(x)
X3(x)

Таблица 5

x-х4
Х4	F(x-x4) f2(x4)
									---
								---	---
							---	---	---
						---	---	---	---
					---	---	---	---	---
				---	---	---	---	---	---
			---	---	---	---	---	---	---

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

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

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

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

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

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

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

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

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

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

х1* = 200;	Zmax = 107
х2* = 100;
х3* = 200;
х4* = 200

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

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

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

f₁(200) + f₂(100) + f₃(200) + f₄(200) = 26 + 15 + 30 + 36 = 107 = Z_max

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