最短路线问题 EX k=1 k=2 k=3 8)3 A 5 10 3
11 最短路线问题 EX: 1 2 3 6 4 7 8 9 10 5 2 4 5 7 4 6 3 2 4 4 1 5 1 4 6 3 3 3 3 4 A B k=1 k=2 k=3 k=4
K一阶段变量 s—状态变量S2={②,③,④} X—决策变量,即当状态为sk时,可选择的下 状态,X=s k+1 ,×k)一从Sk到sk+1的距离 由S到终点的最短距离 采用逆推的方法求解 12
12 K—阶段变量 sk—状态变量 S2={②，③，④} xk—决策变量，即当状态为sk时，可选择的下 一状态，xk=sk+1 rk（sk，xk）—从sk到sk+1的距离 fk（sk）—由sk到终点的最短距离 采用逆推的方法求解
k=1 k=2 k=3 k=4 解 2人7,人5)1 826求 83 A 10B k=4 f4(8)=r4(8,10)=3 7)3 (9)=a(9,10)=4 k=3 f3(s3)=min{3(s3,X3)+f4(s4)} f3(5)=minr3(5,8)+f4(8 (5,9)+f4(9) f2(6)=7 f3(7=6 13
13 k=4 f4（8）=r4（8，10）=3 f4（9）=r4（9，10）=4 k=3 f3（s3）=min{r3（s3 ,x3）+f4（s4）} f3（5）=min r3（5，8）+f4（8） r3（5，9）+f4（9） f3（6）=7 f3（7）=6 1 2 3 6 4 7 8 9 10 5 2 4 5 7 6 4 3 42 4 1 5 1 4 6 3 3 3 3 4 A B k=1 k=2 k=3 k=4 解
k=1 k=2 k=3 k=4 2人7,人5)1 83 A 3269 10B 7)3 k=2 f2(s2)=min{2(S2,x2)+53(S3)} f2(2)=min{r2(2,5)+(5) (2,6)+f3(6) (2,7)+3(7) =min{7+4,4+7,6+6}=11 f,(3)=7 f2(4)=8
14 k=2 f2（s2）=min{r2（s2，x2）+f3（s3）} f2（2）=min{r2（2，5）+f3（5）， r2（2，6）+f3（6）， r2（2，7）+f3（7）} =min{7+4，4+7，6+6}=11 f2（3）=7 f2（4）=8 1 2 3 6 4 7 8 9 10 5 2 4 5 7 6 4 3 42 4 1 5 1 4 6 3 3 3 3 4 A B k=1 k=2 k=3 k=4
k=1 k=2 k=3 k=4 2人7,人5)1 A 826求 83 10B 3 1(S1)=min{r1(s1,x1)+f2(s2)} f1(1)=min{1(1,2)+f2(2), (1,3)+f2(3) 「1(1,4)+f2(4)} min{2+11,4+7,3+8}=11 1(1)=1(1,3)+f2(3) f2(3)=r2(3,5)+f3(5) +3 5)(8 3 (5)=2(5,8)+fA(8) f4(8)=r4(8,10) 69 15
15 k=1 f1（s1）=min{r1（s1，x1）+f2（s2）} f1（1）=min{r1（1，2）+f2（2）， r1（1，3）+f2（3）， r1（1，4）+f2（4）} =min{2+11，4+7，3+8}=11 f1（1）=r1（1，3）+f2（3） f2（3）=r2（3，5）+f3（5） f3（5）=r3（5，8）+f4（8） f4（8）=r4（8，10） 1 3 5 8 10 4 6 9 1 2 3 6 4 7 8 9 10 5 2 4 5 7 6 4 3 42 4 1 5 1 4 6 3 3 3 3 4 A B k=1 k=2 k=3 k=4