Так же решение контрольных, написание курсовых и рефератов по другим предметам.

logo

Решение контрольных по математике!!!

Связаться с нами

E-mail: matica@narod.ru

ICQ 229036787, ICQ 320619

 

Home

Динамическое программирование 1

PDF Печать E-mail

Динамическое программирование

Для увеличения объемов выпуска пользующейся повышенным спросом продукции, изготавливаемой тремя предприятиями, выделены капитальные вложения в объеме 700 млн. руб. Использование i-тым предприятием xi млн. руб. из указанных средств обеспечивает прирост выпуска продукции, определяемый значением нелинейной функции fi(xi).

Найти распределение капитальных вложений между предприятиями, обеспечивающее максимальное увеличение выпус6ка продукции.

Исходные данные приведены в таблицах 1 и 2.

Таблица 1

Исходные данные

Объем

Кап. вложений xi, млн. руб.

Прирост выпуска продукции fi(xi), млн. руб.

Предприятие 1

Предприятие 2

Предприятие 3

0

0

0

0

100

20

50

40

200

50

80

90

300

90

90

110

400

110

150

120

500

170

150

180

600

180

210

220

700

210

220

240

В задаче необходимо:

1. Составить рекуррентное соотношение Беллмана в виде функциональных уравнений.

2. Используя рекуррентные соотношения и исходные данные определить сначала условно оптимальные, а затем оптимальные распределения капиталовложений между предприятиями.

Разобьем решение задачи на шаги. Число шагов положим равным числу предприятий, в которые осуществляется инвестирование.

Введем переменную - количество средств, имеющихся в наличии перед данным шагом и характеризующих состояние системы на каждом шаге.

Управление на -м шаге - - количество средств, инвестируемых в -е предприятие.

Выигрыш на -м шаге – это прибыль, которую приносит -е предприятие при инвестировании в него средств .

Если через выигрыш в целом обозначить общую прибыль , то

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

Если в наличии имеются средства в размере тыс. ден. ед. и в -е предприятие инвестируется х тыс. ден. ед., то для дальнейшего инвестирования остается Тыс. ден. ед.

Таким образом, если на -м шаге система находилась в состоянии и выбрано управление х, то на +1-м шаге система будет находится в состоянии , и следовательно, функция перехода в новое состояние имеет вид

.

На последнем =3 шаге, т. е. перед инвестированием средств в последнее предприятие, оптимальное управление соответствует количеству средств, имеющихся в наличии. Это означает, что сколько средств осталось, столько и надо вложить в последнее предприятие, а выигрыш будет равен доходу, приносимому последним предприятием.

.

Согласно принципу оптимальности Беллмана, управление на каждом шаге надо выбирать так, чтобы оптимальной была сумма выигрышей на всех оставшихся до конца процесса шагах, включая выигрыш на данном шаге. Поэтому, если перед -м шагом у инвестора остались средства в размере Тыс. ден. ед., то вкладывая х тыс. ден. ед. в -е предприятие, оно принесет доход , а оставшиеся Тыс. ден. едд., вложенные в остальные предприятия с +1-го до последнего, составят выигрыш . Так как оптимальным является управление х, при котором сумма и должна быть наибольшей, то основное функциональное уравнение примет вид

.

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

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

S2

Х3

S3 = s2 - з3

φ3(x3)

W*3(s3)

X3(s3)

100

0

100

0

100

0

40

40

100

200

0

200

0

100

100

40

200

0

90

90

200

300

0

300

0

100

200

40

200

100

90

300

0

110

110

300

400

0

400

0

100

300

40

200

200

90

300

100

110

400

0

120

120

400

500

0

500

0

100

400

40

200

300

90

300

200

110

400

100

120

500

0

180

180

500

600

0

600

0

100

500

40

200

400

90

300

300

110

400

200

120

500

100

180

600

0

220

220

600

700

0

700

0

100

600

40

200

500

90

300

400

110

400

300

120

500

200

180

600

100

220

700

0

240

240

700

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

S1

X2

S2 = s1 - x2

φ 2(x2)

W*2(s1)

W1(x2,s1)

W*2(s2)

X2(s2)

100

0

100

0

40

40

100

0

50

0

50

50

100

200

0

200

0

90

90

90

0

100

100

50

40

90

200

0

80

0

80

300

0

300

0

110

110

100

200

50

90

140

140

100

200

100

80

40

120

300

0

90

0

90

400

0

400

0

120

120

100

300

50

110

160

200

200

80

90

170

170

200

300

100

90

40

130

400

0

150

0

150

500

0

500

0

180

180

100

400

50

120

170

200

300

80

110

190

190

200

300

200

90

90

180

400

100

150

40

190

500

0

150

0

150

600

0

600

0

220

220

100

500

50

180

230

200

400

80

120

200

300

300

90

110

200

400

200

150

90

240

240

400

500

100

150

40

190

600

0

210

0

210

700

0

700

0

240

240

100

600

50

220

270

270

100

200

500

80

180

260

300

400

90

120

210

400

300

150

110

260

500

200

150

90

240

600

100

210

40

250

700

0

220

0

220

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

S0

X1

S1 = s0 - x1

φ 1(x1)

W*1(s0)

W0(x1,s0)

W*1(e1)

X1(s1)

100

0

100

0

50

50

50

0

100

0

20

0

20

200

0

200

0

90

90

90

0

100

100

20

50

70

200

0

50

0

50

300

0

300

0

140

140

140

0

100

200

20

90

110

200

100

50

50

100

300

0

90

0

90

400

0

400

0

170

170

170

0

100

300

20

140

160

200

200

50

90

140

300

100

90

50

140

400

0

110

0

110

500

0

500

0

190

190

190

0

100

400

20

170

190

200

300

50

140

190

300

200

90

90

180

400

100

110

50

160

500

0

170

0

170

600

0

600

0

240

240

240

0

100

500

20

190

210

200

400

50

170

220

300

300

90

140

230

400

200

110

90

200

500

100

170

50

220

600

0

180

0

180

700

0

700

0

270

270

270

0

100

600

20

240

260

200

500

50

190

240

300

400

90

170

260

400

300

110

140

250

500

200

170

90

260

600

100

180

50

230

700

0

210

0

210

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

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

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

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

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

Из этой же таблицы получаем, что 1-му предприятию следует выделить x*1(s0 = 700) = 0

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

S1 = s0 - x1

S1 = 700 - 0 = 700

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

Из этой же таблицы получаем, что 2-му предприятию следует выделить x*2(s1 = 700) = 100

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

S2 = s1 - x2

S2 = 700 - 100 = 600

Последнему предприятию достается 600

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

1-му предприятию выделить 0

2-му предприятию выделить 100

3-му предприятию выделить 600

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

 
Яндекс.Метрика
Наверх