运筹学第五六七八章答案.docx

1、运筹学第五六七八章答案运筹学第五、六、七、八章答案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-

2、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

3、60 30 50 40 (3)目标函数最小值,B1的需求为30b150, B2的需求为40，B3的需求为20b360,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)写平衡运价表

4、将第一、二等式两边同除以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（580+560+550+1040）=54000（元） 5.6（1）设xij为第i月生产的产品第j月交货的台数，则此生产计划问题的数学模型为 （2）化为运输问题后运价表（即生产费

5、用加上存储费用）如下，其中第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台

6、；三月份生产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； 总

7、成本 Z1000(58920510110)1598000 注：结果与例5.15的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后最优解不变”结论成立。5.8 求解下列最小值的指派问题，其中第（2）题某人要作两项工作，其余3人每人做一项工作 （1） 【解】最优解 （2） 【解】虚拟一个人，其效率取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 最优解：甲戊完成工作的顺序为3、5、1、2、4，最优值Z=165 最优分配

8、方案：甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。5.9 求解下列最大值的指派问题： （1） 【解】最优解 （2） 【解】最优解 第5人不安排工作。表5-58 成绩表(分钟) 游泳 自行车 长跑 登山 甲 20 43 33 29 乙 15 33 28 26 丙 18 42 38 29 丁 19 44 32 27 戊 17 34 30 28 5.10 学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表5-58所示如何从中选拔一个接力队，使预期的比赛成绩最好 【解】设xij为第i人参加第j项目的状态，则数学模型为 接力队最优组合

9、 乙 长跑 丙 游泳 丁 登山 戊 自行车 甲淘汰。预期时间为107分钟。习题六 图639 6.1如图639所示，建立求最小部分树的01整数规划数学模型。【解】边i，j的长度记为cij，设 数学模型为： 图640 6.2如图640所示，建立求v1到v6的最短路问题的01整数规划数学模型。【解】弧(i，j)的长度记为cij，设 数学模型为： 6.3如图640所示，建立求v1到v6的最大流问题的线性规划数学模型。【解】 设xij为弧（i,j）的流量，数学模型为 6.4求图641的最小部分树。图6-41（a）用破圈法,图6-41（b）用加边法。图641 【解】图6-41（a），该题有4个解，最小树长

10、为21，其中一个解如下图所示。图6-41（b），最小树长为20。最小树如下图所示。6.5 某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。根据勘测，10个村之间修建公路的费用如表6-20所示。乡镇府如何选择修建公路的路线使总成本最低。表6-20 两村庄之间修建公路的费用(万元) 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 12.8 10.5 9.6 8.5 7.7 13.8 12.7 13.1 12.6 11.4 13.9 11.2 8.6 7.5 8.3 14.8 15.7 8.5 9.6 8.9 8.0 13.2 1

11、2.4 10.5 9.3 8.8 12.7 14.8 12.7 13.6 15.8 9.8 8.2 11.7 13.6 9.7 8.9 10.5 13.4 14.6 9.1 10.5 12.6 8.9 8.8 【解】属于最小树问题。用加边法，得到下图所示的方案。最低总成本74.3万元。6.6在图642中，求A到H、I的最短路及最短路长，并对图(a)和(b)的结果进行比较。图642 【解】图642(a): A到H的最短路PAH=A,B,F,H,A,C,F,H最短路长22；A到I的最短路PAI=A,B,F,I,A,C,F,I最短路长21。对于图642(b)： A到H的最短路PAH=A,C,G,F,

12、H,最短路长21；A到I的最短路PAI=A,C,G,F,I,最短路长20； 结果显示有向图与无向图的结果可能不一样。6.7已知某设备可继续使用5年，也可以在每年年末卖掉重新购置新设备。已知5年年初购置新设备的价格分别为3.5、3.8、4.0、4.2和4.5万元。使用时间在15年内的维护费用分别为0.4、0.9、1.4、2.3和3万元。试确定一个设备更新策略，使5年的设备购置和维护总费用最小。【解】设点vj为第j年年初购置新设备的状态，（i，j）为第i年年初购置新设备使用到第j年年初，弧的权为对应的费用（购置费维护费），绘制网络图并计算，结果见下图所示。总费用最小的设备更新方案为：第一种方案，第

13、1年购置一台设备使用到第5年年末；第二种方案，第1年购置一台设备使用到第2年年末，第3年年初更新后使用到第5年年末。总费用为11.5万元。图643 6.8图643是世界某6大城市之间的航线，边上的数字为票价（百美元），用Floyd算法设计任意两城市之间票价最便宜的路线表。【解】教师可利用模板求解：datachpt6ch6.xls L1 v1 v2 v3 v4 v5 v6 v1 0 8.8 9 5.6 8 6 v2 8.8 0 10 5 100 4 v3 9 10 0 3 4.8 14 v4 5.6 5 3 0 12 100 v5 8 100 4.8 12 0 9 v6 6 4 14 100 9

14、 0 L2 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 14 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4 14 9 9 0 L3 v1 v2 v3 v4 v5 v6 v1 0 8.8 8.6 5.6 8 6 v2 8.8 0 8 5 13 4 v3 8.6 8 0 3 4.8 12 v4 5.6 5 3 0 7.8 9 v5 8 13 4.8 7.8 0 9 v6 6 4 12 9 9 0 最优票价表： v1 v2 v3 v4 v5 v6 v1

15、 0 8.8 8.6 5.6 8 6 v2 0 8 5 13 4 v3 0 3 4.8 12 v4 0 7.8 9 v5 0 9 v6 0 v1、v2、v6到各点的最优路线图分别为： 6.9 设图643是某汽车公司的6个零配件加工厂，边上的数字为两点间的距离(km)。现要在6个工厂中选一个建装配车间。（1）应选那个工厂使零配件的运输最方便。（2）装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨，运价为2元/吨公里。应选那个工厂使总运费最小。【解】(1)利用习题6.8表L3的结果 v1 v2 v3 v4 v5 v6 Max v1 0 8.8 8.6

16、 5.6 8 6 8.8 v2 8.8 0 8 5 13 4 12.8 v3 8.6 8 0 3 4.8 12 12 v4 5.6 5 3 0 7.8 9 9 v5 8 13 4.8 7.8 0 9 12.8 v6 6 4 12 9 9 0 12 选第1个工厂最好。(2)计算单件产品的运价，见下表最后一行。计算单件产品的运费，见下表最后一列。v1 v2 v3 v4 v5 v6 单件产品运费 v1 0 8.8 8.6 5.6 8 6 84.88 v2 8.8 0 8 5 13 4 89.16 v3 8.6 8 0 3 4.8 12 82.16 v4 5.6 5 3 0 7.8 9 71.96 v

17、5 8 13 4.8 7.8 0 9 81.92 v6 6 4 12 9 9 0 82.2 运价 1 1.2 1.6 2.6 3.2 3.4 选第4个工厂最好。图644 6.10 如图644，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量。【解】给出初始流如下 第一轮标号：得到一条增广链，调整量等于5，如下图所示 调整流量。第二轮标号：得到一条增广链，调整量等于2，如下图所示 调整流量。第三轮标号：得到一条增广链，调整量等于3，如下图所示 调整流量。第四轮标号：不存在增广链，最大流量等于45，如下图所示 取 ，最小截集(3,7),(4,7),(6,9),(8,10)，最小截

18、量等于45。6.11 将3个天然气田A1、A2、A3的天然气输送到2个地区C1、C2，中途有2个加压站B1、B2，天然气管线如图645所示。输气管道单位时间的最大通过量cij及单位流量的费用dij标在弧上(cij, dij)。求(1)流量为22的最小费用流；（2）最小费用最大流。图645 【解】虚拟一个发点和一个收点 T6.111 得到流量v22的最小费用流，最小费用为271。求解过程参看第4章PPT文档习题答案。T6.1113 最小费用最大流如下图，最大流量等于27，总费用等于351。6.12如图643所示，（1）求解旅行售货员问题；（2）求解中国邮路问题。图6-43 【解】（1）旅行售货员

19、问题。距离表C 1 2 3 4 5 6 1 8.8 9 5.6 8 6 2 8.8 10 5 4 3 9 10 3 4.8 14 4 5.6 5 3 12 5 8 4.8 12 9 6 6 4 14 9 在C中行列分别减除对应行列中的最小数，得到距离表C1。距离表C1 1 2 3 4 5 6 1 3.2 3.4 0 0.6 0.4 2 2.8 6 1 0 3 4 7 0 0 11 4 0.6 2 0 7.2 5 1.2 0 7.2 9 6 0 0 10 3.2 由距离表C1，v1到v4， H1= v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1, C(H1)=5.6+3+4.8+9+4+8

20、.8=35.2 去掉第1行第四列，d41=，得到距离表C2。得到距离表C2 1 2 3 5 6 2 2.8 6 0 3 4 7 0 11 4 2 0 7.2 5 1.2 0 9 6 0 0 10 3.2 距离表C2的每行每列都有零，H2= H1= v1, v4 ,v3 ,v5 ,v6 ,v2 ,v1就是总距离最小的Hamilton回路，C(H1) =35.2。(2)中国邮路问题。虚拟一条边 取回路H1v1，v3，v4，C(H1)=9+5+3=17,C(v1，v3)=9 C(H1)/2，调整回路。所有回路满足最短回路的准则，上图是最短的欧拉回路，其中边(v1, v4)和(v4, v3)各重复一次

21、。习题七 7.2(1)分别用节点法和箭线法绘制表7-16的项目网络图，并填写表中的紧前工序。(2) 用箭线法绘制表7-17的项目网络图，并填写表中的紧后工序 表7-16 工序 A B C D E F G 紧前工序 A C A F、D、B、E 紧后工序 D,E G E G G G 表7-17 工序 A B C D E F G H I J K L M 紧前工序 - - - B B A,B B D,G C,E,F,H D,G C,E I J,K,L 紧后工序 F E,D,F,G I,K H,J I,K I H,J I L M M M 【解】（1）箭线图： 节点图： （2）箭线图： 7.3根据项目工序

22、明细表7-18： （1）画出网络图。（2）计算工序的最早开始、最迟开始时间和总时差。（3）找出关键路线和关键工序。表7-18 工序 A B C D E F G 紧前工序 - A A B,C C D,E D,E 工序时间（周） 9 6 12 19 6 7 8 【解】(1)网络图 (2)网络参数 工序 A B C D E F G 最早开始 0 9 9 21 21 40 40 最迟开始 0 15 9 21 34 41 40 总时差 0 6 0 0 13 1 0 (3)关键路线：；关键工序：A、C、D、G；完工期：48周。7.4 表7-19给出了项目的工序明细表。表7-19 工序 A B C D E

23、F G H I J K L M N 紧前工序 - - - A,B B B,C E D,G E E H F,J I,K,L F,J,L 工序时间(天) 8 5 7 12 8 17 16 8 14 5 10 23 15 12 （1）绘制项目网络图。（2）在网络图上求工序的最早开始、最迟开始时间。（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差。（4）找出所有关键路线及对应的关键工序。（5）求项目的完工期。【解】(1)网络图 （2）工序最早开始、最迟开始时间 （3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差 工序 t TES TEF TLS TLF 总时差S 自由时差F

24、A 8 0 8 9 17 9 0 B 5 0 5 0 5 0 0 C 7 0 7 7 7 0 0 D 12 8 20 17 29 9 9 E 8 5 13 5 13 0 0 F 17 7 24 7 24 0 0 G 16 13 29 13 29 0 0 H 8 29 37 29 37 0 0 I 14 13 27 33 47 20 20 J 5 13 18 19 24 6 6 K 10 37 47 37 47 0 0 L 23 24 47 24 47 0 0 M 15 47 62 47 62 0 0 N 12 47 59 50 62 3 3 (4)关键路线及对应的关键工序 关键路线有两条，第一

25、条：；关键工序：B,E,G,H,K,M 第二条：；关键工序：C,F,L,M （5）项目的完工期为62天。7.5已知项目各工序的三种估计时间如表7-20所示。求： 表7-20 工序 紧前工序 工序的三种时间（小时） a m b A 9 10 12 B A 6 8 10 C A 13 15 16 D B 8 9 11 E B,C 15 17 20 F D,E 9 12 14 （1）绘制网络图并计算各工序的期望时间和方差。（2）关键工序和关键路线。（3）项目完工时间的期望值。（4）假设完工期服从正态分布，项目在56小时内完工的概率是多少。（5）使完工的概率为0.98，最少需要多长时间。【解】（1）网

26、络图 工序 紧前工序 工序的三种时间（小时） 期望值 方差 a m b A 9 10 12 10.17 0.25 B A 6 8 10 8 0.4444 C A 13 15 16 14.83 0.25 D B 8 9 11 9.167 0.25 E B,C 15 17 20 17.17 0.6944 F D,E 9 12 14 11.83 0.6944 (2)关键工序：A,C,E,F；关键路线： (3) 项目完工时间的期望值：10.17+14.83+17.17+11.8354(小时) 完工期的方差为0.25+0.25+0.6944+0.69441.8889 (4)X0=56， 56天内完工的概

27、率为0.927 (5) p=0.98， 要使完工期的概率达到0.98，则至少需要56.82小时。7.6 表7-21给出了工序的正常、应急的时间和成本。表7-21 工序 紧前工序 时间(天) 成本 时间的最大缩量(天) 应急增加成本（万元/天） 正常 应急 正常 应急 A 15 12 50 65 3 5 B A 12 10 100 120 2 10 C A 7 4 80 89 3 3 D B,C 13 11 60 90 2 15 E D 14 10 40 52 4 3 F C 16 13 45 60 3 5 G E,F 10 8 60 84 2 12 （1）绘制项目网络图，按正常时间计算完成项目

28、的总成本和工期。（2）按应急时间计算完成项目的总成本和工期。（3）按应急时间的项目完工期，调整计划使总成本最低。（4）已知项目缩短1天额外获得奖金4万元，减少间接费用2.5万元，求总成本最低的项目完工期。(1) 正常时间项目网络图 项目网络图 总成本为435，工期为64。(2)应急时间项目网络图 总成本为560，工期为51。(3)应急时间调整 工序C、F按正常时间施工，总成本为560-9-15536，完工期为51。(4) 总成本最低的项目完工期 工序A、E分别缩短3天，总成本为435+15+12-6.57416.5，完工期为57。7.7继续讨论表7-21。假设各工序在正常时间条件下需要的人员数

29、分别为9、12、12、6、8、17、14人。（1）画出时间坐标网络图 （2）按正常时间计算项目完工期，按期完工需要多少人。（3）保证按期完工，怎样采取应急措施，使总成本最小又使得总人数最少，对计划进行系统优化分析。【解】（1）正常时间的时间坐标网络图 (2) 按正常时间调整非关键工序的开工时间 (3)略，参看教材。7.8用WinQSB软件求解7.5。7.9用WinQSB软件求解7.6。习题八 8.1 在设备负荷分配问题中，n=10，a=0.7，b=0.85，g=15，h=10，期初有设备1000台。试利用公式(8.7)确定10期的设备最优负荷方案。【解】将教材中a的下标i去掉。由公式得 (g-

30、h)/g(b-a)0.2222，a0a1a21+0.70.492.192.222a0+a1a2a32.533，nt12，t=7，则16年低负荷运行，710年为高负荷运行。各年年初投入设备数如下表。年份 1 2 3 4 5 6 7 8 9 10 设备台数 1000 850 723 614 522 444 377 264 184.8 129 8.2如图84，求A到F的最短路线及最短距离。【解】A到F的最短距离为13；最短路线 A B2 C3 D2 E2 F及AC2 D2 E2 F 8.3求解下列非线性规划 (1) (2) （3） (4) (5) （6） 【解】（1）设s3=x3 , s3+x2=s

31、2，s2+x1=s1=C 则有 x3= s3 ，0x2s2，0x1s1=C 用逆推法，从后向前依次有 k3， 及最优解 x3*=s3 k2， 由 故 为极大值点。所以 及最优解x2*=s2 k=1时， ， 由，得 故 已知知x1 + x2+ x3 = C，因而按计算的顺序推算，可得各阶段的最优决策和最优解如下 ， 由s2=s1x1*=2C/3， 由s3=s2x2*=C/3， 最优解为： 【解】（2）设s3=x3 , s3+x2=s2，s2+x1=s1=C 则有 x3= s3 ，0x2s2，0x1s1=C 用逆推法，从后向前依次有 k3， 及最优解 x3*=s3 k2， 由 =40,故 x2=为极小值点。因而有 k1时， 由知 得到最优解 【解】(3) 设s3=x3 , s3+x2=s2，s2+x1=s1=10 则有 x3= s3 ，0x2s2，0x1s1=10 用逆推法，从后向前依次有 k3时， 及最优解 x3=s3 k2时， 而 。讨论端点：当 x2=0时, x2= s2时 如果s23时, k1时， 同理有, x1=0, f1（s1）= s12= 100，x1= s1, f1（s1）= 2s1= 20 (舍去) 得到最优解 【解】(4) 设s3=x3 ,2s