《运筹学》习题（十）.doc

《《运筹学》习题（十）.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《运筹学》习题（十）班级姓名一、判断下述说法是否正确1、在PERT网络图中只能存在一个始点和一个终点。2、总时差为0的各项作业所组成的路线即为关键路线。3、网络途中的任何一个结点都具有某项作业的开始和它项作业的结束的双重标志属性。4、以同一结点为开始时间的各项作业的最早开始时间相同。5、以同一结点为结束时间的各项作业的最迟结束时间相同。6、某项作业的自由时差被利用后，不影响其他作业自由时差的数值，而某项作业利用了总时差，则可能会影响其他作业的总时差数值。答：二、找出下图中（a）~（d）PERT网络图上的错误画法并将其改正过来。②②d⑤

2、aeda①b④f⑤①b④e⑦g⑧cc③③f⑥(a)(b)③ae②ae①⑥dbf①b④g⑤④cfgcd③②⑤⑦(c)(d)答：第1页三、根据下表给定的条件，绘制PERT网络图。作业代号紧前作业作业代号紧前作业A无GF，CB无HBC无JE，HDA，BKC，D，F，JEBLKFBML，G答：四、计算下面网络图各项作业的相关参数。包括：1、最早开始与最早结束时间；2、最迟开始与最迟结束时间；3、总时差与自由时差；4、找出关键路线及计算工期。②3⑤7⑧2025①8④3⑦4⑨421③8⑥7第2页答:附：《运筹学》习题（九）答案一、解：1、

3、={(vs,v1),(v3,v2),(v2,vt)},={(v3,v1)}.2、是可行流f的一条增广链。二、解：共九个截集见下表。(表中的答案是各顶点的下标)VV(V,V)c(V,V)s1,2,3,4,t（s,1），（s,2）7s,12,3,4,t（s,2），（1,2），（1,4），（1,3）9s,2,1,3,4,t（s,1），（1,2），（2,4）6s,1,2,3,4,t（1,3），（1,4），（2,4）6s,1,32,4,t（s,2），（1,2），（1,4），（3,t），（3,4）9s,2,41,3,t（s,1），

4、（1,2），（1,4），（4,t），（4,3）10s,1,2,34,t（4,3），（1,4），（3,t），（2,4）6s,1,2,43,t（1,3），（4,3），（4,t）9第3页s,1,2,3,4t（3,t），（4,t）7三、解：首先将原问题改变为网络最大流问题如下图（a）所示。从一个可行流f={fs1=30,f13=30,f3t=30,fs2=40,f24=40,f4t=40,其它皆为零流}开始，第一步进行标号，先给vs标号为（0，+∞），检查vs对v2标号为（vs，40），再检查v2对v4标号为（v2，40），检查v4对v3标号

5、为（v4，10），检查v3对vt标号为（v3，10），于是得一条增广链=(vs,v2,v4,v3,vt)。第二步进入调整阶段，其中调整量为：=10，得到可行流如图（b）所示。重复以上第一、二步骤可得最大流如图（c）所示。其最大流量为110。再将最大流中零流弧从图（c）中去掉得单向交通图如图（d）所示。v1(60,30)v3v1(60,30)v3(30,30)(30,30)(10,0)(70,30)(10,0)(70,40)vs(10,0)(20,0)(10,0)vtvs(10,0)(20,0)(10,0)vt(20,0)(10,0

6、)(20,0)(10,10)(80,40)(40,40)(80,50)(40,40)v2(100,40)v4v2(100,50)v4图（a）图（b）v1(60,40)v3v160v3(30,30)30(10,0)(70,70)70vs(10,10)(20,20)(10,0)vtvs102010vt(20,0)(10,10)(80,80)(40,40)8040v2(100,50)v4v2100v4图（c）图（d）四、解：将A,B,C,D,E,F分别用一个点表示，相互之间CF有桥梁相连的连一条弧，弧的容量就是两点间的桥梁数（见右图）。根据

7、最大流量最小截量定理，可以找到此图D网络所示的最小截集，截集所包含的弧AE,CD,CF即AB○6,○7,○12号桥为切断A与F之间联系的最少要破坏的桥梁。E第四题图第4页