运筹学部分课后习题解答 - 1 下载本文

解:如下图所示:

P 173 6.14 用Ford-Fulkerson的标号算法求下图中所示各容量网络中从

vs到

vt的

最大流,并标出其最小割集。图中各弧旁数字为容量cij,括弧中为流量fij.

B)

解:对上有向图进行2F标号得到

由于所有点都被标号了,即可以找到增广链,所以流量还可以调整,调整量为1,得

由图可知,标号中断,所以已经是最大流了,最大流量等于最小割的容量,最小割为与直线KK相交的弧的集合,即为

?(vs,v3),(vs,v4),(vs,v5),(v1,vt),(v2,vt),(v2,v3)?

*?1?2?5?3?2?1?14 所以从vs到vt的最大流为:fst

C)

解:对上有向图进行2F标号得到

由于所有点都被标号了,即可以找到增广链,所以流量还可以调整,调整量为1,得

由图可知,标号中断,所以已经是最大流了,最大流量等于最小割的容量,最小割为与直线KK相交的弧的集合,即为?(vs,v1),(vs,v3),v(2v,5?),所以从vs到vt的最大流为:

*fst?5?3?5?13

P193 7.1 根据下表给定的条件,绘制PERT网络图。 表7-8 作业代号 紧前作业 a1 a2 a3 b1 b2 b3 c1 c2 c3 无 a1 a2 无 b1 b2 a1,b1 a2,b2,c1 a3,b3,c2 解:绘制的PERT网络图为:

表7-9 作业代号 紧前作业 A B C D E F G H I J K L M 无 无 无 A,B B B F,C B E,H E,H C,D,F,J K L,I,G 解:绘制的PERT网络图为:

表7-10 作业代号 紧前作业 A B C D E F G H I J K L M 无 无 B C A,D D A,D E G,H I G J,K L

解:绘制的PERT网络图为: