运筹学1至6章习题参考答案

1、运筹学 1 至 6 章习题参考答案第 1章 线性规划1.1 工厂每月生 A、B、C 三种 品, 件 品的原材料消耗量、 台 的消耗量、 源限量及 件 品利 如表1 23 所示表 1 23产品资源ABC资源限量材料 (kg)1.51.242500设备 (台时 )31.61.21400利润 ( 元/件)101412根据市 需求 , 三种 品最低月需求量分 是150、 260和 120,最高月需求是 250、310和 130. 建立 的数学模型,使每月利 最大【解】 x1、 x2、x3 分 品 A 、 B 、C 的 量， 数学模型 max Z10x114x212x31.5x11.2x24x32500

2、3x11.6x21.2x31400150x1250260x2310120x3130x1 , x2 , x301.2 建筑公司需要用5m 的塑 材料制作A 、B 两种型号的窗架两种窗架所需材料 格及数量如表 1 24所示：表 1 24 窗架所需材料规格及数量型号 A型号 B每套窗架需要长度（ m）数量 (根)长度 (m)数量 (根 )材料A1 ：22B 1： 2.52A 2：1.53B 2： 23需要量（套）300400 怎 下料使得（1）用料最少；（ 2）余料最少【解】 第一步：求下料方案， 下表。方案一二三四五六七八九十需要量B12.52111000000800B22010021100012

3、00A120010010210600A21.50001002023900余料 (m)00.50.51110100.5第二步：建立 性 划数学模型设 xj（ j=1,2, ， 10） 第 j 种方案使用原材料的根数， （ 1）用料最少数学模型 1 / 8010min Zxjj12x1x2x3x4800x22x5x6x71200x3x62x8x9600x42x72x93x10 900xj0, jL,101,2,（ 2）余料最少数学模型 min Z 0.5x20.5x3x4 x5 x6 x8 0.5x102x1x2x3x4800x22x5x6x71200x3x62x8x9600x42x72x93x1

4、0900xj0, j1,2,L,101.3 某企 需要制定 1 6 月份 品 A 的生 与 售 划。已知 品A 每月底交 ，市 需求没有限制， 由于 容量有限， 最多 存 品A1000 件，1 月初 存200 件。16 月份 品 A 的 件成本与售价如表1 25 所示。表 1 25月份123456 品成本 (元 /件 )300330320360360300 售价格 (元 /件 )350340350420410340（ 1）1 6 月份 品 A 各生 与 售多少 利 最大，建立数学模型；（ 2）当 1 月初 存量 零并且要求 6 月底需要 存 200 件 ，模型如何 化。【 解】 xj、 yj（

5、 j 1， 2， 6）分 1 6 月份的生 量和 售量， 数学模型 2 / 80max Z300x1350 y1330x2340 y2320x3350 y3 360x4420 y4360x5410 y5300x6340 y6x1800x1y1x2800x1y1x2y2x3800x1y1x2y2x3y3x4800x1y1x2y2x3y3x4y4x5800x1y1x2y2x3y3x4y4x5y5x6800（ 1）x1y1200x1y1x2y2200x1y1x2y2x3y3200x1y1x2y2x3y3x4y4200x1y1x2y2x3y3x4y4x5y5200x1y1x2y2x3y3x4y4x5y

6、5x6y6 200x j , y j0; j1,2,L ,6（ 2）目标函数不变，前 6 个约束右端常数800 改为 1000 ，第 711 个约束右端常数 200 改为 0，第 12 个约束“ 200”改为“ 200”。1.4 某投资人现有下列四种投资机会, 三年内每年年初都有3 万元（不计利息）可供投资：方案一：在三年内投资人应在每年年初投资，一年结算一次，年收益率是20，下一年可继续将本息投入获利；方案二：在三年内投资人应在第一年年初投资，两年结算一次，收益率是50，下一年可继续将本息投入获利，这种投资最多不超过2 万元；方案三：在三年内投资人应在第二年年初投资，两年结算一次，收益率是6

7、0，这种投资最多不超过 1.5 万元；方案四：在三年内投资人应在第三年年初投资，一年结算一次，年收益率是30，这种投资最多不超过1 万元投资人应采用怎样的投资决策使三年的总收益最大，建立数学模型.【解】是设 xij 为第 i 年投入第 j 项目的资金数，变量表如下项目一项目二项目三项目四第 1 年11x12x第 2 年2123xx第 3 年x31x34数学模型为3 / 80max Z0.2 x110.2x210.2x31 0.5x12 0.6 x23 0.3x34x11x12300001.2 x11x21x23300001.5 x121.2x21 x31x34 30000x1220000x23

8、15000x3410000xij0,iL,3; jL41,1,最 解 X=(30000 ， 0，66000， 0， 109200， 0)； Z 847201.5 油厂 划生 三种成品油，不同的成品油由半成品油混合而成，例如高 汽油可以由中石 油、重整汽油和裂化汽油混合，辛 不低于94，每桶利 5 元， 表 1 26。表 1 26成品油高 汽油一般汽油航空煤油一般煤油中石 油中石 油轻 油 、 裂 化轻 油 、 裂 化油、重油、 残半成品油重整汽油重整汽油油、重油、残油按 10:4:3:1裂化汽油裂化汽油油 合而成辛 94 84蒸汽 ：公斤 1平方厘米利 (元 /桶 )54.231.5半成品油的

9、辛 、气 、及每天可供 数量 表1 27。表 1 27半成品油1 中石脑油2 重整汽油3 裂化汽油4 轻油5 裂化油6 重油7 残油辛 80115105蒸汽 ：公斤1.01.50.60.05平方厘米每天供 数量200010001500120010001000800(桶 ) 油厂每天生 多少桶成品油利 最大，建立数学模型。解 设 xij 第 i（ i 1,2,3,4）种成品油配第j(j=1,2, ,7)种半成品油的数量（桶） 。 利 ：Z 5( x11 x12 x13)4.2( x21x22x23 )3(x34x35 x36 x37 ) 1.5(x44 x45 x46 x47 )高 汽油和一般汽

10、油的辛 束80x11 115x12105x1380x21 115x22105x2394x11x12x1394 , 84x21x22x23航空煤油蒸气 束x341.5x350.6x36 0.05x371x34x35x36 x37一般煤油比例 束x44 : x45 : x46 : x4710 : 4 : 3:14 / 80即x4410x454x463x45,x46,x47143半成品油供应量约束x11x212000x12x221000x13x231500x34x441200x35x451000x36x461000x37x47800整理后得到max Z5x115x125x134.2 x214.2 x

11、224.2x233x343x353x363x371.5x441.5x451.5x46 1.5x4714 x1121x1211x13014 x2121x2211x2304x21 31x2221x2300.5 x350.4x360.95x3704x4410x4503x454x460x463x470x11x212000x12x221000x13x231500x34x441200x35x451000x36x461000x37x47800xij0;i1,2,3, 4; j1,2,L ,71.6 图解下列线性规划并指出解的形式：max Z5x12 x22x1x28(1) x1 3 x2 5x1 , x20

12、【解】 最优解 X （ 3， 2）；最优值Z=195 / 80max Zx14x2x14x25(2) x1 3x2 2 x1 2x2 4x1, x20【解】 有多重解。最优解X （ 1） （ 0， 5/4）； X （2 ）（ 3， 1/2）最优值Z=56 / 80min Z3x1 2x2x12x211x14x210(3)2x1x27x13x21x1 , x20【解】 最优解 X （ 4， 1）；最优值Z= 10，有唯一最优解min Z4x16 x2x12x28(4) x1 x2 8 x2 3x10, x20【解】 最优解 X （ 2， 3）；最优值Z=26 ，有唯一最优解7 / 80max Z

13、x12x2x1x22(5) x1 3 x2 6x1 , x20【解】 无界解。8 / 80min Z2x15x2x12x26(6)x1x22x1, x20【解】 无可行解。9 / 801.7 将下列线性规划化为标准形式min Zx16x2x3(1)x1x23x3155 x17 x24x33210x13x26 x35x1 0, x20, x3无限制【解】（ 1）令 x3x3x3 , x4 , x5 , x6 为松驰变量，则标准形式为max Zx16x2x3x3x1x23x33x3x4155x17x24 x34x3x53210x1 3x26 x36x3x65x1, x2 , x3 , x3 , x

14、4 , x5 , x60min Z9x13x25x3| 6x17x24x3 |20(2) x1 5x18x28x10, x20, x30【解】（ 2）将绝对值化为两个不等式，则标准形式为10 / 80max Z9x1 3x25x36x17x24x3x4206x1 7 x2 4x3x5 20x1x65x18x28x1 , x2 , x3 , x4 , x5 , x60max Z2x13x21x15(3)x21x1x10, x20【解】方法 1：max Z2 x13x2x1x31x1x45x1x21x1 , x2 , x3, x40方法 2：令 x1x11,有 x1 x1 1, x1 5 1 4m

15、ax Z2(x11)3x2x1 4( x11)x21x1, x20则标准型为max Z22x13x2x1x34x1x20x1, x2 , x30max Zmin(3 x14x2 , x1x2x3 )x12x2x330(4) 4x1x22x3159x1x26x35x1无约束 , x2、 x30【解】令 y3x1 4x2 , y x1x2x3 , x1x1x1，线性规划模型变为11 / 80max Zyy3( x1x1)4x2yx1x1x2x3x1x12x2x3304( x1x1) x22x3159( x1x1 ) x26x35x1, x1, x2、 x30标准型为max Zyy 3x13x14x

16、2x40y x1x1x2x3x50x1x12x2x3x6 304x14x1x22 x3x7159x19x1x26 x3x85x1, x1, x2 , x3 , x4 , x5 , x6 , x7 , x8 01.8 设线性规划max Z5x1 2x22 x12x2x3404 x12x2x460xj 0, j 1,L, 4取基B121、B2，对应的基变量和非基变量，求出基本20分别指出4021解，并说明是不是可行基【解】B11324为非基变量 , 基本解为 X= （15，0，10，0）T，B 1是可行：x、 x为基变量， x、x基。 B22413为非基变量，基本解X=（ 0，20，0，100）T

17、，B2是可行基。：x、x是基变量， x 、x1.9 分别用图解法和单纯形法求解下列线性规划，指出单纯形法迭代的每一步的基可行解对应于图形上的那一个极点max Zx13x22x1x22(1)2x13x212x1, x20【解】图解法12 / 80单纯形法：C(j)1300bRatioC(i)BasisX1X2X3X40X3-2110220X42301124C(j)-Z(j)130003X2-21102M0X480-3160.75C(j)-Z(j)70-3063X2010.250.257/21X110-0.3750.1253/4C(j)-Z(j)00-0.375-0.87545/4对应的顶点：基可

18、行解X (1)、=（ 0，0， 2， 12）X (2)、=（ 0，2， 0， 6，）X(3)=（3 , 7 ,0,0) 、423745最优解 X (, ), Z442可行域的顶点（ 0， 0）（ 0， 2）3 7(,)13 / 80min Z3x15x2x12x26(2) x1 4x2 10x1x24x10, x20【解】图解法单纯形法：C(j)-3-5000bRatioBasisC(i)X1X2X3X4X5X301210063X4014010102.5X501100144C(j)-Z(j)-3-50000X300.501-0.5012X2-50.25100.2502.510X500.7500

19、-0.2511.52C(j)-Z(j)-1.75001.250-12.5X1-3102-102MX2-501-0.50.5024X5000-1.50.5100C(j)-Z(j)003.5-0.50-16X1-310-1022X2-50110-12X4000-3120C(j)-Z(j)00201-1614 / 80对应的顶点：基可行解可行域的顶点、（ 0， 0）X (1)=（ 0， 0，6， 10，4）、（ 0， 2.5）X (2)=（ 0， 2.5， 1， 0，1.5，）X (3)=（ 2， 2，0， 0， 0）(2， 2)X (4)=（ 2， 2，0， 0， 0）（ 2， 2）最优解： X=

20、 （ 2， 2， 0，0， 0）；最优值 Z 16该题是退化基本可行解， 5 个基本可行解对应4 个极点。1.10 用单纯形法求解下列线性规划max Z3x14x2 x32x13x2x3 4(1)x12x22x33xj0, j1,2,3【解】单纯形表：C(j)34100R. H. S.RatioBasisC(i)X1X2X3X4X5X402311044/3X501220133/2C(j)-Z(j)341000X242/311/31/304/32X50-1/304/3-2/311/3MC(j)-Z(j)1/30-1/3-4/30 16/3X1313/21/21/202X5001/23/2-1/2

21、11C(j)-Z(j)0-1/2-1/2-3/20-6最优解： X= （ 2， 0， 0，0， 1）；最优值 Z 6max Z 2x1 x23x35x4x15x23x37 x430(2)3x1x2x3x4102 x16x2x34x420x j0, j1,L, 4【解】单纯形表：C(j)21-35000R. H. S.RatioBasisC(i)X1X2X3X4X5X6X7X50153-710030MX603-1110101010X702-6-1400120515 / 80C(j)-Z(j)21-35000X509/2-11/25/40107/465MX605/21/25/4001-1/4510

22、X451/2-3/2-1/41001/45MC(j)-Z(j)-1/217/2-7/4000-5/4X50320150111-1120MX21515/2002-1/21010X45807/2103-1/220MC(j)-Z(j)-430-2300-173因为 7 30 并且ai70( i=1,2,3)，故原问题具有无界解，即无最优解。max Z3x12x218 x3x12x23x34(3)4x12x3123x18x24x310x1 , x2 , x30【解】C(j)32-0.125000R. H. S.RatioBasisC(i)X1X2X3X4X5X6X40-1231004MX5040-20

23、10123X603840011010/3C(j)-Z(j)32-1/80000X40025/211/4073.5X1310-1/201/403MX600811/20-3/4111/8C(j)-Z(j)0211/80-3/409X40009/817/16-1/427/46X1310-1/201/403MX220111/160-3/321/81/80.181818C(j)-Z(j)0000-9/16-1/437/4X3 进基、 X2出基，得到另一个基本最优解。C(j)32-0.125000R. H. S.RatioBasisX1X2X3X4X5X6X400-18/110113/22-5/1172/

24、116X1318/11002/111/1134/11MX3-0.125016/1110-3/222/112/110.1818C(j)-Z(j)0000-9/16-1/437/4原问题具有多重解。基本最优解 X (1)(3,1,0,27,0) 及 X (2)(34,0,2,72,0) T ; Z37,最优解的通解可表84111111416 / 80示为 X aX (1)(1a) X (2 ) 即X(341a,1a,22a,7272a,0) T ,(0 a 1)1111811111111max Z 3x1 2x2x35x14x26x325（ 4）8x16x23x324x j0, j1,2,3【解】

25、单纯形表：C(j)32100R. H. S.RatioBasisC(i)X1X2X3X4X5X4054610255X5086301243C(j)-Z(j)321000X4001/433/81-5/810X1313/43/801/83C(j)-Z(j)0-1/4-1/80-3/89最优解： X= （ 3， 0， 0， 10， 0）；最优值Z 91.11 分别用大M 法和两阶段法求解下列线性规划：max Z10x15x2x35x13x2x310(1)5x1x210x315xj0, j1,2,3【解】大 M 法 。数学模型为max Z 10x15x2x3Mx55x13x2x3x5105x1x210x

26、3x415x j0, j1,2,L ,5C(j)10-510-MR. H. S.RatioBasisC(i)X1X2X3X4X5X5-M53101102X40-51-101015MC(j)-Z(j)10-51000* Big M531000X11013/51/501/52X4004-91125C(j)-Z(j)0-11-10-220* Big M0000-1017 / 80最优解 X (2,0,0) ； Z=20两阶段法 。第一阶段：数学模型为min wx55x13x2x3x5 105x1x210x3x415x j0, jL,51,2,C(j)00001R. H. S.RatioBasisC(i)X1X2X3X4X5X5153101102X40-51-101015MC(j)-Z(j)-5-3-100X1013/51/501/52X4004-91125C(j)-Z(j)00001第二阶段C(j)10-510R. H. S.RatioBasisC(i)X1X2X3X4X11013/51/5022X4004-9125MC(j)-Z(j)0-11-10最优解 X=(2,0,0) ； Z=20min Z5x16x27x3x15x23x315(2)5x16 x210x3