1、二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.1 8.1 证明在证明在9 9座工厂之间，不可能每座座工厂之间，不可能每座工厂只与其他工厂只与其他3 3座工厂有业务联系，也不可能只有座工厂有业务联系，也不可能只有4 4座座工厂与偶数个工厂有业务联系。工厂与偶数个工厂有业务联系。解：将有联系的工厂做一条连线。解：将有联系的工厂做一条连线。如果仅有如果仅有9 9座工厂只与其他座工厂只与其他3 3座工厂有业务联系，座工厂有业务联系，说明顶点次数之和为说明顶点次数之和为2727，矛盾。，矛盾。如果只有如果只有4 4座工厂与偶数个工厂有业务联系，其他
2、座工厂与偶数个工厂有业务联系，其他5 5个工厂一定与奇数个工厂有业务联系，说明顶点次个工厂一定与奇数个工厂有业务联系，说明顶点次数之和还是奇数，矛盾。数之和还是奇数，矛盾。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.2 8.2 有八种化学药品有八种化学药品A A、B B、C C、D D、E E、F F、G G、H H要放进贮藏室。从安全角度考虑，下列各组药品不能要放进贮藏室。从安全角度考虑，下列各组药品不能贮存在同一室内：贮存在同一室内：ACAC，AFAF，AHAH，BDBD，BFBF，BHBH，CDCD，CGCG，DEDE，DGDG，
3、EGEG，EFEF，FGFG，GHGH，问至少需要几间贮藏室存放这些药品。，问至少需要几间贮藏室存放这些药品。解：能贮存在同一室内的两种药品之间作一条连解：能贮存在同一室内的两种药品之间作一条连线。贮存在同一室内的药品应该构成一个完全图。线。贮存在同一室内的药品应该构成一个完全图。ABGABG，CFHCFH，DEDE构成完全图。故，存放这些药品最少需要构成完全图。故，存放这些药品最少需要3 3间间储藏室。储藏室。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.3 68.3 6个人围成圆圈就座，每个人恰好只个人围成圆圈就座，每个人恰好只与相邻
4、者不相识，是否可以重新就座，使每与相邻者不相识，是否可以重新就座，使每 个人都与个人都与邻座认识邻座认识?解：两个人认识作一条连线。解：两个人认识作一条连线。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.4 8.4 判定图判定图8-508-50中的两个图能否一笔画中的两个图能否一笔画出，若能，则用图形表示其画法。出，若能，则用图形表示其画法。解：解：(a)(a)图都是偶点，可以一笔画出。图都是偶点，可以一笔画出。(b)(b)图只有图只有两个奇点，一个奇点为起点，另一个奇点为终点。两个奇点，一个奇点为起点，另一个奇点为终点。二三版兼用二三版
5、兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.5 8.5 求解如图求解如图8-518-51所示的中国邮路问所示的中国邮路问题，题，A A点是邮局。点是邮局。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.6 8.6 分别用深探法、广探法、破圈法找出分别用深探法、广探法、破圈法找出图图8-528-52所示图的一个生成树。所示图的一个生成树。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权
6、主编课后习题答案第八章八章二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.7 8.7 设计如图设计如图5-535-53所示的锅炉房到各座所示的锅炉房到各座楼铺设暖气管道的路线，使管道总长度最楼铺设暖气管道的路线，使管道总长度最(单位：单位：m)m)。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章二三版兼
7、用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.8 8.8 分别用避圈法和破圈法求图分别用避圈法和破圈法求图8-548-54所所示各图的最小树。示各图的最小树。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.9 8.9 给定权数给定权数1 1，4 4，9 9，1616，2525，3636，4949，6464，8181，构造，构造棵霍夫曼树。棵霍夫曼树。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编
8、课后习题答案第胡运权主编课后习题答案第八章八章 8.10 8.10 如图如图8-558-55，v v0 0是一仓库，是一仓库，v v9 9是商是商店，求一条从店，求一条从v v0 0到到v v9 9的最短路。的最短路。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.11 8.11 求图求图8-568-56中中v v1 1到各点的最短路。到各点的最短路。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章
9、二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.12 8.12 求图求图8-578-57网络中各顶点间的最短路。网络中各顶点间的最短路。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章091201820014020121650)0(D0912018200321436020121650)1(D0948123201820032143602012191650)2(D0948123201820032143602012191650)3(D二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡
10、运权主编课后习题答案第八章八章0948123201820032143602012191650)4(D0948123201820020503214360201219165054321)5(54321VVVVVDVVVVV二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.13 8.13 某设备今后五年的价格预测分别某设备今后五年的价格预测分别是是(5(5，5 5，6 6，7 7，8)8)，若该设备连续使用，其第，若该设备连续使用，其第j j年的年的维修费分别为维修费分别为(1(1，2 2，3 3，5 5，6)6)，某单位今年购进一，某单位今年购进
11、一台，问如何确定更新方案可使台，问如何确定更新方案可使5 5年里总支出最小年里总支出最小(不管不管设备使用了多少年，其残值为设备使用了多少年，其残值为0)0)。解：最优解为：先使用两年，更新后再使用三年。解：最优解为：先使用两年，更新后再使用三年。或先使用三年，更新后再使用两年。最小总支出或先使用三年，更新后再使用两年。最小总支出2020。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.14 8.14 求图求图8-588-58中网络最大流，边上数中网络最大流，边上数为为(c(cijij，f fijij)。解：最大流量为解：最大流量为1414
12、。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.15 8.15 如图如图8-598-59，发点，发点S S1 1，S S2 2分别可供应分别可供应1010和和1515个单位，收点个单位，收点t t1 1，t t2 2可以接收可以接收1010和和2525个单位，求个单位，求最大流，边上数为最大流，边上数为c cijij。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 解：最大流量为解：最大流量为2
13、121。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.16 8.16 如图如图8-608-60，从，从v v0 0派车到派车到v v8 8，中间，中间可经过可经过v v1 1，v v7 7各站，若各站间道路旁的数字表示单各站，若各站间道路旁的数字表示单位时间内此路上所能通过的最多车辆数，问应如何派位时间内此路上所能通过的最多车辆数，问应如何派车才能使单位时间到达车才能使单位时间到达v v8 8的车辆最多的车辆最多?二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 解：最大流量为解：最大流量为
14、4040辆。辆。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.17 8.17 某单位招收懂俄、英、日、德、法文某单位招收懂俄、英、日、德、法文翻译各翻译各1 1人，有人，有5 5人应聘。已知：乙懂俄文，甲、乙、人应聘。已知：乙懂俄文，甲、乙、丙懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊丙懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这懂法文，问这5 5个人是否都能得到聘书个人是否都能得到聘书?最多几人能最多几人能得到招聘，各从事哪一方面的翻译任务得到招聘，各从事哪一方面的翻译任务?解：某人懂某种语言作一条连线，权数为解：某人懂某种语
15、言作一条连线，权数为1 1。甲甲-英语英语 乙乙-俄语俄语 丁丁-日语日语 戊戊-法语法语最多招聘最多招聘4 4个人。个人。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.18 8.18 甲、乙、丙、丁、戊、己甲、乙、丙、丁、戊、己6 6人组成一个小人组成一个小组，检查组，检查5 5个单位的工作，若一单位和乙、丙、丁三个单位的工作，若一单位和乙、丙、丁三人有工作联系，则用人有工作联系，则用 乙，丙，丁乙，丙，丁 表示，其余四个单表示，其余四个单位分别为位分别为 甲，戊，己甲，戊，己，甲，乙，戊，己甲，乙，戊，己，甲，甲，乙，丁，己乙，丁，己
16、，甲，乙，丙甲，乙，丙。若到一个单位去检查。若到一个单位去检查工作的人必须是和该单位没有联系的人，问应如何安工作的人必须是和该单位没有联系的人，问应如何安排排?解：此题应该假设解：此题应该假设1 1人只能去人只能去1 1个单位检查工作。个单位检查工作。但是一个单位可以有多人去检查。具体安排如下：但是一个单位可以有多人去检查。具体安排如下：甲和己甲和己单位单位1 1、乙、乙单位单位2 2 、丙、丙单位单位3 3 、丁丁单位单位5 5 、戊、戊单位单位4 4 。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.19 8.19 图图8-618-61
17、所示网络中，有向边旁数字为所示网络中，有向边旁数字为(c(cijij，d dijij)，c cijij表示容量，表示容量，d dijij表示单位流量费用，试表示单位流量费用，试求从求从v vs s到到v vt t流值为流值为6 6的最小费用流。的最小费用流。解：解：最小费用为最小费用为3535。流量分布见下一个图形。流量分布见下一个图形。二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 8.20 8.20 某种货物由某种货物由2 2个仓库个仓库A A1
18、 1，A A2 2运送到运送到3 3个配货个配货中心中心B B1 1，B B2 2，B B3 3。A A1 1，A A2 2的库存量分别为每天的库存量分别为每天13t13t，9t9t；B B1 1，B B2 2，B B3 3每天需求分别为每天需求分别为9t9t，5t5t，6t6t。各仓库到配。各仓库到配货中心的运输能力、单位运费如表货中心的运输能力、单位运费如表8 84 4，求运费最省，求运费最省的运输方案。的运输方案。表表8-4运程运程运量限制运量限制(t(td)d)运费运费(百元百元/t)/t)AlB1AlB183AlB2AlB271lAlB3AlB3510A2B1A2B16SA2B2A2
19、B237A2B3A2B354二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 解：最小费用流为解：最小费用流为105105。流量分布如下：。流量分布如下：二三版兼用二三版兼用运筹学教程运筹学教程胡运权主编课后习题答案第胡运权主编课后习题答案第八章八章 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
20、-6所示。每批货物只所示。每批货物只需一条船装运，在空载和重载时航行时间相同，要求需一条船装运，在空载和重载时航行时间相同，要求制定计划，以最少的船只完成这制定计划，以最少的船只完成这5 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 21 11 12 2 (提示：用提示：用Ti表示运输任务表示运输任务(i=1，2，3，4，5)。作二部。作二部图，凡完成图，凡完成Ti项任务后可继续完成项任务后可继续完成Tj项任务的在项任务的在Ti,Tj间连线，间连线，再求二部图的最大匹配。再求二部图的最大匹配。)
