动态规划.ppt

文档介绍：动态规划
(Dynamic Programming)
动态规划(DP)一般用于解决多阶段决策问
题,应用广泛,可用于解决最优路径问题、资
源分配问题、生产调度问题、库存问题、生产
过程最优控制问题等,是现代企业管理中一种
重要的决策方法。
本章基本要求:
理解多阶段决策问题
掌握动态规划的基本概念
掌握最优化原理的内容
掌握动态规划的逆序解法
动态规划问题求解:
1. 以丰富的想象力去建立模型
2. 以创造***求解
§ 动态规划的基本概念
一. 多阶段决策问题
例1 .
k=1 2 3 4
2
5
3
7
5
6
3
2
4
5
5
1
1
4
6
3
3
3
3
4
C1
C3
D1
A
B1
B3
B2
D2
E
C2
求从A到E的最短路径
2
5
3
7
5
6
3
2
4
5
5
1
1
4
6
3
3
3
3
4
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f5(E)=0
2
5
3
7
5
6
3
2
4
5
5
1
1
4
6
3
3
3
3
4
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f5(E)=0
f4(D1)=3
2
5
3
7
5
6
3
2
4
5
5
1
1
4
6
3
3
3
3
4
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f5(E)=0
f4(D1)=3
f4(D2)=2
2
5
3
7
5
6
3
2
4
5
5
1
1
4
6
3
3
3
3
4
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f5(E)=0
f4(D1)=3
f4(D2)=2
f3(C1)=4
2
5
3
7
5
6
3
2
4
5
5
1
1
4
6
3
3
3
3
4
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f5(E)=0
f4(D1)=3
f4(D2)=2
f3(C1)=4
f3(C2)=7
2
5
3
7
5
6
3
2
4
5
5
1
1
4
6
3
3
3
3
4
C1
C3
D1
A
B1
B3
B2
D2
E
C2
f5(E)=0
f4(D1)=3
f4(D2)=2
f3(C1)=4
f3(C2)=7
f3(C3)=6