Основне рекурентне співвідношення

Стани

Стан системи на кожному етапі будемо описувати за допомогою змінної . Значення визначаються значеннями змінних попередніх етапів. Якщо то

, ,…, ...

На початку -ого періоду система перебуває в одному із станів , а наприкінці цього періоду – у стані .

Оскільки і задані (= 0), вибір напрямку прогонки в цьому випадку довільний. Застосуємо алгоритм прямої прогонки.

Нехай – мінімальні витрати протягом перших періодів (з першого по k-й включно), за умови, що запас на кінець -ого періоду (на початок ( +1)-ого) дорівнює . І нехай в -ому періоді здійснюється поставка в розмірі . (Ми вже з'ясували, що () може приймати значення рівні попиту за ціле число періодів). Це означає, що на кінець ( -1)-ого періоду був запас . Тоді вартість поточного кроку складає , а величина

(20)

являє собою мінімальні витрати за періоди від 1-го до включно, за умови, що на кінець -ого періоду є одиниць продукції, а в -ому періоді здійснюється поставка в об'ємі . Вираз (20) – умовно мінімальні витрати для стану при поставці в -ому періоді. Мінімізуємо (20) по всіх можливих значеннях , одержимо рекурентне співвідношення:

(21)

причому = = + - , .

Мета задачі – знайти .

Може здатися, що (як і раніше) на цьому можна зупинитися. Це не так. Розглянемо, як при виборі допустимих значень змінних враховується співвідношення (19). Оскільки =0, то мінімум (21) у силу опуклості вверх j досягається в одній із крайніх точок

= 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- го періоду, повинна надійти не раніше періоду . Отже, при обчисленні досить розглядати

,

де має обговорений раніше зміст.

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