运筹学1-6章参考答案

1、运筹学(第2版)习题答案第1章线性规划 P3640 第2章线性规划的对偶理论P6869第3章整数规划 P8284第4章目标规划 P98100第5章 运输与指派问题 P134136第6章 网络模型 P164165第7章 网络计划 P185187第8章动态规划 P208210第9章排队论P239240第10章存储论P269270第11章 决策论 Pp297-298 第12章博弈论P325326 全书360页习题一1.1讨论下列问题：(1) 在例1.2中，如果设xj(j=1 , 2,，7)为工作了 5天后星期一到星期日开始休息的营 业员，该模型如何变化.(2) 在例1.3中，能否将约束条件改为等式；

2、如果要求余料最少，数学模型如何变化；简 述板材下料的思路.(3) 在例1.4中，若允许含有少量杂质，但杂质含量不超过1%,模型如何变化.(4) 在例1.6中，假定同种设备的加工时间均匀分配到各台设备上，要求一种设备每台每天的加工时间不超过另一种设备任一台加工时间1小时，模型如何变化.在单纯形法中，为什么说当k o并且aik 0(i 1,2,L ,m)时线性规划具有无界解。1.2工厂每月生产 A、B、C三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源 限量及单件产品利润如表1 - 23所示.表 1-23产品ABC资源限量材料(kg)1.51.242500设备(台时)31.61.21400

3、利润(元/件)101412根据市场需求，预测三种产品最低月需求量分别是150、260和120，最高月需求是250、310和130 试建立该问题的数学模型，使每月利润最大.【解】设X1、X2、X3分别为产品A、B、C的产量，则数学模型为maxZ10X 14x212x31.5x11.2X2 4X325003x11.6x21.2X31400150%250260X2310120X3130X X,X301.3建筑公司需要用 6m长的塑钢材料制作 A、B两种型号的窗架两种窗架所需材料规格及数量如表1 24所示：表1 24窗架所需材料规格及数量型号A型号B每套窗架需要 材料长度(m)数量(根)长度(m)数量

4、(根)A1: 1.72B1: 2.72A2 : 1.33B2 : 2.03需要量(套)200150问怎样下料使得(1)用料最少；(2)余料最少. 【解】 第一步：求下料方案，见下表。万案-一-三四五六七八九十十一十二十三十四需要量B1:2.7m21110000000000300B2:2m01003221110000450A1:1.7m00100102103210400A2:1.3m01120010130234600余料0.600.30.700.30.70.610.10.900.40.8第二步：建立线性规划数学模型设Xj (j=1,2, , 14)为第j种方案使用原材料的根数，则 (1)用料最少

5、数学模型为14min ZjXj12为X2X3X4300x23X52X62X7X8%X10450X3X2x8X9 3X112xi2*3400X2X32X4X7X93x102x123x13 44600Xj0,j1,2,L ,14用单纯形法求解得到两个基本最优解X=(50 ,200 ,0 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=534X=(0 ,200 ,100 ,0,84 ,0,0 ,0 ,0 ,0 ,0 ,150 ,0 ,0 );Z=534 (2)余料最少数学模型为mi nZ 0.6%0.3x3 0.7x4 L 0.4x13 0.8x142x1X2X3x430

6、0X23x52x62x7 xX9X10450X3X62x8X9 3x112x12X13400X2X32X4X7X3x102x123x13 4x14600Xj0,j1,2,L ,14用单纯形法求解得到两个基本最优解X=(0 ,300 ,0 ,0,50 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料 550 根X(2)=( 0 ,450 ,0 ,0,0 ,0,0 ,0 ,0 ,0 ,0 ,200 ,0 ,0 );Z=0，用料 650 根显然用料最少的方案最优。1.4某企业需要制定16月份产品A的生产与销售计划。已知产品 A每月底交货，市场需 求没有限制，由于仓库容量有限，

7、 仓库最多库存产品 A1000件，1月初仓库库存200件。1 6月份产品A的单件成本与售价如表 1 25所示。表 1 25月份123456产品成本（元/件广300330320360360300销售价格（元/件）350340350420410340（1）16月份产品A各生产与销售多少总利润最大，建立数学模型；（2） 当1月初库存量为零并且要求 6月底需要库存200件时，模型如何变化。【解】设Xj、yj (j = 1, 2,，6)分别为16月份的生产量和销售量，则数学模型为max Z 300x1350 y1330x2340 y2320x3350 y3 360x4420 y4360 x5410y53

8、00x6340 y6800y1X2800y1X2y2X3800y1X2y2X3y3X4800y1X2y2X3y3X4y4X5800x1y1X2y2X3y3X4y4 xy5 X6 800（1）X1y1200x1y1X2y2200X1y1X2y2X3 y 200x1y1X2y2X3 y3 X4 y4 200X1y1X2y2X3 y X4 y4 X5 y 200X1y1X2y2X3 y X4 y4 X5 yy 200Xj,yj0);j1,2,L,6（2）目标函数不变，前 6个约束右端常数 800改为1000 ,第711个约束右端常数200改 为0,第12个约束“W 200 ”改为200”。1.5某投

9、资人现有下列四种投资机会，三年内每年年初都有 3万元（不计利息）可供投资：方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20%，下一年可继续将本息投入获利；方案二：在三年内投资人应在第一年年初投资, 继续将本息投入获利，这种投资最多不超过 方案三：在三年内投资人应在第二年年初投资, 最多不超过1.5万元；方案四：在三年内投资人应在第三年年初投资, 资最多不超过1万元.两年结算一次，收益率是2万元；两年结算一次，收益率是50%，下一年可60%，这种投资一年结算一次，年收益率是30%，这种投投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型【解】是设Xij为第i年投入第j

10、项目的资金数，变量表如下项目一项目二项目三项目四第1年X11X12第2年X21X23第3年X31X34数学模型为max Z 0.2xi 0.2x2i 0.2x310.5x120.6x230.3x34xn x12300001.2x11 x21 x23300001.5 xi2 1.2X21 X31X34 30000x12 20000x2315000x3410000Xj0,i 1,L ,3; j 1,L 4最优解 X=(30000 , 0, 66000, 0, 109200, 0); Z = 847201.6炼油厂计划生产三种成品油，不同的成品油由半成品油混合而成，例如高级汽油可以由 中石脑油、重整

11、汽油和裂化汽油混合，辛烷值不低于94,每桶利润5元，见表1-26。表 1-26成品油高级汽油一般汽油航空煤油一般煤油半成品油中石脑油重整汽油裂化汽油中石脑油重整汽油裂化汽油轻油、裂化 油、重油、残 油轻油、裂化 油、重油、残油按 10:4:3:1调合而成辛烷值 94 84蒸汽压：公斤/平方厘米0并且ai7 7x35x2 3x3155x1 6x2 10x3 20x?X35为 0, j 1,2,3【解】大M法。数学模型为min Z 5% 6x2 7x3MA ma3 5x2 3x3 S A155为 6x2 10x3 S220xX2 X3人 5所有变量非负C(j)5-6-700MMR.H.S.Rati

12、oBasisC(i)X1X2X3S1S2A1A3A1M15-3-1010153S205-610010020MA3M111000155C(j)-Z(j)5-6-70000* Big M-2-621000X2-61/51-3/5-1/501/503MS2031/5032/5-6/516/503895/16A3M4/508/51/50-1/5125/4C(j)-Z(j)31/50-53/5-6/506/50* Big M-4/50-8/5-1/506/50X2-61/210-1/801/83/815/4S20300-212-430X3-71/2011/80-1/85/85/4C(j)-Z(j)23/

13、2001/80-1/853/8* Big M0000011min w A A3 5x2 3x3 S 6x2 10x3X2 X3 A5Xi所有变量非负A 15S2205两阶段法。第一阶段：数学模型为C(j)0000011R.H.S.RatioBasisC(i)X1X2X3S1S2A1A3A1115-3-1010153S205-610010020MA31111000155C(j)-Z(j)-2-621000X201/51-3/5-1/501/503MS2031/5032/5-6/516/503895/16A314/508/51/50-1/5125/4C(j)-Z(j)-4/50-8/5-1/506

14、/50X201/210-1/801/83/815/4S20300-212-430X301/2011/80-1/85/85/4C(j)-Z(j)0000011第二阶段:C(j)5-6-700R.H.S.RatioBasisC(i)X1X2X3S1S2X2-61/210-1/8015/43S20300-2130MX3-71/2011/805/45C(j)-Z(j)23/2001/80最优解：X (0, 15,5)t,z1254 44maxZ 10x,15x25x1 3x295为 6x2152x1 x25xp x2、0【解】大M法。数学模型为max Z 10x1 15x2 Mx65x-i 3x2 x

15、395x-i 6x2 x4152x-|&X5X6Xj 0, j 1,2,L ,6C(j)1015000-MR. H. S.RatioBasisC(i)X1X2X3X4X5X6X3053100091.8X40-56010015MX6-M2100-1152.5C(j)-Z(j)101500000* Big M2100-100X11013/51/50009/5X4009110024X6-M0-1/5-2/50-117/5C(j)-Z(j)09-200018* Big M0-1/5-2/50-100因为X60,原问题无可行解。两阶段法第一阶段：数学模型为min Z xs5x-i 3x2 x395x1

16、6x2 冷 152x-iX2X5x6Xj0, j 1,2,L ,6C(j)000001R. H. S.RatioBasisC(i)X1X2X3X4X5X6X3053100091.8X40-56010015MX612100-1152.5C(j)-Z(j)-2-10010514X1013/51/50009/5X4009110024X6 10-1/5-2/50-117/5C(j)-Z(j)01/52/5010max Z 4x1 2x2 5x36论 x2 4x310(4) 3x1 3x2 5x38X| 2x2 x320Xj 0, j 1,2,3【解】大M法。X7是人工变量，数学模型为max Z 4x1

17、 2x2 5x3 Mx76x1 x2 4x3 x4103x1 3x2 5x3 x5x1 2x2 2x3 x6 x720Xj 0, j 1,2,L ,7Cj425000-MR.H.S.RatioCbXbX1X2X3X4X5X6X70X46-141100X53-3-518-MX7121-112010C(j)-Z(j)425* Big MM2MM-10X413/29/21-1/21/2200X59/2-7/21-3/23/2382X21/211/2-1/21/210C(j)-Z(j)341-1* Big M-15X313/912/9-1/91/940/90X586/97/91-17/917/9482

18、/92X2-2/91-1/9-4/94/970/9C(j)-Z(j)-25/9-8/913/9-13/9* Big M-1无界解。两阶段法。第一阶段:min Z x76为 x2 4x3 x4103x, 3x2 5x3 X58x-i 2x2 x3 x6 x720Xj 0, j 1,2,L ,7Cj425000R.H.S.RatioCbXbX1X2X3X4X5X60X413/29/21-1/2200X59/2-7/21-3/2381X21/211/2-1/210C(j)-Z(j)7/29/21/20X313/912/9-1/940/90X586/97/91-17/9482/92X2-2/91-1/

19、9-4/970/9C(j)-Z(j)-3-11原问题无界解。Cj0001R.H.S.RatioCbXbX1X2X3X4X5X6X70X46-141100X53-3-5181X7121-112010C(j)-Z(j)-1-2-110X413/29/21-1/21/2200X59/2-7/21-3/23/2382X21/211/2-1/21/210C(j)-Z(j)1第二阶段:1.13在第1.9题中，对于基B是最优基.2 14 0，求所有变量的检验数j(j 1,4）,并判断B是不【解】B104112CCBB 1A4,B 10(5,2,0,0)(5,0)11423 101 42 0 125 5952,。,。）（5,畀亍吋495（0,0, -）, B不是最优基，可以证明B是可行基。241.14已知线性规划maxz 5x1 8x2 7x3 4x423x23x3 2x4203为5x24x3 2x430Xj0,j1L ,423的最优基为B2，试用矩阵公式5求（1）最优解；单纯形乘子；N1及N3；，和3。【解】53B14141,CB)(4,8,),则22(1)Xb(X4,X2)TBI (5,5)T,最优解X(0,5,0,502 21 CbB (1,1)531N1B乜44241131222533N3B 1P34434