第十章动态规划.ppt

文档介绍：第十章动态规划
如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。
动态规划中能
处理的状态转移
方程的形式。
状态具有无后效性的多阶段决策过程的状态转移方程如下
无后效性(马尔可夫性)
如果某阶段应用
例1、从A 地到D 地要铺设一条煤气管道,其中需经过两级中间站，两点之间的连线上的数字表示距离，如图所示。问应该选择什么路线，使总距离最短？
A
B1
B2
C1
C2
C3
D
2
4
3
3
3
3
2
1
1
1
4
1、最短路径问题
16
解：整个计算过程分三个阶段，从最后一个阶段开始。
第一阶段（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
17
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)
18
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
= min 6 = 3
5
A
B1
B2
C1
C2
C3
D
2
4
3
3
3
3
2
1
1
1
4
D
C1
C2
C3
B1
B2
(最短路线为B2→C1 →D)
19
第三阶段（ A → B ）： A 到B 有二条路线。
f3(A)1 = d(A, B1 )＋ f2 ( B1 ) ＝2＋4＝6
f3 (A)2 = d(A, B2 )＋ f2 ( B2 ) ＝4＋3＝7
∴ f3 (A) = min = min｛6,7｝=6
d(A, B1 )＋ f2 ( B1 )
d(A, B2 )＋ f2 ( B2 )
(最短路线为A→B1→C1 →D)
A
B1
B2
C1
C2
C3
D
2
4
3
3
3
3
2
1
1
1
4
D
C1
C2
C3
B1
B2
A
20
A
B1
B2
C1
C2
C3
D
2
4
3
3
3
3
2
1
1
1
4
D
C1
C2
C3
B1
B2
A
最短路线为 A→B1→C1 →D

路长为 6
21
四、动态规划问题典型应用
现有数量为a（万元）的资金，计划分配给n 个工厂,用于扩大再生产。
假设：xi 为分配给第i 个工厂的资金数量（万元） ；gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。
问题是如何确定各工厂的资金数，使得总的利润为最大。
据此，有下式：
2、投资分配问题