§3. Решение задачи оптимального распределения инвестиций методом динамического программирования

Проиллюстрируем описанную выше процедуру решения задач динамического программирования на следующем примере.

Задача 4.1. Компания выделяет S = 40 млн. руб. для модернизации производства с целью увеличения выпуска продукции. Эти средства следует распределить между тремя филиалами компании. При этом сумма, выделяемая филиалу, должна быть кратна 10 млн. руб.

Известны функции f_k(u) (k = ), которые характеризуют прирост выпуска продукции k-го филиала в млн. руб. за год при получении им капиталовложений u млн. руб. (u = 0, 10, 20, 30, 40). Эти данные приведены в таблице 4.1. Нужно найти оптимальный план распределения капиталовложений между филиалами, обеспечивающий максимальный общий годовой прирост выпуска продукции.

Таблица 4.1. Исходная информация к задаче

Размер капитало-вложений (млн. руб.) u	Прирост выпуска продукции (млн. руб.)
	f1(u)	f2(u)	f3(u)
0	0	0	0
10	5	6	4
20	7	8	7
30	8	9	8
40	11	12	10

Решение. Обозначим через u_k количество средств, выделенных k-му филиалу, где k = , а Z — общий годовой прирост выпуска продукции. Для нахождения оптимального плана распределения инвестиций следует решить следующую задачу:

Z = f₁(u₁) + f₂(u₂) + f₃(u₃) → max, (4.1)

u₁ + u₂ + u₃ = 40, (4.2)

u_k ≥ 0, k = , (4.3)

u_k ϵ {0, 10, 20, 30, 40}, k = . (4.4)

Оптимальное решение задачи (4.1) – (4.4) можно найти, сведя ее к задаче линейного целочисленного программирования, аналогично тому, как это было сделано в предыдущей главе (см. задачу 1.3 в §1 главы 7). Другая возможность — использование метода динамического программирования.

Для этого рассмотрим процедуру распределения капиталовложений между филиалами как многошаговый процесс, на k-ом шаге которого выделяются средства k-му филиалу. Таким образом, число шагов этого процесса равно числу филиалов и номер шага соответствует номеру филиала.

Управление u_k на k-м шаге (k = ) — это объем средств, выделенных k‑му филиалу, а параметры состояния x_k — это остаток капиталовложений после их выделения первым k объектам.

Итак, x₀ = 40 — начальный объем капиталовложений, x₁ — объем средств, оставшийся после выделения капиталовложений первому филиалу, x₂ — объем средств, оставшийся после выделения капиталовложений первому и второму филиалу, а x₃ — объем средств, оставшийся после выделения капиталовложений всем трём филиалам.

Уравнения состояния имеют вид:

x₀ = 40,

x₁ = x₀ – u₁,

x₂ = x₁ – u₂,

x₃ = x₂ – u₃

Множества допустимых управлений на каждом шаге таковы:

D_k = {0 ≤ u_k ≤ x_k-1}, k = .

Показатель эффективности управления f_k(u_k) на каждом шаге зависит только от управления на этом шаге и не зависит от предшествующего состояния. Общий показатель эффективности управления имеет вид:

Z = f₁(u₁) + f₂(u₂) + f₃(u₃) → max.

Оптимальное управление доставляет максимум этой функции на множестве допустимых управлений.

В предыдущем параграфе было дано общее описание процедуры нахождения оптимального управления, состоящей из двух этапов: условной и безусловной оптимизации.