《物流运筹学习题及答案8题目--网络分析.docx》由会员分享，可在线阅读，更多相关《物流运筹学习题及答案8题目--网络分析.docx（11页珍藏版）》请在第壹文秘上搜索。
1、习题八8.1设有四个无向图：G=V,E,G2=V2JE2,G3=V3,E3,G4=V4,E4,其中:Vl=v,V2,V3,V4,V5,V6E|=(V1,V2)(V|,V3)(V2,V3)(V2,V4)(V2,V5)(V3,V4)(V3,V5)(V4,V5)(V4,V6)(V5,V6)；V2=V1,V2,V3,V4,V5,V6E=(v,v2)(v!,v3)(v2,v4)(v2,v5)(v3,v4)(v3,v5)(v4,v6)(v5,v6);V3=V2,V4,V5,V6Ej=(V2,V4)(V2,V5)(V4,VS)(V4,V6)(V5,V6);V4=v,V2,V3,V4,V5,V6Ei=(v,v
2、2)(vv5)(v3,v4)(v4,v6);(1)试求这四个图的图解，判断其是否连通。(2)试问G2,G3,G4是否为Gl的真子图和支撑子图。(3)试问：在Gl中，y1=vv2v3v4v5v6u2=Viv3v2v5v4v6,u3=V3v4V6v5V2，u4=v2v5v6v4v2,5=v2v3vV2V5V4V2P6=VV2V5V4V2V5V6是否为开链，闭链,简单链,初等链,圈，路，回路。8.2已知有向图D=(V,A)其中V=Vi,V2,V3,V4,v5,A=(v1,v2)(v,v3)(v2,v4)(v2,v5)(v3,v2)(v4,v3)(v4,v5)0试求D与G(D)的图解。(2)试问：y1
3、=vv3v4V2V5U2=V2V5V4V3V2U3=Vv3v2v4v3v2v5,4=V3V2V4V3，5=VV3V2V4V3,6=VVjV2v4v5是否为开链，闭链，简单链，初等链，圈，路，回路。83试问：从8.1题的图G,G2的任一点出发，能否走遍该图的各边且仅过每边一次而回到出发点，若能则找出这样的路。8.4某工厂办公室拟在三天内举行六项活动，每项活动各需半天时间。厂办拟请十名厂级干部参加这些活动，如下表中J号所示。已知活动A须安排在第一天上午，活动F须安排在第三天下午，活动B只能安排在卜午，而每名厂级干部都希望每天最多参加一项活动。厂办应如何安排这六项活动的日程。活223456789IO
4、BCDEFJ8.5分别用避圈法和破圈法目立下列网络的最小树。(a)(b)8.6某市六个新建单位之间的交通线路的长度（公里）如下表所示。其中单位A距市煤气供应网最近，为ABCDEFAO1.33.24.33.83.7B1.3O3.54.03.13.9C3.23.502.82.61.0D4.34.02.802.12.7E3.83.12.62.i02.4F3.73.91.02.72.401.5公里。为使这六个单位都能使用煤气，现拟沿交通线铺设地下管道，并且经A与煤气供应网连通。应如何铺设煤气管道使其总长最短。8.7在下列网络中，求点S到各点的最短路。68.9在下面的网络中，试求：各点到点t的最短路;点
5、S到各点的最短路。8.10 某公司正在研制一种有极好销售潜力的新产品。当研究工作接近完成时，公司获悉一家竞争者正计划生产这种产品。要突击赶制出这种产品以参与竞争，还有四个互不重叠的阶段。为了加快进度，每个阶段都可采取“优先”或“应急”的措施。不同的措施卜.每段工作所需要的时间（月）和费用（百万元）如小卜.表示。现有一千万元资金供这四个阶段使用，则卷段应采取什么措施能使这种产品尽早上市。试将此间题化成最短路问题并求解。7段措徽、剩余研究试制工艺设计生产与调拨时间费用时间费用时间费用时间费用正常51优先42325321应急232334I28.11 已知七个村镇之间的交通线路如卜.图所示，点旁的数字
6、为每个村的粮食产量，边旁的数字为两村间的路长。现要为这七个村建一个文化馆和一个粮库，试问：（1）文化馆应建在何村，使各村距其都较近。（2）粮库应建在何村，使总运输量为最小。8.12 在右面的网络中，弧旁的数字为其容量。试求:（1）所有截集及其截量；（2）最大流；（3）最小截集。8.13 求卜.列网络的最大流与最小截集。弧旁的数字为其容量。8.14 有四根同一规格的轴A,B,CD四个同一规格的齿轮I,H,11I,IV,现要将轴与齿轮配对使用。由于精度不高，不能任意匹配。已知A只能与II配合，B能与I,11配合，C能与HI,IV配合，D能与11,HI配合.应如何匹配才能充分利用这些零件。试用网络分
7、析的方法求解。8.15 某河流中有几个岛屿，两岸与各岛以及各岛之间的桥梁如下图所示。在一次敌对的军事行动中，至少应炸断几座桥梁，才能完全切断两岸的交通。试用网络分析的方法求解。8.16 试建立卜.列问题的线性规划模型：例12；例6。8.17求下列网络的最小费用最大流。弧旁数字为(与，)。8.18试用网络分析的方法求解：第四章例五(面粉转运问题)6.11题中(1)。第八章网络分析8.3 对GI能够找出几条这样的路，如二丫22丫4丫6丫5丫3丫4丫5丫2丫3丫4；对62则不能。8.4 第一天上午A,下午E；第二天上午C,下午B；第三天上午D,下午F。8.5 (a)(T*)=14；(b)(T*)=1
8、6；(c)(T*)=18.861cO11O?1O?1OW(T*)=11.4公里8.7 (a)s1,路长7；OOQ2,路长6；003,路长8；O-OQO24,路长8；O-OQ5,路长6；006,路长3；OOQrOQOOCKPs35t,OOQt,路长9；(b)(2)(3)(4)(7)(8)(12)OKQCK)FQ00QQOQfQQO142(8)OOQOrQ*OQ123(15)ORf-QXD23OPQQO85(10)OPQQO87(11)8.8)(2)G(3)G(5)1(7)(8)(ap-f)-Q46(8)(6)(5)(3)(1)(O)(?)岁)q(4)(7)o(O)(2)(4)(7)(bp-D-Q
9、KD4O-Q-Q-O34(O)C(2)yi(4)(O)(2)(5)o(O)(2)(5)(O)O/1OOQQQrDTDQPTPO-QO36,245QO5(6)8.9 (QYroUQt,路长3；OToQt,路长5；OtORt,路长1；OrOiOQO4t,路长3；ONOt,路长4.(QfO亍Of*Q1,路长-1；Os*2,2;OODQQpQ)-*O43,1；OsO-D4,-1COWQt,3.8.10 提示：网络结点编号用一对数字(i,j)表示，其中i表示该阶段末声誉资金；结点(i,j)与结点(i+l,j)之间的弧的权数，表示当采取“费用为(j-k)百万元的措施”时第i+1段的工作所需的时间。设点为(
10、0,10),终点为t。最优方案如下表所示。阶段措施费用时间1.研究应急322.试制优先233.设计应急434.生产优先128.11 (1)文化馆应建在V5村，与最远村镇V5距离4.8。(2)粮库应建在V3村，总运输量为61500。8.12 (2)f(X*)=5；(3)(S*,S*)=(1,t),(2,3)。8.13 (a)f(X*)=21；(S*,5*)=(s,1),(s,2),(s,3)。(b)f(X*)=20；(S*,5*)=(s,2),(1,4),(1,3)。8.14 仿照例13建立网络模型。匹配方案：All,BI,CIV,DIIIo8.15 建立容量模型，求最小截集。应切断编号为7,9,10这三座桥。8.17 (a)f(X*)=11,c(X*)=55；(b)f(X*)=5,c(X+)=37o
