运筹学课后习题五.doc

习题五5.2 用元素差额法直接给出表5-52及表5-53下列两个运输问题的近似最优解表5-52B1B2B3B4B5AiA119161021918A21413524730A3253020112310A478610442Bj152535205表5-53B1B2B3B4AiA1538616A2107121524A31748930Bj20251015【解】表5-52。Z=824表5-53最优表如下，最优值Z=4955.3 求表5-54及表5-55所示运输问题的最优方案（1）用闭回路法求检验数（表5-54）表5-54B1B2B3B4aiA11052370A2431280A3564430bj60604020（2）用位势法求检验数（表5-55）表5-55B1B2B3B4aiA19154810A2317630A321013420A4458340bj20155015解（1）最优表如下，最优值Z610(2)解 最优表如下，最优值Z4455.4 求下列运输问题的最优解（1）C1目标函数求最小值； （2）C2目标函数求最大值 (3)目标函数最小值,B1的需求为30b150, B2的需求为40，B3的需求为20b360,A1不可达B4 ，B4的需求为30【解】（1）（2）（3）先化为平衡表B11B12B2B31B32B4aiA144977M70A266533220A3885991050A4M0MM0M40bj302040204030180最优解：5.5（1）建立数学模型设xij(I=1,2,3;j=1,2)为甲、乙、丙三种型号的客车每天发往B1，B2两城市的台班数，则(2)写平衡运价表将第一、二等式两边同除以40，加入松驰变量x13,x23和x33将不等式化为等式，则平衡表为：B1B2B3ai甲乙丙80605065504000051015bj10155为了平衡表简单，故表中运价没有乘以40，最优解不变（3）最优调度方案：即甲第天发5辆车到B1城市，乙每天发5辆车到B1城市，5辆车到B2城市，丙每天发10辆车到B2城市，多余5辆，最大收入为Z=40（580+560+550+1040）=54000（元）5.6（1）设xij为第i月生产的产品第j月交货的台数，则此生产计划问题的数学模型为（2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费用为零，需求量为30。12345ai12341MMM1.151.25MM1.31.40.87M1.451.551.020.98000065656565bj5040608030(3)用表上作业法，最优生产方案如下表：12345ai123450152560105653065656565Bi5040608030上表表明：一月份生产65台，当月交货50台；二月份交货15台,二月份生产35台，当月交货25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。最小费用Z=235万元。5.7 假设在例516中四种产品的需求量分别是1000、2000、3000和4000件，求最优生产配置方案【解】将表5-35所示的单件产品成本乘以需求量，为计算简便，从表中提出公因子1000 产品1产品2产品3产品4工厂1581385401040工厂275100450920工厂3651405101000工厂4821106001120用匈牙利法得到最优表第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2； 总成本Z1000(58920510110)1598000注：结果与例5.15的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后最优解不变”结论成立。5.8 求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余3人每人做一项工作 （1） 【解】最优解（2）【解】虚拟一个人，其效率取4人中最好的，构造效率表为12345甲2638415227乙2533445921丙2030475625丁2231455320戊2030415220最优解：，最优值Z=165甲戊完成工作的顺序为3、5、1、2、4，最优分配方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。5.9 求解下列最大值的指派问题： （1） 【解】 最优解（2）【解】 最优解第5人不安排工作或第1人不安排工作。表5-57 成绩表(分钟)游泳自行车长跑登山甲20433329乙15332826丙18423829丁19443227戊173430285.10 学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各