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

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

《运筹学第五六七八章答案.docx》由会员分享，可在线阅读，更多相关《运筹学第五六七八章答案.docx（13页珍藏版）》请在冰点文库上搜索。

运筹学第五六七八章答案

运筹学第五、六、七、八章答案

5.2用元素差额法直接给出表5-53及表5-54下列两个运输问题的近似最优解．表5-53B1B2B3B4B5AiA119161021918A21413524730A3253020112310A478610442Bj152535205表5-54B1B2B3B4AiA1538616A2107121524A31748930Bj20251015【解】表5-53。

Z=824表5-54Z=4955.3求表5-55及表5-56所示运输问题的最优方案．

（1）用闭回路法求检验数（表5-55）表5-55B1B2B3B4AiA11052370A2431280A3564430bj60604020

（2）用位势法求检验数（表5-56）表5-56B1B2B3B4AiA19154810A2317630A321013420A4458343bj20155015【解】

（1）

（2）5.4求下列运输问题的最优解

（1）C1目标函数求最小值；

（2）C2目标函数求最大值1545204060305040（3）目标函数最小值,B1的需求为30≤b1≤50,B2的需求为40，B3的需求为20≤b3≤60,A1不可达A4，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（5×80+5×60+5×50+10×40）=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假设在例5.15中四种产品的需求量分别是1000、2000、3000和4000件，求最优生产配置方案．【解】将表5-35所示的单件产品成本乘以需求量，为计算简便，从表中提出公因子1000．　产品1产品2产品3产品4工厂1581385401040工厂275100450920工厂3651405101000工厂4821106001120用匈牙利法得到最优表第一个工厂加工产品1，第二工厂加工产品4，第三个工厂加工产品3，第四个工厂加工产品2；总成本Z＝1000×（58＋920＋510＋110）＝1598000注：

结果与例5.15的第2个方案相同，但并不意味着“某列（行）同乘以一个非负元素后最优解不变”结论成立。

5.8求解下列最小值的指派问题，其中第

（2）题某人要作两项工作，其余3人每人做一项工作．

（1）【解】最优解

（2）【解】虚拟一个人，其效率取4人中最好的，构造效率表为　12345甲2638415227乙2533445921丙2030475625丁2231455320戊2030415220最优解：

甲～戊完成工作的顺序为3、5、1、2、4，最优值Z=165最优分配方案：

甲完成第3、4两项工作，乙完成第5项工作，丙完成第1项工作，丁完成第2项工作。

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

（1）【解】最优解

（2）【解】最优解第5人不安排工作。

表5-58成绩表（分钟）游泳自行车长跑登山甲20433329乙15332826丙18423829丁19443227戊173430285.10学校举行游泳、自行车、长跑和登山四项接力赛，已知五名运动员完成各项目的成绩（分钟）如表5-58所示．如何从中选拔一个接力队，使预期的比赛成绩最好．【解】设xij为第i人参加第j项目的状态，则数学模型为接力队最优组合乙长跑丙游泳丁登山戊自行车甲淘汰。

预期时间为107分钟。

习题六图6－396.1如图6－39所示，建立求最小部分树的0－1整数规划数学模型。

【解】边[i，j]的长度记为cij，设数学模型为：

图6－406.2如图6－40所示，建立求v1到v6的最短路问题的0－1整数规划数学模型。

【解】弧（i，j）的长度记为cij，设数学模型为：

6.3如图6－40所示，建立求v1到v6的最大流问题的线性规划数学模型。

【解】设xij为弧（i,j）的流量，数学模型为6.4求图6－41的最小部分树。

图6-41（a）用破圈法,图6-41（b）用加边法。

图6－41【解】图6-41（a），该题有4个解，最小树长为21，其中一个解如下图所示。

图6-41（b），最小树长为20。

最小树如下图所示。

6.5某乡政府计划未来3年内，对所管辖的10个村要达到村与村之间都有水泥公路相通的目标。

根据勘测，10个村之间修建公路的费用如表6-20所示。

乡镇府如何选择修建公路的路线使总成本最低。

表6-20两村庄之间修建公路的费用（万元）123456789101234567891012.810.59.68.57.713.812.713.112.611.413.911.28.67.58.314.815.78.59.68.98.013.212.410.59.38.812.714.812.713.615.89.88.211.713.69.78.910.513.414.69.110.512.68.98.8【解】属于最小树问题。

用加边法，得到下图所示的方案。

最低总成本74.3万元。

6.6在图6－42中，求A到H、I的最短路及最短路长，并对图（a）和（b）的结果进行比较。

图6－42【解】图6－42（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。

对于图6－42（b）：

A到H的最短路PAH={A,C,G,F,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万元。

使用时间在1～5年内的维护费用分别为0.4、0.9、1.4、2.3和3万元。

试确定一个设备更新策略，使5年的设备购置和维护总费用最小。

【解】设点vj为第j年年初购置新设备的状态，（i，j）为第i年年初购置新设备使用到第j年年初，弧的权为对应的费用（购置费＋维护费），绘制网络图并计算，结果见下图所示。

总费用最小的设备更新方案为：

第一种方案，第1年购置一台设备使用到第5年年末；第二种方案，第1年购置一台设备使用到第2年年末，第3年年初更新后使用到第5年年末。

总费用为11.5万元。

图6－436.8图6－43是世界某6大城市之间的航线，边上的数字为票价（百美元），用Floyd算法设计任意两城市之间票价最便宜的路线表。

【解】教师可利用模板求解：

data＼chpt6＼ch6.xlsL1　v1v2v3v4v5v6v108.895.686v28.801051004v3910034.814v45.653012100v581004.81209v6641410090L2　v1v2v3v4v5v6v108.88.65.686v28.8085134v38.68034.814v45.65307.89v58134.87.809v66414990L3　v1v2v3v4v5v6v108.88.65.686v28.8085134v38.68034.812v45.65307.89v58134.87.809v66412990最优票价表：

　v1v2v3v4v5v6v108.88.65.686v2085134v3034.812v407.89v509v60v1、v2、…、v6到各点的最优路线图分别为：

6.9设图6－43是某汽车公司的6个零配件加工厂，边上的数字为两点间的距离（km）。

现要在6个工厂中选一个建装配车间。

（1）应选那个工厂使零配件的运输最方便。

（2）装配一辆汽车6个零配件加工厂所提供零件重量分别是0.5、0.6、0.8、1.3、1.6和1.7吨，运价为2元/吨公里。

应选那个工厂使总运费最小。

【解】

（1）利用习题6.8表L3的结果　v1v2v3v4v5v6Maxv108.88.65.6868.8v28.808513412.8v38.68034.81212v45.65307.899v58134.87.80912.8v6641299012选第1个工厂最好。

（2）计算单件产品的运价，见下表最后一行。

计算单件产品的运费，见下表最后一列。

v1v2v3v4v5v6单件产品运费v108.88.65.68684.88v28.808513489.16v38.68034.81282.16v45.65307.8971.96v58134.87.80981.92v6641299082.2运价11.21.62.63.23.4选第4个工厂最好。

图6－446.10如图6－44，

（1）求v1到v10的最大流及最大流量；

（2）求最小割集和最小割量。

【解】给出初始流如下第一轮标号：

得到一条增广链，调整量等于5，如下图所示调整流量。

第二轮标号：

得到一条增广链，调整量等于2，如下图所示调整流量。

第三轮标号：

得到一条增广链，调整量等于3，如下图所示调整流量。

第四轮标号：

不存在增广链，最大流量等于45，如下图所示取，最小截集{（3,7）,（4,7）,（6,9）,（8,10），最小截量等于45。

6.11将3个天然气田A1、A2、A3的天然气输送到2个地区C1、C2，中途有2个加压站B1、B2，天然气管线如图6－45所示。

输气管道单位时间的最大通过量cij及单位流量的费用dij标在弧上（cij,dij）。

求

（1）流量为22的最小费用流；

（2）最小费用最大流。

图6－45【解】虚拟一个发点和一个收点T6.11－1得到流量v＝22的最小费用流，最小费用为271。

求解过程参看第4章PPT文档习题答案。

T6.11－13最小费用最大流如下图，最大流量等于27，总费用等于351。

6.12如图6－43所示，

（1）求解旅行售货员问题；

（2）求解中国邮路问题。

图6-43【解】

（1）旅行售货员问题。

距离表C　1234561∞8.895.68628.8∞105∞43910∞34.81445.653∞12∞58∞4.812∞966414∞9∞在C中行列分别减除对应行列中的最小数，得到距离表C1。

距离表C1　1234561∞3.23.400.60.422.8∞61∞0347∞001140.620∞7.2∞51.2∞07.2∞960010∞3.2∞由距离表C1，v1到v4，H1={v1,v4,v3,v5,v6,v2,v1},C（H1）=5.6+3+4.8+9+4+8.8=35.2去掉第1行第四列，d41=∞，得到距离表C2。

得到距离表C2　1235622.8∞6∞0347∞0114∞207.2∞51.2∞0∞9600103.2∞距离表C2的每行每列都有零，H2=H1={v1,v4,v3,v5,v6,v2,v1}就是总距离最小的Hamilton回路，C（H1）=35.2。

（2）中国邮路问题。

虚拟一条边取回路H1＝{v1，v3，v4}，C（H1）=9+5+3=17,C（v1，v3）=9>C（H1）/2，调整回路。

所有回路满足最短回路的准则，上图是最短的欧拉回路，其中边（v1,v4）和（v4,v3）各重复一次。

习题七7.2

（1）分别用节点法和箭线法绘制表7-16的项目网络图，并填写表中的紧前工序。

（2）用箭线法绘制表7-17的项目网络图，并填写表中的紧后工序表7-16工序ABCDEFG紧前工序－－－ACAF、D、B、E紧后工序D,E　G　E　G　G　G　－表7-17工序ABCDEFGHIJKLM紧前工序---BBA,BBD,GC,E,F,HD,GC,EIJ,K,L紧后工序FE,D,F,G　I,K　H,J　I,K　I　H,J　I　L　M　M　M　－　【解】

（1）箭线图：

节点图：

（2）箭线图：

7.3根据项目工序明细表7-18：

（1）画出网络图。

（2）计算工序的最早开始、最迟开始时间和总时差。

（3）找出关键路线和关键工序。

表7-18工序ABCDEFG紧前工序-AAB,CCD,ED,E工序时间（周）961219678【解】

（1）网络图

（2）网络参数工序ABCDEFG最早开始09921214040最迟开始015921344140总时差06001310（3）关键路线：

①→②→③→④→⑤→⑥→⑦；关键工序：

A、C、D、G；完工期：

48周。

7.4表7-19给出了项目的工序明细表。

表7-19工序ABCDEFGHIJKLMN紧前工序---A,BBB,CED,GEEHF,JI,K,LF,J,L工序时间（天）8571281716814510231512

（1）绘制项目网络图。

（2）在网络图上求工序的最早开始、最迟开始时间。

（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差。

（4）找出所有关键路线及对应的关键工序。

（5）求项目的完工期。

【解】

（1）网络图

（2）工序最早开始、最迟开始时间（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差工序tTESTEFTLSTLF总时差S自由时差FA80891790B5050500C7077700D12820172999E851351300F1772472400G161329132900H82937293700I14132733472020J51318192466K103747374700L232447244700M154762476200N124759506233（4）关键路线及对应的关键工序关键路线有两条，第一条：

①→②→⑤→⑥→⑦→→；关键工序：

B,E,G,H,K,M第二条：

①→④→⑧→⑨→→；关键工序：

C,F,L,M（5）项目的完工期为62天。

7.5已知项目各工序的三种估计时间如表7-20所示。

求：

表7-20工序紧前工序工序的三种时间（小时）ambA－91012BA6810CA131516DB8911EB,C151720FD,E91214

（1）绘制网络图并计算各工序的期望时间和方差。

（2）关键工序和关键路线。

（3）项目完工时间的期望值。

（4）假设完工期服从正态分布，项目在56小时内完工的概率是多少。

（5）使完工的概率为0.98，最少需要多长时间。

【解】

（1）网络图工序紧前工序工序的三种时间（小时）期望值方差ambA－9101210.170.25BA681080.4444CA13151614.830.25DB89119.1670.25EB,C15172017.170.6944FD,E9121411.830.6944

（2）关键工序：

A,C,E,F；关键路线：

①→②→④→⑤→⑥（3）项目完工时间的期望值：

10.17+14.83+17.17+11.83＝54（小时）完工期的方差为0.25+0.25+0.6944+0.6944＝1.8889（4）X0=56，56天内完工的概率为0.927（5）p=0.98，要使完工期的概率达到0.98，则至少需要56.82小时。

7.6表7-21给出了工序的正常、应急的时间和成本。

表7-21工序紧前工序时间（天）成本时间的最大缩量（天）应急增加成本（万元/天）正常应急正常应急A1512506535BA1210100120210CA74808933DB,C13116090215ED1410405243FC1613456035GE,F1086084212

（1）绘制项目网络图，按正常时间计算完成项目的总成本和工期。

（2）按应急时间计算完成项目的总成本和工期。

（3）按应急时间的项目完工期，调整计划使总成本最低。

（4）已知项目缩短1天额外获得奖金4万元，减少间接费用2.5万元，求总成本最低的项目完工期。

（1）正常时间项目网络图项目网络图总成本为435，工期为64。

（2）应急时间项目网络图总成本为560，工期为51。

（3）应急时间调整工序C、F按正常时间施工，总成本为560-9-15＝536，完工期为51。

（4）总成本最低的项目完工期工序A、E分别缩短3天，总成本为435+15+12-6.5×7＝416.5，完工期为57。

7.7继续讨论表7-21。

假设各工序在正常时间条件下需要的人员数分别为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-h）/g（b-a）＝0.2222，a0＋a1＋a2＝1+0.7＋0.49＝2.19＜2.222＜a0+a1＋a2＋a3＝2.533，n－t－1＝2，t=7，则1~6年低负荷运行，7~10年为高负荷运行。

各年年初投入设备数如下表。

年份12345678910设备台数1000850723614522444377264184.81298.2如图8－4，求A到F的最短路线及最短距离。

【解】A到F的最短距离为13；最短路线A→B2→C3→D2→E2→F及A→C2→D2→E2→F8.3求解下列非线性规划

（1）

（2）（3）（4）（5）（6）【解】

（1）设s3=x3,s3+x2=s2，s2+x1=s1=C则有x3=s3，0≤x2≤s2，0≤x1≤s1=C用逆推法，从后向前依次有k＝3，及最优解x3*=s3k＝2，由故为极大值点。

所以及最优解x2*=s2k=1时，，由，得故已知知x1+x2+x3=C，因而按计算的顺序推算，可得各阶段的最优决策和最优解如下，由s2=s1－x1*=2C/3，由s3=s2－x2*=C/3，最优解为：

【解】

（2）设s3=x3,s3+x2=s2，s2+x1=s1=C则有x3=s3，0≤x2≤s2，0≤x1≤s1=C用逆推法，从后向前依次有k＝3，及最优解x3*=s3k＝2，由=4>0,故x2=为极小值点。

因而有k＝1时，由知得到最优解【解】（3）设s3=x3,s3+x2=s2，s2+x1=s1=10则有x3=s3，0≤x2≤s2，0≤x1≤s1=10用逆推法，从后向前依次有k＝3时，及最优解x3=s3k＝2时，而。

讨论端点：

当x2=0时,x2=s2时如果s2>3时,k＝1时，同理有,x1=0,f1（s1）=s12=100，x1=s1,f1（s1）=2s1=20（舍去）得到最优解【解】（4）设s3=x3,2s