Алгоритм ПП розв’язку задачі
Визначимо основні елементи моделі динамічного програмування.
Ø Етап 
відповідає -му періоду.
Ø Кожному етапу ставиться у відповідність своя керована змінна 
.
Ø На кожному етапі (крім етапу 
) можливі стани 
(значення числа робітників 
): 
÷ 
.
Ø У кожному стані можливі розв’язки – найм/звільнення якоїсь кількості робітників або збереження їхньої чисельності. При цьому обраний розв’язок однозначно визначає значення керованої змінної – число робітників 
поточного періоду.
Ø Для кожного стану кожного етапу знаходимо
Ø Наша мета – знайти 
.
Отже, алгоритм розв’язання задачі такий:
1. Покласти 
; 
.
2. Планування кроку 
.
2.1 Виділити всі можливі стани, які можуть мати місце на початку кроку (кількість робітників на початку кроку ):
: 
[
; 
]
: = 
.
2.2 Для кожного можливого стану (кількість робітників на початку кроку 
) визначити можливі розв’язки на цьому етапі:
[; ]
2.3. Для кожного значення знаходимо мінімальне значення витрат на кроках від -го до 
-го включно
,
запам'ятати, при якому був досягнутий мінімум.
3. 
. Якщо 
l, то повернутися до п. 2.Інакше – перейти до п.4 .
4. Формування оптимального розв’язку.
| Можливі значення  (число робітників на поточному кроці) починаючи від  збільшуючи із кроком 1, досить перебирати доти, поки не “спіймаємо” мінімум виразу  .
|