运筹学答案(第八章)市公开课一等奖百校联赛优质课金奖名师赛课获奖课件.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,运筹学教程,School of Management,page,*,*,本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。本资料仅供参考，不能作为科学依据。谢谢。本资料仅供参考，不能作为科学依据。,第八章习题解答,8.1 证实在9座工厂之间，不可能每座工厂只与其它3座工厂有业务联络，也不可能只有4座工厂与偶数个工厂有业务联络。,解：将有联络工厂做一条连线。,假如仅有9座工厂只与其它3座工厂有业务联络，说明顶点次数之和为27，矛盾。,假如只有4座工厂与偶数个工厂有业务联络，其它5个工厂一定与奇数个工厂有业务联络，说明顶点次数之和还是奇数，矛盾。,1/37,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间储备室。,第八章习题解答,2/37,8.3 6个人围成圆圈就座，每个人恰好只与相邻者不相识，是否能够重新就座，使每 个人都与邻座认识?,解：两个人认识作一条连线。,第八章习题解答,3/37,第八章习题解答,8.4 判定图8-50中两个图能否一笔画出，若能，则用图形表示其画法。,解：(a)图都是偶点，能够一笔画出。(b)图只有两个奇点，一个奇点为起点，另一个奇点为终点。,4/37,8.5 求解如图8-51所表示中国邮路问题，A点是邮局。,第八章习题解答,5/37,第八章习题解答,6/37,8.6 分别用深探法、广探法、破圈法找出图8-52所表示图一个生成树。,第八章习题解答,7/37,第八章习题解答,8/37,第八章习题解答,9/37,第八章习题解答,10/37,8.7 设计如图5-53所表示锅炉房到各座楼铺设暖气管道路线，使管道总长度最(单位：m)。,第八章习题解答,11/37,第八章习题解答,12/37,8.8 分别用避圈法和破圈法求图8-54所表示各图最小树。,第八章习题解答,13/37,第八章习题解答,14/37,8.9 给定权数1，4，9，16，25，36，49，64，81，结构棵霍夫曼树。,第八章习题解答,15/37,8.10 如图8-55，v,0,是一仓库，v,9,是商店，求一条从v,0,到v,9,最短路。,第八章习题解答,16/37,第八章习题解答,17/37,8.11 求图8-56中v,1,到各点最短路。,第八章习题解答,18/37,第八章习题解答,19/37,8.12,求图,8-57,网络中各顶点间最短路。,第八章习题解答,20/37,第八章习题解答,21/37,第八章习题解答,22/37,8.13,某设备今后五年价格预测分别是,(5,，,5,，,6,，,7,，,8),，若该设备连续使用，其第,j,年维修费分别为,(1,，,2,，,3,，,5,，,6),，某单位今年购进一台，问怎样确定更新方案可使,5,年里总支出最小,(,不论设备使用了多少年，其残值为,0),。,解：最优解为：先使用两年，更新后再使用三年。或先使用三年，更新后再使用两年。最小总支出20。,第八章习题解答,23/37,8.14 求图8-58中网络最大流，边上数为(c,ij,，f,ij,)。,解：最大流量为14。,第八章习题解答,24/37,第八章习题解答,25/37,8.15,如图,8-59,，发点,S,1,，,S,2,分别可供给,10,和,15,个单位，收点,t,1,，,t,2,能够接收,10,和,25,个单位，求最大流，边上数为,c,ij,。,第八章习题解答,26/37,解：最大流量为21。,第八章习题解答,27/37,8.16,如图8-60，从v,0,派车到v,8,，中间可经过v,1,，v,7,各站，若各站间道路旁数字表示单位时间内此路上所能经过最多车辆数，问应怎样派车才能使单位时间抵达v,8,车辆最多?,第八章习题解答,28/37,解：最大流量为40辆。,第八章习题解答,29/37,8.17,某单位招收懂俄、英、日、德、法文翻译各,1,人，有,5,人应聘。已知：乙懂俄文，甲、乙、丙懂英文，甲、丙、丁懂日文，乙、戊懂德文，戊懂法文，问这,5,个人是否都能得到聘书,?,最多几人能得到招聘，各从事哪首先翻译任务,?,解：某人懂某种语言作一条连线，权数为1。,甲-英语 乙-俄语,丁-日语 戊-法语,最多招聘4个人。,第八章习题解答,30/37,8.18,甲、乙、丙、丁、戊、己,6,人组成一个小组，检验,5,个单位工作，若一单位和乙、丙、丁三人有工作联络，则用,乙，丙，丁,表示，其余四个单位分别为,甲，戊，己,，,甲，乙，戊，己,，,甲，乙，丁，己,，,甲，乙，丙,。若到一个单位去检验工作人必须是和该单位没有联络人，问应怎样安排,?,解：此题应该假设1人只能去1个单位检验工作。不过一个单位能够有多人去检验。详细安排以下：,甲和己,单位1,、乙,单位2,、丙,单位3,、丁,单位5,、戊,单位4,。,第八章习题解答,31/37,8.19,图,8-61,所表示网络中，有向边旁数字为,(c,ij,，,d,ij,),，,c,ij,表示容量，,d,ij,表示单位流量费用，试求从,v,s,到,v,t,流值为,6,最小费用流。,解：,最小费用为35。流量分布见下一个图形。,第八章习题解答,32/37,第八章习题解答,33/37,8.20,某种货物由,2,个仓库,A,1,，,A,2,运输到,3,个配货中心,B,1,，,B,2,，,B,3,。,A,1,，,A,2,库存量分别为天天,13t,，,9t,；,B,1,，,B,2,，,B,3,天天需求分别为,9t,，,5t,，,6t,。各仓库到配货中心运输能力、单位运费如表,8,4,，求运费最省运输方案。,第八章习题解答,表8-4,运程,运量限制(td),运费(百元/t),AlB1,8,3,AlB2,7,1l,AlB3,5,10,A2B1,6,S,A2B2,3,7,A2B3,5,4,34/37,解：最小费用流为105。流量分布以下：,第八章习题解答,35/37,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,间连线，再求二部图最大匹配。,),36/37,解：两条船就够了。,一条船完成：T,4,T,5,T,3,；,另一条船完成：T,1,T,2,。,第八章习题解答,37/37,