Постановка задачі

Загальна схема застосування алгоритму ДП

Сутність динамічного підходу полягає в заміні розв’язання -крокової задачі послідовністю задач: однокрокової, двокрокової і т.п.

Основні властивості задач, що необхідні для можливого застосування цього підходу.

1. Задача повинна допускати інтерпретацію як n-кроковий процес прийняття рішень.

2. Задача повинна бути визначена для будь-якої кількості кроків і мати структуру, що не залежить від їхньої кількості.

3. При розгляді -крокової задачі повинна бути задана деяка множина параметрів, що описують стан системи, від яких залежать оптимальні значення змінних. Причому ця множина не повинна змінюватися при збільшенні кількості кроків.

4. Вибір рішення (управління) на -му кроці не повинен впливати на попередні рішення, крім необхідного перерахунку змінних.

При застосуванні методу ДП необхідно виконати наступні дії.

1. Описати побудову оптимальних розв’язків (при цьому процес прийняття рішення повинен бути розбитий на ряд однотипних кроків або етапів, кожен з яких планується окремо, але з урахуванням результатів, отриманих на інших кроках).

2. Визначити етапи (їх кількість і суть планування на кожному етапі).

3. Для кожного етапу визначити множину можливих станів системи.

4. Для кожного стану визначити множину можливих варіантів рішень (значень керованих змінних).

5. Вивести ОРС.

6. Знайти розв’язки множини оптимізаційних задач (за допомогою алгоритму зворотньої або прямої прогонки).

7. Сформувати оптимальний розв’язок (рухаючись у напрямку, зворотньому до розрахунків).

7 ЗАДАЧА управліННЯ ЗАПАСАМИ

Задача управління запасами (ЗУЗ) – одна з найпоширеніших на практиці задач. Правильне визначення стратегії управліннязапасами дозволяє вивільнити значні оборотні кошти, заморожені у вигляді запасів, що в остаточному підсумку підвищує ефективність використання ресурсів. Елементами системи (задачі) управліннязапасами є:

1) Кількість періодів. Може бути:

- скінченним;

- нескінченним.

2) Попит на предмети постачання. Розрізняють попит:

- детермінований;

- випадковий;

- стаціонарний.

3) Спосіб поповнення запасів:

- миттєва поставка;

- затримка поставок на фіксований інтервал часу;

- затримка поставок на випадковий інтервал часу.

4) Спосіб споживання запасів:

- миттєве споживання;

- споживання, розтягнуте в часі.

5) Функції витрат – у сукупності вони визначають критерій ефективності прийнятої стратегії управліннязапасами. Вони можуть враховувати:

- витрати на зберігання,

- вартість поставок,

- витрати, пов'язані із замовленням кожної нової партії,

- витрати на штрафи. пов'язані з відсутністю (недостачею) необхідної продукції й т.п.

6) Обмеження на:

- максимальний об'єм (вага) запасів;

- максимальний об'єм (вага) поставок;

- максимальна вартість запасів;

- кількість поставок у заданому періоді;

- імовірність недостачі продукції.

Розглянемо задачу зі скінченною кількістю періодів, нестаціонарним детермінованим попитом, миттєвою поставкою і миттєвим споживанням.

Змістовна постановка задачі

Нехай маємо систему постачання підприємства, що планує поставки продукції протягом періодів. Об'єм споживання (сумарний попит підприємства на продукцію) у кожному періоді відомий. Для кожного періоду відомі також витрати на поставку (виготовлення) і витрати на зберігання продукції. Необхідно визначити об'єми поставок продукції в кожному з періодів, щоб

1) повністю задовольнити попит кожного періоду;

2) мінімізувати витрати на поставку і зберігання продукції.

Математична постановка задачі

Введемо позначення:

- сумарний попит в k- му періоді;

- об'єм поставки в -му періоді (або запас, що створюється в k- ому періоді).

- залишок запасу, що залишився з ()-го періоду (залишок продукції на початок періоду );

- витрати на виконання поставки величиною .

Припускаємо, що поставка і споживання продукції здійснюються миттєво на початку періоду, але поставка трохи раніше (рис. 23).

Рис. 23.

Виходячи з визначення величин , і випливає справедливість такого співвідношення:

+ – = ,

де - надлишковий запас, що зберігається в -ому періоді.

Позначимо:

( + - )= () – витрати на зберігання надлишкового запасу в -му періоді;

(, ) - загальні витрати в -му періоді.

Сумарні витрати на постачання за періодів

(11)

Припустимо, що величини й задані. Тоді задача формулюється таким чином: відшукати послідовності { } і { }, що мінімізують функцію сумарних витрат (11) за умови задоволення попиту на продукцію у всіх періодах

(12)

і виконання умов (що поєднують змінні сусідніх періодів):

. (13)

Відзначимо, що якщо відомі величини { }, то за ними можна визначити величини { } і навпаки.

Розглянемо окремий випадок ЗУЗ, що значно спрощує схему обчислення:

1. Покладаємо, що всі функції опуклі вверх по .

2. Будемо вважати функції () лінійними. Тоді

( + – )= ()= ,

де – додатня константа.

3. Із пп. 1 і 2 випливає, що функції () також є опуклими вверх по .

4. Вважаємо, що величина запасів на початок першого періоду =0 і запас на кінець останнього періоду =0.

З урахуванням прийнятих спрощень задача (11)-(13) може бути переписана в наступному вигляді:

(14)

при обмеженнях

. (15)

. (16)

Перейдемо до розв’язання задачі. Для цього визначимо елементи динамічної моделі.

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