Приклад розв’язання ЗВРС

Розв’яжемо таку ЗВРС: число місяців =3. Необхідна кількість працівників по місяцях: =7, =4, =6. Кількість працівників на початку робіт: =7. Функції витрат:

Відповідно до теорії ДП у цій задачі діапазон можливих значень і – всі цілі від 4 до 7. Процес розв’язку цієї ЗВРС представлений у табл. 7

Таблиця 7

Крок j	Можливі стани (к-сть робітників на початок етапу j):	Можливі розв’язки	Вартість розв’язку	Умов. оптимальний розв’язок
Дія	Кількість робітників на етапі j:
		-		0+6+0=6	4,5,6
н1		3+3+0=6
н2		6+0+0=6
н3		9+3+0=12
	з1		1+6+0=7	5,6
-		0+3+0=3
н1		3+0+0=3
н2		6+3+0=9
6	з2		2+6+0=8
з1		1+3+0=4
-		0+0+0=0
н1		3+3+0=6
	з3		3+6+0=9
з2		2+1+0=3
з1		1+0+0=1
-		0+3+0=3
		-		0+0+6=6
н1		3+3+3=9
	з1		1+0+6=7
-		0+3+3=6
н1		3+6+0=9
	з2		2+0+6=8
з1		1+3+3=7
-		0+6+0=6
н1		3+9+1=13
7	з3		3+0+6=9	6
з2		2+3+3=8
з1		1+6+0=7
-		0+9+1=10
1	7=	з3		3+9+6=18
з2		2+6+6=14
з1		1+3+6=10
-		0+0+7=7

Розглянемо докладніше планування етапу 2 (стани 4 і 5).

j=2		Можливі розв’язки	Вартість розв’язку
Дія
		- (нікого не наймаємо і не звільняємо)		0+0+6=6
н1 (найм однієї людини)		3+3+3=9
Далі можна не перебирати можливі значения . Це пов’язано з тим, що функція опукла вниз по (), і після того, як ми отримали мінімум, подальше збільшення призведе лише до збільшення значення функції. Тому значення =6 и 7 не аналізуються.
	з1 (звільнення одної людини)		1+0+6=7
- (нікого не наймаємо і не звільняємо)		0+3+3=6
н1 (найм одної людини)		3+6+0=9
Мінімум функції «спійманий». Значення = 7 можно не аналізувати, оскільки значення функції в цьому випадку буде більше 9.

Порядок формування відповіді показаний стрілками в табл. 7.

Відповідь:

Період
Кількість робітників

Мінімальні витрати складають 7 одиниць вартості

Перевірка:

Період					Разом
Кількість робітників	7(задано)
Витрати на зміну чисельності	–
Втрати, пов'язані з відхиленням від ідеального числа робітників	–	( =7)	( =4)	( =6)
Сумарні витрати	–

Іноді задане тільки – кількість робітників, що ми повинні мати по закінченні періодів. У такому випадку рекомендується застосовувати алгоритм прямої прогонки.

Дата добавления: 2014-11-29