Метод рекурентних співвідношень. Використання принципу Беллмана і алгоритму Джонсона.
Фірма планує нарощувати виробничі потужності на чотирьох підприємствах, маючи для цього 4 млн грн. Для кожного з підприємств розроблено інвестиційні проекти, які відбивають прогнозовані сумарні витрати С та доходи D, пов'язані з реалізацією кожного проекту. Зміст цих проектів ілюструє таблиця:
Проєект | Підприємство | |||||||
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—4;
— те саме на кроках 2—4;
— те саме на кроках 3 і 4;
— те саме на кроці 4.
— обсяги інвестицій на г'-му підприємстві .
— оптимальні обсяги інвестицій на і - му підприємстві.
Рекурентне співвідношення для зворотного прогону від кроку 4-го до 1-го (від четвертого підприємства до першого) подається у вигляді:
де — сумарна ефективність інвестицій з і - го кроку до останнього.
Тут , оскільки п'ятого підприємства не існує. Виконаємо поетапні розрахунки за цією моделлю.
Етап 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 |
|
|
Етап 3.
за умов
Результати розрахунків відбиває таблиця:
Дохід | Оптимальний розв’язок | ||||||
0 | 0 | 0 | |||||
1 | 2 | 0 | |||||
2 | 8 | 0 | |||||
3 | 9 | 3 | |||||
4 | 12 | 2 або 4 | |||||
Розрахунки виконуються так. Нехай потрібно знайти .
Обчислюємо
.
Отже,
Запишемо, що , оскільки для третього підприємства не існує проекту з інвестиціями в 1 млн грн. Значення беремо з попередньої таблиці. Далі маємо:
Етап 2.
за умов
Результати розрахунків подаємо таблицею:
Дохід | Оптимальний розв’язок | ||||||
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.
|
|
за умов
Виконуємо розрахунки лише для , подаючи їх у вигляді таблиці:
Дохід | Оптимальний розв’язок | |||||
4 | 15 | 1 |
Знайдемо оптимальний план. Із таблиці першого кроку випливає, що , тобто для першого підприємства реалізується другий проект, який використовує 1 млн грн. інвестицій з ефективністю 3 млн грн. Отже, для другого, третього і четвертого підприємств залишається 4-1=3 млн грн. інвестицій. Із таблиці другого кроку маємо, що за умов максимальний ефект настає в разі реалізації для другого підприємства першого проекту ефективність становить 4 млн грн. Отже, , тобто для третього і чет вертого підприємств слід використати 2 млн грн. інвестицій. Із таблиці третього кроку за умов маємо, що . Отже, , а йому відповідають капітальні вкладення , ефективність яких 8 млн грн. Остаточно маємо: ефективність 4 млн грн. інвестицій становить 3+4 + 8=15 (млн грн.).
Дата добавления: 2022-01-22; просмотров: 17; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!