Автор работы: Пользователь скрыл имя, 06 Февраля 2013 в 11:15, контрольная работа
Динамическое программирование (ДП) представляет собой математический метод, заслуга создания и развития которого принадлежит, прежде всего, Беллману. Характерным для динамического программирования является подход к решению задачи по этапам, с каждым из которых ассоциирована одна управляемая переменная. Набор рекуррентных вычислительных процедур, связывающих различные этапы, обеспечивает получение допустимого оптимального решения задачи в целом при достижении последнего этапа.
ОПИСАНИЕ РЕШЕНИЯ ЗАДАЧИ
Инвестор выделяет средства в размере N условных единиц, которые должны быть распределены между m-предприятиями. Каждое i-е предприятие при инвестировании в него средств x приносит прибыль Zi(x) условных единиц, i=1..m. Нужно выбрать оптимальное распределение инвестиций между предприятиями, обеспечивающее максимальную прибыль.
N=5000 (кратно 1000)
m=3
Значения Zi(x), i=1..3 заданы в таблице
|
Выделяемые средства |
Предприятие | ||
№1 |
№2 |
№3 | |
Прирост Zi(Ui) | |||
Z1(Ui) |
Z2(Ui) |
Z3(Ui) | |
1 |
1 |
2 |
3 |
2 |
4 |
5 |
6 |
3 |
8 |
9 |
8 |
4 |
10 |
12 |
11 |
5 |
14 |
15 |
16 |
Шаг 3
F3(X2,U3)=max(Z3(X2,U3))
X2 |
U3 |
X3 |
F3 |
0 |
0 |
0 |
0 |
1 |
1 |
3 |
3 |
2 |
2 |
6 |
6 |
3 |
3 |
8 |
8 |
4 |
4 |
11 |
11 |
5 |
5 |
16 |
16 |
Шаг 2
F2(X1,U2)=max(Z2(X1,U2)+F3(X2)
X1 |
U2 |
X2 |
Z2 |
F3 |
Z2+F3 |
F2 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 1 |
1 0 |
0 2 |
3 0 |
3 2 |
3 |
2 |
0 1 2 |
2 1 0 |
0 2 5 |
6 3 0 |
6 5 5 |
6 |
3 |
0 1 2 3 |
3 2 1 0 |
0 2 5 9 |
8 6 3 0 |
8 8 8 9 |
9 |
4 |
0 1 2 3 4 |
4 3 2 1 0 |
0 2 5 9 12 |
11 8 6 3 0 |
11 10 11 12 12 |
12 |
5 |
0 1 2 3 4 5 |
5 4 3 2 1 0 |
0 2 5 9 12 15 |
16 11 8 6 3 0 |
16 13 13 15 15 15 |
16 |
Шаг 1
F1(X0,U1)=max(Z1(X0,U1)+F2(X1)
X0 |
U1 |
X1 |
Z1 |
F2 |
Z1+F2 |
F1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 1 |
1 0 |
0 1 |
3 0 |
3 1 |
3 |
2 |
0 1 2 |
2 1 0 |
0 1 4 |
6 3 0 |
6 4 4 |
6 |
3 |
0 1 2 3 |
3 2 1 0 |
0 1 4 8 |
9 6 3 0 |
9 7 7 8 |
9 |
4 |
0 1 2 3 4 |
4 3 2 1 0 |
0 1 4 8 10 |
12 9 6 3 0 |
12 10 10 11 10 |
12 |
5 |
0 1 2 3 4 5 |
5 4 3 2 1 0 |
0 1 4 8 10 14 |
16 12 9 6 3 0 |
16 13 13 14 13 14 |
16 |
Прибыль =16 ден. ед.
ОПИСАНИЕ ИНТЕРФЕЙСА