熊伟编《运筹学》习题五详细解答.doc

习题五 5.2 用元素差额法直接给出表5-53及表5-54下列两个运输问题的近似最优解． 表5-53 B1 B2 B3 B4 B5 Ai A1 19 16 10 21 9 18 A2 14 13 5 24 7 30 A3 25 30 20 11 23 10 A4 7 8 6 10 4 42 Bj 15 25 35 20 5 表5-54 B1 B2 B3 B4 Ai A1 5 3 8 6 16 A2 10 7 12 15 24 A3 17 4 8 9 30 Bj 20 25 10 15 【解】表5-53。Z=824 表5-54 Z=495 5.3 求表5-55及表5-56所示运输问题的最优方案． （1）用闭回路法求检验数（表5-55） 表5-55 B1 B2 B3 B4 Ai A1 10 5 2 3 70 A2 4 3 1 2 80 A3 5 6 4 4 30 bj 60 60 40 20 （2）用位势法求检验数（表5-56） 表5-56 B1 B2 B3 B4 Ai A1 9 15 4 8 10 A2 3 1 7 6 30 A3 2 10 13 4 20 A4 4 5 8 3 43 bj 20 15 50 15 【解】（1） (2) 5.4 求下列运输问题的最优解 （1）C1目标函数求最小值；（2）C2目标函数求最大值 15 45 20 40 60 30 50 40 (3)目标函数最小值,B1的需求为30≤b1≤50, B2的需求为40，B3的需求为20≤b3≤60,A1不可达A4 ，B4的需求为30． 【解】（1） （2） （3）先化为平衡表 　 B11 B12 B2 B31 B32 B4 ai A1 4 4 9 7 7 M 70 A2 6 6 5 3 3 2 20 A3 8 8 5 9 9 10 50 A4 M 0 M M 0 M 40 bj 30 20 40 20 40 30 180 最优解： 5.5（1）建立数学模型 设xij(I=1,2,3;j=1,2)为甲、乙、丙三种型号的客车每天发往B1，B2两城市的台班数，则 (2)写平衡运价表 将第一、二等式两边同除以40，加入松驰变量x13,x23和x33将不等式化为等式，则平衡表为： B1 B2 B3 ai 甲 乙 丙 80 60 50 65 50 40 0 0 0 5 10 15 bj 10 15 5 为了平衡表简单，故表中运价没有乘以40，最优解不变 （3）最优调度方案： 即甲第天发5辆车到B1城市，乙每天发5辆车到B1城市，5辆车到B2城市，丙每天发10辆车到B2城市，多余5辆，最大收入为 Z=40（5×80+5×60+5×50+10×40）=54000（元） 5.6（1）设xij为第i月生产的产品第j月交货的台数，则此生产计划问题的数学模型为 （2）化为运输问题后运价表（即生产费用加上存储费用）如下，其中第5列是虚设销地费用为零，需求量为30。 1 2 3 4 5 ai 1 2 3 4 1 M M M 1.15 1.25 M M 1.3 1.4 0.87 M 1.45 1.55 1.02 0.98 0 0 0 0 65 65 65 65 bj 50 40 60 80 30 (3)用表上作业法，最优生产方案如下表： 1 2 3 4 5 ai 1 2 3 4 50 15 25 60 10 5 65 30 65 65 65 65 Bi 50 40 60 80 30 上表表明：一月份生产65台，当月交货50台；二月份交货15台,二月份生产35台，当月交货25台，四月份交货10台；三月份生产65台，当月交货60台，四月份交货5台，4月份生产65台当月交货。最小费用Z=235万元。 5.7 假设在例5.15中四种产品的需求量分别是1000、2000、3000和4000件，求最优生产配置方案． 【解】将表5-35所示的单件产品成本乘以需求量，为计算简便，从表中提出公因子1000． 　 产品1 产品2 产品3 产品4 工厂1 58 138 540 1040 工厂2 75 100 450 920 工厂3 65 140 510 1000 工厂4 82 110 600 1120 用匈牙利法得到最优表 第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2； 总成本 Z＝1000×(58＋920＋510＋110)＝1598000 注：结果与例5.15的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后最优解不变”结论成立。 5.