《运筹学》题库,.doc

海量资源，欢迎共阅运筹学习题库数学建模题（5）1、某厂生产甲、乙两种产品，这两种产品均需要A、B、C三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：ABC甲94370乙4610120360200300试建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：设甲、乙产品的生产数量应为x1、x2，则x1、x20，设z是产品售后的总利润，则maxz=70x1+120x2s.t.2、某公司生产甲、乙两种产品，生产所需原材料、工时和零件等有关数据如下：甲乙可用量原材料（吨/件）工时（工时/件）零件（套/件）2252.513000吨4000工时500套产品利润（元/件）43建立使利润最大的生产计划的数学模型，不求解。解：设甲、乙两种产品的生产数量为x1、x2，设z为产品售后总利润，则maxz=4x1+3x2s.t.3、一家工厂制造甲、乙、丙三种产品，需要三种资源技术服务、劳动力和行政管理。每种产品的资源消耗量、单位产品销售后所能获得的利润值以及这三种资源的储备量如下表所示：技术服务劳动力行政管理单位利润甲110210乙1426丙1564资源储备量100600300建立使得该厂能获得最大利润的生产计划的线性规划模型，不求解。解：建立线性规划数学模型：设甲、乙、丙三种产品的生产数量应为x1、x2、x3，则x1、x2、x30，设z是产品售后的总利润，则maxz=10x1+6x2+4x3s.t.4、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。每种物品的重量合重要性系数如表所示。设登山队员可携带的最大重量为25kg,试选择该队员所应携带的物品。序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量/Kg55261224重要性系数201518148410试建立队员所能携带物品最大量的线性规划模型，不求解。解：引入01变量xi,xi=1表示应携带物品i，,xi=0表示不应携带物品I5、工厂每月生产A、B、C三种产品，单件产品的原材料消耗量、设备台时的消耗量、资源限量及单件产品利润如下图所示：产品资源ABC资源限量材料（kg）1.51.242500设备（台时）31.61.21400利润（元/件）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元，每单位产品C的销毁费用为1元。预测表明，产品C最多只能售出13个单位。试建立总利润最大的生产计划数学模型，不求解。解：设每月生产A、B数量为销毁的产品C为。7、靠近某河流有两个化工厂（参见附图），流经第一化工厂的河流流量为每天500，在两个工厂之间有一条流量为200万的支流。第一化工厂每天排放有某种优化物质的工业污水2万，第二化工厂每天排放该污水1.4万。从第一化工厂的出来的污水在流至第二化工厂的过程中，有20%可自然净化。根据环保要求，河流中的污水含量不应大于0.2%。这两个工厂的都需要各自处理一部分工业污水。第一化工厂的处理成本是1000元/万，第二化工厂的为800元/万。现在要问满足环保的条件下，每厂各应处理多少工业污水，才能使两个工厂的总的污水处理费用最少？列出数学模型，不求解。附图：工厂1工厂2500万200万解：设第一化工厂和第二化工厂的污水处理量分别为每天和x2万，st8、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等），希望获得其中的营养成分（如：蛋白质、脂肪、维生素等）。设市面上现有这3种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。营养物营养成分甲乙丙至少需要的营养成分数量A462080B11265C10370D21735450价格252045问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用计算。解：设购买甲、乙、丙三种营养物的数量分别为，则根据题意可得如下线性规划模型：9、某公司生产的产品A，B，C和D都要经过下列工序：刨、立铣、钻孔和装配。已知每单位产品所需工时及本月四道工序可用生产时间如下表所示：刨立铣钻孔装配A0.52.00.53.0B1.01.0.0.51.0.C1.01.01.02.0D0.51.01.03.0可用生产时间（小时）1800280030006000又知四种产品对利润贡献及本月最少销售需要单位如下：产品最少销售需要单位元/单位A1002B6003C5001D4004问该公司该如何安排生产使利润收入为最大？（只需建立模型）解：设生产四种产品分别x1,x2,x3,x4单位则应满足的目标函数为：maxz=2x1+3x2+x3+x4满足的约束条件为：10、某航空公司拥有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城的架次为x2A，小型客机飞往A城的架次为x3A，其余依此类推。资源限制派出的大型客机架次不能超过10架，表示为同理班次约束飞往各城的班次要满足非负性约束且为整数；（i=1,2,3;j=A,B,C,D）目标函数为11、AR1AR2AR4AR6联邦航空局的最大产量（每月生产的飞机数目）建造飞机所需要的时间（天）每架飞机所需要的生产经理数目每架飞机的盈利贡献（千美元）84162177184119210315112125CRISP公司下个月可以得到的生产经理的总数是60人。该公司的飞机制造设施可以同时在任何给定的时间生产多达9架飞机。因此，下一个月可以得到的制造天数是270天（9*30，每月按30天计算）。JonathanKuring是该公司飞机制造管理的主任，他想要确定下个月的生产计划安排，以便使盈利贡献最大化。解：设表示下个月生产AR1型飞机的数目，表示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万单位。问如何安排生产，使工厂获利最大？解：设为产品A的售出量；为A在第二车间加工后的售出量；表示产品B的售出量；表示B在第三车间加工后的售出量；为第一车间所用原材料的数量，则目标函数为：约束条件： 化标准形式（5）1、将下列线性规划模型化为标准形式解：2、将下列线性规划模型化为标准形式解：3、将下列线性规划变为最大值标准形。解： 图解法（5）1、用图解法求解下面线性规划minz=3x1+2x2解：可行解域为abcda，最优解为b点。由方程组解出x1=11，x2=0X*=（11，0）Tminz=311+20=332、用图解法求解下面线性规划minz=2x1+x2解：从上图分析，可行解域为abcde，最优解为e点。由方程组解出x1=5，x2=3X*=（5，3）Tminz=Z*=25+3=133、已知线性规划问题如下：MaxZ=用图解法求解，并写出解的情况解：x26Z4x2=42Zx102468105x1+10x2=50x1+x2=1由图可知：解之得：则maxZ=2+3*4=144、用图解法求解下面线性规划问题解：5、用图解法求解下面线性规划问题图解如下：可知，目标函数在B(4,2)处取得最大值，故原问题的最优解为，目标函数最大值为。二、单纯型法（15）1、用单纯型法求解下面线性规划问题的解maxz=3x1+3x2+4x3s.t.解：加入松弛变量x4，x5，得到等效的标准模型：maxz=3x1+3x2+4x3+0x4+0x5s.t.列表计算如下：CBXBb33400Lx1x2x3x4x50x44034（5）1080x566643012200000334004x383/54/511/5040/30x542（21/5）8/503/511012/516/544/503/51/504/504x3204/712/71/73x11018/2101/75/2138324/745/71/703/705/71/7X*=（10，0，2，0，0）Tmaxz=310+42=382、用单纯型法求解下面线性规划问题的解maxz=70x1+120x2s.t.解：加入松弛变量x3，x4，x5，得到等效的标准模型：maxz=70x1+120x2+0x3+0x4+0x5s.t.列表计算如下：CBXBb70120000Lx1x2x3x4x50x336094100900x420046010100/30x53003（10）0013000000701200000x324039/5010-2/5400/130x420（11/5）001-3/5100/11120x2303/101001/1010036120001234000120x31860/1100139/1119/1170x1100/111005/11-3/11120x2300/11010-3/222/11701200170/1130/11000-170/1130/11X*=（，0，0）Tmaxz=70+120=3、用单纯型法求解下面线性规划问题的解maxz=4x1+3x2s.t.解：加入松弛变量x3，x4，x5，得到等效的标准形式：maxz=4x1+3x2+0x3+0x4+0x5s.t.用表解形式的单纯形法求解，列表计算如下：CBXBb43000Lx1x2x3x4x50x33000221003000/2=15000x4400052.50104000/5=8000x5500（1）0001500/1=50000000430000x320000210-22000/2=10000x415000（2.5）01-51500/2.5=6004x150010001400040300-40x3800001-0.8（2）800/2=4003x26000100.4-24x150010001500/1=5004301.2-2000-1.220x5400000.5-0.413x21400011-0.404x110010-0.50.4046004310.4000-1-0.40据上表，X*=（100，1400，0，0，400）Tmaxz=4100+31400=4604、用单纯型法求解下面线性规划问题的解maxz=10x1+6x2+4x3s.t.解：加入松弛变量x4，x5，x6，得到等效的标准模型：maxz=10x1+6x2+4x3+0x4+0x5+0x6s.t.列表计算如下：CBXBb1064000Lx1x2x3x4x5x60x41001111001000x5600（10）45010600x630022600115000000010640000x4400（3/5）1/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，100）Tmaxz=10+6=5、用单纯型法求解下面线性规划问题的解用单纯形法求解，并指出问题的解属于哪一类。解：（1）、将原问题划为标准形得：=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问题。解：引入松弛变量、，化为标准形式：构造单纯形表，计算如下：2.510001535105010520122.510009019/513/545/192.5212/501/550001/2145/19015/193/192.520/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,X*=(7/2,3/2,15/2,0,0)8、用单纯型法求解下面线性规划问题的解解：Cj11000CBXBbx1x2x3x4x5000x3x4x52241-2-112111000100012-Z011000100x1x4x5266100-2-3-1121010001-Z-203-100把表格还原为线性方程令x3=0此时，若让x2进基，则会和基变量x1同时增加，使目标函数值无限增长，所以本题无界9、用单纯型法求解下面线性规划问题的解Cj24000CBXBbx1x2x3x4x5000x3x4x584311020110001000143-Z024000004x3x4x2243110001100010-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/20053x3x2x16220010101001/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，最优值maxz=17/212、用大M法求解如下线性规划模型：minz=5x12x24x3解：用大M法，先化为等效的标准模型：maxz/=5x12x24x3s.t.增加人工变量x6、x7，得到：maxz/=5x12x24x3Mx6Mx7s.t大M法单纯形表求解过程如下：CBXBb52400MMLx1x2x3x4x5x6x7Mx64（3）1210104/3Mx71063501015/39M4M7MMMMM9M54M27M4MM005x14/311/32/31/301/30Mx72011（2）12115-M5/3-M10/3-2M+5/3M2M5/3-M0M1/3M2/32M5/3M3M+5/305x15/311/25/601/601/610/30x410（1/2）1/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，0）T最优目标函数值minz=maxz/=（）=13、用大M法求解如下线性规划模型：minz=540x1450x2720x3解：用大M法，先化为等效的标准模型：maxz/=540x1450x2720x3s.t.增加人工变量x6、x7，得到：maxz/=540x1450x2720x3Mx6Mx7s.t大M法单纯形表求解过程如下：CBXBb54045072000MMLx1x2x3x4x5x6x7Mx670359101070/3Mx730（9）53010130/9=10/312M10M12MMMMM12M54010M45012M720MM00Mx660010/3（8）11/311/360/8=2.5540x110/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/61（5/12）01/241/81/241/85/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，0）T最优目标函数值minz=（5700）=570014、用单纯形法求解线性规划问题化成标准形式有加入人工变量则为列出单纯形表Cj30100M-MCBXBbx1x2x3x4x5x6x70-M-Mx4x6x74191-201131-111000-10010001-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、用单纯形法求解线性规划问题解化为标准形式有列表计算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说明原问题无解 写对偶问题（10）1、 写出下列线性绘画问题的对偶问题解：2、写出下述线性规划的对偶问题解3、写出下列线性规划的对偶问题解：4、写出下列线性规划的对偶问题解 对偶性质1、已知线性规划问题如下：MaxZ=已知该问题的解为（2，4）利用对偶性质写出对偶问题的最优解。解：该问题的对偶问题为：将X=（2，4）T代入原问题可知：1为严格不等式，所以由对偶问题性质可知：解之得：所以Y=（1/5，0，1）TMinZ=142、已知线性规划问题用图解法求对偶问题的解；利用(b)的结果及对偶性质求原问题解。答案：(对偶问题的最优解为；(依据z*=w*及互补松弛性，有x4=0,且解得愿问题最优解X*=(7/5,0,1/5,0)。3、已知线性规划问题已知其对偶问题的最优解为，最优值为。试用对偶理论找出原问题的最优解。解先写出它的对偶问题s.t.将的值代入约束条件，得，为严格不等式；设原问题的最优解为，由互补松弛性得。因；原问题的两个约束条件应取等式，故有求解后得到；故原问题的最优解为；最优值为。4、已知下列问题的最优解为X*=(1/7,11/7),用互补松弛定理求其对偶问题的最优解。解：第一步，写出对偶问题第二步，将LP，DP都化为标准型第三步：将最优解代入标准型中，确定松弛变量取值第四步：利用互补松弛定理Y3*=0Y1S=0Y2S=0第五步：将Y3*=0Y1S=0Y2S=0代入约束条件则有对偶问题的最优解为Y*=(4/7,5/7,0)5、已知线性规划问题：，试用对偶理论证明上述线性规划问题无最优解。证明：首先看到该问题存在可行解，例如，而上述问题的对偶问题为：由第一约束条件可知对偶问题无可行解，因而无最优解。由此，原问题也无最优解。5、已知线性规划问题（1）写出其对偶问题；（2）用图解法求对偶问题的解；（3）利用（2）的结果及对偶性质求原问题解。解：（1）原线性规划问题可化为：其对偶问题为：（2）用图解法解得（3）由互补松弛性定理知道，又由解之，可得原问题最优解 对偶单纯形法（15）1、用对偶单纯形法解下列线性规划问题解：先化为标准型约束条件两边同乘(-1)列单纯形表Cj1524500CBXBbx1x2x3x4x500x4x52105-6-2-1-11001-15-24-500-45-240x2x51/3-1/30-5101/6-2/3-1/6-1/301-150-1-4033/212-24-5x2x31/41/2-5/415/21001-1/41/21/4-3/2-15/200-7/2-3/2X*=(0,1/4,1/2)Y*=(7/2,3/2)2、用对偶单纯形法解下列线性规划问题解：改写为标准形式列单纯形表如下：Cj4121800CBXBbx1x2x3x4x500x4x535100-2-3-21001-4-12-1800-690-12x4x2-35/2-1001-31100-1/2-40-60-64212-18-12x3x213/21/3-1/30110-1/31/30-1/2-200-2-6X*=(0,3/2,1)Y*=(2,6)3、用对偶单纯形法求解下面的问题：解：令，则问题可以标准化为：取为初始基，则是非基可行解，但，是对偶可行解，建立单纯形表（见表4-1）计算结果如下：最优解。或最优解。本例如果用单纯形法计算，确定初始基可行解时，还需要引入两个人工变量，计算量要多于对欧单纯形法。表3-1：C备注-4L=2K=4-1L=1K=2-1/2L=2K=1或3 灵敏度分析1、已知线性规划的标准形式为其最优单纯形表如下Cj12100CBXBbx1x2x3x4x520x2x56101310111101-Z-12-30-1-20问：(1)当C1由1变为4时，求新问题的最优解(2)讨论C2在什么范围内变化时，原有的最优解仍是最优解解：由表可知，C1是非基变量的价值系数，因此C1的改变只影响1可见最优性准则已不满足，继续迭代Cj42100CBXBbx1x2x3x4x520x2x56101310111101610/3-Z-1220-1-2024x2x18/310/301102/31/32/31/3-1/31/3-Z-56/300-5/3-8/3-2/3(2)要使原最优解仍为最优解，只要在新的条件下满足0成立，因为x2是基变量，所以所有的值都将发生变化C-CBB-1A即则c21c2+c21c2-1所以当x2的系数c2-1时，原最优解仍能保持为最优解。2已知线性规划问题及其最优单纯形表Cj114000CBXBbx1x2x3x4x5x6104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3-Z-170-40-10-2若右端列向量，求新问题的最优解。解：因为1小于0，因此继续迭代Cj114000CBXBbx1x2x3x4x5x6104x1x5x3152100-1/322/30011/301/3010-2/311/3-Z-90-40-10-2j/arj123004x6x5x33/27/23/2-3/23/21/21/23/21/2001-1/21/21/2010100-Z-6-3-30-200新问题的最优解为X*=(0,0,3/2,0,7/2,3/2)Z*=63、已知线性规划问题及其最优单纯形表最优单纯形表如下：Cj23100CBXBbx1x2x3x4x523x1x2121001124111610/3-Z-800-3-51若p3由原来的，最优解将如何改变？解：计算继续迭代Cj23100CBXBbx1x2x3x4x523x1x21210011/157/3041111560/7-Z-8001/6-5121x1x33/760/710-2/7-30/70130/7-30/79/7-30/71560/7-Z-66/70-5/70-30/712/7X*=(3/7,0,60/7,0,0)Z*=66/7例4 (仍以例2为例)已知线性规划问题及其最优单纯形表Cj114000CBXBbx1x2x3x4x5x6104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3-Z-170-40-10-2现增加一个新变量x7，且c7=3，p7=(3,1,-3)，求新问题的最优解。解：由表知：继续迭代Cj1140003CBXBbx1x2x3x4x5x6x7104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/33-20-Z-170-40-10-26304x7x5x31/956/913/31/32/30-1/916/92/30011/92/91/3010-2/95/91/3100-Z-53/3-2-10/30-5/30-2/30X*=(0,0,13/3,0,56/9,0,1/9)Z*=53/35已知线性规划问题及其最优单纯形表Cj114000CBXBbx1x2x3x4x5x6104x1x5x31/3613/3100-1/322/30011/301/3010-2/311/3-Z-170-40-10-2现增加新约束，求新问题的最优解。解：将原问题的最优解代入新增约束不满足新增加的约束条件，因此引入松弛变量x7后，新增约束变为，加进最优表得：Cj1140000CBXBbx1x2x3x4x5x6x71040x1x5x3x71/3613/317100-3-1/322/3100161/301/300100-2/311/303-201-Z-170-40-10-201040x1x5x3x71/3613/3-81000-1/322/3-400161/301/3-10100-2/311/3-40001-Z-170-40-10-20111/21040x1x5x3x65/3411/3210001/311/3100101/2-1/41/41/401000001-1/61/41/12-1/4-Z-130-20-1/200-1/2X*=(5/3,0,11/3,0,4,2,0)Z*=135、线性规划问题用单纯形法求解得最终单纯形表如下表所示。x1x2x3x4x5x1611110X51003111cj-zj0-3-1-20试说明分别发生如下变化时，新的最优解是什么？（1）目标函数变为；（2）约束条件右端项由变为；（3）增添一个新的约束。解：（1）cj23100iCBxBbx1x2x3x4x52x161111020x510031110cj-zj01-1-202x18/3102/32/3-1/323X210/3011/31/31/30cj-zj00-4/3-7/3-1