5.3 Алгоритм пп розв’язку задачі
Визначимо основні елементи моделі динамічного програмування.
Етап відповідає -му періоду.
Кожному етапу ставиться у відповідність своя керована змінна
.На кожному етапі (крім етапу
)
можливі стани
(значення числа робітників
):
÷
.У кожному стані можливі розв’язки – найм/звільнення якоїсь кількості робітників або збереження їхньої чисельності. При цьому обраний розв’язок однозначно визначає значення керованої змінної – число робітників поточного періоду.
Для кожного стану кожного етапу знаходимо
Наша мета – знайти
.
Отже, алгоритм розв’язання задачі такий:
1.
Покласти
;
.
2.
Планування
кроку
.
Виділити всі можливі стани , які можуть мати місце на початку кроку (кількість робітників на початку кроку ):
:
[
;
]
:
=
.
Для кожного можливого стану (кількість робітників на початку кроку ) визначити можливі розв’язки на цьому етапі:
[
;
]
Для кожного значення знаходимо мінімальне значення витрат на кроках від -го до -го включно
,
запам'ятати, при якому був досягнутий мінімум.
.
Якщо
l,
то повернутися до п. 2.Інакше – перейти
до п.4 .Формування оптимального розв’язку.
! |
Можливі
значення
|
(число робітників на поточному кроці)
починаючи від
збільшуючи із кроком 1, досить перебирати
доти, поки не “спіймаємо” мінімум
виразу
.5.4 Приклад розв’язання зврс
Розв’яжемо
таку ЗВРС: число місяців
=3.
Необхідна кількість працівників по
місяцях:
=7,
=4,
=6.
Кількість працівників на початку робіт:
=7.
Функції витрат:
Відповідно
до теорії ДП у цій задачі діапазон
можливих значень
і
–
всі цілі від 4 до 7. Процес розв’язку
цієї ЗВРС представлений у табл. 7
Таблиця 7
Крок j |
Можливі стани
|
Можливі розв’язки |
Вартість розв’язку
|
Умов. оптимальний розв’язок |
||
Дія |
Кількість
робітників на етапі j:
|
|
|
|||
3
|
4 |
- |
4 |
0+6+0=6 |
4,5,6 |
6 |
н1 |
5 |
3+3+0=6 |
||||
н2 |
6 |
6+0+0=6 |
||||
н3 |
7 |
9+3+0=12 |
||||
5 |
з1 |
4 |
1+6+0=7 |
5,6 |
3 |
|
- |
5 |
0+3+0=3 |
||||
н1 |
6 |
3+0+0=3 |
||||
н2 |
7 |
6+3+0=9 |
||||
6 |
з2 |
4 |
2+6+0=8 |
6 |
0 |
|
з1 |
5 |
1+3+0=4 |
||||
- |
6 |
0+0+0=0 |
||||
н1 |
7 |
3+3+0=6 |
||||
7 |
з3 |
4 |
3+6+0=9 |
6 |
1 |
|
з2 |
5 |
2+1+0=3 |
||||
з1 |
6 |
1+0+0=1 |
||||
- |
7 |
0+3+0=3 |
||||
2
|
4 |
- |
4 |
0+0+6=6 |
4 |
6 |
н1 |
5 |
3+3+3=9 |
||||
5 |
з1 |
4 |
1+0+6=7 |
5 |
6 |
|
- |
5 |
0+3+3=6 |
||||
н1 |
6 |
3+6+0=9 |
||||
6 |
з2 |
4 |
2+0+6=8 |
6 |
6 |
|
з1 |
5 |
1+3+3=7 |
||||
- |
6 |
0+6+0=6 |
||||
н1 |
7 |
3+9+1=13 |
||||
7 |
з3 |
4 |
3+0+6=9 |
6 |
7 |
|
з2 |
5 |
2+3+3=8 |
||||
з1 |
6 |
1+6+0=7 |
||||
- |
7 |
0+9+1=10 |
||||
1
|
7= |
з3 |
4 |
3+9+6=18 |
7 |
7 |
з2 |
5 |
2+6+6=14 |
||||
з1 |
6 |
1+3+6=10 |
||||
- |
7 |
0+0+7=7 |
||||
(к-сть
робітників на початок етапу j):
Розглянемо докладніше планування етапу 2 (стани 4 і 5).
j=2 |
|
Можливі розв’язки |
Вартість розв’язку
|
|
|
|
Дія |
|
|||||
2
|
4 |
- (нікого не наймаємо і не звільняємо) |
4 |
0+0+6=6 |
4 |
2
|
н1 (найм однієї людини) |
5 |
3+3+3=9 |
||||
Далі
можна не перебирати можливі значения
.
Це пов’язано з тим, що
функція
|
||||||
5 |
з1 (звільнення одної людини) |
4 |
1+0+6=7 |
5 |
|
|
- (нікого не наймаємо і не звільняємо) |
5 |
0+3+3=6 |
||||
н1 (найм одної людини) |
6 |
3+6+0=9 |
||||
Мінімум
функції
|
||||||
опукла вниз по
(
),
і після того, як ми отримали мінімум,
подальше збільшення
призведе лише до
збільшення значення функції. Тому
значення
=6
и 7 не аналізуються.
«спійманий». Значення
=
7 можно не аналізувати, оскільки
значення функції в цьому випадку буде
більше 9.
Порядок формування відповіді показаний стрілками в табл. 7.
Відповідь:
Період |
1 |
2 |
3 |
Кількість робітників |
7 |
6 |
6 |
Мінімальні витрати складають 7 одиниць вартості
Перевірка:
Період |
0 |
1 |
2 |
3 |
Разом
|
Кількість робітників |
7 (задано) |
7 |
6 |
6 |
|
Витрати
на зміну чисельності
|
– |
0 |
1 |
0 |
|
Втрати,
пов'язані з відхиленням від ідеального
числа робітників
|
– |
0 ( =7) |
6 ( =4) |
0
( |
|
Сумарні витрати |
– |
0 |
7 |
0 |
7 |
=6)
Іноді
задане тільки
– кількість робітників, що ми повинні
мати по закінченні
періодів. У такому випадку рекомендується
застосовувати алгоритм прямої прогонки.