logo
Курсовик по прикладу вариант № 8

4.2. Решение задачи распределения капитальных вложений методом динамического программирования

Динамическое программирование - это вычислительный метод для решения задач управления определённой структуры, когда задача с n переменными представляется как многошаговый процесс принятия решений. На каждом шаге (этапе) определяется экстремум функции только от одной переменной. Состояние исследуемой системы на каждом шаге характеризуется некоторой переменной величиной, которая называется параметром состояния. Эффект от принятия параметром состояния того или иного значения на данном этапе вместе с уже рассмотренными шагами характеризуется функцией состояния. Решение конкретной задачи методом динамического программирования сводится к выбору параметра состояния, составления функции состояния и рекуррентных соотношений, связывающих функции состояния для двух соседних последовательных этапов, и их применению для выбора оптимального управления.

Воспользуемся методом динамического программирования для решения полученной задачи распределения капитальных вложений. Последовательно ищется оптимальное распределение для k = 2, 3 и 4 фирм.

Пусть первым двум фирмам выделено  тыс. рублей инвестиции ( - параметр состояния, который может изменяться от 0 до 700). Обозначим через F2 () максимальный прирост прибыли на первых двух предприятиях.

Если из  тыс. рублей 2-ая фирма получит х2 тыс. рублей, то максимальный прирост прибыли на 2-ой фирме можно выразить как f2(x2).

На долю 1-ого предприятия останется  - х2 тыс. рублей, а максимальный прирост прибыли на 1-ом предприятии составит F1 ( - х2).

Тогда максимальный прирост прибыли на двух предприятиях будет равен

F2 () = max {f2(x2) + F1 ( - х2)}

0 ≤ x2 ≤ 700

Используя исходные данные из задания, строим Таблицу № 1.1. Значения f2(x2) складываем со значениями F1 (-x2) = f1(-x2) и на каждой побочной диагонали находим наибольшее число, которое помечаем звёздочкой.

Таблица № 1.1

-х2

0

100

200

300

400

500

600

700

X2

F1(-x2)

f2(x2)

0

37

64

87

105

120

134

145

0

0

0

37

64

87

105

120

134

145

100

48

48*

85*

112*

135

153

168

182

---

200

75

75

112*

139*

162*

180

195

---

---

300

98

98

135

162*

185

203

---

---

---

400

120

120

157

184

207*

---

---

---

---

500

132

132

169

196

---

---

---

---

---

600

144

144

181

---

---

---

---

---

---

700

156

156

---

---

---

---

---

---

---

Звездочкой обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 2-м предприятиям.

В Таблицу № 1.2. в графу F2 () заносим значения максимального прироста прибыли на первых двух предприятиях, а в графе указываем соответствующий каждому значениюF2() размер инвестиций 2-ому предприятию.

Таблица № 1.2.

0

100

200

300

400

500

600

700

F2()

0

48

85

112

139

162

185

207

()

0

100

100

200

200

300

300

400

100

200

Далее действуем также: находим функции F3 (), F4 (), используя на каждом k-ом шаге основное рекуррентное соотношение:

Fk (ξ)=max {fk(xk) + Fk-1(ξ - xk)}

0 ≤ xk ≤ 700

для k= 2,3,4

Заполняем Таблицу № 2.1., аналогичным способом определяя максимальный прирост прибыли от распределения капитальных вложений между тремя предприятиями (F3 ()).

Таблица № 2.1.

-х3

0

100

200

300

400

500

600

700

Х3

F2(-x3)

f3(x3)

0

48

85

112

139

162

185

207

0

0

0

48

85

112

139

162

185

207

100

85

85*

133*

170*

197*

224*

247*

270*

---

200

100

100

148

185

212

239

262

---

---

300

111

111

159

196

223

250

---

---

---

400

118

118

166

203

230

---

---

---

---

500

124

124

172

209

---

---

---

---

---

600

129

129

177

---

---

---

---

---

---

700

132

132

---

---

---

---

---

---

---

Звездочкой обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций 3-м предприятиям.

В Таблицу № 2.2. в графу F3 () заносим значения максимального прироста прибыли на трех предприятиях, а в графе указываем соответствующий функцииF3() размер инвестиций 3-ему предприятию.

Таблица № 2.2.

0

100

200

300

400

500

600

700

F3()

0

85

133

170

197

224

247

270

()

0

100

100

100

100

100

100

100

В Таблице № 3.1., определяющей максимальный прирост прибыли от распределения капитальных вложений между четырьмя предприятиями F4(), заполняем только одну диагональ для значения  = 700, поскольку данный этап является завершающим, предприятий всего четыре и между ними необходимо распределить именно 700 тыс. рублей.

Таблица № 3.1.

-х4

0

100

200

300

400

500

600

700

Х4

F(-x4)

f2(x4)

0

85

133

170

197

224

247

270

0

0

270

100

47

294*

---

200

70

294*

---

---

300

80

277

---

---

---

400

86

256

---

---

---

---

500

91

224

---

---

---

---

---

600

94

179

---

---

---

---

---

---

700

98

98

---

---

---

---

---

---

---

Звездочкой обозначен максимальный суммарный эффект от выделения соответствующего размера инвестиций в размере 700 тыс. рублей 4-м предприятиям.

Z max = 294 тыс. рублей,

причем 4-ому предприятию должно быть выделено

х4* = х4 (700) = 200 тыс. рублей

ЛИБО

х4** = х4 (700) = 100 тыс. рублей.

На долю остальных трех предприятий остается в 1-ом случае (х4* = 200) 500 тыс. рублей,

во 2-ом случае (х4** = 100) 600 тыс. рублей.

Из Таблицы № 2.2. видно, что 3-ему предприятию должно быть выделено

в 1-ом случае (х4* = 200): х3* = х3 (700 – х4*) = х3 (500) = 100 тыс. рублей

во 2-ом случае (х4** = 100): х3** = х3 (700 – х4**) = х3 (600) = 100 тыс. рублей.

Таким образом, х3* = 100 тыс. рублей.

Продолжая обратный процесс, находим:

в 1-ом случае (х4* = 200): х2* = х2 (700 – х4* - х3*) = х2 (400) = 200 тыс. рублей

во 2-ом случае (х4** = 100): х2** = х2 (700 – х4** - х3*) = х2 (500) = 300 тыс. рублей

ЛИБО

х2*** = х2 (500) = 200 тыс. рублей = х2*.

На долю 1-ого предприятия останется:

х1* = 700 – х4* - х3* - х2* = 200 тыс. рублей

х1** = 700 – х4** - х3** - х2*** = 300 тыс. рублей

х1*** = 700 – х4** - х3** - х2** = 200 тыс. рублей = х1*

Таким образом, одинаково оптимальными будут являться 3 варианта распределения капитальных вложений.

1-ый вариант

х1* = 200;

Z max = 294

х2* = 200;

х3* = 100;

х4* = 200

2-ой вариант

х1* = 200;

Z max = 294

х2** = 300;

х3* = 100;

х4** = 100

3-ий вариант

х1** = 300;

Z max = 294

х2* = 200;

х3* = 100;

х4** = 100

В качестве проверки правильности решения задачи можно использовать равенство:

Z max = f1(x1) + f2(x2) + f3(x3) + f4(x4)

1-ый вариант: 64 + 75 + 85 + 70 = 294 тыс. рублей

2-ой вариант: 64 + 98 + 85 + 47 = 294 тыс. рублей

3-ий вариант: 87 + 75 + 85 + 47 = 294 тыс. рублей

Следовательно, полученные решения верны.