Динамическое программирование
Динамическое программирование
Динамическое программирование применяется для решения задач , в которых процесс принятия решений может быть разбит на отдельные шаги - этапы ,
т. е. имеет место динамический процесс принятия решений , а с точки зрения математики имеет место дискретизация , которая может быть естественной ,например во времени , тогда
T=
t *n ,где
t- период дискретизации
n - целочисленные числа(0,1,2,…10)
Существует искусственная дискретизация , например разбиение ресурса на части.
При решении задачи динамического программирования существует 2 этапа:
1) прямой ход- определяется оптимальное значение критерия эффективности.
Рекомендуемые материалы
2) Обратный ход- определяется оптимальная стратегия.
Рассмотрим задачу распределения однородного ресурса:
Компанией планируется распределение ограниченных ресурсов S0=250*106 руб. между четырьмя предприятиями П1,П2,П3,П4. Известна прибыль каждого предприятия, которую они получают (исходные данные приведены в таблице).
| Выделенный Ресурс | Прибыль | |||
| f1(x) | f2(x) | f3(x) | f4(x) | |
| 0 | 0 | 0 | 0 | 0 |
| 50 | 27 | 25 | 20 | 30 |
| 100 | 38 | 40 | 35 | 45 |
| 150 | 50 | 41 | 52 | 50 |
| 200 | 55 | 56 | 60 | 55 |
| 250 | 60 | 63 | 68 | 68 |
1)Весь ресурс выделяется 1-му предприятию:
| Выделенный Ресурс | F1(x) |
| 0 | 0 |
| 50 | 27 |
| 100 | 38 |
| 150 | 50 |
| 200 | 55 |
| 250 | 60 |
2)Ресурс распределяется между двумя предприятиями:
| Выделенный Ресурс | Ресурс для П2 | F2(x) | X2 | |||||
| 0 | 50 | 100 | 150 | 200 | 250 | |||
| 0 | 0 | - | - | - | - | - | 0 | 0 |
| 50 | 27 | 25+0 | - | - | - | - | 27 | 0 |
| 100 | 38 | 25+27 | 40+0 | - | - | - | 52 | 50 |
| 150 | 50 | 25+38 | 40+27 | 41+0 | - | - | 67 | 100 |
| 200 | 55 | 25+50 | 40+38 | 41+27 | 56+0 | - | 78 | 100 |
| 250 | 60 | 25+55 | 40+50 | 41+38 | 56+27 | 63+0 | 90 | 100 |
3) Ресурс распределяется между тремя предприятиями:
| Выделенный Ресурс | Ресурс для П3 | F3(x) | X3 | |||||
| 0 | 50 | 100 | 150 | 200 | 250 | |||
| 0 | 0 | - | - | - | - | - | 0 | 0 |
| 50 | 27 | 20+0 | - | - | - | - | 27 | 0 |
| 100 | 52 | 20+27 | 35+0 | - | - | - | 52 | 0 |
| 150 | 67 | 20+52 | 35+27 | 52+0 | - | - | 72 | 50 |
| 200 | 78 | 20+67 | 35+52 | 52+27 | 60+0 | - | 87 | 50/100 |
| 250 | 90 | 20+78 | 35+67 | 52+52 | 60+27 | 68+0 | 104 | 150 |
4) Ресурс распределяется между четырьмя предприятиями:
| Выделенный Ресурс | Ресурс для П4 | F4(x) | X4 | |||||
| 0 | 50 | 100 | 150 | 200 | 250 | |||
| 0 | 0 | - | - | - | - | - | 0 | 0 |
| 50 | 27 | 30+0 | - | - | - | - | 27 | 50 |
| 100 | 52 | 30+27 | 45+0 | - | - | - | 57 | 50 |
| 150 | 72 | 30+52 | 45+27 | 50+0 | - | - | 82 | 50 |
| 200 | 87 | 30+72 | 45+52 | 50+27 | 55+0 | - | 102 | 50 |
| 250 | 104 | 30+87 | 45+72 | 50+52 | 55+27 | 68+0 | 117 | 50/100 |
Оптимальное значение прибыли для предприятия W=117*106 руб.
| Выделенный Ресурс | 1 | 2 | 3 | 4 | ||||
| f1(x) | X1 | f2(x) | X2 | f3(x) | X3 | f4(x) | X4 | |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 50 | 27 | 50 | 27 | 0 | 27 | 0 | 30 | 50 |
| 100 | 38 | 100 | 52 | 50 | 52 | 0 | 57 | 50 |
| 150 | 50 | 150 | 67 | 100 | 72 | 50 | 82 | 50 |
| 200 | 55 | 200 | 78 | 100 | 87 | 50/ 100 | 102 | 50 |
| 250 | 60 | 250 | 90 | 100 | 104 | 50 | 117 | 50/ 100 |
Х*1=(50,100,50,50)
Х*2=(50,50,100,50)
Х*3=(50,50,50,100)
Проверка: W=
1) W1=27+40+20+30=117
2) W2=27+25+35+30=117
3) W3=27+25+20+45=117
1. Применение метода динамического программирования предполагает , что прибыль для всех предприятий измеряется в одинаковых единицах.
2. Общая прибыль определяется: W=
3. Прибыль одного предприятия не зависит от прибыли других предприятий.
Алгоритм получения решения:
Прямой ход:
1) F1(x)=f1(x)
2) F2(x)=
(f2(x)+F1(x))
3) F3(x)= 
(f3(x)+F2(x))
4) F4(x)= 
(f4(x)+F3(x))
…………………………..
n)Fn(x)= 
(fn(x)+Fn-1(x))
Обратный ход:
Люди также интересуются этой лекцией: 7.Принципы композиции в романах Стендаля и Бальзака.
W=Fn(x)
X*n=arg max Fn(x)
n-1) x*n-1=arg max Fn-1(x)
n-2) x*n-2=arg max Fn-2(x)
………………
1) x*1=arg max F1(x)
