Задачи динамического программирования

Лизинговой компании необходимо сделать выбор объектов предполагаемых лизинговых сделок с определением оптимальных объемов финансирования на приобретение этих объектов в размерах кратных 100 млн. руб. Для инвестирования на эти цели компания располагает капиталом в объеме 700 млн. руб. В таблице 4 приводится среднегодовая прибыль компаний, ожидаемая от лизингополучателей при предоставлении им того или иного объекта на сумму от 0 до 700 млн. руб.

Таблица 4

Объем финансирования, млн. руб.

Среднегодовая прибыль при предоставлении объектов, млн. руб.

f1

f2

f3

xi

0

0

0

0

31

62

55

100

60

120

104

200

87

174

147

300

112

224

184

400

135

270

215

500

156

312

240

600

175

350

269

700

Под оптимальным объемом финансирования на приобретение объектов лизинга администрация компании понимает такое распределение суммы в 700 млн. руб. при котором среднегодовая прибыль от лизингополучателей всех этих объектов оказывается максимальной.

Используя метод динамического программирования, рассчитать такие объемы инвестиций по объектам лизинга, по которым ожидается максимальная по величине среднегодовая прибыль лизингополучателя.

Решение:

I этап. Условная оптимизация.

1-ый шаг. k = 3.

e2

u3

e3 = e2 - u3

f3(u3)

F*3(e3)

u3(e3)

100

0

100

0

 

 

 

100

0

55

55

100

200

0

200

0

 

 

 

100

100

55

 

 

 

200

0

104

104

200

300

0

300

0

 

 

 

100

200

55

 

 

 

200

100

104

 

 

 

300

0

147

147

300

400

0

400

0

 

 

 

100

300

55

 

 

 

200

200

104

 

 

 

300

100

147

 

 

 

400

0

184

184

400

500

0

500

0

 

 

 

100

400

55

 

 

 

200

300

104

 

 

 

300

200

147

 

 

 

400

100

184

 

 

 

500

0

215

215

500

600

0

600

0

 

 

 

100

500

55

 

 

 

200

400

104

 

 

 

300

300

147

 

 

 

400

200

184

 

 

 

500

100

215

 

 

 

600

0

240

240

600

700

0

700

0

 

 

 

100

600

55

 

 

 

200

500

104

 

 

 

300

400

147

 

 

 

400

300

184

 

 

 

500

200

215

 

 

 

600

100

240

 

 

 

700

0

269

269

700

 

 

 

2-ый шаг. k = 2.

 

e1

u2

e2 = e1 - u2

f2(u2)

F*2(e1)

F1(u2,e1)

F*2(e2)

u2(e2)

100

0

100

0

55

55

 

 

 

100

0

62

0

62

62

100

200

0

200

0

104

104

 

 

 

100

100

62

55

117

 

 

 

200

0

120

0

120

120

200

300

0

300

0

147

147

 

 

 

100

200

62

104

166

 

 

 

200

100

120

55

175

175

200

 

300

0

174

0

174

 

 

400

0

400

0

184

184

 

 

 

100

300

62

147

209

 

 

 

200

200

120

104

224

 

 

 

300

100

174

55

229

229

300

 

400

0

224

0

224

 

 

500

0

500

0

215

215

 

 

 

100

400

62

184

246

 

 

 

200

300

120

147

267

 

 

 

300

200

174

104

278

 

 

 

400

100

224

55

279

279

400

 

500

0

270

0

270

 

 

600

0

600

0

240

240

 

 

 

100

500

62

215

277

 

 

 

200

400

120

184

304

 

 

 

300

300

174

147

321

 

 

 

400

200

224

104

328

328

400

 

500

100

270

55

325

 

 

 

600

0

312

0

312

 

 

700

0

700

0

269

269

 

 

 

100

600

62

240

302

 

 

 

200

500

120

215

335

 

 

 

300

400

174

184

358

 

 

 

400

300

224

147

371

 

 

 

500

200

270

104

374

374

500

 

600

100

312

55

367

 

 

 

700

0

350

0

350

 

 

 

 

 

3-ый шаг. k = 1.

 

e0

u1

e1 = e0 - u1

f1(u1)

F*1(e0)

F0(u1,e0)

F*1(e1)

u1(e1)

100

0

100

0

62

62

62

0

 

100

0

31

0

31

 

 

200

0

200

0

120

120

120

0

 

100

100

31

62

93

 

 

 

200

0

60

0

60

 

 

300

0

300

0

175

175

175

0

 

100

200

31

120

151

 

 

 

200

100

60

62

122

 

 

 

300

0

87

0

87

 

 

400

0

400

0

229

229

229

0

 

100

300

31

175

206

 

 

 

200

200

60

120

180

 

 

 

300

100

87

62

149

 

 

 

400

0

112

0

112

 

 

500

0

500

0

279

279

279

0

 

100

400

31

229

260

 

 

 

200

300

60

175

235

 

 

 

300

200

87

120

207

 

 

 

400

100

112

62

174

 

 

 

500

0

135

0

135

 

 

600

0

600

0

328

328

328

0

 

100

500

31

279

310

 

 

 

200

400

60

229

289

 

 

 

300

300

87

175

262

 

 

 

400

200

112

120

232

 

 

 

500

100

135

62

197

 

 

 

600

0

156

0

156

 

 

700

0

700

0

374

374

374

0

 

100

600

31

328

359

 

 

 

200

500

60

279

339

 

 

 

300

400

87

229

316

 

 

 

400

300

112

175

287

 

 

 

500

200

135

120

255

 

 

 

600

100

156

62

218

 

 

 

700

0

175

0

175

 

 

Поясним построение таблиц и последовательность проведения расчетов.

Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).

В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.

Этап II. Безусловная оптимизация.

Из таблицы 3-го шага имеем F*3(e0 = 700) = 374 млн. руб. То есть максимальный доход всей системы при количестве средств e0 = 700 равен 374 млн. руб..

Из этой же таблицы получаем, что объекту №1 следует выделить u*1(e0 = 700) = 0.

При этом остаток средств составит:

e1 = e0 - u1

e1 = 700 - 0 = 700 млн. руб.

Из таблицы 2-го шага имеем F*2(e1 = 700) = 374 млн. руб.. То есть максимальный доход всей системы при количестве средств e1 = 700 равен 374 млн. руб..

Из этой же таблицы получаем, что объекту №2 следует выделить u*2(e1 = 700) = 500 млн. руб.

При этом остаток средств составит:

e2 = e1 - u2

e2 = 700 - 500 = 200 млн. руб.

Последнему объекту достается 200 млн. руб..

Итак, инвестиции в размере 700 млн. руб. необходимо распределить следующим образом:

1-му объекту выделить 0 млн. руб..

2-му объекту выделить 500 млн. руб..

3-му объекту выделить 200 млн. руб..

Что обеспечит максимальный доход, равный 374 млн. руб.

загрузка...