运筹学答案(第八章)

1、 8.1 证明在证明在9座工厂之间，不可能每座工厂只与其座工厂之间，不可能每座工厂只与其他他3座工厂有业务联系，也不可能只有座工厂有业务联系，也不可能只有4座工厂与偶数座工厂与偶数个工厂有业务联系。个工厂有业务联系。 解：将有联系的工厂做一条连线。解：将有联系的工厂做一条连线。如果仅有如果仅有9座工厂只与其他座工厂只与其他3座工厂有业务联系，座工厂有业务联系，说明顶点次数之和为说明顶点次数之和为27，矛盾。，矛盾。如果只有如果只有4座工厂与偶数个工厂有业务联系，其他座工厂与偶数个工厂有业务联系，其他5个工厂一定与奇数个工厂有业务联系，说明顶点次个工厂一定与奇数个工厂有业务联系，说明顶点次数之和

2、还是奇数，矛盾。数之和还是奇数，矛盾。 8.2 有八种化学药品有八种化学药品a、b、c、d、e、f、g、h要放进贮藏室。从安全角度考虑，下列各组药品不能要放进贮藏室。从安全角度考虑，下列各组药品不能贮存在同一室内：贮存在同一室内：ac，af，ah，bd，bf，bh，cd，cg，de，dg，eg，ef，fg，gh，问至少需要几间贮藏室存放这，问至少需要几间贮藏室存放这些药品。些药品。 解：能贮存在同一室内的两种药品之间作一条连解：能贮存在同一室内的两种药品之间作一条连线。贮存在同一室内的药品应该构成一个完全图。线。贮存在同一室内的药品应该构成一个完全图。abg，cfh，de构成完全图。故，存放这

3、些药品最少构成完全图。故，存放这些药品最少需要需要3间储藏室。间储藏室。 8.3 6个人围成圆圈就座，每个人恰好只与相邻个人围成圆圈就座，每个人恰好只与相邻者不相识，是否可以重新就座，使每者不相识，是否可以重新就座，使每 个人都与邻座认个人都与邻座认识识? 解：两个人认识作一条连线。解：两个人认识作一条连线。 8.4 判定图判定图8-50中的两个图能否一笔画出，若能，中的两个图能否一笔画出，若能，则用图形表示其画法。则用图形表示其画法。解：解： (a)图都是偶点，可以一笔画出。图都是偶点，可以一笔画出。(b)图只有两图只有两个奇点，一个奇点为起点，另一个奇点为终点。个奇点，一个奇点为起点，另一

4、个奇点为终点。 8.5 求解如图求解如图8-51所示的中国邮路问题，所示的中国邮路问题，a点是邮点是邮局。局。 8.6 分别用深探法、广探法、破圈法找出图分别用深探法、广探法、破圈法找出图8-52所所示图的一个生成树。示图的一个生成树。 8.7 设计如图设计如图5-53所示的锅炉房到各座楼铺设暖气所示的锅炉房到各座楼铺设暖气管道的路线，使管道总长度最管道的路线，使管道总长度最(单位：单位：m)。 8.8 分别用避圈法和破圈法求图分别用避圈法和破圈法求图8-54所示各图的最所示各图的最小树。小树。 8.9 给定权数给定权数1，4，9，16，25，36，49，64，81，构造构造棵霍夫曼树。棵霍夫

5、曼树。 8.10 如图如图8-55，v0是一仓库，是一仓库，v9是商店，求一条是商店，求一条从从v0到到v9的最短路。的最短路。 8.11 求图求图8-56中中v1到各点的最短路。到各点的最短路。 8.12 求图求图8-57网络中各顶点间的最短路。网络中各顶点间的最短路。 091201820014020121650)0(d0912018200321436020121650)1(d0948123201820032143602012191650)2(d0948123201820032143602012191650)3(d0948123201820032143602012191650)4(d0948

6、123201820020503214360201219165054321)5(54321vvvvvdvvvvv 8.13 某设备今后五年的价格预测分别是某设备今后五年的价格预测分别是(5，5，6，7，8)，若该设备连续使用，其第，若该设备连续使用，其第j年的维修费分别为年的维修费分别为(1，2，3，5，6)，某单位今年购进一台，问如何确定，某单位今年购进一台，问如何确定更新方案可使更新方案可使5年里总支出最小年里总支出最小(不管设备使用了多少不管设备使用了多少年，其残值为年，其残值为0)。解：最优解为：先使用两年，更新后再使用三年。解：最优解为：先使用两年，更新后再使用三年。或先使用三年，更新

7、后再使用两年。最小总支出或先使用三年，更新后再使用两年。最小总支出20。 8.14 求图求图8-58中网络最大流，边上数为中网络最大流，边上数为(cij，fij)。解：最大流量为解：最大流量为14。 8.15 如图如图8-59，发点，发点s1，s2分别可供应分别可供应10和和15个个单位，收点单位，收点t1，t2可以接收可以接收10和和25个单位，求最大流，个单位，求最大流，边上数为边上数为cij。 解：最大流量为解：最大流量为21。 8.16 如图如图8-608-60，从，从v v0 0派车到派车到v v8 8，中间可经过，中间可经过v v1 1，v v7 7各站，若各站间道路旁的数字表示单

8、位时间各站，若各站间道路旁的数字表示单位时间内此路上所能通过的最多车辆数，问应如何派车才能内此路上所能通过的最多车辆数，问应如何派车才能使单位时间到达使单位时间到达v v8 8的车辆最多的车辆最多? ? 解：最大流量为解：最大流量为40辆。辆。 8.17 某单位招收懂俄、英、日、德、法文翻译某单位招收懂俄、英、日、德、法文翻译各各1人，有人，有5人应聘。已知：乙懂俄文，甲、乙、丙人应聘。已知：乙懂俄文，甲、乙、丙懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这法文，问这5个人是否都能得到聘书个人是否都能得到聘书?最多几人能得最多几人能得到招聘，

9、各从事哪一方面的翻译任务到招聘，各从事哪一方面的翻译任务? 解：某人懂某种语言作一条连线，权数为解：某人懂某种语言作一条连线，权数为1 1。 甲甲-英语英语 乙乙-俄语俄语 丁丁-日语日语 戊戊-法语法语最多招聘最多招聘4 4个人。个人。 8.18 甲、乙、丙、丁、戊、己甲、乙、丙、丁、戊、己6人组成一个小组，人组成一个小组，检查检查5个单位的工作，若一单位和乙、丙、丁三人有个单位的工作，若一单位和乙、丙、丁三人有工作联系，则用工作联系，则用乙，丙，丁乙，丙，丁表示，其余四个单位分表示，其余四个单位分别为别为甲，戊，己甲，戊，己，甲，乙，戊，己甲，乙，戊，己，甲，乙，丁，甲，乙，丁，己己，甲，

10、乙，丙甲，乙，丙。若到一个单位去检查工作的人必。若到一个单位去检查工作的人必须是和该单位没有联系的人，问应如何安排须是和该单位没有联系的人，问应如何安排? 解：此题应该假设解：此题应该假设1 1人只能去人只能去1 1个单位检查工作。个单位检查工作。但是一个单位可以有多人去检查。具体安排如下：但是一个单位可以有多人去检查。具体安排如下： 甲和己甲和己单位单位1、乙、乙单位单位2 、丙、丙单位单位3 、丁、丁单位单位5 、戊、戊单位单位4 。 8.19 图图8-61所示网络中，有向边旁数字为所示网络中，有向边旁数字为(cij，dij)，cij表示容量，表示容量，dij表示单位流量费用，试求从表示单

11、位流量费用，试求从vs到到vt流值为流值为6的最小费用流。的最小费用流。解：解： 最小费用为最小费用为3535。流量分布见下一个图形。流量分布见下一个图形。 8.20 某种货物由某种货物由2个仓库个仓库a1，a2运送到运送到3个配货中个配货中心心b1，b2，b3。a1，a2的库存量分别为每天的库存量分别为每天13t，9t；b1，b2，b3每天需求分别为每天需求分别为9t，5t，6t。各仓库到配。各仓库到配货中心的运输能力、单位运费如表货中心的运输能力、单位运费如表84，求运费最省，求运费最省的运输方案。的运输方案。 表表8-4运程运程运量限制运量限制(t(td)d)运费运费( (百元百元/t)

12、/t)alb1alb183alb2alb271lalb3alb3510a2b1a2b16sa2b2a2b237a2b3a2b354 解：最小费用流为解：最小费用流为105。流量分布如下：。流量分布如下： 8.21 8.21 有有5 5批货物，要用船只从批货物，要用船只从x x1 1,x,x2 2地分别运往地分别运往y y1 1,y,y2 2,y,y3 3地。规定每批货物出发日期如表地。规定每批货物出发日期如表8-58-5所示，又所示，又知船只航行所需时间知船只航行所需时间(d)(d)如表如表8-68-6所示。每批货物只需所示。每批货物只需一条船装一条船装运，在空载和重载时航行时间相同，要求制运，在空载和重载时航行时间相同，要求制定计划，以最少的船只完成这定计划，以最少的船只完成这5项运输任务。项运输任务。 表表8-5地点地点y y1 1y y2 2y y3 3x x1 15 51010/ /x x2 2/ /12121,81,8表表8-5地点地点y y1 1y y2 2y y3 3x x1 12 23 32 2x x2 2