运筹学课后答案2.doc 50页

'50运筹学(第2版)习题答案运筹学（第2版）习题答案2第1章线性规划P36~40第2章线性规划的对偶理论P68~69第3章整数规划P82~84第4章目标规划P98~100第5章运输与指派问题P134~136第6章网络模型P164~165第7章网络计划P185~187第8章动态规划P208~210第9章排队论P239~240第10章存储论P269~270第11章决策论Pp297－298第12章博弈论P325~326全书360页由于大小限制，此文档只显示第6章到第12章，第1章至第5章见《运筹学课后答案1》习题六图6－426.1如图6－42所示，建立求最小部分树的0－1整数规划数学模型。【解】边[i，j]的长度记为cij，设数学模型为：图6－436.2如图6－43所示，建立求v1到v6的最短路问题的0－1整数规划数学模型。 50运筹学(第2版)习题答案【解】弧(i，j)的长度记为cij，设数学模型为：6.3如图6－43所示，建立求v1到v6的最大流问题的线性规划数学模型。【解】设xij为弧（i,j）的流量，数学模型为6.4求图6－41的最小部分树。图6-41（a）用破圈法,图6-41（b）用加边法。图6－44【解】图6-44（a），该题有4个解，最小树长为22，其中一个解如下图所示。 50运筹学(第2版)习题答案图6-44（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【解】属于最小树问题。用加边法，得到下图所示的方案。 50运筹学(第2版)习题答案最低总成本74.3万元。6.6在图6－45中，求A到H、I的最短路及最短路长，并对图(a)和(b)的结果进行比较。图6－45【解】图6－45(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－45(b)： 50运筹学(第2版)习题答案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－466.8图6－46是世界某6大城市之间的航线，边上的数字为票价（百美元），用Floyd算法设计任意两城市之间票价最便宜的路线表。【解】教师可利用模板求解：datachpt6ch6.xlsL1　v1v2v3v4v5v6v108.895.686v28.801051004v3910034.814v45.653012100v581004.81209 50运筹学(第2版)习题答案v6641410090L2　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到各点的最优路线图分别为： 50运筹学(第2版)习题答案6.9设图6－46是某汽车公司的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－476.10如图6－47，（1）求v1到v10的最大流及最大流量；（2）求最小割集和最小割量。【解】给出初始流如下 50运筹学(第2版)习题答案第一轮标号：得到一条增广链，调整量等于5，如下图所示调整流量。第二轮标号：得到一条增广链，调整量等于2，如下图所示调整流量。第三轮标号：得到一条增广链，调整量等于3，如下图所示调整流量。第四轮标号：不存在增广链，最大流量等于45，如下图所示 50运筹学(第2版)习题答案取，最小截集{(3,7),(4,7),(6,9),(8,10)，最小截量等于45。6.11将3个天然气田A1、A2、A3的天然气输送到2个地区C1、C2，中途有2个加压站B1、B2，天然气管线如图6－48所示。输气管道单位时间的最大通过量cij及单位流量的费用dij标在弧上(cij,dij)。求(1)流量为22的最小费用流；（2）最小费用最大流。图6－48【解】虚拟一个发点和一个收点T6.11－1得到流量v＝22的最小费用流，最小费用为271。求解过程参看习题部分答案PPT文档。 50运筹学(第2版)习题答案T6.11－13最小费用最大流如下图，最大流量等于27，总费用等于351。6.12如图6－46所示，（1）求解旅行售货员问题；（2）求解中国邮路问题。图6-46【解】（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∞0011 50运筹学(第2版)习题答案40.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紧前工序－－－AA、C－B、D、E、F紧后工序D,EGEGGG－表7-17工序ABCDEFGHIJKLM紧前工序---BBA,BBD,GC,E,F,HD,GC,EIJ,K,L紧后工序FE,D,F,GI,KH,JI,KIH,JILMMM－ 50运筹学(第2版)习题答案【解】（1）节点图：箭线图：（2）节点图：箭线图： 50运筹学(第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)网络图 50运筹学(第2版)习题答案（2）工序最早开始、最迟开始时间（3）用表格表示工序的最早最迟开始和完成时间、总时差和自由时差工序tTESTEFTLSTLF总时差S自由时差FA80891790B5050500C7077700D12820172999E851351300F1772472400G161329132900H82937293700I14132733472020J51318192466K103747374700L232447244700M154762476200N124759506233(4)关键路线及对应的关键工序关键路线有两条，第一条：①→②→⑤→⑥→⑦→→；关键工序：B,E,G,H,K,M第二条：①→④→⑧→⑨→→；关键工序：C,F,L,M（5）项目的完工期为62天。7.5已知项目各工序的三种估计时间如表7-20所示。求：表7-20 50运筹学(第2版)习题答案工序紧前工序工序的三种时间（小时）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工序紧前工序时间(天)成本时间的最大缩量(天)应急增加成本（万元/天）正常应急正常应急A1512506535BA1210100120210 50运筹学(第2版)习题答案CA74808933DB,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)总成本最低的项目完工期 50运筹学(第2版)习题答案工序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)按正常时间调整非关键工序的开工时间 50运筹学(第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期的设备最优负荷方案。【解】由公式得(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用逆推法，从后向前依次有 50运筹学(第2版)习题答案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时，由知得到最优解 50运筹学(第2版)习题答案【解】(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,2s3+4x2=s2，s2+x1=s1=10则有x3=s3，0≤x2≤s2/4，0≤x1≤s1=10用逆推法，从后向前依次有k＝1，及最优解x3*=s3k＝2，由=s2-4x2=0,则x2=s2,故为极大值点。则及最优解x2*=s2/8k＝1，，故得到最优解【解】(5)按问题中变量的个数分为三个阶段s1，s2，s3，且s3≤10，x1，x2，x3为各阶段的决策变量，各阶段指标函数相乘。设s1=2x1,s1+4x2=s2，s2+x3=s3≤10，则有x1=s1/2，0≤x2≤s2/4，0≤x3≤s3=10用顺推法，从前向后依次有k＝1，及最优化解x1*=s1/2 50运筹学(第2版)习题答案k＝2，由,则,故为极大值点。则k＝3，由故，由于s3≤10，则s3=10时取最大值，x3＝10/3，s2=s3－x3＝20/3，x2＝5/6，s1=s2－4x2＝10/3，x1＝5/3得到最优解【解】（6）设s1=x1,s1+x2=s2，s2+x3=s3=8k＝1，及最优化解x1*=s1k＝2，x2*=0时，f2（s2）=s22+2s2,x2*=s2时，f2（s2）=2s22故k＝3，①当x2*=0时，同样得x3*=0时，f3（s3）=s32+2s3x3*=s3时，f3（s3）=s3所以，f3（s3）=s32+2s3=80②当x2*=s2时，f3（s3）=[x3+2（s3-x3）2]同样得x3*=0时，f3（s3）=2s32=128x3*=s3时，f3（s3）=s3=8所以，f3（s3）=2s32=128最优解为8.4用动态规划求解下列线性规划问题。【解】设s2=x2,s2+2x1=s1≤6则有0≤x2=s2≤4，0≤x1≤s1/2用逆推法，从后向前依次有及最优解x2*=s2 50运筹学(第2版)习题答案由s2=s1－2x1≤4，s1≤6，取s1＝6，又1≤x1≤2，取x1＝1，最优解8.510吨集装箱最多只能装9吨，现有3种货物供装载，每种货物的单位重量及相应单位价值如表8.24所示。应该如何装载货物使总价值最大。表8.24货物编号123单位加工时间234单位价值345【解】设装载第I种货物的件数为xi（i=1,2,3）则问题可表为：利用背包问题的前向动态规划计算，建立动态规划模型。由于决策变量离散型值，所以可用列表法求解。当R=1时，。计算结果如下：s20123456789f1（s2）003366991212x1*0011223344当R=2时，f2（s3）=[4x2+f1（s3-3x2）]计算结果如下：s30123456789x20000101010120120120123C2+f2003346467978910812101112131112f2（s3）0034679101213x2*0001010101当R=3时，f3（9）=[5x3+f2（9-4x3）]（x3为整数）=[f2（9），5+f2（5），10+f2（1）]=max[13，12，10]=138.6有一辆货车载重量为10吨，用来装载货物A、B时成本分别为5元/吨和4元/吨。现在已知每吨货物的运价与该货物的重量有如下线性关系：A：P1=10-2x1，B：P2=12-3x2其中x1、x2分别为货物A、B的重量。如果要求货物满载，A和B各装载多少，才能使总利润最大【解】A：P1=15-x1，B：P2=18-2x2由题意可得各种货物利润函数为原问题的数学模型归结为 50运筹学(第2版)习题答案最优解：x1=6，x2=4；z＝488.7现有一面粉加工厂，每星期上五天班。生产成本和需求量见表8-25。表8-25星期(k)12345需求量(dk)单位：袋1020253030每袋生产成本(ck)8691210面粉加工没有生产准备成本，每袋面粉的存储费为hk＝0.5元/袋，按天交货，分别比较下列两种方案的最优性，求成本最小的方案。（1）星期一早上和星期五晚的存储量为零，不允许缺货，仓库容量为S=40袋；（2）其它条件不变，星期一初存量为8。【解】动态规划求解过程如下：阶段k：日期，k=1,2,…,6状态变量sk：第k天早上（发货以前）的冷库存量决策变量xk：第k天的生产量状态转移方程：sk+1=sk+xk－dk；决策允许集合：阶段指标：vk(sk，xk)=ckxk+0.5sk终端条件：f6(s6)=0,s6=0；递推方程：当k=5时，因为s6=0，有由于s5≤15，k=4时，，k=3时，当0≤s4≤30时，，得有 50运筹学(第2版)习题答案当30≤s4≤40时，，有显然此决策不可行。当k=2时，由x2的决策允许集合为当k=1时，由，则x1的决策允许集合为因为(2)期初存储量s1=8,与前面计算相似，x1=2.MinZ=772.5+2.5x1-5s1=737.5则总成本最小的方案是第二种。8.8某企业计划委派10个推销员到4个地区推销产品，每个地区分配1~4个推销员。各地区月收益（单位：10万元）与推销员人数的关系如表8－26所示。表8-26地区人数ABCD1456727122024318232326424242730企业如何分配4个地区的推销人员使月总收益最大。【解】设xk为第k种货物的运载重量，该问题的静态规划模型为 50运筹学(第2版)习题答案利用图表法：X1X2X3X4X5000830002632020631008027080024006230026028022435040436004444024232044032042225200630206027260027220433202434224029204231242022240223400431404027440019420219402220422018600225602024620023800024故最优解为则maxZ=448.9有一个车队总共有车辆100辆，分别送两批货物去A、B两地，运到A地去的利润与车辆数目满足关系100x，x为车辆数，车辆抛锚率为30%，运到B地的利润与车辆数y关系为80y，车辆抛锚率为20%，总共往返3轮。请设计使总利润最高的车辆分配方案。【解】动态规划求解过程如下。阶段k：共往数k=1,2,3,4，k=1表示第一趟初，k=4表示第三趟末（即第六年初）；状态变量sk：第k趟初完好的车辆数（k=1,2,3,4），也是第k－1趟末完好的车辆数，其中s4表示第三趟末的完好车辆数。决策变量xk：第k年初投入高负荷运行的机器数；状态转移方程：sk+1=0.7xk+0.8(sk－xk)决策允许集合：Dk(sk)={xk|0£xk£sk}阶段指标：vk(sk，xk)=100xk+80(sk－xk)终端条件：f4(s4)=0递推方程：fk(xk)表示第k趟初分配xk辆车到A地，到第3趟末的最大总运价为 50运筹学(第2版)习题答案因为s1=100，最大总运价f1(s1)=21900元8.10系统可靠性问题。一个工作系统由个部件串联组成，见图8-5。只要有一个部件失灵，整个系统就不能工作。为提高系统的可靠性，可以增加部件的备用件。例如，用5个部件1并联起来作为一个部件与部件2串联，如果其中一个部件失灵其它4个部件仍能正常工作。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。部件1部件2……部件n图8-5假设部件上装有个备用件，该部件正常工作的概率为。设装一个部件的备用件的成本为，要求备件的总费用为C。那么该问题模型为：（8.8）同理，如果一个复杂的工作系统由个部件并联组成的，只有当个部件都失灵，整个系统就不能工作，见图8-6。图8-6假设为第个部件失灵的概率，为提高系统的可靠性，可以增加部件的备用件。由于系统成本（或重量、体积）的限制，应如何选择各个部件的备件数，使整个系统的可靠性最大。系统的可靠性为，则该问题的数学模型归结为（8.9）利用式(8.8)或（8.9）求解下列问题。（1 50运筹学(第2版)习题答案）工厂设计的一种电子设备，其中有一系统由三个电子元件串联组成。已知这三个元件的价格和可靠性如表8-27所示，要求在设计中所使用元件的费用不超过200元，试问应如何设计使设备的可靠性达到最大。表8-27元件单价可靠性1400.952350.83200.6（2）公司计划在5周内必须采购一批原料，而估计在未来的5周内价格有波动，其浮动价格和概率根据市场调查和预测得出，如表8-28所示，试求在哪一周以什么价格购入，使其采购价格的期望最小，并求出期望值。表8-28单价概率5500．16500．258000．39000．35【解】（1）数学模型为最优解X=(1，2，4)；可靠性Z=0.888653，总费用190。（2）设阶段k，可按采购期限分为5段，k＝l，2，3，4，5决策变量为xk，第k周采购则xk＝l，若不采购则xk＝0状态变量sk表示第k周原料实际价格用Qk表示当第k周决定等待，而在以后采购时的采购价格期望值，即最优指标函数fk(sk)表示第k周实际价格为sk时，从第k周到第5周采取最优决策所花费的最低期望价格，递推公式为则k＝5时，因为若前四周尚未购买，则无论本周价格如何，该企业都必须购入原料所以当k＝4时， 50运筹学(第2版)习题答案当k＝3时，当k＝2时，当k＝1时，最优采购策略：若前面四周原料价格为550或650时，则立即采购，否则在以后的几周内再采购。第五周无论当时的价格为多少都必须采购。期望价格为（元）习题九9.1某蛋糕店有一服务员，顾客到达服从=30人/小时的Poisson分布，当店里只有一个顾客时，平均服务时间为1.5分钟，当店里有2个或2个以上顾客时，平均服务时间缩减至1分钟。两种服务时间均服从负指数分布。试求：（1）此排队系统的状态转移图；（2）稳态下的概率转移平衡方程组； 50运筹学(第2版)习题答案（3）店内有2个顾客的概率；（4）该系统的其它数量指标。【解】（1）此系统为排队模型，该系统的状态转移图如下：（2）由转移图可得稳态下的差分方程组如下：（3）已知由得令，有则（4）系统中的平均顾客数（队长期望值） 50运筹学(第2版)习题答案在队列中等待的平均顾客数（队列长期望值）系统中顾客逗留时间系统中顾客等待时间9.2某商店每天开10个小时，一天平均有90个顾客到达商店，商店的服务平均速度是每小时服务10个，若假定顾客到达的规律是服从Poisson分布，商店服务时间服从负指数分布，试求：（1）在商店前等待服务的顾客平均数。（2）在队长中多于2个人的概率。（3）在商店中平均有顾客的人数。（4）若希望商店平均顾客只有2人，平均服务速度应提高到多少。【解】此题是属于系统，其中：=9（个/小时）=10(个/小时)=9/10(1)（个）(2)(3)（个）(4)(个/小时)9.3为开办一个小型理发店，目前只招聘了一个服务员，需要决定等待理发的顾客的位子应设立多少。假设需要理发的顾客到来的规律服从泊松流，平均每4分钟来一个，而理发的时间服从指数分布，平均每3分钟1人。如果要求理发的顾客因没有等待的位子而转向其他理发店的人数占要理发的人数比例为7％时，应该安放几个位子供顾客等待？【解】此题属于模型,依题意知：＝1/4，=1/3，，由题意解方程 50运筹学(第2版)习题答案则应设立4个座位供顾客排队。9.4某服务部平均每小时有4个人到达，平均服务时间为6分钟。到达服从Poisson流，服务时间为负指数分布。由于场地受限制，服务部最多不能超过3人，求：（1）服务部没有人到达的概率；（2）服务部的平均人数；（3）等待服务的平均人数；（4）顾客在服务部平均花费的时间；（5）顾客平均排队的时间。【解】依题意，这是排队系统。其中：=3，=4，=10，=0.4（1）=（1-0.4）/[1-（0.4）4]=0.6158（2）（人）（3）（人）（4）（小时）（5）（小时）9.5某车间有5台机器，每台机器连续运转时间服从负指数分布，平均连续运转时间为15分钟。有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。求该排队系统的数量指标，，，，，和。【解】由题意知，每台机器每小时出故障的平均次数服从泊松分布，故该排队系统为系统，其中：　　=1/15，=5，=1/12，=0.8（台）（台）（分钟）（分钟）9.6证明：一个的排队系统要比两个 50运筹学(第2版)习题答案的排队系统优越。试从队长这个指标证明。【证】设的服务强度为，则服务强度为2。则两个单服务台的系统　　两个服务台的系统　　队长　　由于，即系统1的队长大于系统2的队长，故单队2服务台的系统优于2队单服务对的系统。9.7某博物馆有4个大小一致的展厅。来到该博物馆参观的观众服从泊松分布，平均96人/小时。观众大致平均分散于各展厅，且在各展厅停留的时间服从分钟的负指数分布，在参观完4个展厅后离去。问该博物馆的每个展厅应按多大容量设计，使在任何时间内观众超员的概率小于5%。【解】此问题中服务员数量，属于系统，每个展厅内：人/小时，人/小时，　　　　　　　　　　要确定展厅的容量，使观众超过的概率小于0.05，即有由泊松累积分布表查得。　　故每个展厅应至少容纳10人，使在任何时间内观众超员的概率小于5%。9.8两个技术程度相同的工人共同照管5台自动机床，每台机床平均每小时需照管一次，每次需一个工人照管的平均时间为15分钟。每次照管时间及每相继两次照管间隔都相互独立且为负指数分布。试求每人平均空闲时间，系统四项主要指标和机床利用率。【解】由题意可知，该系统为系统，且：，，台/小时，台/小时，，。工人空闲率：计算得：台台 50运筹学(第2版)习题答案工人平均空闲时间：（小时）=16.8（分钟）（小时）=1.8（分钟）机床利用率：9.9某储蓄所有一个服务窗口，顾客按泊松分布平均每小时到达10人，为任一顾客办理存款、取款等业务的时间服从～(0.05,0.012)的正态分布。试求储蓄所空闲的概率及其主要工作指标。【解】这是一个排队系统。由题意知：　　人/小时，人/小时，，，储蓄所空闲的概率及其主要工作指标为：（人）（人）（分钟）（分钟）9.10某检测站有一台自动检测机器性能的仪器，检测每台机器都需6分钟。送检机器按泊松分布到达，平均每小时4台。试求该系统的主要工作指标。解：这是一个系统，且：台/小时，分钟/台，各主要工作指标为：（台）（台）（分钟）（分钟）9.11一个电话间的顾客按泊松流到达，平均每小时到达6人，平均通话时间为8分钟，方差为8分钟，直观上估计通话时间服从爱尔朗分布，管理人员想知道平均列队长度和顾客平均等待时间是多少。解：该系统为排队系统，其中：，（人） 50运筹学(第2版)习题答案（分钟）9.12对某服务台进行实测，得到如下数据：系统中的顾客数（n）记录到的次数(mn)0123161975334平均服务时间为10分钟，服务一个顾客的收益为2元，服务机构运行单位时间成本为1元，问服务率为多少时可使单位时间平均总收益最大。【解】该系统为系统，首先通过实测数据估计平均到达率：因为　　　可以用下式来估计由/小时，可得的估计值为：　　人/小时为求最优服务率，根据公式9.6.5，取：，可得　　故　　当人/小时时，总收益为：（元/小时）当人/小时时，总收益为：（元/小时）单位时间内平均收益可增加1.373元。9.13某检验中心为各工厂服务，要求进行检验的工厂（顾客）的到来服从流，平均到达率为（次/天）；工厂每次来检验由于停工造成损失6元；服务（检验）时间服务负指数分布，平均服务率为（次/天）；每设置一个检验员的服务成本为每天4元，其他条件均适合系统。问应设几个检验员可使总费用的平均值最少。【解】已知，，，，，设检验员数为，则：将依次代入，得到下表。由于落在区间(0.583,21.845)之间，故，即当设3　个检验员时可使总费用最小，最小值为： 50运筹学(第2版)习题答案（元）检验员数s平均顾客数L(s)L(s)-L(s+1)～L(s-1)-L(s)总费用（元）z(s)12345∞24.492.6452.0631.95221.845～∞0.582～21.8450.111～0.582∞154.9427.8728.3831.71习题十10.1某企业每月甲零件的生产量为800件，该零件月需求量为500件，每次准备成本50元，每件月存储费为10元，缺货费8元，求最优生产批量及生产周期。【解】模型1。D=500，P=800，H＝10，A＝50，B＝8最优订货批量约为173件，约11天订货一次。10.2某产品月需要量为600件，若要订货，可以以每天50件的速率供应。存储费为5元/（月·件），订货手续费为100元，求最优订货批量及订货周期。【解】模型2。D=600，P=30×50＝1500，H＝5，A＝100最优订货批量约为200件，约10天订货一次。10.3某公司预计年销售计算机2000台，每次订货费为500元，存储费为32元/（年·台），缺货费为100元/年·台。试求：（1）提前期为零时的最优订货批量及最大缺货量；（2）提前期为10天时的订货点及最大存储量。【解】模型3。D=2000，A=500，H=32，B=100,L=0.0274(年)R＝LD－S＝0.0274×2000－69＝55－69＝－14（件）(1)最优订货批量为287台，最大缺货量为69台；(2)再订货点为－14台，最大存储量为218台。 50运筹学(第2版)习题答案10.4某化工厂每年需要甘油100吨，订货的固定成本为100元，甘油单价为7800元/吨，每吨年保管费为32元，求：（1）最优订货批量；（2）年订货次数；（3）总成本。【解】模型4。D=100，A=100，H=32，C=7800元则（1）最优订货批量为25件；（2）年订货4次；（3）总成本为780800元。10.5工厂每月需要甲零件3000件，每件零件120元，月存储费率为0.5%，每批订货费为150元，求：（1）经济订货批量及订货周期；（2）提前期为6天时的订货点【解】模型4。D=3000，A=150，H=120×0.005＝0.6，C=120（1）则经济订货批量为1225件，订货周期为0.408月（2）L＝6（天）＝0.2（月），R＝3000×0.2＝600（件）10.6求图10－1中缺货周期及缺货周期内的生产时间t2。【解】缺货周期为因为所以另解缺货周期：由，有 50运筹学(第2版)习题答案10.7将式(10－1)表达为（Q，S）的函数，推导出最优订货量和订货周期。10.8将式(10－15)表达为（Q，S）的函数，推导出最优订货量和订货周期。10.9将式（10－22）化为t的函数f(t)，推导出最优解Q*及t*。10.10证明式(10－15)的持有成本小于式(10－22)的持有成本，并验证当习题10.4的缺货费为100元时的情形。【证】由式（10－24）,，存储费为由式（10－16）及（10－17）：,；持有成本证毕。习题10.4中，D=100，A=100，H=32，C=7800，B=100时，允许缺货的存储费为不允许缺货的存储费为 50运筹学(第2版)习题答案10.11证明：在式（10－24）中，当Q*在14%范围内变化为Q时，总成本约增加1%。【证】由Q=(1+δ)Q*,δ＝±0.14及式(10.29)，则当δ1＝0.14及δ1＝－0.14时证毕。10.12在题4中，假定工厂考虑流动资金问题，决定宁可使总成本超过最小成本5%作存储策略，求此时的订货批量。【解】引用例10.7的结果：i=0.05时δ1=0.37及δ2=－0.27，当δ1=0.37时，由题2的结果有当δ1=－0.27时订货量约为34件或18件。10.13假定习题10.5中的需求现在是1500件，存储费和准备费不变，问现在的经济订货批量和订货周期各是原来的多少倍。【解】则现在的经济订货批量和订货周期各是原来的0.707倍和1.414倍。10.14证明式（10－18）修改中，当订货费、存储费和缺货费同时增加δ倍时，经济订货批量不变。【证】由式(10.18)知10.15商店拟定在第二、三季度采购一批空调。预计销售量的概率见表10.16。表10.16需求量xi（百台）012345概率pi0.010.150.250.300.200.09已知每销售100台空调可获利润4500元，如果当年未售完，就要转到下一年度销售，每一百台的存储费为500元，问商店应采购多少台空调最佳。【解】P－C＝4500，H=500，B=0，C－S=0，Co＝C－S＋H＝500，Cu=P－C＋B＝4500商店最佳订货量为400台。 50运筹学(第2版)习题答案10.16由于电脑不但价格变化快而且更新快，某电脑商尽量缩短订货周期，计划10天订货一次。某周期内每台电脑可获得进价15％的利润，如果这期没有售完，则他只能按进价的90％出售并且可以售完。到了下一期电脑商发现一种新产品上市了，价格上涨了10％，他的利润率只有10％，，如果没有售完，则他可以按进价的95％出售并且可以售完。假设市场需求量的概率不变。问电脑商的订货量是否发生变化，为什么。【解】（1）设初期价格为C，Cu=0.15C，CO＝0.1C，则（2）设单价为C，Cu=0.1×1.1C，CO=0.05×1.1C，则因为SL2>SL1,所以应增加订货量。10.17鲜花商店准备在9月10日教师节到来之前比以往多订购一批鲜花，用来制作“园丁颂”的花篮。每只花篮的材料、保养及制作成本是60元，售价为120元/只。9月10日过后只能按20元/只出售。据历年经验，其销售量服从期望值为200、均方差为150的正态分布。该商店应准备制作多少花篮使利润最大，期望利润是多少。【解】P＝120，C＝60，S=20，B＝H＝0Co＝C－S＋H＝40，Cu=P－C＋B＝60查正态分布表得到，则Q=150×0.25+200＝238（件）。期望利润为6204.85元。10.18某涂料工厂每月需要某种化工原料的概率服从75吨至100吨之间的均匀分布，原料单价为4000元/吨，每批订货的固定成本为5000元，每月仓库存储一吨的保管费为60元，每吨缺货费为4300元，求缺货补充的（s，Q）存储策略。【解】该题增加条件L=6天。C＝4000，A=5000，H＝60，B=4300，p=100，q＝0；均匀分布（Uniform）：a=75，b=100，L＝0.2月，平均需求量（100+75）/2＝87.5。提前期内的平均需求量为87.5×0.2＝17.5，分布参数为100*0.2－75*0.2＝5。迭代过程见下表。数据订货量Q(i)不缺货的概率F(s)再订货点s(i)安全存量SS(i)H=60　Q(1)=120.7615F(1)=0.9807s(1)=4.90SS(1)=-12.60D=87.5Q(2)=120.8096F(2)=0.9807s(2)=4.90SS(2)=-12.60A=5000Q(3)=120.8096F(3)=0.9807s(3)=4.90SS(3)=-12.60B=4300Q(4)=120.8096F(4)=0.9807s(4)=4.90SS(4)=-12.60q=0Q(5)=120.8096F(5)=0.9807s(5)=4.90SS(5)=-12.60a=5　　　　　　　　　q=0时：Q*=120.80965s*=4.9037公式：Q(1)=SQRT(2*C5*C4/C3) 50运筹学(第2版)习题答案Q(2)=SQRT((2*$C$5*$C$4+$C$4*$C$6*$C$8+$C$4*$C$6*J3^2/$C$8-2*$C$4*$C$6*J3)/$C$3)F(1)=1-$C$3*F3/($C$7*$C$3*F3+$C$6*$C$4)s(1)=$C$8*H3SS(1)=J3-17.5Q*=SQRT(C5*C4*2/C3)*SQRT(C4*C6/(C4*C6-C3*C8))s*=C8*(1-C3*F9/(C6*C4))其余单元格用上一步迭代公式复制即可。最优存储策略为：再订货点s＝5，订货量Q＝121。结果显示，安全存量为负数，一次订货量是一个月平均需求量的1.37倍，这是因为一次订购成本很大、持有成本较小引起的。10.19若H=0.15，B=1，A=100，L=1/10（年）,在L这段时间内的需求量服从μ=1000，σ2=625的正态分布，年平均需要量D=10000件，求缺货补充的（s，Q）存储策略。【解】迭代过程见下表。数据订货量Q(i)不缺货的概率F(s)(s-μ)/σ(查表）H=0.15　Q(1)=3651.4837F(1)=0.94521.6000D=10000Q(2)=3638.1334F(2)=0.94541.6000A=100Q(3)=3644.4866F(3)=0.94531.6000B=1Q(4)=3643.2734F(4)=0.94541.6000q=0Q(5)=3640.9071F(5)=0.94541.6000μ=1000Q(6)=3640.4113F(6)=0.94541.6000σ=25　　　　　　s(i)f((s-μ)/σ)G((s-μ)/σ)b(i)安全存量SS(i)s(1)=1040.00000.05840.0548-0.7299SS(1)=40.00s(2)=1040.00000.07200.0546-0.3829SS(2)=40.00s(3)=1040.00000.06950.0547-0.4492SS(3)=40.00s(4)=1040.00000.06430.0546-0.5785SS(4)=40.00s(5)=1040.00000.06320.0546-0.6055SS(5)=40.00s(6)=1040.00000.06320.0546-0.6052SS(6)=40.00公式：Q(1)=SQRT(2*C5*C4/C3)Q(2)=SQRT((2*$C$4*($C$5+$C$6*N3)/$C$3))F(1)=1-$C$3*F3/($C$7*$C$3*F3+$C$6*$C$4)s(1)=I3*$C$9+$C$8G=1-H3b(1)=$C$9*L3+($C$8-K3)*M3其余单元格用上一步迭代公式复制即可。(s-μ)/σ、f((s-μ)/σ)查表得到最优存储策略为：再订货点s＝1040，订货量Q＝3640。10.20在习题10.18中，假设在提前期L内平均有订单10吨。求缺货补充的（s，S）存储策略。【解】O=10,s/＝5，Q＝121，s＝s/＋O/2=10，S=5+121=126，则再订货点s＝10，订货量等于126减去当前存量。 50运筹学(第2版)习题答案习题十一11.1某地方书店希望订购最新出版的图书．根据以往经验，新书的销售量可能为50，100，150或200本．假定每本新书的订购价为4元，销售价为6元，剩书的处理价为每本2元．要求：（1）建立损益矩阵；（2）分别用悲观法、乐观法及等可能法决策该书店应订购的新书数字；（3）建立后悔矩阵，并用后悔值法决定书店应订购的新书数．（4）书店据以往统计资料新书销售量的规律见表11－22，分别用期望值法和后悔值法决定订购数量；（5）如某市场调查部门能帮助书店调查销售量的确切数字，该书店愿意付出多大的调查费用。表11－22需求数50100150200比例（%）20403010【解】（1）损益矩阵如表11.1－1所示。表11.1－1销售订购E1E2E3E450100150200S150100100100100S21000200200200S3150-100100300300S4200-2000200400（2）悲观法：S1乐观法：S4等可能法：S2或S3。（3）后悔矩阵如表11.1－2所示。表11.1－2E1E2E3E4最大后悔值S10100200300300S21000100200200S32001000100200S43002001000300按后悔值法决策为：S2或S3（4）按期望值法和后悔值法决策，书店订购新书的数量都是100本。（5）如书店能知道确切销售数字，则可能获取的利润为，书店没有调查费用时的利润为：50×0.2+100×0.4+150×0.3+200×0.1=115元，则书店愿意付出的最大的调查费用为11.2某非确定型决策问题的决策矩阵如表11－23所示：表11－23事件方案E1E2E3E4S141681 50运筹学(第2版)习题答案S2451214S315191413S4217817（1）若乐观系数α=0.4，矩阵中的数字是利润，请用非确定型决策的各种决策准则分别确定出相应的最优方案．（2）若表11－23中的数字为成本，问对应于上述决策准则所选择的方案有何变化？【解】（1）悲观主义准则：S3；乐观主义准则：S3；Lapalace准则：S3；Savage准则：S3；折衷主义准则：S3。（2）悲观主义准则：S2；乐观主义准则：S3；Lapalace准则：S1；Savage准则：S1；折衷主义准则：S1或S2。11.3在一台机器上加工制造一批零件共10000个，如加工完后逐个进行修整，则全部可以合格，但需修整费300元．如不进行修理，根据以往资料统计，次品率情况见表11－24．表11－24次品率（E）0.020.040.060.080.10概率P（E）0.200.400.250.100.05一旦装配中发现次品时，需返工修理费为每个零件0.50．要求：（1）用期望值决定这批零件要不要整修；（2）为了获得这批零件中次品率的正确资料，在刚加工完的一批10000件中随机抽取130个样品，发现其中有9件次品，试修正先验概率，并重新按期望值决定这批零件要不要整修．【解】（1）先列出损益矩阵见表11.3-1表11.3-1E0.020.040.060.080.10EMVP（E）0.20.40.250.100.05S1：零件修正-300-300-300-300-300-300S1：不修正-100-200-300-400-500-240故按期望值法决策，零件不需修正。（不修正时的收益：E*0.5*10000）（2）记T为事件｛130个样品有9件次品｝，，（这里p=E,q=1－p）,修正先验概率见表11.3-2表11.3-2(1)(2)(3)(4)=(2)*(3)(5)=(4)/P(T)EP（E）P（T|E）P（T,E）P（E|T）0.020.20.0009780.0001960.0030920.040.40.0413150.0165260.2611780.060.250.1243320.0310830.4912340.080.10.1227120.0122710.1939340.100.050.0639870.0031990.050563P(T)=0.0632751.0000根据修正后的概率再列出损益矩阵如表11.3-3所示。表11.3-3E0.020.040.060.080.10EMVP（E）0.0030920.2611780.4912340.1939340.050563S1：修正-300-300-300-300-300-300 50运筹学(第2版)习题答案S1：不修正-100-200-300-400-500-302.77故按期望值法决策时，采用修正零件的方案。11.4某工厂正在考虑是现在还是明年扩大生产规模问题．由于可能出现的市场需求情况不一样，预期利润也不同．已知市场需求高（E1）、中（E2）、低（E3）的概率及不同方案时的预期利润，如表11－25所示．表11－25(单位：万元)事件概率方案E1E2E3P（E1）=0.2P（E2）=0.5P（E3）=0.3现在扩大108-1明年扩大861对该厂来说损失1万元效用值0，获利10万元效用值为1，对以下事件效用值无差别：①肯定得8万元或0.9概率得10万和0.1概率失去1万；②肯定得6万元或0.8概率得10万和0.2概率失去1万；③肯定得1万元或0.25概率得10万和0.75概率失去1万。求：（1）建立效用值表；（2）分别根据实际盈利额和效用值按期值法确定最优决策．【解】（1）见表11.4－1表11.4－1MU（M）-1010.2560.880.9101（2）画出决策树见图11.4－1，图中括孤内数字为效用值。图11.4－1结论：按实际盈利额选现在扩建的方案；如按效用值选明年扩建的方案。11.5有一种游戏分两阶段进行．第一阶段，参加者需先付10元，然后从含45%白球和55%红球的罐中任摸一球，并决定是否继续第二阶段．如继续需再付10元，根据第一阶段摸到的球的颜色的相同颜色罐子中再摸一球．已知白色罐子中含70%蓝球和30%绿球，红色罐子中含10%的蓝球和90%的绿球．当第二阶段摸到为蓝色球时，参加者可得50元，如摸到的绿球，或不参加第二阶段游戏的均无所得．试用决策树法确定参加者的最优策略．【解】决策树为： 50运筹学(第2版)习题答案E(6)=50×0.7+0×0.3－10=25E(7)=0E(8)=50×0.1+0×0.9－10=－5E(9)=0E(2)=25×0.0.45+0×0.55－10=1.25最优策略是应参加第一次摸球。当摸到的白球，继续摸第二次；如摸到的红球，则不摸第二次。11.6你现有人民币100万元，投资股票或债券一年（只选择一种），第二年将第一年的收入再全部投资股票或债券一年（只选择一种）。已知收益率与经济环境有关，见表11－26所示。表11－26经济环境收益率％股票债券增长205衰退－1510萧条－4015第一年经济增长、衰退和萧条的概率分别为0.7、0.3和0。如果第一年增长则第二年的概率不变，如果第一年衰退，则第二年这些概率分别为0.2、0.7和0.1。你如何作出投资决策使两年的总期望收益最大。【解】决策树及求解参看文件：datachpt11ch11.xls11.7某投资商有一笔投资，如投资于A项目，一年后能肯定得到一笔收益C；如投资于B项目，一年后或以概率P得到的收益C1，或以概率（1－P）得到收益C2，已知C1