若已经做了k-1次决策,1≤k-1<n,设x1,x2,…,xk-1的最优决 策值是r1,r2,…,rk-1,所产生的状态依次为S1,S2,…,Sk-1 设X={(rk,1,rk,2,…,rk,k是x可能的决策值的集合,S,是在 选择决策值r,j之后所产生的状态,1≤永k≤Dk Tk,是相应于状态Sk,的最优决策序列。 则,相应于Sk1的最优决策序列是 就一个特定的r而言 相应于S的最优决策序列为r1,…,rk-1,rk,Tk 2021/2/20
2021/2/20 11 若已经做了k-1次决策，1≤k-1＜n，设x1,x2,…,xk-1的最优决 策值是r1,r2,…,rk-1，所产生的状态依次为S1,S2,…,Sk-1。 设Xk={rk,1,rk,2,…,rk,pk}是xk可能的决策值的集合，Sk,jk是在 选择决策值rk,jk之后所产生的状态, 1≤jk≤pk。 Γk,jk是相应于状态Sk,jk的最优决策序列。 则，相应于Sk-1的最优决策序列是 相应于S0的最优决策序列为r1,…,rk-1，rk, Γk k j k j k k j pk OPT r r k k k = { } , , 1 就一个特定的rk,jk而言
k,2 K 2 n soS1S2……Sk1 k,jk k, pk 2021/2/20
2021/2/20 12 s0 s1 s2……. sk-1 rk,1 rk,2 . . . rk,pk sn Γk,jk Γk,1 Γk,2 Γkpk
5.递推策略 1)向前处理法 列出根据ⅹ+1xn的最优决策序列求取x决策值的关系式 从最后一个阶段,逐步向前递推求出各阶段的决策值。决 策序列X1,X2,,Xn就是问题的最优解 1.1 Xn 向前递推 -1pn-1 2021/2/20
2021/2/20 13 5. 递推策略 1）向前处理法 列出根据xi+1,…,xn的最优决策序列求取xi决策值的关系式。 从最后一个阶段，逐步向前递推求出各阶段的决策值。决 策序列x1 ,x2 ,…,xn就是问题的最优解。 xn-1,1 … xn-1,pn-1 xn 向前递推
例43利用向前处理法求解k段图问题 设V2,∈V2,12sp2M2=p2 I,是由V2到的最短路径,则s到t的最短路径是 {sI|v2∈V2,12sp2}中最短的那条路径。 若s, ,v1…,t,t是s到t的一条最短路径,是其中的 个中间点,则s,v2,v3,…,V和v1,Wk1,t分别是由s到和到t 的最短路径(最优性原理) 从中的结点到t的最短路径将是 mini v >∈E ∈v+1,1Sj+1Sp++ 14
2021/2/20 14 例4.3 利用向前处理法求解k段图问题 设 ∈V2，1≤j2≤p2 ,|V2 |=p2 ; 是由 到t的最短路径，则s到t的最短路径是 {s | ∈V2 ,1≤j2≤p2 }中最短的那条路径。 若s,v2 ,v3 ,…,vi ,…,vk-1 ,t是s到t的一条最短路径，vi是其中的 一个中间点，则s,v2 ,v3 ,…,vi和 vi ,…,vk-1 ,t分别是由s到vi和vi到t 的最短路径（最优性原理） 从Vi中的结点j i到t的最短路径将是： min { |< > ∈E, ∈Vi+1,1≤ji+1≤pi+1} 2, j 2 v 2 2, j v 2 2, j v 2, j 2 v 2 2, j v 2 2, j v 1 +1, + i i j v 1 1, + i+ i j v i i j v , 1 1, + i+ i j v i i j v
V2 4 6 6 5 7 3 2 3 10 12 4 6 8)0→ 11 8 5段图 2021/2/20
2021/2/20 15 1 2345 678 9 10 11 12 9732 4 3 2 7 11 11 8 1 4 563 5 6 425 V 1 V2 V3 V4 V5 5段图