3.3.2. Рекурентні співвідношення динамічного програмування

Процес розподілу ресурсу між технологічними процесами можна розбити на етапів, на кожному з яких будуть прийматись рішення по окремому технологічному процесу в залежності від стану запасу ресурсу. Крім того, постановка задачі дає можливість оцінити загальний прибуток, як суму прибутків від кожного технологічного процесу. Врахування цих особливостей дає можливість використання методу динамічного програмування для розв’язування задачі (3.3.1)-(3.3.3).

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

на множині, яка описується умовами (3.3.2) та (3.3.3).

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

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

,

за умов

,
.

Ефективність цих двох кроків визначається сумою прибутків від -го технологічного процесу та всіх інших:

.

Вимога максимальної ефективності від реалізації цих кроків еквівалентна запису:

,

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

З аналогічних міркувань максимальний прибуток від розподілу залишку ресурсу ( ) визначається формулою:

,

де

.

Максимальний прибуток від розподілу ресурсу на проміжному кроці визначається наступною формулою:

,

(3.3.4)

де

.

Враховуючи, що на останньому кроці

,

природно вважати .

Таким чином, максимальний прибуток від розподілу ресурсу на -му кроці дорівнює

,

(3.3.5)

Рівняння типу (3.3.4) називається основним рекурентним співвідношенням, яке є математичним відображенням так званого принципу оптимальності: оптимальна поведінка має таку властивість, що, в якому б стані не знаходилася система і які б рішення не приймалися у попередні моменти, наступні рішення повинні бути оптимальними відносно стану, в якому опинилася система.

3.3.3. Обчислювальний алгоритм

Алгоритм розв’язування задачі (3.3.1)-(3.3.3) методом динамічного програмування складається з двох етапів. Перший етап — розв’язування рекурентних рівнянь вигляду (3.3.4), тобто визначення сукупності для та оптимальних для кожного . Другий — формування оптимального розв’язку задачі.

Розглянемо обчислювальну процедуру знаходження оптимального розв’язку задачі (3.3.1)-(3.3.3). Оскільки в процесі розв’язування задачі методом динамічного програмування необхідно мати інформацію про величини прибутків від кожного технологічного процесу при різних варіантах розподілу ресурсу, то для виконання першого етапу зручно користуватися таблицями, одну з яких будемо називати основною (табл.3.17), а другу — допоміжною (табл.3.18).

Таблиця 3.17.

0
1

В основній таблиці 3.17 зміст величин у стовпчиках такий: - наявна кількість ресурсу; - ефективність використання технологічних способів, ; - інтенсивність використання -го технологічного способу, .

Зрозуміло, що неможливо протабулювати всі значення функцій при будь-яких значеннях . Тому доцільно скористатися значенням функцій , у скінченій кількості точок, скажімо,

,

де — довжина інтервалу, — кількість дискретних інтервалів, на які розбивається відрізок (у табл.3.17 ).

Значення для , які не співпадають з указаними точками, можна одержати інтерполяцією.

Таблиця 3.18.

0
1

У допоміжній таблиці 3.18 зміст стовпчиків такий: - аналогічно таблиці 3.17; - залишок ресурсу після знаходження рішення по -му технологічному процесу; - загальна ефективність від прийняття рішення по -му технологічному процесу та по решті ( )-му процесам.

Допоміжна таблиця 3.18 складається для . Для обчислення оптимуму задачі (3.3.1)-(3.3.3) необхідно починати з визначення за формулою (3.3.5), а потім виконати весь шлях у зворотньому напрямку відповідно з (3.3.4) до визначення та .

Знайдені значення функції при і відповідне значення змінної заносяться до основної таблиці 3.17. Далі переходимо до обчислення згідно з (3.3.4) при . Для зручності обчислень використовується допоміжна таблиця 3.18 при . Знайдені значення функції при і відповідне значення змінної заносяться до основної таблиці 3.17.

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

Тепер перейдемо до другого етапу методу динамічного програмування, тобто розглянемо обчислювальну процедуру формування оптимального розв’язку задачі (3.3.1)-(3.3.3). Для визначення вектора скористаємося основною таблицею 3.17, з якої спочатку визначимо , яке відповідає максимальному загальному прибутку . Потім обчислимо кількість ресурсів, які залишилися після фіксації . У результаті розподілу ресурсів , які залишилися, максимальна величина прибутку дорівнює . Цьому значенню прибутку відповідає певне значення змінної . Далі знову обчислюємо кількість ресурсів, які залишилися після фіксації та :

.

З основної таблиці 3.17 можна визначити величину максимального прибутку , одержаного в результаті оптимального розподілу ресурсів, які залишилися. Відповідно визначаємо і т.д.

Якщо після виконання кроків залишок ресурсу , то автоматично решті змінних надаються нульові значення.

Приклад 3.4. Розглянемо задачу знаходження максимального прибутку від розподілу 6 одиниць ресурсу на виробництво 3 видів продукції A, B і C. Норми витрат ресурсу та прибуток з кожної одиниці продукції всіх видів наведено в таблиці 3.19:

Таблиця 3.19.

Види продукції	A	B	C
Норми витрат ресурсу (ум.од.)	4	5	2
Прибуток з одиниці продукції кожного виду (грн.)	9	7	4

Прибуток підприємства можна підрахувати тоді, коли визначено план виробництва.

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

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

за обмежень на використання ресурсу

і на вибір змінних

цілі, .

Розв’яжемо задачу методом динамічного програмування. У відповідності з принципом оптимальності побудуємо рекурентні співвідношення типу (3.3.4) для даної задачі. В результаті розподілу ресурсу максимальний прибуток від виробництва продукції виду C в кількості одиниць і оптимального використання залишку ресурсу на виробництво інших видів продукції визначатиметься наступною формулою:

.

Оскільки норма витрат ресурсу на одиницю продукції виду C дорівнює 2, то можлива кількість продукції виду C коливається від 0 до , де — ціла частина числа .

Величина максимального прибутку від розподілу залишку ресурсу на виробництво продукції видів A і B визначається формулою:

.

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

.

(3.3.6)

Складемо і почнемо заповнювати основну таблицю 3.20. Будемо вважати, що кількість ресурсу - дискретна величина, яка набуває всіх цілих значень від 0 до 6.

Таблиця 3.20.

0	0	0	0	0
1	0	0	0	0
2	0	0	0	0
3	0	0	0	0
4	9	1	9	0
5	9	1	9	0
6	9	1	9	0	13	1

Заповнювати основну таблицю починаємо зі стовпчиків та . Якщо величина ресурсу дорівнює нулю, то на виробництво продукції виду A ресурс не можуть бути виділений. Відповідно та . Якщо залишилася 1 одиниця ресурсу, то, враховуючи норму витрат на продукцію виду A, яка дорівнює 4, виробництво цієї продукції неможливе. Тому та . З аналогічних міркувань та , та . При , враховуючи (3.3.6), та , при , та і т.д.

Для визначення скористаємося допоміжною таблицею 3.21.

Таблиця 3.21.

0	0	0	0+0=0
1	0	1	0+0=0
2	0	2	0+0=0
3	0	3	0+0=0
4	0	4	0+9=9
5	0 1	5 0	0+9=9 7+0=7
6	0 1	6 1	0+9=9 7+0=7

Прокоментуємо заповнення таблиці 3.21. За відсутності ресурсу, тобто , обсяг виробництва продукції виду B неможливий, тому . Відповідно залишок ресурсів буде тим самим, тобто , і прибутку підприємство не одержить, тобто .

При кількості ресурсу виробництво продукції виду B неможливе, тобто . Тоді кількість нерозподілених ресурсів залишається такою ж самою, тобто . Відповідно підприємство прибуток не одержить, і т.д.

Заповнивши допоміжну таблицю 3.21 до кінця, зробимо з неї вибірку про максимальні значення прибутків при та відповідні значення змінної . Ці дані вносимо до основної таблиці 3.20 у стовпчики та .

Для обчислення заповнимо наступну допоміжну таблицю 3.22:

Таблиця 3.22.

6	0	6	0+9=9
	1	1	4+9=13
	2	2	8+0=8
	3	0	12+0=12

Максимальному значенню , яке дорівнює 13, відповідає значення змінної . Ці результати вносимо до основної таблиці 3.20 у стовпчики та .

Оскільки відповідає оптимальному значенню цільової функції , то перший етап алгоритму закінчено.

Перейдемо до другого етапу — формування оптимального розв’язку . Цей етап виконується за допомогою основної таблиці 3.20.

Якщо , то на виробництво решти видів продукції залишається 4 одиниці ресурсу. При та . На виробництво продукції виду A залишається 4 одиниці ресурсу. При та .

Так, оптимальним розв’язком задачі є , тобто продукції А та С треба виробляти по одній одиниці, продукт В не виробляється, а максимальний прибуток складає 13 грн.

Для програмної реалізації методу динамічного програмування можна запропонувати наступну схему.

Позначимо — кількість способів, що вже розглянуті, . Схема алгоритму буде такою:

1. .

2. Розіб’ємо весь інтервал зміни ресурсів від 0 до одиниць на інтервалів довжиною .

3. Для кожного з інтервалів визначимо можливі значення інтенсивності технологічного способу , тобто

,

де — кількість точок поділу відрізку на частин;

— проміжні значення ресурсів, ;

— нормативи витрат ресурсів на -й технологічній спосіб.

Нехай змінна може набувати значень .

4. Визначимо величини невитрачених ресурсів для кожного інтервалу :

.

5. Ефективність використання , , ресурсів технологічним способом з інтенсивністю буде визначатися як

.

6. Найкращий варіант використання ресурсу , технологічним способом з інтенсивністю буде визначатися як

Для кожного значення зафіксуємо значення , а також відповідне значення змінної .

7. Якщо , тоді та повернутися до пункту 3.

Якщо , тоді перейти до пункту 8.

8. Оскільки на технологічних способів виділяється ресурсів, то на цьому етапі доцільно розглянути розподіл саме одиниць ресурсу, тобто , тоді . Повернутися до пункту 3. Пункти 3-6 виконати тільки для . На цьому закінчити перший етап алгоритму. В результаті виконаних обчислень ми визначили максимальний прибуток від розподілу можливої кількості ресурсу, а також оптимальний спосіб досягнення цього прибутку при фіксованій кількості технологічних способів.

Другий етап алгоритму — побудова оптимального розв’язку. Він здійснюється за такою схемою:

1. .

2. Знаходимо та відповідне йому . Зафіксуємо .

3. Визначимо, скільки ресурсів ще залишилося невикористаними

.

4. . Якщо , тоді перейти до пункту 6. Якщо , тоді перейти до пункту 5.

5. Якщо , тоді . Якщо , тоді повернутися до пункту 2.

6. Кінець.