运筹学习题答案(第八章).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,运筹学教程,School of Management,page,*,*,同样适合第三版黄皮版,运筹学教程（第二版）习题解答,电话：,5108157(,H),，,5107443(O),E-mail:Hongwen9509_,cn,sina,.com,安徽大学管理学院,洪 文,第八章习题解答,8.1,证明在,9,座工厂之间，不可能每座工厂只与其他,3,座工厂有业务联系，也不可能只有,4,座工厂与偶数个工厂有业务联系。,解：将有联系的工厂做一条连线。,如果仅有,9,座工厂只与其他,3,座工厂有业务联系，说明顶点次数之和为,27,，矛盾。,如果只有,4,座工厂与偶数个工厂有业务联系，其他,5,个工厂一定与奇数个工厂有业务联系，说明顶点次数之和还是奇数，矛盾。,8.2,有八种化学药品,A,、,B,、,C,、,D,、,E,、,F,、,G,、,H,要放进贮藏室。从安全角度考虑，下列各组药品不能贮存在同一室内：,A,C,，,A,F,，,A,H,，,B,D,，,B,F,，,B,H,，,C,D,，,C,G,，,D,E,，,D,G,，,E,G,，,E,F,，,F,G,，,G,H,，,问至少需要几间贮藏室存放这些药品。,解：能贮存在同一室内的两种药品之间作一条连线。贮存在同一室内的药品应该构成一个完全图。,ABG,，,CFH,，,DE,构成完全图。故，存放这些药品最少需要,3,间储藏室。,第八章习题解答,8.3 6,个人围成圆圈就座，每个人恰好只与相邻者不相识，是否可以重新就座，使每,个人都与邻座认识,?,解：两个人认识作一条连线。,第八章习题解答,第八章习题解答,8.4,判定图,8-50,中的两个图能否一笔画出，若能，则用图形表示其画法。,解：,(,a),图都是偶点，可以一笔画出。,(,b),图只有两个奇点，一个奇点为起点，另一个奇点为终点。,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,，构造,棵霍夫曼树。,第八章习题解答,8.10,如图,8-55,，,v,0,是一仓库，,v,9,是商店，求一条从,v,0,到,v,9,的最短路。,第八章习题解答,第八章习题解答,8.11,求图,8-56,中,v,1,到各点的最短路。,第八章习题解答,第八章习题解答,8.12,求图,8-57,网络中各顶点间的最短路。,第八章习题解答,第八章习题解答,第八章习题解答,8.13,某设备今后五年的价格预测分别是,(5,，,5,，,6,，,7,，,8),，若该设备连续使用，其第,j,年的维修费分别为,(1,，,2,，,3,，,5,，,6),，某单位今年购进一台，问如何确定更新方案可使,5,年里总支出最小,(,不管设备使用了多少年，其残值为,0),。,解：最优解为：先使用两年，更新后再使用三年。或先使用三年，更新后再使用两年。最小总支出,20,。,第八章习题解答,8.14,求图,8-58,中网络最大流，边上数为,(,c,ij,，,f,ij,),。,解：最大流量为,14,。,第八章习题解答,第八章习题解答,8.15,如图,8-59,，发点,S,1,，,S,2,分别可供应,10,和,15,个单位，收点,t,1,，,t,2,可以接收,10,和,25,个单位，求最大流，边上数为,c,ij,。,第八章习题解答,解：最大流量为,21,。,第八章习题解答,8.16,如图,8-60,，从,v,0,派车到,v,8,，,中间可经过,v,1,，,，,v,7,各站，若各站间道路旁的数字表示单位时间内此路上所能通过的最多车辆数，问应如何派车才能使单位时间到达,v,8,的车辆最多,?,第八章习题解答,解：最大流量为,40,辆。,第八章习题解答,8.17,某单位招收懂俄、英、日、德、法文翻译各,1,人，有,5,人应聘。已知：乙懂俄文，甲、乙、丙懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这,5,个人是否都能得到聘书,?,最多几人能得到招聘，各从事哪一方面的翻译任务,?,解：某人懂某种语言作一条连线，权数为,1,。,甲,-,英语 乙,-,俄语,丁,-,日语 戊,-,法语,最多招聘,4,个人。,第八章习题解答,8.18,甲、乙、丙、丁、戊、己,6,人组成一个小组，检查,5,个单位的工作，若一单位和乙、丙、丁三人有工作联系，则用,乙，丙，丁,表示，其余四个单位分别为,甲，戊，己,，,甲，乙，戊，己,，,甲，乙，丁，己,，,甲，乙，丙,。若到一个单位去检查工作的人必须是和该单位没有联系的人，问应如何安排,?,解：此题应该假设,1,人只能去,1,个单位检查工作。但是一个单位可以有多人去检查。具体安排如下：,甲和己,单位,1,、乙,单位,2,、丙,单位,3,、丁,单位,5,、戊,单位,4,。,第八章习题解答,8.19,图,8-61,所示网络中，有向边旁数字为,(,c,ij,，,d,ij,),，,c,ij,表示容量，,d,ij,表示单位流量费用，试求从,v,s,到,v,t,流值为,6,的最小费用流。,解：,最小费用为,35,。流量分布见下一个图形。,第八章习题解答,第八章习题解答,8.20,某种货物由,2,个仓库,A,1,，,A,2,运送到,3,个配货中心,B,1,，,B,2,，,B,3,。,A,1,，,A,2,的库存量分别为每天,13,t,，,9t,；,B,1,，,B,2,，,B,3,每天需求分别为,9,t,，,5t,，,6t,。,各仓库到配货中心的运输能力、单位运费如表,8,4,，求运费最省的运输方案。,第八章习题解答,表,8-4,运程,运量限制(,td),运费(百元/,t),Al,B1,8,3,Al,B2,7,1l,Al,B3,5,10,A2,B1,6,S,A2,B2,3,7,A2,B3,5,4,解：最小费用流为,105,。流量分布如下：,第八章习题解答,8.21,有,5,批货物，要用船只从,x,1,x,2,地分别运往,y,1,y,2,y,3,地。规定每批货物出发日期如表,8-5,所示，又知船只航行所需时间,(,d),如表,8-6,所示。每批货物只需一条船装,运，在空载和重载时航行时间相同，要求制定计划，以最少的船只完成这,5,项运输任务。,第八章习题解答,表,8-5,地点,y,1,y,2,y,3,x,1,5,10,/,x,2,/,12,1,8,表,8-5,地点,y,1,y,2,y,3,x,1,2,3,2,x,2,1,1,2,(,提示：用,T,i,表示运输任务,(,i=1,，,2,，,3,，,4,，,5),。,作二部图，凡完成,T,i,项任务后可继续完成,T,j,项任务的在,T,i,T,j,间连线，再求二部图的最大匹配。,),解：两条船就够了。,一条船完成：,T,4,T,5,T,3,；,另一条船完成：,T,1,T,2,。,第八章习题解答,