运筹学第5章答案

5.2 用元素差额法直接给出表5-52及表5-53下列两个运输问题的近似最优解． 表5-52 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-53 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-52。Z=824

表5-53最优表如下，最优值Z=495 5.3 求表5-54及表5-55所示运输问题的最优方案． （1）用闭回路法求检验数（表5-54） 表5-54 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-55） 表5-55 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 40 bj 20 15 50 15 解（1）最优表如下，最优值Z＝610

(2)解 最优表如下，最优值Z＝445 5.4 求下列运输问题的最优解 （1）C1目标函数求最小值； （2）C2目标函数求最大值

135925064852511131273015452040C 271015206014139630587109060305040C



(3)目标函数最小值,B1的需求为30≤b1≤50, B2的需求为40，B3的需求为20≤b3≤60,A1不可达B4 ，B4的需求为30．

502070109482356794

【解】（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两城市的台班数，则

111221223132112131122232111211223132

max40(806560505040)404040400404040600510150(1,2,3;1,2)ijZxxxxxxxxxxxxxxxxxxxij













(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月交货的台数，则此生产计划问题的数学模型为

1112131421441121314112223242132333431424344411121314212223243132333441424344

min1.151.31.450.9850406080656565650,(,ijZxxxxMxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxij1,,4)

（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－16中四种产品的需求量分别是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.8 求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余3人每人做一项工作．

（1）20151062510183526181220159612＝C 【解】最优解 11,4311XZ



（2）2053453122255647302021594433252752413826＝C 【解】虚拟一个人，其效率取4人中最好的，构造效率表为 1 2 3 4 5 甲 26 38 41 52 27 乙 25 33 44 59 21 丙 20 30 47 56 25 丁 22 31 45 53 20 戊 20 30 41 52 20

最优解：11111X，最优值Z=165

甲～戊完成工作的顺序为3、5、1、2、4， 最优分配方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。

5.9 求解下列最大值的指派问题：

（1）26128161913131820101415176910＝C

【解】 26128161913131820101415176910＝C 最优解11,6411XZ （2）【解】 9651096510164854085167109127109121661571661571616986898681671011600946012168110515111096740250401019003020078108007380C－＝ 094600835051511105140100250403504130200402010738006270 04310510060310018020502250



最优解111144111111XXZ或； 第5人不安排工作或第1人不安排工作。 5.10 学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表5-57所示．如何从中选拔一个接力队，使预期的比赛成绩最好． 【解】设xij为第i人参加第j项目的状态，则数学模型为

1112131454111213142122232431323334414243445152535411213141511222324252132333435314243444min204333292811111111Zxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx54101,1,2,,5;1,2,3,4ijxij

或

接力队最优组合 乙 长跑 丙 游泳 丁 登山 戊 自行车 甲淘汰。预期时间为107分钟。

表5-57 成绩表(分钟) 游泳 自行车 长跑 登山 甲 20 43 33 29

乙 15 33 28 26 丙 18 42 38 29

丁 19 44 32 27 戊 17 34 30 28