Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І.

Математичне програмування - Наконечний С.І.

9.6. Приклади розв’язування задач динамічного програмування

Фірма планує нарощувати виробничі потужності на чотирьох підприємствах, маючи для цього 4 млн грн. Для кожного підприємства розроблено інвестиційні проекти, які відображають прогнозовані загальні витрати С (обсяги капіталовкладень) та доходи D, пов’язані з реалізацією кожного проекту. Ці показники наведені в табл. 9.22:

Таблиця 9.22

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

Розв’язання. Як вже наголошувалось, спрощеним, але і найменш ефективним способом розв’язування подібних задач є перебір усіх можливих варіантів. Проте на практиці їх так багато, що проаналізувати їх всі і вибрати серед них найефективніший неможливо. Головними недоліками такого способу розв’язування є великий обсяг обчислень, відсутність апріорної інформації про недопустимі розв’язки, а також неможливість скористатися проміжними результатами аналізу для відкидання неоптимальних комбінацій проектів.

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

Зауважимо, що в цьому разі нединамічний процес розглядаємо як динамічний, аби скористатися методами динамічного програмування для знаходження оптимального розв’язку. Зв’язок між зазначеними кроками забезпечується обмеженням на загальний обсяг виділених коштів — 4 млн грн.

Змінні задачі візьмемо так, щоб можна було послідовно керувати процесом розподілу коштів:

х1 — обсяг капіталовкладень, виділених на кроках 1—4;

х2 — обсяг капіталовкладень, виділених на кроках 2—4;

х3 — обсяг капіталовкладень, виділених на кроках 3 і 4;

х4 — обсяг капіталовкладень, виділених на 4 кроці.

— обсяг інвестицій в і-те підприємство .

— оптимальний обсяг інвестицій в і-те підприємство.

Рекурентне співвідношення, що описує зв’язок між ефективностями управління від 4-го до 1-го кроку (від четвертого до першого підприємства) подається у вигляді:

,

, ,

де — сумарна ефективність інвестицій з і-го кроку до останнього.

Тут , оскільки п’ятого підприємства не існує.

Виконаємо поетапні розрахунки за цією моделлю.

Етап IV.

.

Результати розрахунків подамо таблицею:

Таблиця 9.23

за умов

,

Результати розрахунків наведені в табл. 9.24:

Таблиця 9.24

Розрахунки виконують так. Нехай потрібно знайти . Обчислюємо за формулою:

.

Отже,

,

,

.

Зауважимо, що , оскільки для третього підприємства не існує проекту з інвестиціями в 1 млн грн. Значення беремо з попередньої таблиці. Потім маємо:

.

Етап 2

за умов:

, .

Результати розрахунків подані в табл. 9.25:

Таблиця 9.25

Етап 1.

за умов:

, .

Виконуємо розрахунки лише для х1 = 4, подаючи їх у табл. 9.26:

Таблиця 9.26

Знайдемо оптимальний план. Із таблиці першого кроку випливає, що , тобто для першого підприємства реалізується другий проект, яким передбачено 1 млн грн інвестицій з доходом, що дорівнює 3 млн грн. Отже, для другого, третього і четвертого підприємств залишається 4 – 1 = 3 млн грн інвестицій. Із таблиці другого кроку маємо, що за умов х2 = 3 максимальний ефект можна отримати в разі реалізації для другого підприємства першого проекту (k2 = 1). Дохід у такому разі становитиме 4 млн грн. Отже, х3 = 3 – 1 = 2, тобто для третього і четвертого підприємств слід використати 2 млн грн інвестицій. Із таблиці третього кроку за умов х3 = 2 маємо, що k3 = 0. Отже, х4 = 2, а йому відповідають капітальні вкладення k4 = 2, які забезпечують дохід обсягом 8 млн грн. Остаточно маємо: дохід від 4 млн грн інвестицій становить 3 + 4 + 8 = 15 (млн грн).

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

Потрібно розробити програму управління запасами підприємства, тобто визначити обсяги замовлення й період його розміщення, щоб загальні витрати на постачання та зберігання продукції були мінімальними, а попит задовольнявся повністю й своєчасно.
Дані задачі подано в табл. 9.27:

Таблиця 9.27

Відомо, що на початку планового періоду запас становить 2 тис. од., а під час купівлі продукції діє система оптових знижок. Витрати на придбання 1 тис. од. продукції становлять 15 тис. грн, а коли розмір замовлення перевищує 3 тис. од., то витрати знижуються на 12 % і становлять 12 тис. грн.

Нехай — кількість етапів планового періоду. Тоді для і-го етапу введемо такі позначення: хі — запас продукції на початок етапу; yi — обсяг замовленої продукції (обсяг замовлення); hi — витрати на зберігання 1 тис. од. запасу продукції; kі — витрати на розміщення замовлення; — обсяг попиту на продукцію; Ciyi — витрати, що пов’язані з купівлею (виробництвом) продукції yi.

Визначимо f(xi, yi) як мінімальні витрати на етапах , якщо обсяги запасів дорівнюють xі.

Рекурентні залежності, що відповідають схемі зворотного прогону, набувають вигляду:

за умов:

, , .

Для N-го етапу маємо:

за умов:

, .

Розглянемо покроковий розрахунок оптимальної стратегії управління запасами.

Етап 4. Маємо: ,

за умов:

.

Можливі варіанти розв’язків наведені в табл. 9.28:

Таблиця 9.28

Етап 3. Маємо: .

за умов:

.

Результати розрахунків подамо у табл. 9.29:

Таблиця 9.29

Розрахунки виконуємо так. Наприклад, обчислимо і . Оскільки за умовою , то може набувати значень 0, 1, 2, 3, 4, 5, а — також значень 0, 1, 2, 3, 4, 5. Тепер знайдемо і для і . Для і маємо:

Аналогічно:

,

.

Далі обчислюємо:

Отже,

при .

Так само виконуємо розрахунки для х = 1, 2, 3, 4, 5, а результати записуємо у відповідну таблицю.

Етап 2. Маємо: β2 = 5.

за умов:

.

У таблицю записуємо лише остаточні результати обчислень (табл. 9.30):

Таблиця 9.30

Етап 1.

Маємо: β1 = 4.

за умов:

.

Діємо так, як і на етапі 2, складаючи таблицю результатів (табл. 9.31):

Таблиця 9.31

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

Інформацію про перший варіант оптимального плану містить табл. 9.32:

Таблиця 9.32

Другий варіант оптимального плану наведено в табл. 9.33:

Таблиця 9.33

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