《运筹学习题答案第八章》由会员分享，可在线阅读，更多相关《运筹学习题答案第八章（39页珍藏版）》请在金锄头文库上搜索。
1、运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 1 17/28/20247/28/2024同样适合第三版黄皮版运筹学教程（第二版）运筹学教程（第二版）习题解答习题解答电话：电话：5108157(H)，5107443(O)E-mail: Hongwen9509_安徽大学管理学院安徽大学管理学院安徽大学管理学院安徽大学管理学院洪洪 文文运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 3 37/28/20247/28/2024第八章习题解答第八章习题解答
2、 8.1 证明在证明在9座工厂之间，不可能每座工厂只与其座工厂之间，不可能每座工厂只与其他他3座工厂有业务联系，也不可能只有座工厂有业务联系，也不可能只有4座工厂与偶数座工厂与偶数个工厂有业务联系。个工厂有业务联系。 解：将有联系的工厂做一条连线。解：将有联系的工厂做一条连线。如果仅有如果仅有9座工厂只与其他座工厂只与其他3座工厂有业务联系，座工厂有业务联系，说明顶点次数之和为说明顶点次数之和为27，矛盾。，矛盾。如果只有如果只有4座工厂与偶数个工厂有业务联系，其他座工厂与偶数个工厂有业务联系，其他5个工厂一定与奇数个工厂有业务联系，说明顶点次数个工厂一定与奇数个工厂有业务联系，说明顶点次数之
3、和还是奇数，矛盾。之和还是奇数，矛盾。运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 4 47/28/20247/28/2024 8.2 有八种化学药品有八种化学药品A、B、C、D、E、F、G、H要放进贮藏室。从安全角度考虑，下列各组药品不能要放进贮藏室。从安全角度考虑，下列各组药品不能贮存在同一室内：贮存在同一室内：AC，AF，AH，BD，BF，BH，CD，CG，DE，DG，EG，EF，FG，GH，问至少需要几间贮藏室存放这问至少需要几间贮藏室存放这些药品。些药品。 解：能贮存在同一室内的两种药品之间作一条连解：能贮存
4、在同一室内的两种药品之间作一条连线。贮存在同一室内的药品应该构成一个完全图。线。贮存在同一室内的药品应该构成一个完全图。ABG，CFH，DE构成完全图。故，存放这些药品最少构成完全图。故，存放这些药品最少需要需要3间储藏室。间储藏室。第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 5 57/28/20247/28/2024 8.3 6个人围成圆圈就座，每个人恰好只与相邻个人围成圆圈就座，每个人恰好只与相邻者不相识，是否可以重新就座，使每者不相识，是否可以重新就座，使每 个人都与邻座认个人都与邻
5、座认识识? 解：两个人认识作一条连线。解：两个人认识作一条连线。第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 6 67/28/20247/28/2024第八章习题解答第八章习题解答 8.4 判定图判定图8-50中的两个图能否一笔画出，若能，中的两个图能否一笔画出，若能，则用图形表示其画法。则用图形表示其画法。解：解： (a)图都是偶点，可以一笔画出。图都是偶点，可以一笔画出。(b)图只有图只有两个奇点，一个奇点为起点，另一个奇点为终点。两个奇点，一个奇点为起点，另一个奇点为终点。 运筹学教程
6、运筹学教程 School of ManagementSchool of Managementpage page 7 77/28/20247/28/2024 8.5 求解如图求解如图8-51所示的中国邮路问题，所示的中国邮路问题，A点是邮点是邮局。局。 第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 8 87/28/20247/28/2024第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 9 9
7、7/28/20247/28/2024 8.6 分分别别用用深深探探法法、广广探探法法、破破圈圈法法找找出出图图8-52所所示图的一个生成树。示图的一个生成树。 第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 10107/28/20247/28/2024第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 11117/28/20247/28/2024第八章习题解答第八章习题解答运筹学教程运筹学教程 S
8、chool of ManagementSchool of Managementpage page 12127/28/20247/28/2024第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 13137/28/20247/28/2024 8.7 设计如图设计如图5-53所示的锅炉房到各座楼铺设暖气所示的锅炉房到各座楼铺设暖气管道的路线，使管道总长度最管道的路线，使管道总长度最(单位：单位：m)。 第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchoo
9、l of Managementpage page 14147/28/20247/28/2024第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 15157/28/20247/28/2024 8.8 分别用避圈法和破圈法求图分别用避圈法和破圈法求图8-54所示各图的最所示各图的最小树。小树。 第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 16167/28/20247/28/2024第八章习题解答
10、第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 17177/28/20247/28/2024 8.9 给定权数给定权数1，4，9，16，25，36，49，64，81，构造，构造棵霍夫曼树。棵霍夫曼树。 第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 18187/28/20247/28/2024 8.10 如图如图8-55，v0是一仓库，是一仓库，v9是商店，求一条是商店，求一条从从v0到到v9的最短路。的最
11、短路。 第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 19197/28/20247/28/2024第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 20207/28/20247/28/2024 8.11 求图求图8-56中中v1到各点的最短路。到各点的最短路。 第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpa
12、ge page 21217/28/20247/28/2024第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 22227/28/20247/28/2024 8.12 求图求图8-57网络中各顶点间的最短路。网络中各顶点间的最短路。 第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 23237/28/20247/28/2024第八章习题解答第八章习题解答运筹学教程运筹学教程 School of Ma
13、nagementSchool of Managementpage page 24247/28/20247/28/2024第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 25257/28/20247/28/2024 8.13 某设备今后五年的价格预测分别是某设备今后五年的价格预测分别是(5，5，6，7，8)，若该设备连续使用，其第，若该设备连续使用，其第j年的维修费分别年的维修费分别为为(1，2，3，5，6)，某单位今年购进一台，问如何确，某单位今年购进一台，问如何确定更新方案可使定更新方案可使
14、5年里总支出最小年里总支出最小(不管设备使用了多不管设备使用了多少年，其残值为少年，其残值为0)。解：最优解为：先使用两年，更新后再使用三年。解：最优解为：先使用两年，更新后再使用三年。或先使用三年，更新后再使用两年。最小总支出或先使用三年，更新后再使用两年。最小总支出20。第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 26267/28/20247/28/2024 8.14 求图求图8-58中网络最大流，边上数为中网络最大流，边上数为(cij，fij)。解：最大流量为解：最大流量为14。 第
15、八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 27277/28/20247/28/2024第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 28287/28/20247/28/2024 8.15 如图如图8-59，发点，发点S1，S2分别可供应分别可供应10和和15个个单位，收点单位，收点t1，t2可以接收可以接收10和和25个单位，求最大流，个单位，求最大流，边上数为边上数为cij。 第八章习
16、题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 29297/28/20247/28/2024 解：最大流量为解：最大流量为21。第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 30307/28/20247/28/2024 8.16 如图如图8-608-60，从，从v v0 0派车到派车到v v8 8，中间可经过中间可经过v v1 1，v v7 7各站，若各站间道路旁的数字表示单位时间各站，若各站间道路
17、旁的数字表示单位时间内此路上所能通过的最多车辆数，问应如何派车才能内此路上所能通过的最多车辆数，问应如何派车才能使单位时间到达使单位时间到达v v8 8的车辆最多的车辆最多? ?第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 31317/28/20247/28/2024 解：最大流量为解：最大流量为40辆。辆。第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 32327/28/20247/28/
18、2024 8.17 某某单单位位招招收收懂懂俄俄、英英、日日、德德、法法文文翻翻译译各各1人人，有有5人人应应聘聘。已已知知：乙乙懂懂俄俄文文，甲甲、乙乙、丙丙懂懂英英文文，甲甲、丙丙、丁丁懂懂日日文文，乙乙、戊戊懂懂德德文文，戊戊懂懂法法文文，问问这这5个个人人是是否否都都能能得得到到聘聘书书?最最多多几几人人能能得得到招聘，各从事哪一方面的翻译任务到招聘，各从事哪一方面的翻译任务? 解：某人懂某种语言作一条连线，权数为解：某人懂某种语言作一条连线，权数为1 1。 甲甲-英语英语 乙乙-俄语俄语 丁丁-日语日语 戊戊-法语法语最多招聘最多招聘4 4个人。个人。第八章习题解答第八章习题解答运筹
19、学教程运筹学教程 School of ManagementSchool of Managementpage page 33337/28/20247/28/2024 8.18 甲甲、乙乙、丙丙、丁丁、戊戊、己己6人人组组成成一一个个小小组组，检检查查5个个单单位位的的工工作作，若若一一单单位位和和乙乙、丙丙、丁丁三三人人有有工工作作联联系系，则则用用乙乙，丙丙，丁丁表表示示，其其余余四四个个单单位位分分别别为为甲甲，戊戊，己己，甲甲，乙乙，戊戊，己己，甲甲，乙乙，丁丁，己己，甲甲，乙乙，丙丙。若若到到一一个个单单位位去去检检查查工工作作的的人人必必须是和该单位没有联系的人，问应如何安排须是和该单
20、位没有联系的人，问应如何安排? 解解：此此题题应应该该假假设设1 1人人只只能能去去1 1个个单单位位检检查查工工作作。但是一个单位可以有多人去检查。具体安排如下：但是一个单位可以有多人去检查。具体安排如下： 甲甲和和己己单单位位1、乙乙单单位位2 、丙丙单单位位3 、丁丁单位单位5 、戊、戊单位单位4 。第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 34347/28/20247/28/2024 8.19 图图8-61所所示示网网络络中中，有有向向边边旁旁数数字字为为(cij，dij)，ci
21、j表表示示容容量量，dij表表示示单单位位流流量量费费用用，试试求求从从vs到到vt流值为流值为6的最小费用流。的最小费用流。解：解： 最小费用为最小费用为3535。流量分布见下一个图形。流量分布见下一个图形。第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 35357/28/20247/28/2024第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 36367/28/20247/28/2024
22、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)t)AlAlB1B183AlAlB2B271lAlAlB3B3510A2A2B1B16SA2A2B2B237A2A2B3B354
23、运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 37377/28/20247/28/2024 解：最小费用流为解：最小费用流为105。流量分布如下：。流量分布如下：第八章习题解答第八章习题解答运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 38387/28/20247/28/2024 8.21 8.21 有有5 5批批货货物物，要要用用船船只只从从x x1 1,x,x2 2地地分分别别运运往往y y1 1,y,y2 2,y,y3 3地地。规规定定每
24、每批批货货物物出出发发日日期期如如表表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 21 11 12 2 (提提示示：用用Ti表表示示运运输输任任务务(i=1，2，3，4，5)。作作二二部部图图，凡凡完完成成Ti项项任任务务后后可可继继续续完完成成Tj项项任任务务的的在在Ti,Tj间间连连线线，再再求求二部图的最大匹配。二部图的最大匹配。) 运筹学教程运筹学教程 School of ManagementSchool of Managementpage page 39397/28/20247/28/2024 解：两条船就够了。解：两条船就够了。一条船完成：一条船完成：T T4 4T5T3；另一条船完成：另一条船完成：T T1 1T2 。第八章习题解答第八章习题解答
