《系统工程与运筹学》习题及答案 第6章 课后习题答案

习题答案1.求图1中各图的最小部分树和最大部分树。答案：最小部分树：图1a：36；图1b：28；图1c：22；图1d：49；最大部分树：图1a：62；图1b：49；图1c：38；图1d：72；2.某奶站在V1处办公，每天送奶员需要给居住在各个街区的用户送牛奶。问送奶员应如何安排路线，使其给所有用户送完牛奶返回奶站，所走的路程最短。答案：图2应该重复走v1-v2，v3-v4-v6，重复路长为28，所走总路程为128；列表找出图3的所有S到T的割集，确定其容量，并找出该图的最大流量，见下表所示。VSGT割集割集容量SV1,V2,V3,V4,T(S,V1)(S,V2)24S,V1V2,V3,V4,T(S,V2)(V1,V4)(V1,V3)28S,V2V1,V3,V4,T(S,V1)(V2,V4)26S,V3V1,V2,V4,T(S,V1)(S,V2)(V3,T)39S,V4V1,V2,V3,T(S,V1)(S,V2)(V4,T)(V4,V3)42S,V1,V2V3,V4,T(V1,V3)(V2,V4)(V1,V4)30S,V1,V3V3,V4,T(S,V2)(V1,V4)(V3,T)36S,V1,V4V2,V3,T(S,V2)(V1,V3)(V4,T)32S,V1,V2,V3V4,T(V3,T)(V1,V4)(V2,V4)38S,V1,V2,V3,V4T(V3,T)(V4,T)27S,V1,V3,V4V2,T(S,V2)(V3,T)(V4,T)40S,V1,V2,V4V3,T(V1,V3)(V4,V3)(V4,T)40S,V2,V3V1,V4,T(S,V1)(V2,V4)(V3,T)41S,V2,V4V1,V3,T(S,V1)(V4,V3)(V4,T)29S,V2,V3,V4V1,T(S,V1)(V3,T)(V4,T)38S,V3,V4V1,V2,T(S,V1)(S,V2)(V3,T)(V4,T)514.用Dijkstra算法求出图4中S到T的最短路径。答案：最短路径为：S-v1-v3-T，路长265.采用福特法求图5中S到各点的最短路径。答案见下表。Sv1v2v3v4v5S0710∞∞∞0000v1-30148∞77(S-1)7(S-1)7(S-1)v2∞∞0∞11∞108(S-1-2)8(S-1-2)8(S-1-2)v3∞-2∞0∞13∞11(S-1-3)11(S-1-3)11(S-1-3)v4∞∞-6605∞15(S-1-4)15(S-1-4)15(S-1-4)v5∞∞∞∞∞0∞∞20(S-1-4-5)20(S-1-4-5)6.图6为一网络最大流问题，其中弧上的数字为容量，括号内的数字为流量。（1）在空白的括号内填上数字，使之构成一个可行流。（2）对可行流进行判断、调整，求该图的最大流。答案:空白处填入数字及最大流如下图6a与图6b所示。7.如图7所示，从三个生产基地经公路将货物运至两个经销中心，中间要经过四个中转站。图中弧旁数字为各条公路的最大运输能力（单位为吨/小时），求从生产基地每小时能运送到经销中心的最大流量。生产基地每小时能运送到经销中心的最大流量为205.运送过程见图7a所示。8.图8所求为一最小费用最大流问题，弧上第一个数字表示单位物资运费（dij），第二个数字表示该路的允许流量(Cij)，求该图的最小费用最大流。v1vv1v6443349464255v9v8v7v5v4v2v3图99.某工地值班人员每天需对所管辖的范围进行巡视，其巡视路线如图9所示，如何确定最优巡视路线？答案：最优巡视路线为重复走v2-v3-v6，v4-v7-v8，重复路长为15，所走总路程为68；10.某工地道路网如图9所示，工地值班员准备从v1点出发去v9点，怎样走，距离最近呢？答案：路线为v1-v2-v3-v6-v9，最短距离为16.11.采用福特法求图10中S到各点的最短路径。S到各点的最短路径见下表v1v2v3v4v5v10-15-1∞000v2∞02∞3-1-1(1-2)-1(1-2)v3-1∞0∞151(1-2-3)1(1-2-3)v434∞02-1-1(1-4)-1(1-4)v5∞∞∞∞0∞1(1-4-5)1(1-4-5)12.图11为一网络最大流问题，其中弧上的数字为容量，用标记法找出S-T的最大流。答案：流量见图11a所示。最大流量为24.13.某塑钢厂S与建筑工地T间道路的容许流量为C(i,j)，单位运价为d(i,j)，塑钢厂S与建筑工地T之间的网络如图12所示（弧中左边的数字为运输物资的单位费用d(i,j)，右面的数字为线路容量C(i,j)，现需确定怎样运输才能使塑钢厂S运到建筑工地T的塑钢最多且运费最省。答案：实际运量见图12a所示。最大运量11，最小费用58.图10图1014.有六台机床，用x1,x2,…，x6表示，现有六个零件需要加工，用y1,y2,…，y6表示。其中机床x1可加工零件y1；机床x2可加工零件y1、y2；机床x3可加工零件y1、y2、y3；机床x4可加工零件y2；机床x5可加工零件y2、y3、y4；机床x6可加工零件y2、y5、y6。现要求制定加工方案，使一台机床只加工一个零件，一个零件只在一台机床上加工，要求尽可能多地安排零件的加工。试将该问题化为网络最大流问题，求出能满足上述条件的加工方案。答案：最多加工5个零件。机床x1-y1；机床x2-y2；机床x3-y3；机床x4不加工零件；机床x5-y4；机床x6-y6。15.某建筑公司一季度需完成四项施工任务，其中第一项任务工期为1月～2月份共两个月，总计需2000元；第二项任务工期为1月～3月份共三个月，总计需1500元；第三项任务工期为2月～3月，共两个月，总计需3000元；第四项任务工期为1月～3月，共三个月，总计需2500元。该公司每月可用资金为3000元，但在任一项任务上投入的资金数不能超过1000元。问该建筑公司要想按期完成上述四项任务应如何合理安排资金。试将此问题化为网络最大流问题进行求解。答案：最优安排为：第1月分别分配给项目1、3各1000，分配给项目2、4各500；第2月分别分配给项目1、3、4各1000，分配给项目2为0；第3月分别分配给项目2、3、4各1000，即能满足要求。16.为了维护社会治安，公安系统部门需要日夜安排治安巡逻。某派出所辖区的街道巡逻路线示意图如图13所