Принцип оптимальности Беллмана

Инвестор выделяет средства в размере т.д. ед, которые должны быть распределены между тремя предприятиями.
Требуется, используя принцип оптимальности Беллмана, составить план распределения средств между предприятиями, обеспечивающий наибольшую общую прибыль, если каждое предприятие при инвестировании в него средств Х т.д.ед. приносит прибыль U(Х) по следующим данным:

Инвестирование средств т/р Прибыль т/р
Х U1(Х) U2(Х) U3(Х)
1 6,58 5,14 6,1
2 12,3 4,26 8,5
3 14,5 10,52 11,52
4 20,9 18,54 18,26
5 26,86 25,62 17,4

Решение находим с помощью калькулятора.
I этап. Условная оптимизация.
 Первый шаг. k = 3.

e2 u3 e3 = e2 - u3 f3(u3) F*3(e3) u3(e3)
1 0 1 0 0 0
1 0 6.1 6.1 1
2 0 2 0 0 0
1 1 6.1 0 0
2 0 8.5 8.5 2
3 0 3 0 0 0
1 2 6.1 0 0
2 1 8.5 0 0
3 0 11.52 11.52 3
4 0 4 0 0 0
1 3 6.1 0 0
2 2 8.5 0 0
3 1 11.52 0 0
4 0 18.26 18.26 4
5 0 5 0 0 0
1 4 6.1 0 0
2 3 8.5 0 0
3 2 11.52 0 0
4 1 18.26 18.26 4
5 0 17.4 0 0


 Второй шаг. k = 2.

e1 u2 e2=e1-u2 f2(u2) F*2(e1) F1(u2,e1) F*2(e2) u2(e2)
1 0 1 0 6.1 6.1 6.1 0
1 0 5.14 0 5.14 0 0
2 0 2 0 8.5 8.5 0 0
1 1 5.14 6.1 11.24 11.24 1
2 0 4.26 0 4.26 0 0
3 0 3 0 11.52 11.52 0 0
1 2 5.14 8.5 13.64 13.64 1
2 1 4.26 6.1 10.36 0 0
3 0 10.52 0 10.52 0 0
4 0 4 0 18.26 18.26 0 0
1 3 5.14 11.52 16.66 0 0
2 2 4.26 8.5 12.76 0 0
3 1 10.52 6.1 16.62 0 0
4 0 18.54 0 18.54 18.54 4
5 0 5 0 18.26 18.26 0 0
1 4 5.14 18.26 23.4 0 0
2 3 4.26 11.52 15.78 0 0
3 2 10.52 8.5 19.02 0 0
4 1 18.54 6.1 24.64 0 0
5 0 25.62 0 25.62 25.62 5


 Третий шаг. k = 1.

e0 u1 e1=e0-u1 f1(u1) F*1(e0) F0(u1,e0) F*1(e1) u1(e1)
1 0 1 0 6.1 6.1 0 0
1 0 6.58 0 6.58 6.58 1
2 0 2 0 11.24 11.24 0 0
1 1 6.58 6.1 12.68 12.68 1
2 0 12.3 0 12.3 0 0
3 0 3 0 13.64 13.64 0 0
1 2 6.58 11.24 17.82 0 0
2 1 12.3 6.1 18.4 18.4 2
3 0 14.5 0 14.5 0 0
4 0 4 0 18.54 18.54 0 0
1 3 6.58 13.64 20.22 0 0
2 2 12.3 11.24 23.54 23.54 2
3 1 14.5 6.1 20.6 0 0
4 0 20.9 0 20.9 0 0
5 0 5 0 25.62 25.62 0 0
1 4 6.58 18.54 25.12 0 0
2 3 12.3 13.64 25.94 0 0
3 2 14.5 11.24 25.74 0 0
4 1 20.9 6.1 27 27 4
5 0 26.86 0 26.86 0 0

 Поясним построение таблиц и последовательность проведения расчетов.
 Столбцы 1, 2 и 3 для всех трех таблиц одинаковы, поэтому их можно было бы сделать общими. Столбец 4 заполняется на основе исходных данных о функциях дохода, значения в столбце 5 берутся из столбца 7 предыдущей таблицы, столбец 6 заполняется суммой значений столбцов 4 и 5 (в таблице 3-го шага столбцы 5 и 6 отсутствуют).
 В столбце 7 записывается максимальное значение предыдущего столбца для фиксированного начального состояния, и в 8 столбце записывается управление из 2 столбца, на котором достигается максимум в 7.
 Этап II. Безусловная оптимизация.
 Из таблицы 1-го шага имеем F*3(e0 = 5) = 27. То есть максимальный доход всей системы при количестве средств e0 = 5 равен 27.
 Из этой же таблицы получаем, что 1-му предприятию следует выделить u*1(e0 = 5) = 4
 При этом остаток средств составит:
 e1 = e0 - u1
 e1 = 5 - 4 = 1
 Из таблицы 2-го шага имеем F*2(e1 = 1) = 6.1. То есть максимальный доход всей системы при количестве средств e1 = 1 равен 6.1.
 Из этой же таблицы получаем, что 2-му предприятию следует выделить u*2(e1 = 1) = 0.
 При этом остаток средств составит:
 e2 = e1 - u2
 e2 = 1 - 0 = 1
 Последнему предприятию достается 1.
 Итак, инвестиции в размере 5 необходимо распределить следующим образом:
 1-му предприятию выделить 4,
 2-му предприятию выделить 0,
 3-му предприятию выделить 1.
 Что обеспечит максимальный доход, равный 27.

загрузка...