1 1 4 s1 ，故 f1 ( s1 ) s1 4 64 1 1 由于 s1=c，∴ x1* c ， f1 (c ) c 4 4 64 2 1 1 由 s2 =s1－x1＊，∴ x2* s2 c , f 2 ( s2 ) c 3 3 2 16 1 1 由 s3 =s2－x2＊，∴ x3* s3 c ， f3 ( s3 ) c 4 4 1 1 1 因此最优解为： x1* c ， x2* c ， x3* c ， 4 2 4 1 4 最大值为： max z f1 (c) c 64
u3* (C3 ) D1
2)当 k=2 时：s2 的取值为 B1、B2、B3，从 B1 出发到 E 有三条路，分别是经 过 C1、C2、C3 到 E，则有：
d ( B1 , C1 ) f 3 (C1 ) 6 7 f 2 ( B1 ) d ( B1 , C2 ) f3 (C2 ) 4 5 9, d ( B , C ) f (C ) 5 5 1 3 3 3
回
于是得到从 A 到 E 的最短距离 17，为了找出最短路线，按计算的顺序逆推 去 ， 可 得 到 最 优 策 略 为 ：
p1,4 ( A) {u1* ( A) B1 , u2* ( B1 ) C2 , u3* (C2 ) D2 , u4* ( D2 ) E} ，最短路线是 A→B1→
例 1：最短路线问题 某工厂需要把一批货物从城市 A 运到城市 E，中间可经过 B1 、B2、B3、C1、 C2 、C3、D1 、D2 等城市，各城市之间的交通线和距离如下图所示，问应该选择一 条什么路线，使得从 A 到 E 的距离最短？ 6 B1 C1 3 8 4 5 D1 5 6 4A B2 9 8 C2 7 2 6 D3 3 6 7 1 8 3 C B3 3 7 下面利用动态规划的逆推归纳法，将例 1 从最后一个城市 E 逐步推算到第 一个城市 A，在此 f k ( sk ) 表示第 k 阶段从城市 sk 到城市 E 最短路。 1)当 k=4 时：要求 f 4 ( s4 ) ，由于第 4 阶段只有两个城市 D1、D2（即 s4 的取 值为 D1、D2） ，从 D1 到 E 只有一条路，故 f 4 ( D1 ) d ( D1 , E ) 4, u4* ( D1 ) E ，同 理 f 4 ( D2 ) d ( D2 , E ) 3, u4* ( D2 ) E 。 2)当 k=3 时：s3 的取值为 C1、C2、C3，从 C1 出发到 E 有两条路，一条是经 过 D1 到 E，另一条是经过 D2 到 E ，显然：
u2* ( B1 ) C2
同理
d ( B2 , C1 ) f3 (C1 ) 8 7 f 2 ( B2 ) d ( B2 , C2 ) f3 (C2 ) 7 5 11, d ( B , C ) f (C ) 6 5 2 3 3 3 d ( B3 , C1 ) f3 (C1 ) 7 7 f 2 ( B3 ) d ( B3 , C2 ) f 3 (C2 ) 8 5 12, d ( B3, C ) f (C ) 7 5 3 3 3
d (C2 , D1 ) f 4 ( D1 ) 6 4 f3 (C2 ) 5, d (C2 , D2 ) f 4 ( D2 ) 2 3 d (C3 , D1 ) f 4 ( D1 ) 1 4 f3 (C3 ) 5, d (C3 , D2 ) f 4 ( D2 ) 3 3 u3* (C2 ) D2
max z 4 x12 x2 2 2 x3 2 12
例 4：用顺推解法求解下面问题: 3 x1 2 x2 x3 9 x1 , x2 , x3 0 解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。 设状态变量为 s0，s1，s2，s3。并记 s3≤9； 令变量 x1，x2，x3 为决策变量； 最优值函数 f k(sk)表示为第 k 阶段末的结束状态为 sk， 从第 1 阶段到第 k 阶 段所得到的最大值。 设: 3x1=s1, s1+2x2=s2, s2+ x3=s3≤9 则有：x1=s1／3,0≤x2≤s2／2 , 0≤x3≤s3≤9 即状态转移方程为： s1=s2－2x2, s2=s3－x3 由顺推解法， f1 ( s1 ) max(4 x12 )
x1 s2
f 2 ( s3 ) max[ x1 x2 2 ] max [ x2 2 f1 (s2 )]
x1 , x2 0 x2 s3
max [ x2 2 ( s3 x2 )]
0 x2 s3
4 3 s3 27

最优解 x2*
2 s3 。 3
f3 ( s4 ) max[ x1 x2 2 x3 ] max [ x3 f 2 (s3 )]
由
dh2 14 16 8 x2 s2 0 ,得 x2 s2 (它不在决策集内) 7 dx2 9 9
s 4 2 1 s2 , h2 ( 2 ) s2 2 9 2 4 4 2 ∴最大值点为 x2=0。故得到 f 2 ( s2 ) s2 及最优解 x2* 0 。 9
则最大值在端点上，∵ h2 (0)
由
dh3 44 8 2 x3 s3 0 ,得 x3 s3 11 dx3 9 9
dh3 2 44 0 ，故该点为极小值点。 dx32 9
4 2 s3 12, h2 ( s3 ) 2s32 12 9
又
而 h3 (0)
∴最大值点为 x3=s3。故得到 f3 ( s3 ) 2 s3 2 12 及最优解 x3* s3 。 由于 s3 不知道，故须在对 s3 求一次极值，即
C2→D2→E。
max z x1 x2 2 x3
例 3：逆推解法求解下面问题: x1 x2 x3 c
x1 , x2 , x3 0
解: 按问题的变量个数划分阶段,把它看作一个三阶段决策问题。设状态变 量为 s1，s2，s3，s4。并记 s1＝c；令变量 x1，x2，x3 为决策变量；各阶段指标按 乘积方式结合。 即令: v1 ( s1 , x1 ) x1 , v2 ( s2 , x2 ) x2 2 , v3 ( s3 , x3 ) x3 令最优值函数 f k(sk)表示为第 k 阶段的初始状态为 sk 时， 从第 k 阶段到第 3 阶段所得到的最大值。 设: s3= x3, s3+ x2=s2, s2+ x1=s1=c 则有：x3=s3, 0≤x2≤s2, 0≤x1≤s1=c 即状态转移方程为： s3=s2－x2, s2 =s1－x1 由逆推解法，
x1 s1 3
4 2 s1 , 即最优解 x1＊=s1／3, 9
f 2 ( s2 ) max[4 x12 x2 2 ] max [ x2 2 f1 ( s1 )]
x1 , x2 0 x2 s2 2
4 max [ x2 2 ( s2 2 x2 ) 2 ] max h2 ( s2 , x2 ) s s 9 0 x2 2 0 x2 2 2 2
E
d (C1 , D1 ) f 4 ( D1 ) 3 4 f 3 (C1 ) min min 7, d ( C , D ) f ( D ) 5 3 1 2 4 2
u3* (C1 ) D1
即从 C1 出发到 E 的最短路为 7，相应决策为 u3* (C1 ) D1 ，最短路线是 C1 →D1→E。 同理
f3 ( s3 ) max[4 x12 x2 2 2 x32 12] max [2 x3 2 12 f 2 ( s2 )]
x1 , x2 , x3 0 x3 s3
4 max [2 x32 12 ( s3 x3 )2 ] max h3 ( s3 , x3 ) 0 x3 s3 0 x3 s3 9
x1 , x2 , x3 0 x3 s4
max [ x3
0 x3 s4
4 1 4 (s4 x3 )3 ] s4 27 64
最优解 x3*
1 s4 4
1 1 由于 s4=c，∴ x3* c ， f3 (c) c 4 4 64 2 1 1 由 s3=s4－x3＊，∴ x2* s3 c , f 2 ( s2 ) c 3 2 16 1 1 由 s2=s3－x2＊，∴ x1* s2 c ， f3 ( s3 ) c 4 4 1 1 1 因此最优解为： x1* c ， x2* c ， x2* c ， 4 2 4 1 最大值为： max z c 4 64
0 x2 s2 0 x2 s2
由
dh2 2 2 x2 s2 3 x2 2 0 ,得 x2 s2 和 x2 0 （舍去） 3 dx2
d 2 h2 d 2 h2 2 ，而 2 s 6 x | 2 s2 0 ，故 x2 s2 为极大值点。 2 2 2 2 x 2s 3 dx2 dx2 2 3 2
u2* ( B2 ) C3
u2* ( B3 ) C3
2)当 k=1 时：s1 的只有一个取值为 A. 从 A 出发到 E 有三条路，分别是经 过 B1、B2、B3 到 E，则有：
d ( A, B1 ) f 2 ( B1 ) 8 9 f1 ( A) min d ( A, B2 ) f 2 ( B2 ) min 9 11 17, d ( A, B ) f ( B ) 6 12 3 2 3 u1* ( A) B1
4 2 2 s2 即最优解 x2* s2 。 27 3
0 x1 s1
又
所以 f 2 ( s2 )