《运筹学》题库

1、运筹学习题库数学建模题（5）1、某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲94370乙4610120360200300试建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：设甲、乙产品的生产数量应为xl、x2,则xl、x220,设z是产品售后的总利润，则maxz=70x+120x122、某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下：甲乙可用量223000吨原材料（吨/件）工时（工时/件）54000工时零件（套/件）1500套产品利润（元/件）43建立使

2、利润最大的生产计划的数学模型，不求解。解：设甲、乙两种产品的生产数量为x、x,12设z为产品售后总利润，则maxz=4x+3x123、一家工厂制造甲、乙、丙三种产品，需要三种资源技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：技术服务劳动力行政管理单位利润甲110210乙1426丙1564资源储备量100600300建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为x、x、x,贝VX、x、x20,设z是产品123123售后的总利润,则maxz=10x+6x+4

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

4、00设备（台时）31400利润（元/件）101412根据市场需求，预测三种产品最低月需求量分别是150、260、120，最高需求量是250、310、130，试建立该问题数学模型，使每月利润最大，为求解。解：设每月生产A、B、C数量为x,x,x。1236、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数量为x,x,销毁的产品C为x。1237、靠近某河流有两个化工厂（参见附图），流经第一化工厂的河流流量为每天500m3,在两个工厂之间有一条流量为200万m3的支流。第一化工厂每天排放有某种优化物质的工业污水2万m3，第二化工厂每天排放该污水万m3。从第一化工厂的出来的污水在流至第二化工厂的过程中，有20%可自然净化。根据环保要求，河流中的污水含量不应大于%。这两个工厂的都需要各自处理一部分工业污水。第一化工厂的处理成本是1000元/万m3，第二化工厂的为800元

6、/万m3。现在要问满足环保的条件下，每厂各应处理多少工业污水，才能使两个工厂的总的污水处理费用最少列出数学模型，不求解。m3禾口乂2万m3，21x1.61 2x0128、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等），希望获得其中的营养成分（如：蛋白质、脂肪、维生素等）。设市面上现有这3种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。营养物营养成分-甲乙丙至少需要的营养成分数量A462080B11265C10370D21735450价格252045问：消费者怎么购买营养物，才能既获得必要的营养成分，而花

7、钱最少只建立模型，不用计算。解：设购买甲、乙、丙三种营养物的数量分别为x、x和x，则根据题意可得如下123线性规划模型：9、某公司生产的产品A,B，C和D都要经过下列工序：刨、立铣、钻孔和装配。已知每单位产品所需工时及本月四道工序可用生产时间如下表所示：又知四种产品对利润贡献及本月最少销售需要单位如下：产品最少销售需要单位元/单位A1002B6003C5001D4004问该公司该如何安排生产使利润收入为最大（只需建立模型）解：设生产四种产品分别x,x,x,x单位1234则应满足的目标函数为：maxz=2x+3x+x+x1234满足的约束条件为：10、某航空公司拥有10架大型客机、15架中型客机

8、和2架小型客机，现要安排从一机场到4城市的航行计划，有关数据如表1-5,要求每天到D城有2个航次（往返），到A,B,C城市各4个航次（往返），每架飞机每天只能完成一个航次，且飞行时间最多为18小时，求利润最大的航班计划。客机类型到达城市飞行费用（元/次）飞行收入（元/次）飞行时间（h/d）大型A6000700080001000050007000100001800012510BCD中型A10002000400030004000600024820BCD小型A20003500600040005500800012619BCD解：设大型客机飞往A城的架次为x，中型客机飞往A城的架次为x，小型客1A2A机

9、飞往A城的架次为x，其余依此类推。3A资源限制派出的大型客机架次不能超过10架，表示为同理x+x+x152A2B2Cx+x+x0且为整数；（i=1,2,3j二A,B,C,D）目标函数为maxz二一lOOOx+0x+2000x+8000x+2000x+1A1B1C1D2A2000x+2000x+2000x+2000x+2000x11、2B2C3A3B3CAR1AR2AR4AR6联邦航空局的最大产量（每月生产的飞机数目）8171115建造飞机所需要的时间（天）47911每架飞机所需要的生产经理数目1122每架飞机的盈利贡献（千美元）6284103125CRISP公司下个月可以得到的生产经理的总数是

10、60人。该公司的飞机制造设施可以同时在任何给定的时间生产多达9架飞机。因此，下一个月可以得到的制造天数是270天（9*30,每月按30天计算）。JonathanKuring是该公司飞机制造管理的主任，他想要确定下个月的生产计划安排，以便使盈利贡献最大化。解：设x表示下个月生产AR1型飞机的数目，x表示AR2型，x表示AR4型，x表l234示AR6型目标函数：maxz=62x+84x+103x+125xl2344x+7x+9x+llx2701234x+x+2x+2x601 234x8约束条件：x172x113x01234x,x,x,x为整数123412、永辉食品厂在第一车间用1单位原料N可加工3

11、单位产品A及2单位产品B，产品A可以按单位售价8元出售，也可以在第二车间继续加工，单位生产费用要增加6元，加工后单位售价增加9元。产品B可以按单位售价7元出售，也可以在第三车间继续加工，单位生产费用要增加4元，加工后单位售价可增加6元。原料N的单位购入价为2元，上述生产费用不包括工资在内。3个车间每月最多有20万工时，每工时工资元，每加工1单位N需要工时，若A继续加工，每单位需3工时，如B继续加工，每单位需2工时。原料N每月最多能得到10万单位。问如何安排生产，使工厂获利最大解：设x为产品A的售出量；x为A在第二车间加工后的售出量；x表示产品B123的售出量；x表示B在第三车间加工后的售出量；

12、x为第一车间所用原材料的数45量，则目标函数为：maxz=8x+9.5x+7x+8x一2.75x12345x1OOOOO53x+2x+1.5x200000约束条件：2 45012345化标准形式（5）1、将下列线性规划模型化为标准形式minz=x-2x+3x123x+x+x21233x+x+2x=-5i23x0x0x无约束i23maxz=-x+2x-3(x-x)+0-x+0-x124567x+x+xx+x=712456xx+xxx=2124573xx2x=5i23x017解：2、将下列线性规划模型化为标准形式解：3、将下列线性规划变为最大值标准形解：图解法（5）1、用图解法求解下面线性规划mi

13、nz=3x+2x12解：可行解域为abcda,最优解为b点。”2x+4x=22由方程组1J=0解出x=ll,x=OX0122xX*=1=(11,0)TIx丿2.minz=3X11+2X0二一332、用图解法求解下面线性规划minz=2x+x12解：从上图分析，可行解域为abcde，最优解为e点。由方程组x+x=8解出x=5,x=31212x=51fxX*二1=(5,3)tIx丿2minz=Z*=2X5+3=133、已知线性规划问题如下：MaxZ=x+3x12用图解法求解,并写出解的情况解：62x2x=402468105x+10x=5012x+x=112由图可知：r5x+10x=50解之得:x=

14、212w1.则maxZ=2+3*4=144、用图解法求解下面线性规划问题解：5、用图解法求解下面线性规划问题图解如下：可知，目标函数在B（4,2）处取得最大值，故原问题的最优解为X*二（4,2）t，目标函数最大值为z*=2*4+3*2=14。二、单纯型法（15）1、用单纯型法求解下面线性规划问题的解maxz=3x1+3x2+4x33x+4x+5x401236x+4x+3x0123解：加入松弛变量x,x，45得到等效的标准模型：二40maxz=3x+3x2+4x3+0x+012x0,j二j列表计算如下：31,2,.,5b53x13x24x30x40x50LC:BXB0x44034(5)1080x

15、566643012200000334t004x383/54/511/5040/3+x二663x+4x+5x+x12346x+4x+3x0x542(21/5)8/503/511012/516/544/503/5t1/504/504x3204/712/71/73x11018/2101/75/21324/745/71/73803/705/71/7X*=(10,0,2,0,0)Tmaxz=3X10+4X2=382、用单纯型法求解下面线性规划问题的解maxz=70x+120x12”9兀+4x360124x+6x20012-3x+10x012解：加入松弛变量X,x,x，得到等效的标准模型:345maxz=

16、70x+120x+0x+0x+0x列表计算如下：1270x134120x250x30x40x50LCBXBb0x336094100900x420046010100/30x53003(10)0013012007012070120tx3x4x2X*=2402030x31860/11x1100/11x2300/11100，300,111139/5(11/5)3/103634t70120-2/53/51/1012120139/1119/11005/11-3/11103/222/111200170/1130/1100-170/1130/11I860IT0)Tmaxz=70X100+120X11300二4

17、3000IT113、用单纯型法求解下面线性规划问题的解maxz4x+3x.122x+2x3000125x+2.5x400012x012解：加入松弛变量X3,X4,X5,得到等效的标准形式:400/13100/111002x15x+2x+x二23+2.5x+x3000二4000maxz=4x+3x+0x+0123x+0x.451x124+x5二500xj0,j二1,2,.,5用表解形式的单纯形法求解，列表计算如下：43000CBXBb9x1x2x3x4x50x33000221003000/2=15000x4400050104000/5=8000x5500(1)0001500/1=50000000

18、4t30000x320000210-22000/2=10000x415000()01-51500/=6004x1500100014000403t00-40x3800001(2)800/2=4003x2600010-24x150010001500/1=500430-20002t0x54000014、用单纯型法求解下面线性规划问题的解maxz=10x+6x+4x123解：加入松弛变量X,x,x，得到等效的标准模型:456x+05maxz=10x+6x+4x+0x+0x+x+x+x123410x+4x+5x123=100=6002342x+2x+6x+x610x1=3006x24x30x40x50x

19、60L1xj表计CB20,j=1如下XB3,2,.,6b0x41001111001000x5600（10）45010600x630022600115000000010t640000x4400(3/5)1/21-1/100200/3515015010x16012/51/201/1000x618006/550-1/51104501002t-10-106x2200/3015/65/3-1/6010x1100/3101/6-2/31/600x6100004-20110620/310/32/3000-8/310/3-2/30100200100)TX*=(3，3，0,0，01002002200-maxz=

20、10TE丁=r5、用单纯型法求解下面线性规划问题的解用单纯形法求解，并指出问题的解属于哪一类。解：（1）、将原问题划为标准形得：3x+x+x+x1234=604-22000b0603111000101-120100402-220014-220004-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,0)T为唯一最优解MaxZ=4*15-2*5=506、用单纯形法求解下述LP问题。解：引入松弛变量x

21、、x,化为标准形式：3410009019/51-3/545/19212/501/55000-1/2145/19015/19-3/1920/1910-2/195/19000-1/2由单纯形表，可得两个最优解X二(2,0,9,0)T、X二(20/19,45/19,0,0)t，所以两点之间的所有解都是最优解，即最优解集合为：aX(1)+(1-a)X，其中01。maxz=2x+x15x22156x+2x2412x+x0x0127、用单纯形法解线性规划问题解：化为标准型maxz=2x+x+0x+0x+0xc5x2+x3=156x+2x+x=2401-512345列出单纯形表C21000CBXBbxxxx

22、x0x1505100340x2462010450x5511001-Z0210000x3150510032x1411/301/60120x5102/30-1/613/2-Z-801/30-1/300x315/20015/4-15/22x17/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)8、用单纯型法求解下面线性规划问题的解maxz=x+x12x2x2122x+x2i2x+x0x012解：把表格还原为线性方程令x=03此时，若让x2进基，贝y会和基变fixi同时增加，使目标函数值无限增长，所以本题无

23、界-Z-2000-2002x14100100x5100-1/21/214x22011/2-1/20-Z-2000-200Z*=20,X*=(2,3,0,2,0)Z*=20,X*=(4,2,0,0,1)maxz=3x+i5x2x141V2x2123x+2x0x01210、用单纯型法求解下面线性规划问题的解解：列表如下Cj35000CXbxxxxxBB123450x341010060x4120201090x51832001-Z0350000x341010045x260101/2030x56300-11-Z-30300-5/20053x3x2x16220010101001/31/2-1/3-1/30

24、1/3-Z-20000-3/2-1X*=(2,6,6,0,0)Z*=3611、用单纯型法求解下面线性规划问题的解解：化为标准型单纯型表如下：Cj21000CBXBbx1x2x3x4x50x315051000x4246201040x55110015Z0210000x3150510032x1411/301/60120x5102/30-1/613/2Z001/30-1/300x315/20015/4-15/22x17/21001/4-1/21x23/2010-1/43/2Z17/2000-1/4-1/2由些可得，问题的最优解为x=7/2,x=3/2，最优值maxz=17/21212、用大M法求解如下

25、线性规划模型:minz=5x2x4x123解：用大M法，先化为等效的标准模型:maxz/=5x2x4x123增加人工变量x、x,得到:67123maxz/=-5x-2x-4x-Mx-Mx6大M法单纯形表求解过程如下:CBXBx6x710-5x1(3)-24x2x3x4x5x6x7-14/3-15/3-5-M-5-9M-4M-7M-M-Mx1x7x14/35/39M-5t4M-27M-4-M-M-51/3-M-5/3M-1/31/22/3-1/301/3-M10/3M-2/35/6(2)-1-2-2M+5/3M2M-5/32M-5/3-M-3M+5/30-1/60-M1/610/3x4(1/2)

26、1/21/211/2525x1x22/322T52x*=(3,2,0，5/225/61/2t1/620，0)1/315/65/65/6MM+5/61/3121/311/31/31/311/311/3M+1M+1/3最优目标函数值minz=maxz/13、用大M法求解如下线性规划模型:minz=540x450x720x123解：用大M法，先化为等效的标准模型:maxz/=540x450x720x123增加人工变量x、x,得到:67maxz/=540x450x720xMxMx6大M法单纯形表求解过程如下:CBXBx670540x1450720x2x3x4x5x6x7170/3一Mx730(9)53

27、0-10130/9=10/3-12M-10M-12MMM-M-M12M-540t10M-45012M720-M-M00-Mx660010/3(8)-11/31-1/360/8=10/3/1540x110/315/91/30-1/901/9/3=10-300+10/3M-8M180-M-M/3+60-MM/3-600-150+10/3M8M-540tMM/3-600-M/3+6015/2/5720x315/205/121-1/81/241/8-1/24/12=185/6/5/540x15/61(5/12)01/24-1/8-1/241/812=2-540-572-720135/2475/12-1

28、35/2-75/20125t0135/2-475/12135/2-M75/2-M-720x320/3-101-450x2212/510-360-450-7205700-1800020该对偶问题的最优解是x*=（0,2,了，0，0）T1/61/61/6-1/61/10-3/10-1/103/107515-75-15-75-1575-M15-M最优目标函数值minz=-(-5700)=570014、用单纯形法求解线性规划问题化成标准形式有加入人工变量则为列出单纯形表Cj-30100-M-MCBXBbx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx7903100

29、01-Z10M-2M-34M10-M000x4330211-100x21-21-10-110-Mx7660403-31-Z6M6M-304M+103M-4M00x400001-1/2-1/21/20x23011/30001/3-3x11102/301/2-1/21/6-Z300303/2-M-3/2-M+1/20x400001-1/21/2-1/20x25/2-1/2100-1/41/41/41x33/23/20103/4-3/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、用单纯形法求解线

30、性规划问题解化为标准形式有列表计算Cj-3-200MCBXBbx1x2x3x4x50x32211002Mx512340-113-Z-12M3M+34M+20-M0-2x2221100Mx54-50-4-11-Z4-4M-5M-10-4M-2-M0X*=(0,2,0,0,4)Z*=4M-4说明原问题无解写对偶问题(10)1、写出下列线性绘画问题的对偶问题解：2、写出下述线性规划的对偶问题maxz=x+4x+3x1232x+3x5x10X0X无约束I1233、写出下列线性规划的对偶问题minz=25x+2x+3x123X+XX11232xX+X=1123X0X0X无约束J123解maxw=Yl+Y

31、2-Y1+Y+i-Yi-Y0232 y3Y3=Y无约束32523解：4、写出下列线性规划的对偶问题maxz=2x+x+4x1232x+3x+X11233xX+X40X0X无约束1123对偶性质1、已知线性规划问题如下：MaxZ=x+3x12已知该问题的解为（2，4）利用对偶性质写出对偶问题的最优解解：该问题的对偶问题为：将X二（2,4）t代入原问题可知：x+x1为严格不等式，所以y=0122由对偶问题性质可知：解之得:yi二1/5MinZ=1450y+4y=1413-所以Y二（1/5,0，1）t2、已知线性规划问题用图解法求对偶问题的解；利用的结果及对偶性质求原问题解。81答案：（对偶问题的最

32、优解为y*二（,）；（依据z*=w*及互补松弛性，有x=0，且4解得愿问题最优解X*=（7/5,0,1/5,0）。3、已知线性规划问题已知其对偶问题的最优解为y*=5,y；=5，最优值为z*=5。试用对偶理论找出原问题的最优解。解先写出它的对偶问题y+2y212y-y3122y+3y513y+y2123y+y0;原问题的两个约束1523412条件应取等式，故有求解后得到x*=1,x*=1；故原问题的最优解为15X*二10001;最优值为w*=5。4、已知下列问题的最优解为X*=(l/7,ll/7),用互补松弛定理求其对偶问题的最优解。解：第一步，写出对偶问题LP:maxz=x+2x1:LP:m

33、aixz丰:x玉2x1223x+x-x+-2x3+2x-3x012x1,x20x1S2S3S01233y一y+y一y=11231Sy+2y一3y一y=21232Sy01y02y03y1S2S0DP:minw=2y+3y+y第二步，将LP，DP都化为标准型第三步：将最优解代入标准型中，确定松弛变量取值第四步：利用互补松弛定理Y*=03Y=01SY=02S第五步：将Y*=03Y=01SY=02S代入约束条件则有A2y2=2y2对偶问题的最优解为Y*=(4/7,5/7,0)5、已知线性规划问题上述线性规划问题无最优解厂x11+22x2+x3v2x+xx0123maxz二x+x，试用对偶理论证明证明：

34、首先看到该问题存在可行解，例如X=（000）,而上述问题的对偶问题为：minw=2y+y12一y12y21y+y1v12yy012y,1y20由第一约束条件可知对偶问题无可行解，因而无最优解。由此，原问题也无最优解。5、已知线性规划问题1）写出其对偶问题；2）用图解法求对偶问题的解；3）利用（2）的结果及对偶性质求原问题解。解：（1）原线性规划问题可化为其对偶问题为：用图解法解得Y*二8y2）二（8,1）W*二19123由互补松弛性定理知道，0人-3，2=16,.x=04又由z*=w*,可得:192x+3x+5x=-1 235x+2x+3x=21232 x-x+x=3解之，可得原问题最优解X*=（75,0,15,0）。对偶单纯形法(15)1、用对偶单纯形法解下列线性规划问题解：先化为标准型minw=15x+24x+5xi20X136Xx+4约束条件两边同乘(