运筹学答案学习.pptx
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间储藏室。第八章习题解答第1页/共37页 8.3 6个人围成圆圈就座，每个人恰好只与相邻者不相识，是否可以重新就座，使每 个人都与邻座认识?解：两个人认识作一条连线。第八章习题解答第2页/共37页第八章习题解答 8.4 判定图8-50中的两个图能否一笔画出，若能，则用图形表示其画法。解：(a)图都是偶点，可以一笔画出。(b)图只有两个奇点，一个奇点为起点，另一个奇点为终点。第3页/共37页 8.5 求解如图8-51所示的中国邮路问题，A点是邮局。第八章习题解答第4页/共37页第八章习题解答第5页/共37页 8.6 分别用深探法、广探法、破圈法找出图8-52所示图的一个生成树。第八章习题解答第6页/共37页第八章习题解答第7页/共37页第八章习题解答第8页/共37页第八章习题解答第9页/共37页 8.7 设计如图5-53所示的锅炉房到各座楼铺设暖气管道的路线，使管道总长度最(单位：m)。第八章习题解答第10页/共37页第八章习题解答第11页/共37页 8.8 分别用避圈法和破圈法求图8-54所示各图的最小树。第八章习题解答第12页/共37页第八章习题解答第13页/共37页 8.9 给定权数1，4，9，16，25，36，49，64，81，构造棵霍夫曼树。第八章习题解答第14页/共37页 8.10 如图8-55，v0是一仓库，v9是商店，求一条从v0到v9的最短路。第八章习题解答第15页/共37页第八章习题解答第16页/共37页 8.11 求图8-56中v1到各点的最短路。第八章习题解答第17页/共37页第八章习题解答第18页/共37页 8.12 求图8-57网络中各顶点间的最短路。第八章习题解答第19页/共37页第八章习题解答第20页/共37页第八章习题解答第21页/共37页 8.13 某设备今后五年的价格预测分别是(5，5，6，7，8)，若该设备连续使用，其第j年的维修费分别为(1，2，3，5，6)，某单位今年购进一台，问如何确定更新方案可使5年里总支出最小(不管设备使用了多少年，其残值为0)。解：最优解为：先使用两年，更新后再使用三年。或先使用三年，更新后再使用两年。最小总支出20。第八章习题解答第22页/共37页 8.14 求图8-58中网络最大流，边上数为(cij，fij)。解：最大流量为14。第八章习题解答第23页/共37页第八章习题解答第24页/共37页 8.15 如图8-59，发点S1，S2分别可供应10和15个单位，收点t1，t2可以接收10和25个单位，求最大流，边上数为cij。第八章习题解答第25页/共37页 解：最大流量为21。第八章习题解答第26页/共37页 8.16 如图8-608-60，从v v0 0派车到v v8 8，中间可经过v v1 1，v v7 7各站，若各站间道路旁的数字表示单位时间内此路上所能通过的最多车辆数，问应如何派车才能使单位时间到达v v8 8的车辆最多?第八章习题解答第27页/共37页 解：最大流量为40辆。第八章习题解答第28页/共37页 8.17 某单位招收懂俄、英、日、德、法文翻译各1人，有5人应聘。已知：乙懂俄文，甲、乙、丙懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这5个人是否都能得到聘书?最多几人能得到招聘，各从事哪一方面的翻译任务?解：某人懂某种语言作一条连线，权数为1 1。甲-英语 乙-俄语 丁-日语 戊-法语最多招聘4 4个人。第八章习题解答第29页/共37页 8.18 甲、乙、丙、丁、戊、己6人组成一个小组，检查5个单位的工作，若一单位和乙、丙、丁三人有工作联系，则用乙，丙，丁表示，其余四个单位分别为甲，戊，己，甲，乙，戊，己，甲，乙，丁，己，甲，乙，丙。若到一个单位去检查工作的人必须是和该单位没有联系的人，问应如何安排?解：此题应该假设1 1人只能去1 1个单位检查工作。但是一个单位可以有多人去检查。具体安排如下：甲和己单单位位1、乙单单位位2、丙单单位位3、丁单位单位5、戊单位单位4。第八章习题解答第30页/共37页 8.19 图8-61所示网络中，有向边旁数字为(cij，dij)，cij表示容量，dij表示单位流量费用，试求从vs到vt流值为6的最小费用流。解：最小费用为3535。流量分布见下一个图形。第八章习题解答第31页/共37页第八章习题解答第32页/共37页 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)AlB1AlB183AlB2AlB271lAlB3AlB3510A2B1A2B16SA2B2A2B237A2B3A2B354第33页/共37页 解：最小费用流为105。流量分布如下：第八章习题解答第34页/共37页 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 21 11 12 2 (提示：用Ti表示运输任务(i=1，2，3，4，5)。作二部图，凡完成Ti项任务后可继续完成Tj项任务的在Ti,Tj间连线，再求二部图的最大匹配。)第35页/共37页 解：两条船就够了。一条船完成：T T4 4T5T3；另一条船完成：T T1 1T2。第八章习题解答第36页/共37页感谢您的观看！第37页/共37页
