Розділи

загрузка...
9.6. Приклади розв’язування задач динамічного програмування; Математичне програмування - Наконечний С.І.

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

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

.

Отже,

,

,

.

Зауважимо, що