Динамическое программирование. Пример решения задачи

Найти оптимальное распределение средств между 6 предприятиями при условии, что прибыль f(x), полученная от каждого предприятия, является функцией от вложенных в него средств х. Выписать все оптимальные управления.
N f 1(x ) f 2 (x) f 3 (x) f 4 (x) f 5 (x)
0 0 0 0 0 0
1 6 5 3 4 2
2 8 12 13 10 11
3 10 15 16 15 14
4 14 20 21 22 18
5 18 22 26 25 21
6 22 26 29 31 30
Решение получаем через сервис распределение средств между предприятиями.
I этап. Условная оптимизация.
Первый шаг. k = 5.
e4 u5 e5 = e4 - u5 f5(u5) F*5(e5) u5(e5)
1 0 1 0
1 0 2 2 1
2 0 2 0
1 1 2
2 0 11 11 2
3 0 3 0
1 2 2
2 1 11
3 0 14 14 3
4 0 4 0
1 3 2
2 2 11
3 1 14
4 0 18 18 4
5 0 5 0
1 4 2
2 3 11
3 2 14
4 1 18
5 0 21 21 5
6 0 6 0
1 5 2
2 4 11
3 3 14
4 2 18
5 1 21
6 0 30 30 6

Второй шаг. k = 4.
e3 u4 e4 = e3 - u4 f4(u4) F*4(e3) F3(u4,e3) F*4(e4) u4(e4)
1 0 1 0 2 2
1 0 4 0 4 4 1
2 0 2 0 11 11 11 0
1 1 4 2 6
2 0 10 0 10
3 0 3 0 14 14
1 2 4 11 15 15 1
2 1 10 2 12
3 0 15 0 15
4 0 4 0 18 18
1 3 4 14 18
2 2 10 11 21
3 1 15 2 17
4 0 22 0 22 22 4
5 0 5 0 21 21
1 4 4 18 22
2 3 10 14 24
3 2 15 11 26 26 3
4 1 22 2 24
5 0 25 0 25
6 0 6 0 30 30
1 5 4 21 25
2 4 10 18 28
3 3 15 14 29
4 2 22 11 33 33 4
5 1 25 2 27
6 0 31 0 31

Третий шаг. k = 3.
e2 u3 e3 = e2 - u3 f3(u3) F*3(e2) F2(u3,e2) F*3(e3) u3(e3)
1 0 1 0 4 4 4 0
1 0 3 0 3
2 0 2 0 11 11
1 1 3 4 7
2 0 13 0 13 13 2
3 0 3 0 15 15
1 2 3 11 14
2 1 13 4 17 17 2
3 0 16 0 16
4 0 4 0 22 22
1 3 3 15 18
2 2 13 11 24 24 2
3 1 16 4 20
4 0 21 0 21
5 0 5 0 26 26
1 4 3 22 25
2 3 13 15 28 28 2
3 2 16 11 27
4 1 21 4 25
5 0 26 0 26
6 0 6 0 33 33
1 5 3 26 29
2 4 13 22 35 35 2
3 3 16 15 31
4 2 21 11 32
5 1 26 4 30
6 0 29 0 29

Четвертый шаг. k = 2.
e1 u2 e2 = e1 - u2 f2(u2) F*2(e1) F1(u2,e1) F*2(e2) u2(e2)
1 0 1 0 4 4
1 0 5 0 5 5 1
2 0 2 0 13 13 13 0
1 1 5 4 9
2 0 12 0 12
3 0 3 0 17 17
1 2 5 13 18 18 1
2 1 12 4 16
3 0 15 0 15
4 0 4 0 24 24
1 3 5 17 22
2 2 12 13 25 25 2
3 1 15 4 19
4 0 20 0 20
5 0 5 0 28 28
1 4 5 24 29 29 1
2 3 12 17 29
3 2 15 13 28
4 1 20 4 24
5 0 22 0 22
6 0 6 0 35 35
1 5 5 28 33
2 4 12 24 36 36 2
3 3 15 17 32
4 2 20 13 33
5 1 22 4 26
6 0 26 0 26

Пятый шаг. k = 1.
e0 u1 e1 = e0 - u1 f1(u1) F*1(e0) F0(u1,e0) F*1(e1) u1(e1)
1 0 1 0 5 5
1 0 6 0 6 6 1
2 0 2 0 13 13 13 0
1 1 6 5 11
2 0 8 0 8
3 0 3 0 18 18
1 2 6 13 19 19 1
2 1 8 5 13
3 0 10 0 10
4 0 4 0 25 25 25 0
1 3 6 18 24
2 2 8 13 21
3 1 10 5 15
4 0 14 0 14
5 0 5 0 29 29
1 4 6 25 31 31 1
2 3 8 18 26
3 2 10 13 23
4 1 14 5 19
5 0 18 0 18
6 0 6 0 36 36 36 0
1 5 6 29 35
2 4 8 25 33
3 3 10 18 28
4 2 14 13 27
5 1 18 5 23
6 0 22 0 22

 Поясним построение таблиц и последовательность проведения расчетов.
 Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 5-го шага столбцы 5 и 6 отсутствуют).
 В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
Этап II. Безусловная оптимизация.
Управлением в многошаговом процессе называется совокупность решений (управляющих переменных) uk = (uk1, ..., ukr), принимаемых на каждом шаге k и переводящих систему из состояния εk-1 = (εk-11, …, εk-1s) в состояние εk = (εk1, …, εks).
Из таблицы 1-го шага имеем F*5(e0 = 6) = 36. То есть максимальный доход всей системы при количестве средств e0 = 6 равен 36
 Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0 = 6) = 0.
 При этом остаток средств составит:
 e1 = e0 - u1
 e1 = 6 - 0 = 6
 Из таблицы 2-го шага имеем F*4(e1 = 6) = 36. То есть максимальный доход всей системы при количестве средств e1 = 6 равен 36.
 Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1 = 6) = 2.
 При этом остаток средств составит:
 e2 = e1 - u2
 e2 = 6 - 2 = 4
 Из таблицы 3-го шага имеем F*3(e2 = 4) = 24. То есть максимальный доход всей системы при количестве средств e2= 4 равен 24
 Из этой же таблицы получаем, что 3-му предприятию следует выделить u*3(e2 = 4) = 2.
 При этом остаток средств составит:
 e3 = e2 - u3
 e3 = 4 - 2 = 2
 Из таблицы 4-го шага имеем F*2(e3 = 2) = 11. То есть максимальный доход всей системы при количестве средств e3 = 2 равен 11.
 Из этой же таблицы получаем, что 4-му предприятию следует выделить u*4(e3 = 2) = 0.
 При этом остаток средств составит:
 e4 = e3 - u4
 e4 = 2 - 0 = 2
 Последнему предприятию достается 2.
 Итак, инвестиции в размере 6 необходимо распределить следующим образом:
 1-му предприятию выделить 0;
 2-му предприятию выделить 2;
 3-му предприятию выделить 2;
 4-му предприятию выделить 0;
 5-му предприятию выделить 2;
 Что обеспечит максимальный доход, равный 36.
загрузка...