Динамическое программирование 01
Динамическое программирование
Для увеличения объемов выпуска пользующейся повышенным спросом продукции, изготавливаемой тремя предприятиями, выделены капитальные вложения в объеме 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
| < Предыдущая | Следующая > |
|---|
