Автор работы: Пользователь скрыл имя, 13 Января 2012 в 15:48, лекция
Для того чтобы можно было решить задачу с помощью динамического программирования обязательно должны присутствовать следующие моменты:
1) должна быть возможность, позволяющая представить решаемую задачу в виде многошагового процесса, где решение, принимаемое на каждом шаге, заключается в выборе одной или несколько управляющих переменных, которые однозначно определяют переход в следующий этап;
1. Постановка задачи динамического программирования
2. Вычислительная схема метода динамического программирования (рекуррентные соотношения Беллмана)
3. Некоторые экономические задачи, решаемые методом динамического программирования
24
Таблица
– Прирост выпуска продукции,
млн. руб.
Инвестиции
Предприятие
1
Предприятие
2
Предприятие
3
Предприятие
4
20
8
10
12
11
40
16
20
21
23
60
25
28
27
30
80
36
40
38
37
100
44
48
50
51
120
62
62
63
63
25
Решение.
Разобьем
решение задачи на четыре
Для
предприятия № 1
для
всех остальных предприятий
26
1-й
этап. Инвестиции выделяем
f1(20) =8,
f1(40) = 16,
f1 (60) =25,
f1 (80) = 36
f1 (100) = 44
f1 (120) = 62
2-й этап. Инвестиции выделяют первому и второму предприятиям:
27
получим:
при х = 20
f2(20) = max [10 + 0; 0 + 8 ] = 10
при х = 40
f2(40) = max [20 + 0; 10 + 8, 0 + 16] = 20
при х = 60
f2(60) = max [28 + 0; 20 + 8, 10 + 16, 0 + 25 ] = 28
при х = 80
f2(80)
= max [40 + 0; 28 + 8, 20 + 16, 10 + 25, 0 + 36] = 40
28
при х = 100
f2(100) = max [48 + 0; 40 + 8, 28 + 16, 20 + 25, 10 + 36, 0 + 44] = 48
при х = 120
f2(120) = max [62 + 0; 48 + 8, 40 + 16, 28 + 25, 20 + 36, 10 + 44, 0 + 62] = 62
т.е. получим:
f2(20) =10,
f2(40) = 20,
f2 (60) =28,
f2 (80) = 40
f2 (100) = 48
f2
(120) = 62
29
3-й
этап. Инвестиции выделяют 1-3-
получим:
при х = 20
f3(20) = max [12+0; 0+10] = 12
при х = 40
f3(40) = max [21+0; 12+10; 0+20] = 22
при х = 60
f3(60) = max [27+0; 21+10; 12+20; 0+28] = 32
при х = 80
f3(80) = max [38+0; 27+10; 21+20; 12+28; 0+40] = 41
30
при х = 100
f3(100) = max [50+0; 38+10; 27+20; 21+28; 12+40; 0+48] = 52
при х = 120
f3(120) = max [63+0; 50+10; 38+20; 27+28; 21+40; 12+48; 0+62] = 63
т.е. получим:
f3(20) =12,
f3(40) = 22,
f3 (60) =32,
f3 (80) = 41
f3 (100) = 52
f3
(120) = 63
31
4-й этап. Инвестиции в объеме 120 млн. р. Распределяем между четырьмя предприятиями:
при х = 120
f4(120) = max [63+0; 51+12; 37+22; 30+32; 23+41; 11+52; 0+63] = 64
Получены условия управления от первого до четвертого этапа. Вернемся от четвертого этапа к первому. Максимальный прирост выпуска продукции в 64 млн. р. получен на 4-м этапе как 23+41 , т.е. 23 млн. р. соответствуют выделению 40 млн. р. четвертому предприятию (см. таблицу).
32
Согласно 3-му этапу, 41 млн. р. Получен как 21 + 20, т.е. 21 млн. р. соответствует выделению 40 млн. р. третьему предприятию.
Согласно 2-му этапу, 20 млн. р. получено при выделении 40 млн. р. второму предприятию.
Ответ.
Инвестиции в объеме 120 млн.
р. целесообразно выделить