动态规划.ppt

动态规划是用来解决多阶段决策过程最优化的一种数量方法。其特点在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。
需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。
多阶段决策问题
动态规划问题
多阶段决策问题的典型例子：
1 . 生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。
2. 机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。
动态规划问题举例
假定开始生产时完好的机器数量为s1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。
3. 航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。
不包含时间因素的静态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。
4 . 线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。
5 . 最短路问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。
1
2
3
4
5
6
A
B1
B2
C1
C2
C3
C4
D1
D2
D3
E1
E2
E3
F1
F2
G
5
3
1
3
6
8
7
6
3
6
8
5
3
3
8
4
2
2
2
1
3
3
3
5
2
5
6
6
4
3
动态规划问题的一些例子
1 最短路径问题
2 背包问题
例一、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？
A
B1
B2
C1
C2
C3
D
2
4
3
3
3
3
2
1
1
1
4
1 最短路径问题
A
B
C
D
解：整个计算过程分三个阶段，从最后一个阶段开始。
第一阶段（C →D）： C 有三条路线到终点D 。
A
B1
B2
C1
C2
C3
D
2
4
3
3
3
3
2
1
1
1
4
D
C1
C2
C3
显然有 f1 (C1 ) = 1 ； f1(C2 ) = 3 ； f1 (C3 ) = 4
d( B1,C1 ) + f1 (C1 ) 3+1
f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3
d( B1,C3 ) + f1 (C3 ) 1+4
4
= min 6 = 4
5
第二阶段（B →C）： B 到C 有六条路线。
A
B1
B2
C1
C2
C3
D
2
4
3
3
3
3
2
1
1
1
4
D
C1
C2
C3
B1
B2
(最短路线为B1→C1 →D)
d( B2,C1 ) + f1 (C1 ) 2+1
f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3
d( B2,C3 ) + f1 (C3 ) 1+4
3
=