7.2 Елементи динамічної моделі
Сутність динамічного підходу полягає в заміні розв’язку -крокової задачі послідовністю задач: однокрокової, двокрокової і т.д. ЗУЗ має необхідні властивості задач, до яких можливо застосувати цей підхід: задача припускає інтерпретацію як n-кроковий процес прийняття рішень; задача визначена для будь-якої кількості кроків і має структуру, що не залежить від їхньої кількості.
Отже, для мінімізації z можна скористатися методом динамічного програмування.
7.2.1 Етапи
Задача природно розбивається на етапи: k-й етап (крок) відповідає k-му періоду. Стан системи на кожному кроці визначається величиною запасів у відповідному періоді планування. Для даної задачі простіше спочатку визначитися з можливими варіантами розв’язку, а вони вже дозволять визначити можливі стани системи.
7.2.2 Варіанти розв’язків
Варіантами
розв’язків є можливі значення об'ємів
поставок
,
.
Твердження. Оптимальним розв’язком задачі (14)-(16) є одна із крайніх точок допустимої множини розв’язків, зумовлених обмеженнями (15)-(16).
Доведення
цього твердження витікає з того, що
шукається мінімум суми опуклих вверх
функцій
.
Визначимо координати крайніх точок.
З урахування обмежень (15) і не можуть бути рівними нулю одночасно (інакше величина
буде від’ємною). Значить допустимий
розв’язок {
} і {
}, має наступну властивість:
,
(17)
Врахуємо опуклість вверх функцій
.
За означенням мінімум опуклої вверх
функції перебуває на кінці допустимої
області (рис. 24).
Рис. 24.
Мінімально
допустимому значенню
= 0 відповідає максимально допустиме
значення
(=
+
);
максимально допустимому значенню
(=
+
))
відповідає мінімально допустиме значення
(=0).
Отже, для крайніх точок області
справедливо:
(18)
Умови (18) еквівалентні співвідношенню
=
0 (19)
З умов (17) і (18) випливає справедливість такого твердження: замовлення на доставку нової партії не надходить, якщо на початку періоду k є запас >0 і навпаки, якщо здійснюється поставка нової партії, то на початок відповідного періоду є нульовий запас. Із цього твердження випливає дуже важлива властивість розглянутої ЗУЗ: замовлення дорівнює попиту за ціле число періодів.
В силу вищесказаного можливі значення змінних такі:
=0
(не виконується для k=1,
якщо
);
або
=
;
або
=
+
;
…....
або
=
+
+ …
(замовлення дорівнює попиту за ціле
число періодів).
7.2.3 Стани
Стан
системи на кожному етапі будемо описувати
за допомогою змінної
.
Значення
визначаються значеннями змінних
попередніх етапів. Якщо
то
,
,…,
...
На
початку
-ого
періоду система перебуває в одному із
станів
,
а наприкінці цього періоду – у стані
.
7.2.4 Основне рекурентне співвідношення
Оскільки і задані ( = 0 ), вибір напрямку прогонки в цьому випадку довільний. Застосуємо алгоритм прямої прогонки.
Нехай
– мінімальні
витрати протягом перших
періодів
(з першого по k-й
включно), за
умови, що запас на кінець
-ого
періоду
(на початок (
+1)-ого)
дорівнює
.
І нехай в
-ому
періоді здійснюється поставка в розмірі
.
(Ми вже з'ясували, що
(
) може приймати значення рівні попиту
за ціле число періодів). Це означає, що
на кінець (
-1)-ого
періоду був запас
.
Тоді вартість поточного кроку складає
,
а величина
(20)
являє собою мінімальні витрати за періоди від 1-го до включно, за умови, що на кінець -ого періоду є одиниць продукції, а в -ому періоді здійснюється поставка в об'ємі . Вираз (20) – умовно мінімальні витрати для стану при поставці в -ому періоді. Мінімізуємо (20) по всіх можливих значеннях , одержимо рекурентне співвідношення:
(21)
причому
=
=
+
-
,
.
Мета
задачі – знайти
.
Може здатися, що (як і раніше) на цьому можна зупинитися. Це не так. Розглянемо, як при виборі допустимих значень змінних враховується співвідношення (19). Оскільки =0, то мінімум (21) у силу опуклості вверх досягається в одній із крайніх точок
=
s +
(max) або
=0
(min)
(
= 0) (min) (
> 0) (max).
Тому
; (22)
Розглянемо
тепер величину
– мінімальні витрати протягом перших
(
)
періодів, за умови, що запас на кінець
(
)-го
періоду дорівнює
.
Для періоду (
)
виконується рівність
=0,
при цьому об'єм поставки
може
приймати або мінімально можливе значення
(
=0)
або максимально можливе (
=
+
+
). При цьому
=
=
+
–
.
. (23)
Підставивши вираз (23) в (22), одержимо:
.
Аналогічно
визначається співвідношення для
:
.
Позначимо
через
мінімальні витрати за перші k
періодів за умови, що остання поставка
була виконана на початку періоду j
і
на кінець k-го
періоду запас дорівнює
:
.
(24)
Записавши
вирази, аналогічні (22), для
,
одержимо
(25)
Особлива
структура
(у
розрахунках використовуються тільки
величини
з нульовими аргументами) і
той факт, що
і
,
дозволяють зробити висновок, що на
кожному кроці досить визначати тільки
.
Значить ОРС (25) набуває такого вигляду:
Розглянемо
окремий випадок вигляду функції
виробничих витрат
.
Нехай
Тоді витрати за перші k періодів за умови, що остання поставка була виконана на початку періоду j і на кінець k-го періоду запас дорівнює , визначаються співвідношенням:
Подальше
спрощення в обчислювальній схемі може
бути отримано, якщо врахувати наступну
обставину. Якщо при обчисленні
виявилося, що поставка, за допомогою
якої задовольнявся попит (k-1)-ого
періоду, надходить у періоді
,
то й поставка, що задовольняє попит k-го
періоду, повинна
надійти не раніше періоду
.
Отже, при обчисленні
досить розглядати
,
де має обговорений раніше зміст.