Распределить Т=100 тыс ден ед по четырем предприятиям с целью получения максимальной суммарной прибыли

Для решения используем принцип оптимальности Беллмана.
Метод динамического программирования состоит в том, что оптимальное управление строится постепенно. На каждом шаге оптимизируется управление только этого шага. Каково бы ни было начальное состояние системы перед очередным шагом, управление на этом этапе выбирается так, чтобы выигрыш на данном шаге плюс оптимальный выигрыш на всех последующих шагах был максимальным.
Задача решается по алгоритму за два этапа:
1 этап (прямая прогонка): условная оптимизация, т.е. определяются условные оптимальные управления и выигрыши для всех шагов.
2 этап (обратная прогонка): определяется безусловное оптимальное управление, приводящее к оптимальному решению.
Для данной задачи для четырех предприятий алгоритм решения будет такой:
Согласно этому алгоритму, проводим расчеты.
I этап. Проводим условную оптимизацию пошагово .
1-й шаг. k=4.
Первым делом все имеющиеся средства в размере 100 тыс. ден. ед. отдаются только на 4-е предприятие. Занесем в таблицу размер возможных вложений, т.е. 0, 20, 40, 60, 80, или 100 тыс. ден. ед. и получаемую при этом прибыль (задана по условию):
Х
g4
20
25
40
53
60
66
80
70
100
84
Получим:
Таблица 2.1.
C4
X4
F4(C4)
X4*
0 20 40 60 80 100
0 0 - - - - - 0 0
20 - 25 - - - - 25 20
40 - - 3968751461790053 - - - 53 40
60 - - - 66 - - 66 60
80 - - - - 70 - 70 80
100 - - - - - 84 84 100
2-й шаг . k =3. Теперь будем инвестировать средства в два предприятия (3-е и 4-е). Рекуррентное соотношение Беллмана будет иметь вид:
F3(C3) = max {g3C3+F3(C3-x3)}.
Запишем все возможные пары распределения средств: если 3-му предприятию отдается 20 ден. ед. то на 4-е ничего не выдается, и наоборот. Аналогично 40 ден. ед. делятся тремя способами: (0;40), (20;20); (40;20), аналогично 60 ден. ед. делятся четырьмя способами (0;60), (20;40), (40;20), (60;0). И так далее для всех средств.
Выписываем прибыль от инвестиций в 3-е предприятие (дано в исходной таблице), а прибыль от инвестиций в 4-е предприятие выписываем из таблицы для предыдущего шага:
Х
g3 F4
20
20 25
40
36 53
60
47 66
80
72 70
100
80 84
Получим:
Таблица 2.2.
C3
X3
F3(C3)
X3*
0 20 40 60 80 100
0 0+0 - - - - - 0 0
20 0+25 20+0 - - - - 25 0
40 0+53 20+25 36+0 - - - 53 0
60 0+66 512445895350020+53 36+25 47+0 - - 73 20
80 0+70 20+66 36+53 47+25 72+0 - 89 40
100 0+84 20+70 36+66 47+53 72+25 80+0 102 40
3-й шаг. k =2. Добавляется 2-е предприятие. Тогда рекуррентное уравнение Беллмана приобретет вид: F2(C2) = max {g2C2+F2(C2-x2)}
Выписываем прибыль от инвестиций во 2-е предприятие (дано в исходной таблице), а прибыль F3 от предыдущих инвестиций выписываем из таблицы для предыдущего шага:
Х
g2 F3
20
14 25
40
32 53
60
52 73
80
61 89
100
79 102
Получим:
Таблица 2.3.
C2
X2
F2(C2)
X2*
0 20 40 60 80 100
0 0+0 - - - - - 0 0
20 0+25 14+0 - - - - 25 0
40 0+53 14+25 32+0 - - - 53 0
60 5308601553380+73 14+53 32+25 52+0 - - 73 0
80 0+89 14+73 32+53 52+25 61+0 - 89 0
100 0+102 14+89 32+73 52+53 61+25 79+0 105 40
4-й шаг