《运筹学》题库.docx

《《运筹学》题库.docx》由会员分享，可在线阅读，更多相关《《运筹学》题库.docx（50页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、运筹学习题库数学建模题51、某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储藏如下表所示：ABC甲94370乙4610120360200300试建立使得该厂能获得最大利润的生产方案的线性规划模型，不求解。解：设甲、乙产品的生产数量应为x1、x2，那么x1、x20，设z是产品售后的总利润，那么max z =70x1+120x2s.t.2、某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下：甲 乙可用量原材料吨/件工时工时/件零件套/件2 25 13000吨4000工时500套产品利润元/件 4 3建

2、立使利润最大的生产方案的数学模型，不求解。解：设甲、乙两种产品的生产数量为x1、x2，设z为产品售后总利润，那么max z = 4x1+3x2s.t.3、一家工厂制造甲、乙、丙三种产品，需要三种资源技术效劳、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储藏量如下表所示：技术效劳劳动力行政管理单位利润甲110210乙1426丙1564资源储藏量100600300建立使得该厂能获得最大利润的生产方案的线性规划模型，不求解。解：建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为x1、x2、x3，那么x1、x2、x30，设z是产品售后的总利润，那么max

3、 z =10x1+6x2+4x3s.t.4、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量/Kg55261224重要性系数2试建立队员所能携带物品最大量的线性规划模型，不求解。解：引入01变量xi, xi=1表示应携带物品i，,xi=0表示不应携带物品I5、工厂每月生产A、B、C三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如以下图所示：产品资源A BC资源限量材料

4、kg42500设备台时31400利润元/件101412根据市场需求，预测三种产品最低月需求量分别是150、260、120，最高需求量是250、310、130，试建立该问题数学模型，使每月利润最大，为求解。解：设每月生产A、B、C数量为。 6、A、B两种产品，都需要经过前后两道工序，每一个单位产品A需要前道工序1小时和后道工序2小时，每单位产品B需要前道工序2小时和后道工序3小时。可供利用的前道工序有11小时，后道工序有17小时。 每加工一个单位产品B的同时，会产生两个单位的副产品C，且不需要任何费用，产品C一局部可出售盈利，其余只能加以销毁。 出售A、B、C的利润分别为3、7、2元，每单位产品

5、C的销毁费用为1元。预测说明，产品C最多只能售出13个单位。试建立总利润最大的生产方案数学模型，不求解。解：设每月生产A、B数量为销毁的产品C为。 7、靠近某河流有两个化工厂参见附图，流经第一化工厂的河流流量为每天500，在两个工厂之间有一条流量为200万的支流。第一化工厂每天排放有某种优化物质的工业污水2万。从第一化工厂的出来的污水在流至第二化工厂的过程中，有20%可自然净化。根据环保要求，河流中的污水含量不应大于0.2%。这两个工厂的都需要各自处理一局部工业污水。第一化工厂的处理本钱是1000元/万，第二化工厂的为800元/万。现在要问满足环保的条件下，每厂各应处理多少工业污水，才能使两个

6、工厂的总的污水处理费用最少？列出数学模型，不求解。附图： 工厂1 工厂2 500万 200万解：设第一化工厂和第二化工厂的污水处理量分别为每天和x2万，st8、消费者购置某一时期需要的营养物如大米、猪肉、牛奶等，希望获得其中的营养成分如：蛋白质、脂肪、维生素等。设市面上现有这3种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量单位都略去见下表。营养物营养成分甲乙丙至少需要的营养成分数量A462080B11265C10370D21735450价格252045问：消费者怎么购置营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用

7、计算。解：设购置甲、乙、丙三种营养物的数量分别为， 那么根据题意可得如下线性规划模型：9、某公司生产的产品A，B，C和D都要经过以下工序：刨、立铣、钻孔和装配。每单位产品所需工时及本月四道工序可用生产时间如下表所示：刨立铣钻孔装配AB1.0.1.0.CD可用生产时间小时06000又知四种产品对利润奉献及本月最少销售需要单位如下：产品最少销售需要单位元/单位A1002B6003C5001D4004问该公司该如何安排生产使利润收入为最大？只需建立模型解：设生产四种产品分别x1,x2,x3,x4单位那么应满足的目标函数为：max z=2 x1+3 x2+ x3+ x4满足的约束条件为：10、某航空公

8、司拥有10架大型客机、15架中型客机和2架小型客机，现要安排从一机场到4城市的航行方案，有关数据如表1-5，要求每天到D城有2个航次往返，到A,B,C城市各4个航次往返，每架飞机每天只能完成一个航次，且飞行时间最多为18小时，求利润最大的航班方案。客机类型到达城市飞行费用元/次飞行收入元/次飞行时间h/d大型A6000700080001000050007000100001800012510BCD中型A100020004000-300040006000-24820BCD小型A200035006000-400055008000-12619BCD解：设大型客机飞往A城的架次为x1A，中型客机飞往A城

9、的架次为x2A，小型客机飞往A城的架次为x3A，其余依此类推。资源限制 派出的大型客机架次不能超过10架，表示为同理 班次约束 飞往各城的班次要满足非负性约束 且为整数；i=1,2,3;j=A,B,C,D目标函数为 11、 CRISP公司制造四种类型的小型飞机：AR1型具有一个座位的飞机、AR2型具有两个座位的飞机、AR4型具有四个座位的飞机以及AR6型具有六个座位的飞机。AR1和AR2一般由私人飞行员购置，而AR4和AR6一般由公司购置，以便加强公司的飞行编队。为了提高平安性，联邦航空局F.A.A对小型飞机的制造做出了许多规定。一般的联邦航空局制造规章和检测是基于一个月进度表进展的，因此小型

10、飞机的制造是以月为单位进展的。表说明了CRISP公司的有关飞机制造的重要信息。AR1AR2AR4AR6联邦航空局的最大产量每月生产的飞机数目建造飞机所需要的时间天每架飞机所需要的生产经理数目每架飞机的盈利奉献千美元84162177184119210315112125CRISP公司下个月可以得到的生产经理的总数是60人。该公司的飞机制造设施可以同时在任何给定的时间生产多达9架飞机。因此，下一个月可以得到的制造天数是270天9*30，每月按30天计算。Jonathan Kuring是该公司飞机制造管理的主任，他想要确定下个月的生产方案安排，以便使盈利奉献最大化。解：设表示下个月生产AR1型飞机的数

11、目，表示AR2型，表示AR4型， 表示AR6型 目标函数： 约束条件： 为整数12、永辉食品厂在第一车间用1单位原料N可加工3单位产品A及2单位产品B，产品A可以按单位售价8元出售，也可以在第二车间继续加工，单位生产费用要增加6元，加工后单位售价增加9元。产品B可以按单位售价7元出售，也可以在第三车间继续加工，单位生产费用要增加4元，加工后单位售价可增加6元。原料N的单位购入价为2元，上述生产费用不包括工资在内。3个车间每月最多有20万工时，每工时工资0.5元，每加工1单位N需要1.5工时，假设A继续加工，每单位需3工时，如B继续加工，每单位需2工时。原料N每月最多能得到10万单位。问如何安排

12、生产，使工厂获利最大？解：设为产品A的售出量；为A在第二车间加工后的售出量；表示产品B的售出量；表示B在第三车间加工后的售出量；为第一车间所用原材料的数量， 那么目标函数为： 约束条件： 化标准形式51、将以下线性规划模型化为标准形式解： 2、将以下线性规划模型化为标准形式解：3、将以下线性规划变为最大值标准形。解： 图解法51、用图解法求解下面线性规划min z =3x1+2x2解：可行解域为abcda，最优解为b点。由方程组 解出x1=11，x2=0X*=11，0Tmin z =311+20=332、用图解法求解下面线性规划min z =2x1+x2解：从上图分析，可行解域为abcde，最

13、优解为e点。由方程组 解出x1=5，x2=3X*=5，3Tmin z =Z*= 25+3=133、线性规划问题如下：Max Z= 用图解法求解，并写出解的情况解： x2 6 Z 4 x2=4 2Zx10 2 4 6 8 105x1+10x2=50 x1+x2=1由图可知： 解之得：那么max Z=2+3*4=14 4、用图解法求解下面线性规划问题解：5、用图解法求解下面线性规划问题图解如下：可知，目标函数在B(4, 2)处取得最大值，故原问题的最优解为，目标函数最大值为。二、单纯型法151、用单纯型法求解下面线性规划问题的解max z= 3x1+3x2+4x3s.t.解：参加松弛变量x4，x5

14、，得到等效的标准模型：max z= 3x1+3x2+4x3+0 x4+0 x5s.t.列表计算如下：CBXBb33400Lx1x2x3x4x50x4403451080x566643012200000334004x383/54/511/5040/30x54221/58/503/511012/516/544/503/51/504/504x3204/712/71/73x11018/2101/75/2138324/745/71/703/705/71/7X*=10，0，2，0，0T max z =310+42 =382、用单纯型法求解下面线性规划问题的解max z =70x1+120x2s.t.解：参加

15、松弛变量x3，x4，x5，得到等效的标准模型：max z =70x1+120x2+0 x3+0 x4+0 x5s.t.列表计算如下：CBXBb70120000Lx1x2x3x4x50x336094100900x420046010100/30x53003100013000000701200000x324039/5010- 2/5400/130x42011/5001 - 3/5100/11120x2303/10 100 1/1010036120001234000120x31860/1100139/1119/1170x1100/11100 5/11- 3/11120x2300/11010- 3/22

16、 2/11701200170/1130/11000-170/1130/11X*=，0，0Tmax z =70+120=3、用单纯型法求解下面线性规划问题的解max z = 4x1+3x2s.t.解：参加松弛变量x3，x4，x5，得到等效的标准形式：max z= 4x1+3x2+0 x3+0 x4+0 x5s.t.用表解形式的单纯形法求解，列表计算如下：CBXBb43000Lx1x2x3x4x50x330/2 =15000x4400050104000/5 =8000x550010001500/1 =50000000 430000x320000210-22000/2 =10000x41500001

17、-51500/2.5 =6004x150010001400040 300-40x38000012800/2 =4003x2600010-24x0/1 =500430-2000- 20x540000-0.413x21400011-04x110010-04600431000-1-0据上表，X*=100，1400，0，0，400T max z =4100+31400=4604、用单纯型法求解下面线性规划问题的解max z =10x1+6x2+4x3s.t.解：参加松弛变量x4，x5，x6，得到等效的标准模型：max z =10x1+6x2+4x3+0 x4+0 x5+0 x6s.t.列表计算如下：C

18、BXBb1064000Lx1x2x3x4x5x60x410x56001045010600x6300000010640000x44003/51/211/100200/310x16012/51/201/1001500x618006/5501/5115010450100210106x2200/3015/65/31/6010x1100/3101/62/31/600x610000420110620/310/32/30008/310/32/30X*=，0，0，0，100Tmax z =10+6=5、用单纯型法求解下面线性规划问题的解用单纯形法求解，并指出问题的解属于哪一类。解：1、将原问题划为标准形得：

19、=604-22000b0603111000101-120100402-220014-22000 4-22000b03004-51-304101-1201002004-60-2102-60-404-22000b0100011-1-1415101/201/21/4-2501-3/20-1/21/400-30-3-1/2所以X=15，5，0，10，0，0T 为唯一最优解 Max Z=4*15-2*5=50 6、用单纯形法求解下述LP问题。解：引入松弛变量、，化为标准形式：构造单纯形表，计算如下：100015351050105201210009019/513/545/19212/501/550001/

20、2145/19015/193/1920/19102/195/190001/2由单纯形表，可得两个最优解、，所以两点之间的所有解都是最优解，即最优解集合为：，其中。7、用单纯形法解线性规划问题解：化为标准型列出单纯形表Cj21000CBXBbx1x2x3x4x5000x3x4x51524506152110001000145-Z021000020x3x1x5154101051/32/310001/6-1/60013123/2-Z-801/30-1/30021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2-Z-20000-1/4-1/2Z*=17/2,

21、 X*=(7/2,3/2, 15/2,0,0)8、用单纯型法求解下面线性规划问题的解解：Cj11000CBXBbx1x2x3x4x5000x3x4x52241-2-112111000100012-Z011000100x1x4x5266100-2-3-1121010001-Z-203-100把表格复原为线性方程令x 3=0此时，假设让x2进基，那么会和基变量x1同时增加，使目标函数值无限增长，所以此题无界9、用单纯型法求解下面线性规划问题的解Cj24000CBXBbx1x2x3x4x5000x3x4x584311020110001000143-Z024000004x3x4x22431100011

22、00010-20124-Z-122000-4204x1x4x22231000011-10010-221-Z-2000-200204x1x5x24121000010-1/21/211/2-1/2010-Z-2000-200Z*=20, X*=(2,3,0,2,0)Z*=20, X*=(4,2,0,0,1)10、用单纯型法求解下面线性规划问题的解解：列表如下Cj35000CBXBbx1x2x3x4x5000x3x4x54121810302210001000169-Z035000050x3x2x546610301010001/2-100143-Z-30300-5/20053x3x2x16220010

23、101001/31/2-1/3-1/301/3-Z-20000-3/2-1X*=(2,6,6,0,0) Z*=3611、用单纯型法求解下面线性规划问题的解解：化为标准型单纯型表如下：Cj21000CBXBbx1x2x3x4x5000x3x4x51524506152110001000145Z021000020x3x1x5154101051/32/310001/6-1/60013123/2Z001/30-1/30021x3x1x215/27/23/20100011005/41/4-1/4-15/2-1/23/2Z17/2000-1/4-1/2由些可得，问题的最优解为x1=7/2，x2=3/2，最优

24、值max z=17/212、用大M法求解如下线性规划模型：min z =5x12x24x3解：用大M法，先化为等效的标准模型：max z/ =5x12x24x3s.t.增加人工变量x6、x7，得到：max z/ =5x12x24x3Mx6Mx7大M法单纯形表求解过程如下：CBXBb52400MMLx1x2x3x4x5x6x7Mx6431210104/3Mx71063501015/39M4M7MMMMM9M54M27M4MM005x14/311/32/31/301/30Mx72011212115-M5/3-M10/3-2M+5/3M2M5/3-M0M1/3M2/32M5/3M3M+5/305x1

25、5/311/25/601/601/610/30x4101/21/211/211/2255/225/605/605/601/21/605/6MM+5/652x12/3101/311/311/3x2201121215211/311/311/3001/311/3M+1M+1/3x*=，2，0，0，0T最优目标函数值min z =max z/ =13、用大M法求解如下线性规划模型：min z =540x1450x2720x3解：用大M法，先化为等效的标准模型：max z/ =540x1450x2720x3s.t.增加人工变量x6、x7，得到：max z/ =540x1450x2720x3Mx6Mx7大

26、M法单纯形表求解过程如下：CBXBb54045072000MMLx1x2x3x4x5x6x7Mx670359101070/3Mx730953010130/9=10/312M10M12MMMMM12M54010M45012M720MM00Mx660010/3811/311/3540x110/315/91/301/901/910/3/1/3=10-300+10/3M-8M180MM/3+60MM/3600-150+10/3M8M-540MM/3600M/3+60720x315/205/1211/81/241/81/2415/2/5/12=18540x15/615/1201/241/81/241/8

27、5/6/5/12=2540572720135/2475/12135/275/201250135/2475/12135/2M75/2M720450x320/31011/61/61/61/6x2212/5101/103/101/103/1057003604507207515751518000751575M15M该对偶问题的最优解是x*=0，2，0，0T最优目标函数值min z =5700=5700 14、用单纯形法求解线性规划问题化成标准形式有参加人工变量那么为列出单纯形表Cj30100M-MCBXBbx1x2x3x4x5x6x70-M-Mx4x6x74191-201131-111000-1001

28、0001-Z10M-2M-34M10-M0000-Mx4x2x73163-260102-141001-13-11-3001-Z6M6M-304M+103M-4M000-3x4x2x103100101001/32/3100-1/201/2-1/20-1/21/21/31/6-Z300303/2-M-3/2-M+1/2001x4x2x305/23/20-1/23/2010001100-1/2-1/43/41/21/4-3/4-1/21/41/4-Z-3/2-9/2000-3/4-M+3/4-M-1/4人工变量已不在基变量中，X*=(0,5/2,3/2,0,0,0,0) Z*=3/215、用单纯形法

29、求解线性规划问题解 化为标准形式有列表计算Cj3200MCBXBbx1x2x3x4x50Mx3x52122314100-10123-Z-12M3M+34M+20-M0-2Mx2x5242-5101-40-101-Z4-4M-5M-10-4M-2-M0X*=(0,2,0,0,4) Z*=4M-4 说明原问题无解 写对偶问题101、 写出以下线性绘画问题的对偶问题解： 2、写出下述线性规划的对偶问题解3、写出以下线性规划的对偶问题解：4、写出以下线性规划的对偶问题解 对偶性质1、线性规划问题如下：Max Z= 该问题的解为2，4利用对偶性质写出对偶问题的最优解。解：该问题的对偶问题为：将X=2，4T代入原问题可知：1 为严格不等式，所以由对偶问题性质可知： 解之得： 所以Y=1/5，0，1T Min Z=14 2、线性规划问题用图解法求对偶问题的解；利用(b)的结果及对偶性质求原问题解。答案：(对偶问题的最优解为；(依据z*=w*及互补