Навигация
 
Главная  - Прочие дисциплины  - Книги  - Математичне програмування - Наконечний С.І.
Математичне програмування - Наконечний С.І.
<< Содержание < Предыдущая

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

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



 
Главная
Банковское дело
Бухгалтерский учет, аудит
Инвестиции
Экономика
Налоги
Финансы
Финансовое право
Прочие дисциплины
Карта сайта
Правила користування