Page 86 - 6449

РОЗДІЛ 4. ДИНАМІЧНЕ ПРОГРАМУВАННЯ

4.1 Елементи динамічного програмування. Задача розподілу
капіталовкладень
Динамічне програмування є математичним апаратом, який
розроблений з метою підвищення ефективності обчислень при розв’язанні
певного класу задач шляхом їх розкладу (декомпозиції) на відносно
невеликі, і, відповідно більш прості під задачі. Характерним для
динамічного програмування є підхід до розв’язання задач по етапах, з
кожним з яких асоційована одна керована змінна [13,17]. Набір
рекурентних обчислювальних процедур, що зв’язує різні етапи, забезпечує
одержання допустимого оптимального розв’язку задачі в цілому після
досягнення останнього етапу.
Походження назви “динамічне програмування” імовірно пов’язане з
використанням цих методів у задачах прийняття рішень через фіксовані
проміжки часу (наприклад, у задачах управління запасами). Проте методи
динамічного програмування успішно застосовують також для розв’язання
задач, у яких фактор часу не враховується. З цієї причини тільки вдалим
видається термін “багатоетапне програмування”, яке відображає
покроковий характер процесу прийняття задачі.
Фундаментальним принципом, що лежить в основі теорії
динамічного програмування, є принцип оптимальності. Він визначає
порядок поетапного розв’язку задачі, яка дозволяє декомпозицію за
допомогою рекурентних обчислювальних процедур.
Рада директорів фірми вивчає пропозиції стосовно нарощування
виробничих потужностей на трьох підприємствах, що належать фірмі. Для
розширення всіх трьох підприємств виділяються кошти в об’ємі 6 млн. у.о.
Кожне з підприємств пропонує проекти, в яких вказуються сумарні
затрати на реалізування проекту (С) та прибутки (R) пов’язані з
реалізацією проекту. Деякі задачі наведено в таблиці:

Таблиця 4.1 – Проекти трьох підприємств
Проект Підприємство Підприємство 2 Підприємство 3
1
C1 R1 C1 R1 C1 R1
1 0 0 0 0 0 0
2 1 4 2 8 1 6
3 2 7 3 9 3 10
4 4 10 5 13 4 12
5 - - 6 15 - -

У таблиці враховано можливості відмови від розширення будь-
якого підприємства.

86