物流运筹学 习题 8题目-网络分析

习题八8.1设有四个无向图：G1={V1,E1},G2={V2,E2},G3={V3,E3},G4={V4,E4},其中：V1={v1,v2,v3,v4,v5,v6}E1={(v1,v2)(v1,v3)(v2,v3)(v2,v4)(v2,v5)(v3,v4)(v3,v5)(v4,v5)(v4,v6)(v5,v6)};V2={v1,v2,v3,v4,v5,v6}E2={(v1,v2)(v1,v3)(v2,v4)(v2,v5)(v3,v4)(v3,v5)(v4,v6)(v5,v6)};V3={v2,v4,v5,v6}E3={(v2,v4)(v2,v5)(v4,v5)(v4,v6)(v5,v6)};

V4={v1,v2,v3,v4,v5,v6}E4={(v1,v2)(v2,v5)(v3,v4)(v4,v6)};（1）试求这四个图的图解，判断其是否连通。（2）试问G2,G3,G4是否为G1的真子图和支撑子图。（3）试问：在G1中，μ1=v1v2v3v4v5v6，μ2=v1v3v2v5v4v6，μ3=v3v4v6v5v2，μ4=v2v5v6v4v2，μ5=v2v3v1v2v5v4v2，μ6=v1v2v5v4v2v5v6，是否为开链，闭链，简单链，初等链，圈，路，回路。8.2已知有向图D=(V,A)，其中V={v1,v2,v3,v4,v5,},A={(v1,v2)(v1,v3)(v2,v4)(v2,v5)(v3,v2)(v4,v3)(v4,v5)}。(1)试求D与G(D)的图解。(2)试问：μ1=v1v3v4v2v5，μ2=v2v5v4v3v2，μ3=v1v3v2v4v3v2v5，μ4=v3v2v4v3，μ5=v1v3v2v4v3，μ6=v1v3v2v4v5，是否为开链，闭链，简单链，初等链，圈，路，回路。8.3试问：从8.1题的图G1，G2的任一点出发，能否走遍该图的各边且仅过每边一次而回到出发点，若能则找出这样的路。8.4某工厂办公室拟在三天内举行六项活动，每项活动各需半天时间。厂办拟请十名厂级干部参加这些活动，如下表中√号所示。已知活动A须安排在第一天上午，活动F须安排在第三天下午，活动B只能安排在下午，而每名厂级干部都希望每天最多参加一项活动。厂办应如何安排这六项活动的日程。干部活动22345678910A√√√√√√B√√√√C√√√√√D√√√E√√√F√√√√√8.5分别用避圈法和破圈法求下列网络的最小树。55232223321423332786425191057143412752424（a）134655232223321423332786425191057143412752424（a）134675253783222746461314(b)123456788.6某市六个新建单位之间的交通线路的长度（公里）如下表所示。其中单位A距市煤气供应网最近，为1.5公里。ABCDEFA01.33.24.33.83.7B1.303.54.03.13.9C3.23.502.82.61.0D4.34.02.802.12.7E3.83.12.62.102.4F3.73.91.02.72.40为使这六个单位都能使用煤气，现拟沿交通线铺设地下管道，并且经A与煤气供应网连通。应如何铺设煤气管道使其总长最短。8.7在下列网络中，求点s到各点的最短路。247t61S332247t61S332563447122437S123456t861(a)943182811675129163411427(b)25897178.8在下列网络中，求各点间的最短路。710710218469296121235646(a)327322112356436(b)8.9在下面的网络中，试求：①各点到点t的最短路;②点s到各点的最短路。-2-2215253s1234-24-3t448.10某公司正在研制一种有极好销售潜力的新产品。当研究工作接近完成时，公司获悉一家竞争者正计划生产这种产品。要突击赶制出这种产品以参与竞争，还有四个互不重叠的阶段。为了加快进度，每个阶段都可采取“优先”或“应急”的措施。不同的措施下每段工作所需要的时间（月）和费用（百万元）如小下表示。现有一千万元资金供这四个阶段使用，则每段应采取什么措施能使这种产品尽早上市。试将此问题化成最短路问题并求解。阶段措施剩余研究试制工艺设计生产与调拨时间费用时间费用时间费用时间费用正常51优先42325321应急232334128.11已知七个村镇之间的交通线路如下图所示，点旁的数字为每个村的粮食产量，边旁的数字为两村间的路长。现要为这七个村建一个文化馆和一个粮库，试问：（1）文化馆应建在何村，使各村距其都较近。（2）粮库应建在何村，使总运输量为最小。2.52.532000810001.51.544323157462700003000100050004000621.88.12在右面的网络中，弧旁的数字为其容量。试求：（1）所有截集及其截量；（2）最大流；（3）最小截集。1132425s12t338.13求下列网络的最大流与最小截集。弧旁的数字为其容量。6464157433332613s1234t(a)109554495613s12345t45(b)8.14有四根同一规格的轴A,B,C,D四个同一规格的齿轮Ⅰ，Ⅱ，Ⅲ，Ⅳ，现要将轴与齿轮配对使用。由于精度不高，不能任意匹配。已知A只能与Ⅱ配合，B能与Ⅰ，Ⅱ配合，C能与Ⅲ，Ⅳ配合，D能与Ⅱ，Ⅲ配合.应如何匹配才能充分利用这些零件。试用网络分析的方法求解。8.15某河流中有几个岛屿，两岸与各岛以及各岛之间的桥梁如下图所示。在一次敌对的军事行动中，至少应炸断几座桥梁，才能完全切断两岸的交通。试用网络分析的方法求解。112563489107111213AFBCDE8.16试建立下列问题的线性规划模型：①例12；②例6。8.17求下列网络的最小费用最大流。弧旁数字为（）。(6,2)(3,10)(6,2)(3,10)(1,8)(2,5