§5 Динамічне програмування

У реальному житті є задачі, в яких необхідно враховувати зміни параметрів систем у часі. Ці параметри можуть змінюватися неперервно або дискретно - від етапу до етапу. Наприклад, рік у рік міняється вік машин та встаткування, змінюється виробнича потужність і продуктивність праці на підприємствах, фондовіддача. Необхідно приймати оптимальні рішення на рік (або інший строк) і одночасно на весь розглянутий період у цілому з урахуванням можливих змін параметрів. Показником ефективності може служити, наприклад, прибуток, собівартість, сумарні витрати тощо. Для розв’язання такого виду багатокрокових задач розроблений відповідний математичний апарат, який отримав назву динамічне програмування.

Метод динамічного програмування був запропонований та розвинений Р. Беллманом і його учнями на початку 50-х років XX сторіччя. В основу цього методу покладено принцип оптимальності:

Принцип оптимальності Р. Беллмана. Якщо деяка послідовність розв'язків оптимальна, то окремі наступні розв'язки усередині її оптимальні стосовно попередніх розв'язків.

Відповідно до цього принципу задачу розкладають на прості етапи та починають розв’язувати з останнього етапу. Потім переходять до попереднього етапу, відкидаючи можливі альтернативи, які суперечать вже відпрацьованому розв’язку.

Одним з найбільш численних класів економічних задач, які розв'язуються методом динамічного програмування, є задача керування запасами. В рамках цієї задачі планується діяльність промислової групи підприємств на період років. На початку періоду для розвитку групи виділяються кошти, які потрібно якось розподілити між підприємствами. В процесі роботи підприємств частина коштів, які вкладені в них (перший індекс – номер шагу, другий – номер підприємства) витрачається, а частина залишається і може бути знову перерозподілена. Кожне підприємство за рік приносить прибуток, який є заданою функцією вкладених в нього коштів ‑ . Ставиться питання: яку кількість коштів потрібно виділити кожному підприємству на початку року, щоб сумарний прибуток за років був максимальним?

Ця задача є задачею динамічного програмування. Розподіл коштів є керований процес, тобто ми можемо обирати деякі параметри, які впливають на прибуток на даному кроці та на сумарний прибуток в цілому. Кошти, які виділяються підприємствам будемо називати вектором крокового керування. Керування всією операцією складається з сукупності усіх крокових керувань.

Потрібно знайти оптимальне керування , при якому сумарний прибуток максимальний:

Розв’язання цієї задачі розглянемо на прикладі.

Приклад. Нехай  од. – кількість капіталовкладень, які необхідно розподілити між двома галузями Х та Y.

Кількість капітальних коштів  од., які вкладені у галузь X, приносить прибуток  од., та наприкінці року залишається  од.

Кількість капітальних коштів  од., які вкладені у галузь Y, приносить прибуток  од. та залишок  од.

Наприкінці року залишкові капіталовкладення заново перерозподіляють по галузям. Потрібно розподілити кошти між галузями так, щоб сумарний прибуток за 3 роки був максимальним.

Розв’язання. Планування починаємо з останнього року.

Кошти, що залишилися з к-го року позначимо . Кошти, які виділені галузі X в к-й рік позначимо , галузі Y – . Всього на к-й рік виділено . Виразимо

(5.1)

Прибуток к-го року обчислюємо за формулою

(5.2)

Залишок коштів к-го року обчислюємо за формулою

(5.3)

Залишок коштів (к-1)-го року буде розподілений на наступний

к-й рік, тому з іншого боку

(5.4)

Максимальний прибуток знаходимо за функцією Беллмана (прибуток за поточний та наступні роки періоду, який розглядається)

(5.5)

Зміст функції (5.5) полягає в тому, що потрібно підібрати значення змінної , змінюючи її у вказаних границях від до так, щоб величина прибутку за к-й та наступні роки була найбільшою.

Формула (5.5) є рекурентною формулою, тому – це максимальний прибуток за всі роки періоду, що розглядається.

Використовуючи формулу (5.2), перепишемо функцію Беллмана у вигляді

(5.6)

Планування починаємо з третього року.

. Оскільки планування включає тільки три роки, будемо вважати, що . Тоді з формули (5.6) функція Беллмана має вигляд

.

Оскільки , то за формулою (1) . Це означає, що кошти у третій рік, ми повністю віддамо галузі Y.

. За формулою (5.6) запишемо функцію Беллмана

Розглянемо, що таке . З попереднього кроку маємо

.

Отже, функція Беллмана для другого року має вигляд

Оскільки , за формулою (5.1) . Тобто у другий рік всі кошти також віддаємо галузі Y.

. За формулою (5.6) запишемо функцію Беллмана

(5.7)

Оскільки , за формулою (5.1) , тобто у перший рік всі кошти ми віддамо галузі X.

- це кошти які виділяються на перший рік, за умовою .

Максимальний прибуток, який ми отримаємо за три роки, згідно (5.7) дорівнює  од.

Підведемо підсумок, та перевіримо результат.

В перший рік виділені кошти . Ці кошти, вкладені в галузь Х ( ), принесуть прибуток . Залишок коштів в цей рік складатимемо .

В другий рік виділені кошти – це залишок першого року . Ці кошти, вкладені в галузь Y ( ), принесуть прибуток . Залишок коштів в другий рік складатимемо .

В третій рік виділені кошти – це залишок другого року . Ці кошти, вкладені в галузь Y ( ), принесуть прибуток . Залишок коштів складатимемо .

Ці дані зручно записувати у таблиці розподілу коштів між галузями за три роки.

	Галузь X			Галузь Y
	Виділені кошти	прибуток	залишок	Виділені кошти	прибуток	залишок
1-й рік	10000	22 000	7 000			
2-й рік				7 000	17 500	4 200
3-й рік				4 200	10 500	2 520

Максимальний прибуток згідно таблиці розподілу коштів буде складати

Цей результат збігається з одержаним раніше ( ) і є перевіркою правильності розв’язку.

Залишок коштів, оскільки в 3-й рік всі кошти дісталися галузі Y, складає