- Цветы и растения
- Аквариум и рыбы
- Для работы
- Для сайта
- Для обучения
- Почтовые индексы Украины
- Всяко-разно
- Электронные библиотеки
- Реестры Украины
- Старинные книги о пивоварении
- Словарь старославянских слов
- Все романы Пелевина
- 50 книг для детей
- Стругацкие, сочинения в 33 томах
- Записи Леонардо да Винчи
- Биология поведения человека
Главная Прочие дисциплины Книги Математичне програмування - Наконечний С.І. |
Математичне програмування - Наконечний С.І.
9.6. Приклади розв’язування задач динамічного програмування
Фірма планує нарощувати виробничі потужності на чотирьох підприємствах, маючи для цього 4 млн грн. Для кожного підприємства розроблено інвестиційні проекти, які відображають прогнозовані загальні витрати С (обсяги капіталовкладень) та доходи D, пов’язані з реалізацією кожного проекту. Ці показники наведені в табл. 9.22:
Таблиця 9.22
Проект | Підприємство |
|||||||
1 |
2 |
3 |
4 |
|||||
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2 |
1 |
3 |
1 |
4 |
2 |
4 |
1 |
2 |
3 |
2 |
5 |
2 |
6 |
3 |
9 |
2 |
8 |
4 |
3 |
7 |
3 |
8 |
4 |
12 |
3 |
5 |
Перший проект не передбачає розширення виробництва, а тому має нульові витрати і доходи. Необхідно розробити план інвестування виділених коштів у зазначені підприємства так, щоб одержати максимальний прибуток.
Розв’язання. Як вже наголошувалось, спрощеним, але і найменш ефективним способом розв’язування подібних задач є перебір усіх можливих варіантів. Проте на практиці їх так багато, що проаналізувати їх всі і вибрати серед них найефективніший неможливо. Головними недоліками такого способу розв’язування є великий обсяг обчислень, відсутність апріорної інформації про недопустимі розв’язки, а також неможливість скористатися проміжними результатами аналізу для відкидання неоптимальних комбінацій проектів.
Розв’яжемо цю задачу, починаючи пошук умовно-оптимального управління з останнього кроку. Кроками задачі вважатимемо кожне з чотирьох підприємств, оскільки для кожного з них маємо вибрати оптимальний інвестиційний проект за обмежених грошових ресурсів.
Зауважимо, що в цьому разі нединамічний процес розглядаємо як динамічний, аби скористатися методами динамічного програмування для знаходження оптимального розв’язку. Зв’язок між зазначеними кроками забезпечується обмеженням на загальний обсяг виділених коштів — 4 млн грн.
Змінні задачі візьмемо так, щоб можна було послідовно керувати процесом розподілу коштів:
х1 — обсяг капіталовкладень, виділених на кроках 1—4;
х2 — обсяг капіталовкладень, виділених на кроках 2—4;
х3 — обсяг капіталовкладень, виділених на кроках 3 і 4;
х4 — обсяг капіталовкладень, виділених на 4 кроці.
— обсяг інвестицій в і-те підприємство .
— оптимальний обсяг інвестицій в і-те підприємство.
Рекурентне співвідношення, що описує зв’язок між ефективностями управління від 4-го до 1-го кроку (від четвертого до першого підприємства) подається у вигляді:
,
, ,
де — сумарна ефективність інвестицій з і-го кроку до останнього.
Тут , оскільки п’ятого підприємства не існує.
Виконаємо поетапні розрахунки за цією моделлю.
Етап IV.
.
Результати розрахунків подамо таблицею:
Таблиця 9.23
х4 |
Дохід |
Оптимальний розв’язок |
|||||
0 |
0 |
0 |
|
|
|
0 |
0 |
1 |
0 |
2 |
|
|
|
2 |
1 |
2 |
0 |
2 |
8 |
|
|
8 |
2 |
3 |
0 |
2 |
8 |
5 |
|
8 |
2 |
4 |
0 |
2 |
8 |
5 |
|
8 |
2 |
за умов
,
Результати розрахунків наведені в табл. 9.24:
Таблиця 9.24
х3 |
Дохід |
Оптимальний розв’язок |
||||
0 |
|
|
|
0 |
0 |
|
1 |
|
|
|
2 |
0 |
|
2 |
|
|
8 |
0 |
||
3 |
|
9 |
3 |
|||
4 |
12 |
2 або 4 |
Розрахунки виконують так. Нехай потрібно знайти . Обчислюємо за формулою:
.
Отже,
,
,
.
Зауважимо, що , оскільки для третього підприємства не існує проекту з інвестиціями в 1 млн грн. Значення беремо з попередньої таблиці. Потім маємо:
.
Етап 2
за умов:
, .
Результати розрахунків подані в табл. 9.25:
Таблиця 9.25
х2 |
Дохід |
Оптимальне рішення |
|||||
k2 = 0 |
k2 = 1 |
k2 = 2 |
k2 = 3 |
k2 = 4 |
|||
0 |
0 |
|
|
|
|
0 |
0 |
1 |
4 |
4 |
|
|
|
4 |
1 |
2 |
8 |
6 |
6 |
|
|
8 |
0 |
3 |
9 |
12 |
8 |
8 |
|
12 |
1 |
4 |
12 |
13 |
14 |
10 |
|
14 |
2 |
Етап 1.
за умов:
, .
Виконуємо розрахунки лише для х1 = 4, подаючи їх у табл. 9.26:
Таблиця 9.26
х1 |
Дохід |
Оптимальний розв’язок |
||||
4 |
|
15 |
1 |
Знайдемо оптимальний план. Із таблиці першого кроку випливає, що , тобто для першого підприємства реалізується другий проект, яким передбачено 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
Період (квартал року) |
Обсяг попиту на продукцію, тис. од. |
Витрати на розміщення замовлення, тис. грн |
Витрати на зберігання, тис. грн |
1 |
4 |
7 |
2 |
2 |
5 |
8 |
3 |
3 |
3 |
6 |
1 |
4 |
2 |
9 |
0 |
Відомо, що на початку планового періоду запас становить 2 тис. од., а під час купівлі продукції діє система оптових знижок. Витрати на придбання 1 тис. од. продукції становлять 15 тис. грн, а коли розмір замовлення перевищує 3 тис. од., то витрати знижуються на 12 % і становлять 12 тис. грн.
Нехай — кількість етапів планового періоду. Тоді для і-го етапу введемо такі позначення: хі — запас продукції на початок етапу; yi — обсяг замовленої продукції (обсяг замовлення); hi — витрати на зберігання 1 тис. од. запасу продукції; kі — витрати на розміщення замовлення; — обсяг попиту на продукцію; Ciyi — витрати, що пов’язані з купівлею (виробництвом) продукції yi.
Визначимо f(xi, yi) як мінімальні витрати на етапах , якщо обсяги запасів дорівнюють xі.
Рекурентні залежності, що відповідають схемі зворотного прогону, набувають вигляду:
за умов:
, , .
Для N-го етапу маємо:
за умов:
, .
Розглянемо покроковий розрахунок оптимальної стратегії управління запасами.
Етап 4. Маємо: ,
за умов:
.
Можливі варіанти розв’язків наведені в табл. 9.28:
Таблиця 9.28
х4 |
Оптимальний розв’язок |
||||
0 |
|
|
39 |
2 |
|
1 |
|
|
24 |
1 |
|
2 |
|
|
0 |
0 |
Етап 3. Маємо: .
за умов:
.
Результати розрахунків подамо у табл. 9.29:
Таблиця 9.29
х3 |
Доходи: |
Оптимальний розв’язок |
||||||
y3 = 0 |
y3 = 1 |
y3 = 2 |
y3 = 3 |
y3 = 4 |
y3 = 5 |
|||
0 |
|
|
|
6 + 3 • 15 + + 39 = 90 |
6 + 4 • 12 + + 24 = 78 |
6 + 5 • 12 + + 0 = 66 |
66 |
5 |
1 |
|
|
6 + 2 • 15 + + 1 • 1 + 39 = 76 |
6 + 3 • 15 + + 1 • 1 + 39 = 76 |
6 + 3 • 12 + + 1 • 1 + 0 = 55 |
|
55 |
4 |
2 |
|
6 + 1 • 15 + + 2 • 1 + 39 = 62 |
6 + 2 • 15 + + 2 • 1 + 24 = 62 |
6 + 3 • 15 + + 2 • 1 + 0 = 53 |
|
|
53 |
3 |
3 |
3 • 1 + 39 = 42 |
6 + 1 • 15 + + 3 • 1 + 24 = 48 |
6 + 2 • 15 + + 3 • 1 + 0 = 39 |
|
|
|
39 |
2 |
4 |
4 • 1 + 24 = 48 |
6 + 1 • 15 + + 4 • 1 + 0 = 25 |
|
|
|
|
25 |
1 |
5 |
5 • 1 + 0 = 5 |
|
|
|
|
|
5 |
0 |
Розрахунки виконуємо так. Наприклад, обчислимо і . Оскільки за умовою , то може набувати значень 0, 1, 2, 3, 4, 5, а — також значень 0, 1, 2, 3, 4, 5. Тепер знайдемо і для і . Для і маємо:
Аналогічно:
,
.
Далі обчислюємо:
Отже,
при .
Так само виконуємо розрахунки для х = 1, 2, 3, 4, 5, а результати записуємо у відповідну таблицю.
Етап 2. Маємо: β2 = 5.
за умов:
.
У таблицю записуємо лише остаточні результати обчислень (табл. 9.30):
Таблиця 9.30
х2 |
Оптимальні розв’язки |
|||||||||||||||||||||||
y2 = 0 |
y2 = 1 |
y2 = 2 |
y2 = 3 |
y2 = 4 |
y2 = 5 |
y2 = 6 |
y2 = 7 |
y2 = 8 |
y2 = 9 |
y2 = 10 |
||||||||||||||
х2 = 0 |
|
|
|
|
|
134 |
135 |
145 |
143 |
141 |
133 |
133 |
10 |
|||||||||||
х2 = 1 |
|
|
|
|
125 |
126 |
136 |
134 |
132 |
124 |
|
124 |
9 |
|||||||||||
х2 = 2 |
|
|
|
125 |
117 |
127 |
125 |
123 |
115 |
|
|
115 |
8 |
|||||||||||
х2 = 3 |
|
|
113 |
117 |
118 |
116 |
114 |
106 |
|
|
|
106 |
7 |
|||||||||||
х2 = 4 |
|
101 |
105 |
118 |
107 |
105 |
97 |
|
|
|
|
97 |
6 |
|||||||||||
х2 = 5 |
81 |
93 |
106 |
107 |
96 |
88 |
|
|
|
|
|
81 |
0 |
|||||||||||
х2 = 6 |
73 |
94 |
95 |
96 |
79 |
|
|
|
|
|
|
73 |
0 |
|||||||||||
х2 = 7 |
74 |
83 |
74 |
79 |
|
|
|
|
|
|
|
74 |
0 або 2 |
|||||||||||
х2 = 8 |
63 |
72 |
67 |
|
|
|
|
|
|
|
|
63 |
0 |
|||||||||||
х2 = 9 |
52 |
55 |
|
|
|
|
|
|
|
|
|
52 |
0 |
|||||||||||
х2 = 10 |
35 |
|
|
|
|
|
|
|
|
|
|
35 |
0 |
Етап 1.
Маємо: β1 = 4.
за умов:
.
Діємо так, як і на етапі 2, складаючи таблицю результатів (табл. 9.31):
Таблиця 9.31
x1 |
Оптимальні розв’язки |
||||||||||||
y1 = 2 |
y1 = 3 |
y1 = 4 |
y1 = 5 |
y1 = 6 |
y1 = 7 |
y1 = 8 |
y1 = 9 |
y1 = 10 |
y1 = 11 |
y1 = 12 |
|||
2 |
174 |
180 |
174 |
177 |
180 |
176 |
180 |
193 |
194 |
195 |
180 |
174 |
2 або 4 |
Отже, дістали два варіанти оптимального плану управління запасами підприємства, яким відповідають однакові мінімальні загальні витрати на постачання та зберігання продукції.
Інформацію про перший варіант оптимального плану містить табл. 9.32:
Таблиця 9.32
Етап |
Запас |
Обсяг замовлення |
Попит |
Залишок продукції на кінець етапу |
Витрати на придбання продукції та її зберігання |
1 |
|||||
2 |
|||||
3 |
|||||
4 |
|||||
Разом |
|
|
|
|
174 |
Другий варіант оптимального плану наведено в табл. 9.33:
Таблиця 9.33
Етап |
Запас |
Обсяг замовлення |
Попит |
Залишок продукції на кінець етапу |
Витрати на придбання продукції та її зберігання |
1 |
|||||
2 |
|||||
3 |
|||||
4 |
|||||
Разом |
|
|
|
|
174 |
Зіставляючи ці два варіанти, бачимо, що відрізняються вони лише першими двома етапами і дають змогу маневрувати фінансовими ресурсами підприємства, яке водночас вирішує ще низку інших проблем.
Created/Updated: 25.05.2018