《运筹学》题库

运筹学习题库数学建模题（5）1某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲94370乙4610120360200300试建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：设甲、乙产品的生产数量应为x1、x2,则xl、x20,设z是产品售后的总利润，则maxz=70xi+120x2s.t.9x14x23604x16x22003x110x230Xx202、某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下:甲乙可用量原材料（吨/件）223000吨工时（工时/件）52.54000工时零件（套/件）1500套产品利润（元/件）43建立使利润最大的生产计划的数学模型，不求解。解：设甲、乙两种产品的生产数量为x1、x2,设z为产品售后总利润，则maxz=4x1+3x2s.t.2xi2x230005x12.5x24000x1500x1,x203、一家工厂制造甲、乙、丙三种产品，需要三种资源一一技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：技术服务劳动力行政管理单位利润甲110210乙1426丙1564资源储备量100600300建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为Xi、X2、X3,则Xi、X2、X30,设z是产品售后的总利润，则maxz=10x1+6X2+4X3s.t.x1x2x310010X!4x25x36002x12x26X3300Xi，X2，X304、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量/Kg55261224重要性系数2试建立队员所能携带物品最大量的线性规划模型，不求解。解：弓I入01变量Xi,Xi=1表示应携带物品i,Xi=0表示不应携带物品Inaxz20x115x218x314x48x54x610x75x-|5x22x36x412x52x64x725Xi0或1,i1,2,.,75、工厂每月生产A、B、C三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如下图所示：产资品源ABC资源限量材料（kg）1.51.242500设备（台时）31.61.21400利润（元/件）101412根据市场需求，预测三种产品最低月需求量分别是150、260、120,最高需求量是250、310、130,试建立该问题数学模型，使每月利润最大，为求解。解：设每月生产A、B、C数量为x1,X2,X3。MaxZ10xi14x212x3厂1.5x11.2x24x325003x11.6x21.2x31400150X1250260X2310120X3130X1,X2,X306、A、B两种产品，都需要经过前后两道工序，每一个单位产品A需要前道工序1小时和后道工序2小时，每单位产品B需要前道工序2小时和后道工序3小时。可供利用的前道工序有11小时，后道工序有17小时。每加工一个单位产品B的同时，会产生两个单位的副产品C,且不需要任何费用，产品C一部分可出售盈利，其余只能加以销毁。出售AB、C的利润分别为3、7、2元，每单位产品C的销毁费用为1元。预测表明，产品C最多只能售出13个单位。试建立总利润最大的生产计划数学模型，不求解。解：设每月生产A、B数量为X1，X2,销毁的产品C为X3。MaxZ3x17x22(2x2x3)x3厂X2x2112x13x2172X2X313X1,X2,X307、靠近某河流有两个化工厂（参见附图），流经第一化工厂的河流流量为每天500m3，在两个工厂之间有一条流量为200万m3的支流。第一化工厂每天排放有某种优化物质的工业一33污水2万m，第二化工厂每天排放该污水1.4万m。从第一化工厂的出来的污水在流至第二化工厂的过程中，有20%可自然净化。根据环保要求，河流中的污水含量不应大于0.2%。这两个工厂的都需要各自处理一部分工业污水。第一化工厂的处理成本是1000元/万m3，第二化工厂的为800元/万m3。现在要问满足环保的条件下，每厂各应处理多少工业污水，才能使两个工厂的总的污水处理费用最少？列出数学模型，不求解。附图:。工厂1十33500万m200万m解：设第一化工厂和第二化工厂的污水处理量分别为每天x1m3和x2万m3,minZ1000x1800x21x120.8x1x21.6stx21.4x1,x208、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等），希望获得其中的营养成分（如：蛋白质、脂肪、维生素等）。设市面上现有这3种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。营养物营养成分甲乙丙至少需要的营养成分数量A462080B11265C10370D21735450价格252045问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用计算。解：设购买甲、乙、丙三种营养物的数量分别为为、x2和x3，则根据题意可得如下线性规划模型：minz25%20x245x34%6x220x380%x22x365s.t.%3x37021x17x235x34509、某公司生产的产品A，B，C和D都要经过下列工序：刨、立铳、钻孔和装配。已知每单位产品所需工时及本月四道工序可用生产时间如下表所示：刨立铳钻孔装配A0.52.00.53.0B1.01.0.0.51.0.C1.01.01.02.0D0.51.01.03.0可用生产时间（小时）06000又知四种产品对利润贡献及本月最少销售需要单位如下:产品最少销售需要单位元/单位A1002B6003C5001D4004问该公司该如何安排生产使利润收入为最大？（只需建立模型）解：设生产四种产品分别Xi,X2,X3,X4单位则应满足的目标函数为：maxz=2X1+3X2+X3+x4满足的约束条件为：0.5为x2x30.5x418002Xjx2x3冷28000.5X|0.5x2x3x430003Xjx22x33x46000x1100x2600x3500x440010、某航空公司拥有10架大型客机、15架中型客机和2架小型客机，现要安排从一机场到4城市的航行计划，有关数据如表1-5,要求每天到D城有2个航次（往返），到A,B,C城市各4个航次（往返），每架飞机每天只能完成一个航次，且飞行时间最多为18小时，求利润最大的航班计划。客机类型到达城市飞行费用（元/次）飞行收入（元/次）飞行时间（h/d）大型A6000700080001000050007000100001800012510BCD中型A10002000400030004000600024820BCD小型A20003500600040005500800012619BCD解：设大型客机飞往A城的架次为X1A，中型客机飞往A城的架次为X2A，小型客机飞往A城的架次为X3A，其余依此类推。资源限制派出的大型客机架次不能超过10架，表示为同理x2Ax2Bx2C15x3Ax3Bx3C2班次约束飞往各城的班次要满足X1Ax2Ax3A4x1Bx2Bx3B4x1Cx2Cx3C4x1Dx2Dx3D2非负性约束非负性约束Xj0且为整数；(i=1,2,3;j=A,B,C,D)maxz1000x1AOxiB2000x1C8000xid+2000x2a目标函数为2000x2b2000x?c2000x3A2000x3B2000x3c11、CRISP公司制造四种类型的小型飞机：AR1型（具有一个座位的飞机）、AR2型（具有两个座位的飞机）、AR4型（具有四个座位的飞机）以及AR6型（具有六个座位的飞机）。AR1和AR2一般由私人飞行员购买，而AR4和AR6一般由公司购买，以便加强公司的飞行编队。为了提高安全性，联邦航空局（）对小型飞机的制造做出了许多规定。一般的联邦航空局制造规章和检测是基于一个月进度表进行的，因此小型飞机的制造是以月为单位进行的。表说明了CRISP公司的有关飞机制造的重要信息。AR1AR2AR4AR6联邦航空局的最大产量（每月生产的飞机数目）8171115建造飞机所需要的时间（天）47911每架飞机所需要的生产经理数目1122每架飞机的盈利贡献（千美元）6284103125CRISP公司下个月可以得到的生产经理的总数是60人。该公司的飞机制造设施可以同时在任何给定的时间生产多达9架飞机。因此，下一个月可以得到的制造天数是270天（9*30，每月按30天计算）。JonathanKuring是该公司飞机制造管理的主任，他想要确定下个月的生产计划安排，以便使盈利贡献最大化。解：设x1表示下个月生产AR1型飞机的数目，x2表示AR2型，x3表示AR4型，x4表示AR6型目标函数：maxz62x-|84x2103x3125x44x17x29x311x4270x1x22x32x460x18约束条件：x217X311x415X1，X2，X3,X40X|,X2,X3,X4为整数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万单位。问如何安排生产，使工厂获利最大？解：设X1为产品A的售出量；X2为A在第二车间加工后的售出量；X3表示产品B的售出则目标函数为:则目标函数为:量；X4表示B在第三车间加工后的售出量；X5为第一车间所用原材料的数量，maxz8x19.5x27x38x42.75x5X5X51000003x23x2约束条件：x12x41.5x5200000x23x50X3X3X42x50X1,X2,X3,X4,X50?化标准形式（5）1将下列线性规划模型化为标准形式解：minzx12x23x3X1X2X37X1X2X323x1X22x35X10X20X3无约束X170maxzX12x23(X4X5)0x60x7X1X2X4X5X67X1X2X4X5X723xX22X352、将下列线性规划模型化为标准形式minzx-i2x23x32x1X2X393x1X22x344x12x23x36X10X20X3无约束解:maxzX12x23x33x32x1X2X3X3X493x1X22x32x3X544x12x23x33x36X1503、将下列线性规划变为最大值标准形。minz3x14x22x35x44x1x22x3x42x1x23x3Xt14st2x-i3x2x32x42X1,X2,X30,X4无约束maxz3%|4x22x35x45x44x-|X22x3X4Xix23x3x4x4x514st2x-i3x2x32x42x4x62?图解法(5)1用图解法求解下面线性规划minz=3xi+2x22x4x222x14x2102x1x27Xi3x21Xl,X20解：XL可行解域为abcda，最优解为b点。2x1由方程组4x222x20解出Xi=11,X2=0*Xi=(11,=(11,:、X=X2minz=3X11+2X0=332、用图解法求解下面线性规划minz=2x1+X2x14x224Xjx285X,10x20从上图分析，可行解域为abcde,最优解为e点。由方程组X1x28X15解出X1=5,X2=3X*=X1=(5,3)T用图解法求解，并写出解的情况X15X1+10x2=50X计X2=1X2/minz=Z=2x5+3=133、已知线性规划问题如下：MaxZ=x13x2(5x110x250x1x21X24x-t,x20由图可知:10x250x24则maxZ=2+3*4=144、用图解法求解下面线性规划问题maxz2x1x25x1156x12x224st.x2x25x!,x20解：5、用图解法求解下面线性规划问题maxz2x13x2X12x284x116st4x212Xj0,j1,2图解如下：大值为z*2*43*214。二、单纯型法（15）1、用单纯型法求解下面线性规划问题的解maxz=3x1+3X2+4X33xi4x25x340s.t.6x4x23x366X1,X2，x解：加入松弛变量X4，X5，得到等效的标准模型:maxz=3x1+3X2+4X3+Ox4+0x5列表计算如下:3捲4x25x3X440s.t.6X14x23x3x566Xj0,j1,2,.,533400CBXBbx1x2x3x4x50L0x44034(5)1080x566643012200000334f004x383/54/511/5040/30x542（21/5）8/503/511012/516/544/503/5f1/504/504x3204/712/71/73x11018/2101/75/21324/745/71/73803/705/71/7*TX=(10,0,2,0,0)maxz=3x10+4x2=382、用单纯型法求解下面线性规划问题的解maxz=70x1+120x29x4x23604x6x2200si3xi10X2300x1，x20解：加入松弛变量X3，X4，X5，得到等效的标准模型:maxz=70x1+120X2+0x3+0x4+0x5s.t.9x14x2X33604x16x2X42003x110X2X5300Xj0,j1,2,.,5列表计算如下:70120000CBXBbx1x2x3x4x50L0x336094100900x420046010100/30x53003(10)001300000070120T0000x324039/5010-2/5400/130x420(11/5)001-3/5100/11120x2303/101001/1010036120001234T000120x31860/1100139/1119/1170x1100/111005/11-3/11120x2300/11010-3/222/11701200170/1130/114300011000-170/1130/11*z1003001860、TX=(,00),0,111111100-30043000Xmaxz11x=11113、用单纯型法求解下面线性规划问题的解2x12x23000maxz=4x1+3x2s.t.解：加入松弛变量x3，5xiXiXi,X4,2.5X24000500X2X5,得到等效的标准形式:2Xi2x2X33000maxz=4x1+3x2+0x3+0x4+0x5s.t.5x-2.5x2X44000XiX5500Xj0，j1,2,.,5用表解形式的单纯形法求解，列表计算如下:43000CBXBbX1X2X3X4X50L0X330/2=15000X4400052.50104000/5=8000X5500（1）0001500/1=500000004f30000X320000210-22000/2=10000X415000(2.5)01-51500/2.5=6004X1500100014000403f00-40X3800001-0.8(2)800/2=4003X26000100.4-24X0/1=5004301.2-2000-1.22f0X5400000.5-0.413X21400011-0.404X110010-0.50.404310.40460000-1-0.40据上表,X=(100,1400,0,0,400)Tmaxz=4X100+3X1400=4604、用单纯型法求解下面线性规划问题的解maxz=10x1+6X2+4X3s.t.XiX2X310x14x22x12x2Xi，X2，X31005x36006x33000解：加入松弛变量X4,X5,X6，得到等效的标准模型:maxz=10x计6X2+4X3+Ox4+0x5+0x6x1x2x3x4100X*=(1002000，0，0,100)10x14x25x3x5600st2x12x26x3Xj0,j1,2,.,6x6300列表计算如下:1064000CBXBbX1x2x3x4x5X60L0x410x5600(10)45010600x6300000010f640000x4400(3/5)1/211/100200/310X16012/51/201/1001500x618006/5501/51150104501002f-10106x2200/3015/65/31/6010x1100/3101/62/31/600x6100004201220010620/310/32/303008/310/32/301002002200maxz=10X+6X=3335、用单纯型法求解下面线性规划问题的解MaxZ4x1-2x22x3(3x1X2X360XiX22X3102xi2x22X340Xi,X2,X30用单纯形法求解，并指出问题的解属于哪一类。解：（1）、将原问题划为标准形得：MaxZ4xi2X22X30X40X50X6%X2X3x4=60XiX22x3X5102x12x22x3x640(Xi,X2,X3,X4,X5,X6Cj4-22000CBXbbXiX2X3X4X5X60X4603iii000X5i0i-i20i00X6402-2200ij4-22000Cj4-22000CBXbbXiX2X3X4X5X60X43004-5i-304Xii0i-i20i00X62004-60-2ij02-60-40Cj4-22000CBXbbX1X2X3X4X5X60X4100011-1-14Xi15101/201/21/4-2X2501-3/20-1/21/4j00-30-3-1/2所以X=(15,5,0,10,0,0)T为唯一最优解MaxZ=4*15-2*5=506、用单纯形法求解下述LP问题。maxz2.5X1X23x15x215st5x12x210x1,x20解：引入松弛变量x3、X4，化为标准形式:maxz2.5xX23x15x2X315st5x2x2X410Xl,X2,X3,X4构造单纯形表，计算如下:Cj2.5100iCbXbbX1X2X3X40X315351050X41052012j2.51000X39019/513/545/192.5Xi212/501/55j0001/21X245/19015/193/192.5Xi20/19102/195/19j0001/2由单纯形表，可得两个最优解x(2,0,9,0)T、X(20/19,45/19,0,0)T，所以两点之间的所有解都是最优解，即最优解集合为：X(1)X，其中01。7、用单纯形法解线性规划问题maxz2x1X25x2156x12x224X1X25X10X20解：化为标准型maxz2x1x20x30x40x55x2X3156x12x2X424XX2X55X150列出单纯形表C21000CB沟bX1X2X3X4X50X315051000X424201040X55110015-Z0210000X3150510032X1411/301/60120X5102/30-1/613/2-Z-801/30-1/30021X3XiX215/27/23/20100011005/41/4-1/4-15/2-1/23/2-Z-20000-1/4-1/2Z*=17/2,X*=(7/2,3/2,15/2,0,0)8、用单纯型法求解下面线性规划问题的解maxzx1x2X12x222x1X22X1X24x10X2解:C11000CB沟bX1X2X3X4X50X3211210020X42-210100X54-11001-Z0110001X121-21000X460-32100X560-1101-Z-203-100把表格还原为线性方程9、用单纯型法求解下面线性规划问题的解maxz3x2x32X12x2X323x22X3X46X2X3X56X122x2X3X463x22x3X56X2X3令X3=0X122x2X463x2X56X2此时，若让X2进基，则会和基变量x侗时增加，使目标函数值无限增长，所以本题无界maxz2xi4X2Xi2x28Xi4X23Xi0X20Z*=20,X*=(2,3,0,2,0)Z*=20,X*=(4,2,0,0,1)C24000CbXbbXiX2X3X4X50X38i2i0040X44i00i00X530i00i3-Z0240000X32i0i0-220X44i00i044X230i00i-Z-i22000-42Xi2i0i0-20X4200-ii24X230i00i-Z-2000-2002Xi4i00i00X5i00-i/2i/2i4X220ii/2-i/20-Z-2000-20010、用单纯型法求解下面线性规划问题的解maxz3xi5x2Xi42x2i23x12x2i8X-0x20解：列表如下c35000CbXbbXiX2X3X4X50X34i0i000X4i2020i060X5i83200i19-Z035000X*=(2,6,6,0,0)Z*=360X341010045X260101/200X56300-113-Z-30300-5/200X360011/3-1/35X220101/203X12100-1/31/3-Z-20000-3/2-111、用单纯型法求解下面线性规划问题的解maxz2x1x25xi15st.6X1X22x224x25x-,x20解：化为标准型maxz2x1X25x.|X3156x12x2x424st.X2X2X55X1,X2,X3,X4,X50单纯型表如下:C21000CbXbbX1X2X3X4X50X315051000X4246201040X55110015Z0210000X3150510032X1411/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由些可得，问题的最优解为X1=7/2,X2=3/2，最优值maxz=17/212、用大M法求解如下线性规划模型：minz=5x1+2x2+4x33x1x22x346x13x25x310Xl,X2,X30解：用大M法，先化为等效的标准模型：maxz=5xi2X24x3s.t.3为X22X3X46X-3x25x3X510yj0,j1,2,.,5增加人工变量X6、X7，得到：/maxz=5xi2X24X3一M6一M7s.t3x-jX22x3XX46为3x25x3XX710Xj0,j1,2,.,7大M法单纯形表求解过程如下:52400MMCBXBbX1x2x3x4x5x6X70LMx64(3)1210104/3Mx71063501015/39M4M7MMMMM9M-5f4M-27M-4MM005X14/311/32/31/301/30Mx72011(2)12115-M5/3-M10/3-2M+5/3M2M-5/3-M0M-1/3M-2/32M-5/3fM3M+5/305X15/311/25/601/601/610/30x410(1/2)1/211/211/225-5/225/605/605/601/2f1/605/6MM+5/65X12/3101/311/311/32x220112121一5211/311/311/3223001/311/3M+1M+1/3*x=2(2(3，0,0,0)T2222最优目标函数值minz=maxZ=()=3313、用大M法求解如下线性规划模型：minz=540x1+450X2+720x33xi5x29x3709捲5x23x330Xi,X2,X30解：用大M法，先化为等效的标准模型：maxz=540xi450x2720x3s.t.3x15x29x3X4709x15x23x3X530yj0,j1,2,.,5增加人工变量X6、X7,得到：/maxz=540x：1450x2720x3MxMxs.t3x15x29X3X4X6709x15x23x3X5x730Xj0,j1,2,.,5大M法单纯形表求解过程如下:54045072000MMCBXBbx1x2x3x4x5x6x70LMx670359101070/3Mx730(9)53010130/9=10/312M10M12MMMMM12M-540T10M-45012M-720MM00Mx660010/3(8)11/311/360/8=2.520540Xi10/315/91/301/901/910/3/1/3=10-300+10/3M-8M180MM/3+60MM/3600-150+10/3M8M-540fMM/3600M/3+6015/2/5/1720x315/205/1211/81/241/81/242=18540Xi5/61(5/12)01/241/81/241/85/6/5/12=2540572720135/2475/12135/275/20125f0135/2475/12135/2M75/2M720x320/31011/61/61/61/6450x2212/5101/103/101/103/1036045072075157515570018000751575M15M该对偶问题的最优解是x=(0,2,0,0)3最优目标函数值minz=(5700)=570014、用单纯形法求解线性规划问题maxz3x1X3X1X2X342x1X2X313x2X39%0X20X30化成标准形式有Xi50maxz3x1X30x40x5X1X2X3X442为X2X3X513x2X39加入人工变量则为maxz3x1x30x4OX5Mx6Mx7XiX2X3X442为X2X3X5X613x2X3x79X170列出单纯形表C-30100-M-MCbXbbX1X2X3X4X5X6X70X441111000-MX61-21-10-110-MX790310001-Z10M-2M-34M10-M000X4330211-100X21-21-10-110-MX760403-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、用单纯形法求解线性规划问题maxz3x12x22x1x223x14x212X10X20解化为标准形式有maxz3x12x20x30x4Mx52x-iX2X323x-i4x2X4X512Xi50列表计算X*=(0,2,0,0,4)Z*=4M-4说明原问题无解Cj-3-200MCBXbbX1X2X3X4X50X32211002MX512340-113-Z-12M3M+34M+20-M0-2X2221100MX54-50-4-11-Z4-4M-5M-10-4M-2-M0?写对偶问题（10）1、写出下列线性绘画问题的对偶问题maxz2x1x23x3X4Xi2x1X2X2X33X3X4XiXi,X310,x2,x4无约束X3X4解:min5y14y2y3y12y2y2y1y21y13y2y33y1y1y0”2无约束,y302、写出下述线性规划的对偶问题maxzx14x23x32x13x25x323x1X26X31XiX2X34x10x20X3无约束minw2yiy24y32yi3y2y3i3yiy2y345yi6y2y33yi0y20y3无约束3、写出下列线性规划的对偶问题minz25xi2x23x3XiX2X3iXi2x2X3i2xiX2X3iX.)0X20x3无约束解:maxwyiy2y3yiy22y325yi2y2y32yiy2y33yi0y20y3无约束4、写出下列线性规划的对偶问题maxz2%X24x32xi3x2X3i3%X2X34XiX33xi0X20X3无约束minwyi4y23y32yi3y2y323yiy21yiy2y34yi0y20y3无约束?对偶性质1已知线性规划问题如下：MaxZ=捲3x210x250Xix21x24X1,x20已知该问题的解为（2,4）禾9用对偶性质写出对偶问题的最优解。解：该问题的对偶问题为：MinZ50y1y24y3*5yiy21i为严格不等式，所以y20由对偶问题性质可知:50%4y314解之得：“yi1/510yiy33Vy20ly31所以Y=(1/5,0,1)TMinZ=142、已知线性规划问题minz2x-i3x25x36x4x12x23x3x422x1x2X33x43Xj0(j123,4)用图解法求对偶问题的解；利用（b）的结果及对偶性质求原问题解。答案：（对偶问题的最优解为Y*（8,丄）;55（依据z*=M及互补松弛性，有X4=0,且2x；3x25x319/5x；2x23x3