课程

k 2 Sk B3 C3 D3 Xk B2 C2 B2 C2 D2 C2 D2 B3 C3 B3 C3 D3 Vk 10 13 12 5 6 7 8 9 5 10 10 8 15 7 Vkn=Vk+fk+1 10+7 13+6 12+7 5+6 6+12 7+6 8+12 9+17 5+11 10+17 10+11 8+13 15+11 7+13 fk 17 11 Xk B2 C2 13 16 21 C2 C3 C3、D3 1 B C D C3 D3 20 D3 由表中计算结果可以看出： 从B到A的最短路线为BC3C2B1A，最短距离为16；

从C到A的最短路线为CC3C2B1A或CD3C2B1A，最短距离为21； 从D到A的最短路线为DD3C2B1A，最短距离为20。

从A到B的最短路线为AB1C2C3B，最短距离为16；

从A到C的最短路线为AB1C2C3C或AB1C2D3C，最短距离为21； 从A到D的最短路线为AB1C2D3D，最短距离为20。

P（198）7.5 用递推方法求解下列问题。

（1）

max z =4x1+9x2+2x3

2 x1+x2+x3=10 xi>=0,i=1,2,3

解：当初始状态给定时，使用逆推解法；当终止状态给定时，使用顺推解法。 由题意，将问题划分为三个阶段，设状态变量为S0，S1，S2，S3，并记S3=10，x1,x2,x3 为各阶段的决策变量，各阶段指标函数按加法方式结合。

fk(Sk)表示第k阶段结束状态为Sk，第1至第k阶段的最大值则由约束条件可知

x1=s1 ,s1+x2=s2 ,s2+x3 s3=10 即

s1=x1, 0<=x2<=s2, 0<=x3<=s3 由顺推法

f1(s1)=max(4x1)=4s1 最优解：x1 =s1

f2(s2)=max[9x2+f1(s1)]=9s2 最优解：x2 =s2

f3(s3)=max[2x +f2(s2)]=200 最优解：x3 =10

x2 =s2=10—x3 =0 x1 =s1=s2—x2 =0-0=0 从而得到最优解

x1 =0, x2 =0, x3 =10 最优值为：200

P（238）8.7 用迪克斯特拉方法求图中从V1到各点的最短路。

解：此为最短路问题，在权数为正，可采用迪克斯特拉方法。

Vj v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 初始值 T( ) {0} ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 第一次迭代 P( )+Lij 0+2 0+∞ 0+∞ 0+∞ 0+∞ 0+∞ 0+∞ 0+∞ 0+∞ 0+∞ T( ) {2} ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 第二次迭代 P( )+Lij 2+∞ 2+6 2+1 2+∞ 2+∞ 2+∞ 2+∞ 2+∞ 2+∞ T( ) ∞ 8 {3} ∞ ∞ ∞ ∞ ∞ ∞ 第三次迭代 P( )+Lij 3+∞ 3+5 3+∞ 3+∞ 3+∞ 3+∞ 3+∞ 3+∞ T( ) ∞ 8 ∞ ∞ ∞ {4} ∞ ∞ 第四次迭代 P( )+Lij 4+∞ 4+∞ 4+6 4+∞ 4+7 4+∞ 4+∞ ∞ 8 {10} ∞ 11 ∞ ∞ T( ) 第五次迭代 P( )+Lij 10+∞ 10+4 10+∞ 10+∞ 10+∞ 10+∞ ∞ 8 ∞ 11 ∞ ∞ T( ) 第六次迭代 P( )+Lij 8+7 8+∞ 8+∞ 8+∞ 8+∞ {15} 10 11 ∞ ∞ T( ) 第七次迭代 P( )+Lij 15+9 15+∞ 15+∞ 15+∞ {14} 11 ∞ ∞ T( ) 第八次迭代 P( )+Lij 14+∞ 14+1 10+∞ 11 15 ∞ T( ) 第九次迭代 P( )+Lij 11+∞ 11+9 T( ) {15} 20 第十次迭代 P( )+Lij 15+4 {19} T( ) 由上表的迭代过程可得： Sq={v1,v2,v5,v9,v4,v6,v8,v7,v3,v10,v11} d(v1,v2)=2,最短路：（v1,v2）； d(v1,v5)=3,最短路：（v1,v2,v5）； d(v1,v9)=4,最短路：（v1,v2,v5,v9）； d(v1,v7)=14,最短路：（v1,v2,v5,v9,v6,v7）； d(v1,v8)=11,最短路：（v1,v2,v5,v9,v8）； d(v1,v4)=8,最短路：（v1,v2,v4）或（v1,v4）； d(v1,v6)=10,最短路：（v1,v2,v5,v9,v6）； d(v1,v3)=15,最短路：（v1,v2,v4,v3）或（v1,v4,v3）； d(v1,v10)=15,最短路：（v1,v2,v5,v9,v6,v7,v10）； d(v1,v11)=19,最短路：（v1,v2,v5,v9,v6,v7,v10,v11）。

P（239）8.12 求图所示的网络的最大流（每弧旁的数字是（Cij,fij））。

解：用寻求最大流的标号法求解。 给中间点标上编号如下：

（1）标号过程:开始先给Vs标上（0，+∞），这时，Vs是标号而未检查的点。

第1步：弧（v1,v4），因fs1=3,Cs1=4,则fs1< Cs1.则给v1标号（Vs,L(v1)）

L(v1)=min{L(Vs), Cs1—fs1}=min{+∞,4—3}=1 第2步：检查弧（v1,v4）。

f14=1,C14=1,不满足标号条件，对v4进行标号。 对于弧（v1,v5）,f15=2,C15=3,则f15< C15。 给v5标号（v1,L(v5)）

L(v5)=min{L(v1),C15—f15}=min(1,3—2)=1 第3步：弧（v5,v4）,f54=3,C54=5,则f54< C54 则给v4标号（v5,L(v4)）。

L(v4)=min{L(v5), C15—f15}=min{1,4—3}=1 第4步：对于弧（v4,vt）因f4t=0,C4t=7 , f4t< C4t 。 则给vt标号（v4,L(vt)）

L(vt)=min{L(v4), C4t—f4t}=min{1,7—6}=1 故 =L（vt）=1

(2)调整过程：由点的第一个标号找到一条增广链，如图中的“/”所示：

按 =1在M上进行调整，

fs1+1=4，f15+1=2+1=3，f54+1=4，f4t+1=7 其余fij不变，调整后如图所示。

再对这个可行流进行标号过程，寻找增广链。 （1）标号过程:开始先给Vs标上（0，+∞）， 第1步：对于（v1,v2），因fs2=2,Cs2=10,则fs2< Cs2.则给v1标号

（V2,L(v2)）

L(v2)=min{L(Vs), Cs2—fs2}=min{+∞,10—4}=6 第2步：对于弧（v2,v3）。

f23=2,C23=4,则f23< C23。

给v2标号（Vs,L(v3)）

L(v3)=min{L(v2),C23—f23}=min(6,4—2)=2

第3步：对于弧（v3,vt）,f3t=3,C3t=8,则f3t< C3t。 则给vt标号（v3,L(vt)）。

L(vt)=min{L(v3), C3t—f3t}=min{2,8—3}=2 故vt有了标点，转入调整过程。

(2)调整过程：由点的第一个标号找到一条增广链，如图中的“/”所示：

按 =2在M上调整f:

fs2+2=2，f23+2=4， f3t+2=5 其余fij不变，调整后得到如图所示的可行流。对这个可行流进入标号过程，寻找增广链。

（1）标号过程:首先给Vs标上（0，+∞）。 第1步：对于弧（vs,v5），因fs5=2,Cs5=3,则fs5< Cs5.则给v5标号

（Vs,L(v5)）

L(v5)=min{L(Vs), Cs5—fs5}=min{+∞,3—2}=1 第2步：对于弧（v5,v4）。

F54=4,C54=4,则v4不能标号。

第3步：对于弧（vs,v2）,fs2=8,Cs2=10,则fs2< Cs2 则给v2标号（vs,L(v2)）。

L(v2)=min{L(v5), Cs2—fs2}=min{+∞,10—8}=2 第4步：对于弧（v2,v3）因f23=4,C23=4 , f4t= C4t 故v3不能标号。

此时，标号无法继续下去，算法结束。此时的可行流即为网络最大流，

其最大流为：v(f )=fs1+f54+f23=4+4+4=12 对应的最小截集为（v1 ,v1 ）,其中

v1 ={vs,v2,v5},v1 ={v1,v3,v4,vt}。