运筹学期末考试答案(考试A).doc

三、已知某项工程的各道工序顺序及用时如图所示（单位：天），其中弧的上方为各工序的代号，下方为完成此工序所需的时间。（共10分）12346785a20b40echj30ig2015d1020f101525（1）试求下列工序的最早开始时间，最迟开始时间，最早完成时间及最迟完成时间，并求出该工序的时差，填入下表。(6分)工序最早开始时间(ES)最迟开始时间(LS)最早完成时间(EF)最迟完成时间(LF)时差c202040400e203045555h4560607515i555575750（2）试求完成此工程所需的最少时间，并列出该项工程的关键工序。 （6分）a.c.g.i.j最少时间为105天四、已知线性规划问题: （共15分） (1)将上述线性规划问题变换为标准型； （5分）(2)用单纯形求解该线性规划问题，填满下表。（8分）基CBx1x2x3x4x5b比值35000x3x4x50001030221000100014121869cj-zj35000x3x2x505010301010001/2-100146642cj-zj300-5/20x3x2x10530010101001/31/2-1/3-1/301/3262cj-zj000-3/2-1(3) 写出该线性规划的最优解和最优目标函数值。（2分）最优解为x1=2, x2=6，最优值为z=36五、某城市建设了一个从湖中（V1）抽水到城市的蓄水池（V8）的管道系统，如图所示。试求由湖到蓄水池的最大流量。（共10分）(提示：无需图上标注，但要写出每次找到的可增广链及可调整值)V8(9,6)V1V2V4V7V3V5V6(4,3)(10,5)(3,3)(9,9)(11,3)(12,8)(10,8)(6,4)(9,4)(6,1)(4,2)(4,0)(1)通过标号求寻找可增广链V1-V2-V5-V8；调整值为1(2)通过标号求寻找可增广链V1-V3-V6-V5-V8；调整值为2(3)通过标号求寻找可增广链V1-V4-V7-V3-V6-V8；调整值为1最大流为22六、某防疫站每年需用某种疫苗1500支，每次订购费50元，每月补充速度为2500支，每支每月的保管费为1.25元，每支每月缺货费为2元。（1）该防疫站为把成本降到最低，每次的生产量和间隔时间为多少；（4分）（2）其他条件不变，如不允许缺货，每次的生产量和间隔时间为多少；（4分）（3）试比较上述两种情况下，防疫站的最低月总成本何时更低，并说明理由。（2分）（共10分）由于不允许缺货相对允许缺货来说约束更为严格，所以第一种情况的最低月总成本不高于第二种情况。七、已知运输问题的供需关系表与单位运价。（共20分） (1) 以最小元素法确定初始基本可行解,并以闭回路法判别；（6分） 销地产地B1B2B3B4产量A1573123515213514A212825203010155-4A315181110351724530销量10154530(2) 求该运输问题的最优解,并以闭回路法判别；（6分） 销地产地B1B2B3B4产量A1573123511173510A2128252030101545A3151811103513101025销量10154530(3) 由于市场变化，经研究制定新的运输方案时要考虑以下目标。（8分）第一优先级：总运费不超过1300元。第二优先级：第B3销地为重要市场，必须满足其需要；第三优先级：供应B4销地的产品中，工厂A1的产品控制在20个单位；第四优先级：为兼顾一般，至少满足B1和B2销地需求率的80%；第五优先级：工厂A3的不得超负荷生产；试建立该目标规划问题的数学模型（不需要求解）。提示：设xij表示从产地Ai运输到销地Bj的运输量（i=1,2,3;j=1,2,3,4），如x12表示从A1运输到B2的物品数量。Min f=P1（d1+）+ P2（d2-）+ P3（d3-+d3+）+ P4（d4-+d5-）+ P5（d6_）5x11+7x12+3x13+12x14+12x21+8x22+25x23+20x24+15x31+18x32+11x33+10x34 +d1-+d1+=1300x13+ x23+ x33+ d2-+ d2+= 45 x14+ d3-+ d3+= 20x11+ x21+ x31+ d4-+ d4+= 8 x12+ x22+ x32+ d5-+ d5+= 12x31+ x32+ x33+ d6-+ d6+= 35 xij,dk-, dk+ 0 (i=1,2 j=1,2,3 k=1,2,3,4,5,6)八、某公司职员因工作需要购买了一台摩托车，4年内他可以连续使用或于任一年末卖掉旧车，购买新的。已知于j年初购置一台新摩托车的价格和不同役龄摩托车的处理价格如表所示。又新摩托车第一年运行及维修费为0.2万元，使用13年后机器每年的运行及维修费用分别为0.6，0.9，1.1万元。试据此确定该人最优的更新策略，使4年内用于摩托车的更换、购买及运行维修的总费用为最省。（共15分） 单位：万元J第一年第二年第三年第四年年初购置价1.51.61.92.3使用j年后的处理价1.10.80.60.4（1）将该摩托车更新问题转化为最短路问题，填写权数表：(5分) 单位：万元v1V2v3v4v5v10.61.52.63.9v20.71.62.7v31.01.9v41.4（2）画出最短路问题的图示，以Dijkstra法求最短路，并确定最优的更新策略。（