Розділи

загрузка...
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

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

.

Отже,

,

,

.

Зауважимо, що , оскільки для третього підприємства не існує проекту з інвестиціями в 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 тис. од. запасу продукції; — витрати на розміщення замовлення; — обсяг попиту на продукцію; Ciyi — витрати, що пов’язані з купівлею (виробництвом) продукції yi.

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

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

за умов:

, , .

Для 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

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