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

Приклад 9.1.

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

 

Проект	Підприємство

 

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

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

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

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

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

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

— те саме на кроках 2—4;

— те саме на кроках 3 і 4;

— те саме на кроці 4.

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

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

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

,

, ,

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

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

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

Етап 4.

.

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

 

	Дохід	Оптимальний розв’язок

Етап 3.

за умов

,

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

 

	Дохід	Оптимальний розв’язок
						2 або 4

 

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

.

Отже,

,

,

.

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

.

Етап 2.

за умов

, .

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

 

	Дохід	Оптимальний розв’язок

 

Етап 1.

за умов

, .

Виконуємо розрахунки лише для х ₁ = 4, подаючи їх у вигляді таблиці:

 

	Дохід	Оптимальний розв’язок

 

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

 

Приклад 9.2.

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

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

Дані задачі наведено в таблиці:

 

Період часу (квартал року)	Попит на продукцію, тис. од.	Витрати на розміщення замовлення, тис. грн.	Витрати на зберігання, тис. грн.

 

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

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

Визначимо f (x_i, y_i) як мінімальні витрати на етапах , якщо рівень запасів х_і.

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

за умов

, , .

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

за умов

, .

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

Етап 4. Маємо

за умов

.

Можливі варіанти розв’язків ілюструє таблиця:

 

		Оптимальний розв’язок

 

Етап 3. Маємо

за умов

.

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

 

 

 

 

	Доходи	Оптимальний розв’язок

 

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

.

Аналогічно:

,

.

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

Отже, при .

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

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

Маємо b₃ = 5.

за умов

.

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

 

 

Оптимальні розв ’язки

0 або 2

 

Оптимальні розв’язки

2 або 4

 

 

Маємо b₁ = 4.

за умов

.

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

Інформацію про перший оптимальний план містить таблиця:

Етап	Запас	Розмір замовлення	Попит	Залишок продукції на кінець етапу	Витрати на придбання продукції та її зберігання
Разом

 

Інформація про другий оптимальний план:

 

Етап	Запас	Розмір замовлення	Попит	Залишок продукції на кінець етапу	Витрати на придбання продукції та її зберігання
Разом

 

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

9.2 Приклади та завдання для самостійної роботи

9.1 Фірма планує нарощувати виробничі потужності на трьох підприємствах, виділяючи для цього 18 млн грн. За кожним із підприємств розроблено інвестиційний проект із зазначенням прогнозованих сумарних витрат С та доходів D, що пов’язані з його реалізацією. Розробити план інвестування.

 

Інвестиційний проект	Підприємство
Інвестиції, млн грн.	Прибуток, млн грн.	Інвестиції, млн грн.	Прибуток, млн грн.	Інвестиції, млн грн.	Прибуток, млн грн.

 

9.2 Розв’язати попередню задачу (9.1), якщо розмір інвестицій становить 20 млн грн., а перший інвестиційний проект (ситуація, коли певному підприємству не виділяється коштів) є неприпустимим.

9.3 Розв’язати задачу 9.1, якщо модернізація має проводитися ще на одному — четвертому підприємстві фірми, для якого розроблено три інвестиційні проекти:

 

Проект	Інвестиції, млн грн.	Прибуток, млн грн.

 

Врахувати, що інвестиційний портфель збільшиться на 2 млрд грн.

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

Розмір капіталовкладень, млн грн.	Прибуток по підприємствах, млн грн.
I	II	III
	0,27	0,34	0,21
	0,31	0,44	0,35
	0,42	0,57	0,46
	0,65	0,69	0,68
	0,74	0,87	0,74
	0,93	0,95	0,85

 

9.5 Розв’язати задачу оптимального розподілу капіталовкладень між чотирма підприємствами, якщо загальний розмір інвестицій становить 12 млн грн. Вихідні дані вміщено в таблиці:

 

Проект	Підприємство
Інвестиції, млн грн.	Прибуток, млн грн.	Інвестиції, млн грн.	Прибуток, млн грн.	Інвестиції, млн грн.	Прибуток, млн грн.	Інвестиції, млн грн.	Прибуток, млн грн.

 

9.6 Розв’язати чотириетапну задачу управління запасами за вихідними даними:

 

Етап	Попит, од.	Витрати на розміщення замовлення, грн.

 

Відомо, що витрати на зберігання одиниці продукції протягом одного етапу сталі і становлять 2 грн., витрати на придбання одиниці продукції — 3 грн. для всіх етапів. Вихідний запас на початок досліджуваного періоду — 10 од.

 

9.7 Розв’язати попередню задачу, якщо вихідний запас дорівнює 40 од., а витрати на зберігання змінюються поетапно і становлять відповідно 1; 1,5; 2; 5 грн.

9.8 Розв’язати п’ятиетапну детерміновану задачу управління запасами:

 

Етап	Попит, од.	Витрати на розміщення замовлення, грн.	Витрати на зберігання, грн.

 

Функція витрат на розміщення замовлення визначає питомі витрати: 20 грн. для перших 50 од. та 10 грн. за кожну додаткову одиницю (знижка на кількість).

9.9 Розв’язати на ПК десятиетапну детерміновану задачу управління запасами, вважаючи, що вихідний запас дорівнює 65 од.

 

Етап	Попит	Витрати на придбання, грн.	Витрати на зберігання, грн.	Витрати на розміщення замовлення, грн.

9.10. Розв’язати задачу, розв’язок якої наведено в прикладі 9.1, якщо розмір інвестицій становить 10 млн грн., а перший інвестиційний проект має наступні характеристики

Проект	Підприємство

ТЕОРІЯ ІГОР