运筹学习题集

1、数学建模题1、某厂生产甲、乙两种产品，这两种产品均需要 A B、C三种资源，每种产品的资源消耗 量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲94370乙4610120360200300试建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：设甲、乙产品的生产数量应为x1、x2,则x1、x20,设z是产品售后的总利润，则max z =70x 1+120X2 .9xi 4x23604x1 6x2 2003xi 10x2 300 xv x2 02、某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下：甲乙可用量原材料（吨/件）223000 吨工时

2、（工时/件）54000工时零件（套/件）1500套产品利润（元/件）43建立使利润最大的生产计划的数学模型，不求解。解：设甲、乙两种产品的生产数量为x1、x2,设z为产品售后总利润，则 max z = 4x 1+3x2.2x1 2x2 30005x1 2.5x2 4000xi500x1 , x2 03、一家工厂制造甲、乙、丙三种产品，需要三种资源一一技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表 所示：技术服务劳动力行政管理单位利润甲110210乙1426丙1564资源储备量100600300建立使得该厂能获得最大利润的生产计划的线

3、性规划模型，不求解。解：建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为XI、X2、X3,则XI、X2、X30,设z是产品售后的总利润，则maX z =10x 1+6X2+4X3X1 x2 x3 10010X 4x2 5x3 6002x1 2x2 6x3 300X1, X2, X304、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。序号1234567物品:食品氧气冰镐绳索帐篷照相器材P通信设备重量/Kg55261224重要性系数201518148

4、410试建立队员所能携带物品最大量的线性规划模型，不求解。解：引入01变量Xi, Xi=1表示应携带物品i , , Xi =0表示不应携带物品Inaxz 20X1 15x2 18x3 14x4 8x5 4x6 10x75x1 5x2 2x3 6x4 12x5 2x6 4x7 25为 0 或 1,i 1,2，,75、工厂每月生产 A、B、C三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源 限量及单件产品利润如下图所示：产资品 源、ABC资源限量材料（kg）142500设备（台时）31400利润（元/件）101412根据市场需求，预测三种产品最低月需求量分别是150、260、120,最高需

5、求量是250、310、130,试建立该问题数学模型，使每月利润最大，为求解。解：设每月生产 A B、C数量为x1,X2.X3oMaxZ 10X114x2 12x33xi 1.6X2 1.2X3140011.5x1 1.2x2 4x32500150 Xi 250260 X2310120 X3 130Xi, X2, X306、A、B两种产品，都需要经过前后两道工序，每一个单位产品A需要前道工序1小时和后道工序2小时，每单位产品B需要前道工序2小时和后道工序3小时。可供利用的前道工序 有11小时，后道工序有17小时。 每加工一个单位产品 B的同时，会产生两个单位的副产 品C,且不需要任何费用，产品C

6、 一部分可出售盈利，其余只能加以销毁。出售A B、C的利润分别为3、7、2元，每单位产品C的销毁费用为1元。预测表明，产品 C最多只能售 出13个单位。试建立总利润最大的生产计划数学模型，不求解。解：设每月生产 A B数量为X1，X2，销毁的产品C为X3。MaXZ 3x1 7x2 2(2x2 x3) x3广 x1 2x2 112x1 3x2 172x2 x3 13L X1,X2,X307、靠近某河流有两个化工厂（参见附图），流经第一化工厂的河流流量为每天500 m3,在两个工厂之间有一条流量为200万m3的支流。第一化工厂每天排放有某种优化物质的工业污水2万m3 ,第二化工厂每天排放该污水万m

7、3。从第一化工厂的出来的污水在流至第二化工厂的过程中，有20前自然净化。根据环保要求，河流中的污水含量不应大于这两个工厂的都需要各自处理一部分工业污水。第一化工厂的处理成本是1000元/万m3,第二化工厂的为800元/万m3。现在要问满足环保的条件下，每厂各应处理多少工业污水，才 能使两个工厂的总的污水处理费用最少？列出数学模型，不求解。解：设第一化工厂和第二化工厂的污水处理量分别为每天X1 m3和X2万m3 ,min Z 1000x1 800x21 x120.8x1 x2 1.6 stx2 1.4x1,x208、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等），希望获得其中的营养成分（

8、如：蛋白质、脂肪、维生素等）。设市面上现有这 3种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量 （单位都略去）见下表。营养物 营养成二甲乙丙至少需要的营养成分数量A462080B11265C10370D21735450价格252045问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用计算。解：设购买甲、乙、丙三种营养物的数量分别为X、x2和x3,则根据题意可得如下线性规划模型：min z 25x1 20x2 45兄4x1 6x2 20x3 80x1 x2 2x3 65stx1 3x3 7021x1 7

9、x2 35x3 450x1,x2,x309、某公司生产的产品 A, B, C和D都要经过下列工序：包（J、立铳、钻孔和装配。已知每单 位产品所需工时及本月四道工序可用生产时间如下表所示：刨立铳钻孔装配AB.CD可用生产时间 （小时）1800280030006000又知四种产品对利润贡献及本月最少销售需要单位如下:产品最少销售需要单位元/单位A1002B6003C5001D4004问该公司该如何安排生产使利润收入为最大？（只需建立模型）解：设生产四种产品分别X1,X 2,x 3,x 4单位则应满足的目标函数为：max z=2 x i+3 X2+X3+ x 4满足的约束条件为：0.5为 x2 x3

10、 0.5x4 18002为 x2 x3 x4 28000.5x, 0.5x2 x3 x4 30003为 x2 2x3 3x4 6000x1 100x2 600x3 500x4 40010、某航空公司拥有 10架大型客机、15架中型客机和2架小型客机，现要安排从一机场 到4城市的航行计划，有关数据如表 1-5 ,要求每天到D城有2个航次（往返），到A,B,C 城市各4个航次（往返），每架飞机每天只能完成一个航次，且飞行时间最多为18小时，求利润最大的航班计划。客机类型到达城市飞行费用（元/次）飞行收入（元/次）飞行时间（h/d ）A600050001大型B700070002C8000100005

11、D100001800010中型A100030002B200040004C400060008D20小型A200040001B350055002C600080006D19解：设大型客机飞往A城的架次为x1A,中型客机飞往 A城的架次为x2A,小型客机飞往 A城的架次为x3A,其余依此类推。资源限制 派出的大型客机架次不能超过10架，表示为xA XbxcxD 10同理X2A X2B X2C 15X3A X3B X3C 2班次约束飞往各城的班次要满足X2AX3A4X2BX3B4X2CX3C4X2DX3D2X1AX1BX1CX1D非负性约束目标函数为Xj0 且为整数；(i=1,2,3rA,B,C,D)m

12、aXz 1000X1A 0XB 2000X1c 8000X1D+2000X2 A 2000X2B 20000 2000X3A 2000X3B 2000X3C11、CRISP公司制造四种类型的小型飞机：AR1型（具有一个座位的飞机）、AR2型（具有两个座位的飞机）、AR4型（具有四个座位的飞机）以及AR6型（具有六个座位的飞机）。AR1和AR2一般由私人飞行员购买，而 AR4和AR6一般由公司购买，以便加强公司的飞行编队。为了提高安全性，联邦航空局（）对小型飞机的制造做出了许多规定。一般的联邦航空局制造规章和检测是基于一个月进度表进行的，因此小型飞机的制造是以月为单位进行的。表说明了 CRISP

13、公司的有关飞机制造的重要信息。AR1AR2AR4AR6联邦航空局的最大产量（每月生产的飞机数目）8171115建造飞机所需要的时间（天）47911每架飞机所需要的生产经理数目1122每架飞机的盈利贡献（千美元）6284103125CRISP公司下个月可以得到的生产经理的总数是60人。该公司的飞机制造设施可以同时在任何给定的时间生产多达9架飞机。因此，下一个月可以得到的制造天数是270天（9*30,每月按30天计算）。Jonathan Kuring是该公司飞机制造管理的主任，他想要确定下个月的 生产计划安排，以便使盈利贡献最大化。解：设X1表示下个月生产 AR1型飞机的数目，X2表示AR2型，X

14、3表示AR4型，X4表示AR6 型目标函数： maxz 62x1 84x2 103x3 125x44x1 7x2 9x3 11x4270x1 x2 2x3 2x460x18约束条件：x2 17X3 11X4 15 X1,X2,X3,X40Xl,X2,X3,X4 为整数12、永辉食品厂在第一车间用1单位原料N可加工3单位产品A及2单位产品B,产品A可以按单位售价8 元出售，也可以在第二车间继续加工，单位生产费用要增加6 元， 加工后单位售价增加9 元。 产品B 可以按单位售价7 元出售， 也可以在第三车间继续加工，单位生产费用要增加4元，加工后单位售价可增加 6元。原料N的单位购入价为2元，上述

15、生产费用不包括工资在内。3 个车间每月最多有20 万工时，每工时工资元，每加工1 单位 N 需要工时，若A继续加工，每单位需 3工时，如B继续加工，每单位需 2工时。原料N每月最多能得到 10 万单位。问如何安排生产，使工厂获利最大？解：设Xi为产品A的售出量；X2为A在第二车间加工后的售出量；必表示产品B的售出量;X4表示B在第三车间加工后的售出量；X5为第一车间所用原材料的数量，则目标函数为：maX z 8X1 9.5 X2 7X3 8X4 2.75X5X5 1000003X2 2X4 1.5X5 200000约束条件：X1 X2 3X5 0X3 X4 2 X5 0X1,X2,X3,X4,

16、X5化标准形式1、将下列线性规划模型化为标准形式解：min z x12x23x3xx2x37x1x2x323x1x22x35x10x20x3无约束0 x7maxzx1 2x2 3(x4 x5) 0 x6Xix2x4 x5 %xix2x4 x5 夫3x1x22x3xi 702、将下列线性规划模型化为标准形式min z x12x23x32x1乂2x393x1乂22x344x12x23x36x10x20&无约束解:max zx1 2x23x3 3x32x1x2x3 x3x493x1x22x3 2x3x544x12x23x3 3x36x1 503、将下列线性规划变为最大值标准形。min z3x1 4x

17、2 2x3 5x44x1 x2 2x3 x42x1 x2 3x3 x414st2x1 3x2 x3 2x42x1,x2,x3 0,x4 无约束解：max z 3x1 4x2 2x3 5x4 5x4st4 x1x2 2 x3x4x1 x2 3x3 x4 x42 x13 x2x3 2x4x42x5 142 x4 x6x1, x2,x3,x4,x4 , x5, x6图解法1、用图解法求解下面线性规划min z = - 3xi+2x22xi 4x222x1 4x2 102x1 x2 7xi 3x21xi, x20解：可行解域为abcda,最优解为b点。2x1 4x222由方程组解出xi=11, x2=

18、0x2 0x11 ,_、 T. X= = (11, 0)x22 .min z = -3X 11+2X0=332、用图解法求解下面线性规划min z =2x 1+x2x1 4x224X 沟 85 x 10x20解：从上图分析，可行解域为abcde,最优解为e点。由方程组x1 x2 8_解出 x1=5, x2=3x15x1. X= = (5, 3) T x2 .min z =Z = 2X5+3=133、已知线性规划问题如下：Max Z= x1 3x2/5x1 10x2 50x1 x2 1X2Xi,X2 0用图解法求解，并写出解的情况解之得:5xi 10X250X12X2贝U maX Z=2+3*4

19、=144、用图解法求解下面线性规划问题maXz2x1 x25x16x1 st.X2152x2 24 x2 5X1 , X20解:5、用图解法求解下面线性规划问题max z 2xi 3x2x1 2x28st4x1 164x2 12xj 0, j 1,2图解如下:T可知，目标函数在 B(4, 2)处取得最大值，故原问题的最优解为X (4,2),目标函数最大值为 z 2*43*214。二、单纯型法1、用单纯型法求解下面线性规划问题的解max z= 3x 1 +3x2+4x33x1 4x2 5x3406x1 4x2 3x3 66 .K,x2, x3 0解：加入松弛变量 x4, x5,得到等效的标准模型

20、：max z= 3x1+3*2+4*3+0 x 4+0 x 53x1 4x2 5x3 x4406x1 4x2 3x3x5 66xj 0, j 1,2,.,5列表计算如下:CBXBb3x13x24x30x40x50 L0x44034(5)1080x566643012200000334T004x383/54/511/5040/30x542(21/5 )8/50-3/511012/516/544/503/5 T1/50-4/504x3204/712/71/73x11018/2101/75/21324/745/71/7380 3/70-5/71/7. X*= 10, 0, 2, 0, 0 T max

21、z =3 10+4 2 =382、用单纯型法求解下面线性规划问题的解max z =70x 1+120X29x1 4x2 3604x1 6x2 200.3xi 10x2300x1, x2 0解：加入松弛变量 x3, x4, x5,得到等效的标准模型： max z =70x 1+120x2+0 x 3+0 x 4+0 x 5 .9x1 4x2 x33604x1 6x2x42003x110x2x5300xj 0,j 1,2,.,5列表计算如下:CBXBb70x1120x20x30x40x50 L0x336094100900x420046010100/30x53003(10)0013000000701

22、20T0000x324039/5010-2/5400/130x420(11/5 )001-3/5100/11120x2303/101001/1010036120001234 T000120x31860/1100139/1119/1170120x1x2100/11300/111005/11- 3/11010- 3/222/1143000701200170/1130/11000-170/11- 30/1111.X=(整11300111860 八，0,110)max z =7010030043000彳+1201干3、用单纯型法求解下面线性规划问题的解max z = 4x 1+3x2.2x15x1x1

23、2x230002.5x24000500x1 , x2解：加入松弛变量x3 , x4,x5,得到等效的标准形式:2x1 2x2 x3 30005x1 2.5x2 x44000max z= 4x 1 + 3x2+0 x 3+0 x 4+0 x 5.xx 500xj 0, j 1,2,.,5用表解形式的单纯形法求解，列表计算如下:43000CBXBbx1x2x3x4x50 L0x33000221003000/2 =15000x4400050104000/5 =8000x5500(1)0001500/1 =500000004 T30000x320000210-22000/2 =10000x415000

24、()01-51500/ =6004X1500100014000403 T00-40X3800001(2)800/2 =4003X2600010-24X150010001500/1 =500430-20002 20X54000013X2140001104X1100100r 4310460000-10据上表，X= (100, 1400, 0, 0, 400) Tmax z = 4X 100+3X 1400=4604、用单纯型法求解下面线性规划问题的解max z =10x 1+6X2+4X3 .X1 x2 x3 10010X1 4X2 5X3 600 2X1 2X2 6X3 300 X, X2, X

25、30解：加入松弛变量 X4, X5, X6,得到等效的标准模型： maX z =10x 1+6X2+4X3+0 x 4+0 x 5+0 x 6X1 x2 x3 x410010x1 4x2 5x3x5600.2x1 2x2 6x3X6 300Xj 0,j 1,2,.,6列表计算如下:1064000CBXBbx50 Lx1x2x3x4x60x41001111001000x5600(10)45010600x630022600115000000010T640000x4400(3/5 )1/211/100200/310x16012/51/201/1001500x618006/5501/511501045

26、01002 T10106x2200/3015/65/31/6010x1100/3101/6 2/31/600x6100004-201220010620/310/32/30300 8/310/3 2/30*100 X=(,32000,0, 0,100) Tmax z = 10X100+6X 200 22005、用单纯型法求解下面线性规划问题的解Max Z4x1 -2x2 2x 33x1X2X360xix22x3102x12x22x340x1，x2,x3用单纯形法求解，并指出问题的解属于哪一类。 解：（1）、将原问题划为标准形得：MaxZ4x12x2 2x3 0x4 0x5 0x63x1x2x3x

27、4二60xix22x3X5102x12x2 2x3x640Xi,X2,X3,X4,X5,X6Cj4-22000XbbX1X2X3X4X5X60X4603111000X5101-120100X6402-22001j4-22000Cj4-22000XbbX1X2X3X4X5X60X43004-51-304Xi101-120100X62004-60-21j02-60-40Cj4-22000XbbX1X2X3X4X5X60X4100011-1-14Xi15101/201/21/4-2X2501-3/20-1/21/4j00-30-3-1/2所以X= (15, 5, 0, 10, 0, 0) T为唯一最

28、优解MaX Z=4*15-2*5=506、用单纯形法求解下述 LP问题。max z 2.5x1 x23x1 5x2 15st 5xi 2x2 10 x1,x2 0解：引入松弛变量 x3、化为标准形式:max z 2.5x1 x2st3x1 5x25x1 2x2x315x4 10xi,x2,x3,x4构造单纯形表，计算如下:cj100icBXBbXiX2X3X40x315351050x41052012j1000x39019/51 3/545/19Xi212/501/55j0001/21X245/19015/19 3/19Xi20/1910 2/195/19j0001/2由单纯形表，可得两个最优解

29、X(2,0,9,0) T、X(20 /19,45 /19,0,0) T,所以两点之间的所有解都是最优解，即最优解集合为：X(1) (1)*出，其中01。7、用单纯形法解线性规划问题max z 2x1 x25x2156x12x224x1x25x10解：化为标准型maxz 2x1 x2 0x3 0x4 0x55x2x3156x12x2x424x1x2x55x1 50列出单纯形表C21000CB先bxix2x3x4x50*315051000x4246201040x55110015-Z0210000x3150510032xi411/301/60120x5102/30-1/613/2-Z-801/30-

30、1/300x315/20015/4-15/22xi7/21001/4-1/21x23/2010-1/43/2-Z-20000-1/4-1/2Z*=17/2, X*=(7/2,3/2, 15/2,0,0)x108、用单纯型法求解下面线性规划问题的解maxz x1 x2x12x222x1x22x1x24x2解:C11000CB先bXiX2X3x4X50x3211210020x42-210100x54-11001-Z0110001Xi21-210000x4x56600-3-1211001-Z-203-100把表格还原为线性方程max z 3x2 x3 2x12x2x323x，22x.3x46x2x3

31、x56x122x2x3x463x22x3x56x2x3令 x 3 =0x122x2x463x2x56x2此时，若让x2进基，则会和基变量xi同时增加，使目标函数值无限增长，所以本题无界9、用单纯型法求解下面线性规划问题的解max z 2x1 4x2x12x28x14x23x1 0x2 0C24000CbXbbx1x2x3x4x50x381210040x44100100x53010013-Z0240000x321010-220x441001044x2301001-Z-122000-42x121010-20x4200-1124x2301001-Z-2000-2002x14100100x5100-1

32、/21/214x22011/2-1/20-Z-2000-200Z*=20, X*=(2,3,0,2,0) Z*=20, X*=(4,2,0,0,1)10、用单纯型法求解下面线性规划问题的解max z 3xi 5x2x142x2123xi2x218x1 0x2 0解：列表如下C35000CbXbbx1x2XsX4X50x34101000x4120201060x518320019-Z0350000x341010045x260101/200x56300-113-Z-30300-5/200x360011/3-1/35x220101/203x12100-1/31/3-Z-20000-3/2-1X*=(2

33、,6,6,0,0)Z*=3611、用单纯型法求解下面线性规划问题的解maxz 2x1 x25x1 156x1 2x2 24 st.x2 x2 5xnx2 0解：化为标准型max z 2x1 x25xi X3 156x1 stx22x2 x424X2 x55x1,x2,x3,x4,x5 0单纯型表如下：C21000CbXbbxix2x3x4x50x31505100一0x4246201040x55110015Z0210000x3150510032xi411/301/60120x5102/30-1/613/2Z001/30-1/300x315/20015/4-15/22xi7/21001/4-1/2

34、1x23/2010-1/43/2Z17/2000-1/4-1/2由些可得，问题的最优解为xi=7/2 , x2=3/2 ,最优值 max z=17/212、用大M法求解如下线性规划模型：min z =5x 1 + 2x2+4x33 x1 x2 2 x46x1 3x2 5x3 10 x1,x2,x3 0解：用大M法，先化为等效的 标准模型： max z/ = - 5xi 2x2 4x3 .3x1 x2 2x3 x446x1 3x2 5x3% 10V 、 0,j 1,2,.,5增加人工变量*6、x7,得到：max z/ = 5xi 2x2 4x3一做6 MeCB3xj x2 2x3 x46 k 3

35、x2 5x3 xj 0,j 1,2,7大M法单纯形表求解过程如下：x%一 4x34x7 10一 Mx6一 Mx70 LXBb-5x1-2x20x40x5一 Mx64(3)1210104/3一 Mx71063501015/39M-4M-7MMM一 M一 M9M- 5 T4M- 27M- 4一 M一 M00-5x14/311/32/31/301/30一 Mx72011(2)1-211-5-M5/3-M-10/3-2M+5/3M2M- 5/3-M0M- 1/3M- 2/32M- 5/3 T一 M3M+5/30-5x15/311/25/601/601/610/30x410(1/2 )1/211/211

36、/22-5 5/2 25/605/60-5/601/2 T1/60-5/6一 MM+5/6-5x12/3101/311/311/3-2x2201121-21一-5-211/311/311/3223001/311/3M+1-M+1/3*x =(23 2,0, 0, 0) T最优目标函数值min z =max z/ =,22、3=22 313、用大M法求解如下线性规划模型:min z =540x 1+ 450X2+720X33x1 5x2 9x3 709xi 5x2 3x3 30x1,x2,x30解：用大M法，先化为等效的 标准模型：max z/ = 540xi 450x2 720x3.3x1 5

37、x2 9x3 x4709x1 5x2 3x3x5 30yj0, j 1,2,.,5增加人工变量x6、7,得到：max z/ = 540xi 450x2 720x3 Mx, Mx3x15x2 9x3 x4x6709x15x2 3x3x5x730xj0,j 1,2,.,5大M法单纯形表求解过程如下:CBXBb-540x1-450x2-720x30x40x5一 Mx6一 Mx70 L一 Mx670359101070/3一 Mx730(9)53010130/9=10/3-12M10M12MMM一 M一 M12M- 540 T10M- 45012M- 720一 M一 M00一 Mx660010/3(8)

38、11/311/360/8=-540x110/315/91/301/901/910/3/1/3=10-300+10/3M-8M-180一 MM/3+60一 MM/3 600-150+10/3M8M-540 TMM/3-600M/3+6015/2/5/1 720x315/205/121-1/81/241/8-1/242=18-540x15/61(5/12 )01/241/81/241/85/6/5/12=2-540-572-720135/2475/12135/2-75/20125 T0135/2-475/12135/2 M75/2 M-720x320/31011/61/61/61/6-450x2212/5101/10 3/101/103/10 360-450 720751575-15-5700 18000-75-1575-M15-M*T20，该对偶问题的最优解是x=(0, 2,0, 0)最优目标函数值 min z = ( 5700)14、用单纯形法求解线性规划问题二5700化成标准形式有maxz3x1 x3Xi2x1x1 0x2x3x2x33x2x3x2 0 x3 0max z3x1 x