Варіанти розв’язків

Етапи

Елементи динамічної моделі

Сутність динамічного підходу полягає в заміні розв’язку -крокової задачі послідовністю задач: однокрокової, двокрокової і т.д. ЗУЗ має необхідні властивості задач, до яких можливо застосувати цей підхід: задача припускає інтерпретацію як n-кроковий процес прийняття рішень; задача визначена для будь-якої кількості кроків і має структуру, що не залежить від їхньої кількості.

Отже, для мінімізації z можна скористатися методом динамічного програмування.

Задача природно розбивається на етапи: k- й етап (крок) відповідає k- му періоду. Стан системи на кожному кроці визначається величиною запасів у відповідному періоді планування. Для даної задачі простіше спочатку визначитися з можливими варіантами розв’язку, а вони вже дозволять визначити можливі стани системи.

Варіантами розв’язків є можливі значення об'ємів поставок , .

Твердження. Оптимальним розв’язком задачі (14)-(16) є одна із крайніх точок допустимої множини розв’язків, зумовлених обмеженнями (15)-(16).

Доведення цього твердження витікає з того, що шукається мінімум суми опуклих вверх функцій .

Визначимо координати крайніх точок.

ü З урахування обмежень (15) і не можуть бути рівними нулю одночасно (інакше величина буде від’ємною). Значить допустимий розв’язок { } і { }, має наступну властивість:

, (17)

ü Врахуємо опуклість вверх функцій . За означенням мінімум опуклої вверх функції перебуває на кінці допустимої області (рис. 24).

Рис. 24.

Мінімально допустимому значенню = 0 відповідає максимально допустиме значення (= + ); максимально допустимому значенню (= + )) відповідає мінімально допустиме значення (=0). Отже, для крайніх точок області справедливо:

(18)

Умови (18) еквівалентні співвідношенню

= 0 (19)

З умов (17) і (18) випливає справедливість такого твердження: замовлення на доставку нової партії не надходить, якщо на початку періоду k є запас >0 і навпаки, якщо здійснюється поставка нової партії, то на початок відповідного періоду є нульовий запас. Із цього твердження випливає дуже важлива властивість розглянутої ЗУЗ: замовлення дорівнює попиту за ціле число періодів.

В силу вищесказаного можливі значення змінних такі:

=0 (не виконується для k =1, якщо );

або = ;

або = + ;

…....

або = + + … (замовлення дорівнює попиту за ціле число періодів).

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