《运筹学》题库

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

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

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

4、量及单件产 品利润如下图所示：、, 产资品源ABC资源限量材料（kg）1.51.242500设备（台时）31.61.21400利润（元/件）101412根据市场需求，预测三种产品最低月需求量分别是150、260、120,最高需求量是 250、310、130,试建立该问题数学模型，使每月利润最大，为求解。解：设每月生产 A、B、C数量为X1,X2.X3o ,736、A、B两种产品，都需要经过前后两道工序，每一个单位产品 A需要前道工序1小时和后道工序 2小时，每单位产品B需要前道工序2小时和后道工序 3小时。可供利用的前道工序有11小时，后道工序有 17小时。每加工一个单位产品 B的同时，会产生

5、两个单位的副产品C,且不需要任何费用，产品C一部分可出售盈利，其余只能加以销毁。出售A、B、C的利润分别为3、7、2元，每单位产品 C的销毁费用为1元。预测表明，产品 C最多只能售出13个单位。试建立总利润最大的生产计划数学模型，不求解。解：设每月生产 A、B数量为X1,X2，销毁的产品C为X37、靠近某河流有两个化工厂（参见附图），流经第一化工厂的河流流量为每天500 m3,在两个工厂之间33有一条流量为200万m的支流。第一化工厂每天排放有某种优化物质的工业污水2万m ,第二化工厂3每天排放该污水 1.4万m。从第一化工厂的出来的污水在流至第二化工厂的过程中，有20%可自然净化。根据环保要

6、求，河流中的污水含量不应大于0.2%。这两个工厂的都需要各自处理一部分工业污水。第一化33工厂的处理成本是 1000兀/万m ,第二化工厂的为 800元/万m o现在要问满足环保的条件下，每厂各应处理多少工业污水，才能使两个工厂的总的污水处理费用最少？列出数学模型，不求解。0.8x1 x2 1.6 stx2 1.4x1 ,x208、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等），希望获得其中的营养成分（如：蛋白质、脂肪、维生素等）。设市面上现有这3种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。营养物

7、营养成人""7甲乙丙至少需要的营养成分数量A462080B11265C10370D21735450价格252045问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用计算。解：设购买甲、乙、丙三种营养物的数量分别为X1、*2和*3,则根据题意可得如下线性规划模型:9、某公司生产的产品 A, B, C和D都要经过下列工序：包IJ、立铳、钻孔和装配。已知每单位产品所需工 时及本月四道工序可用生产时间如下表所示：刨立铳钻孔装配A0.52.00.53.0B1.01.0.0.51.0.C1.01.01.02.0D0.51.01.03.0可用生产时间（小时）

8、1800280030006000又知四种产品对利润贡献及本月最少销售需要单位如下:产品最少销售需要单位元/单位A1002B6003C5001D4004问该公司该如何安排生产使利润收入为最大？（只需建立模型）解：设生产四种产品分别X1,X2,X3,X4单位则应满足的目标函数为：maX z=2 x 1+3 X2+X3+ X4满足的约束条件为：10、某航空公司拥有10架大型客机、15架中型客机和2架小型客机，现要安排从一机场到4城市的航行计划，有关数据如表1-5,要求每天到D城有2个航次（往返），到 A,B,C城市各4个航次（往返），每架飞机每天只能完成一个航次，且飞行时间最多为18小时，求利润最大

9、的航班计划客机类型到达城市飞行费用（元/次）飞行收入（元/次）飞行时间（h/d ）大型A600050001B700070002C8000100005D100001800010中型A100030002B200040004C400060008D20小型A2000350060004000550080001 26 19BCD解：设大型客机飞往A城的架次为Xia,中型客机飞往 A城的架次为X2A,小型客机飞往 A城的架次为X3A,其余依此类推。资源限制派出的大型客机架次不能超过10架，表示为同理X2AX2BX2C15X3AX3BX3C2班次约束飞往各城的班次要满足非负性约束Xij 0 且为整数；（i=1

10、,2,3rA,B,C,D ）目标函数为maXZ 1000X1A 0x1b 2000X1C 8000Xid+2000x2A2000X2B 2000X2C 2000X3A 2000X3B 2000X3c11、AR1AR2AR4AR6联邦航空局的最大产量（每月生产的飞机数目）8171115建造飞机所需要的时间（天）47911每架飞机所需要的生产经理数目1122每架飞机的盈利贡献（千美元）6284103125CRISP公司下个月可以得到的生产经理的总数是 60人。该公司的飞机制造设施可以同时在任何给定的时间生产多达 9架飞机。因此，下一个月可以得到的制造天数是270天（9*30,每月按30天计算）。J

11、onathanKuring是该公司飞机制造管理的主任，他想要确定下个月的生产计划安排，以便使盈利贡献最大化。解：设X1表示下个月生产 AR1型飞机的数目，X2表示AR2型，X3表示AR4型，X4表示AR6型目标函数：max z 62x1 84x2 103x3 125x44xi 7X2 9X3 11x4270X1 x2 2x3 2x4 60X18约束条件：X2 17X3 11X4 15Xi, X2,X3,X4 0Xi, X2, X3,X4 为整数12、永辉食品厂在第一车间用1单位原料N可加工3单位产品A及2单位产品B,产品A可以按单位售价8元出售，也可以在第二车间继续加工，单位生产费用要增加6元

12、，加工后单位售价增加9元。产品B可以按单位售价7元出售，也可以在第三车间继续加工，单位生产费用要增加4元，加工后单位售价可增加6元。原料N的单位购入价为 2元，上述生产费用不包括工资在内。3个车间每月最多有 20万工时，每工时工资0.5元，每加工1单位N需要1.5工时，若 A继续加工，每单位需3工时，如B继续加工，每单位需 2 工时。原料N 每月最多能得到 10 万单位。问如何安排生产，使工厂获利最大？解：设Xi为产品A的售出量；X2为A在第二车间加工后的售出量；X3表示产品B的售出量； 刈表示B在第三车间加工后的售出量；x5 为第一车间所用原材料的数量，则目标函数为： maX z 8X1 9

13、.5X2 7X3 8X4 2.75 X5X5 1000003X2 2X4 1.5 X5 200000约束条件：X1 X2 3X5 0X3 X4 2X50X1,X2,X3,X4,X50化标准形式（5） 1、将下列线性规划模型化为标准形式 解：min z x1 2x2 3x3xiX2X37XiX2X323xiX22X35Xi 0 X2 0 X3无约束2、将下列线性规划模型化为标准形式max z'Xi2x23(X4 X5) 0 X6XiX2X4X5 X67XiX2X4X5X723x1X22X35Xi 70解：0 x73、将下列线性规划变为最大值标准形。解：? 图解法(5)1、用图解法求解下面

14、线性规划min z = 3xi+2x2解：可行解域为abcda ,最优解为b点。2xi 4x222由方程组解出xi=11, x2=0x2 0xiT. X= = (11, 0) Tx2.min z = -3X 11+2X0 = 332、用图解法求解下面线性规划min z =2x 1+x2解：从上图分析，可行解域为abcde ,最优解为e点。由方程组x1x28解出 x1=5, x2=3x15X*, T. X= = (5, 3)x2min z =Z = 2 x 5+3=13 3、已知线性规划问题如下：Max Z= x1 3x2用图解法求解，并写出解的情况5x1 10x250解之得：1x12贝ij m

15、ax Z=2+3*4=144、用图解法求解下面线性规划问题解:5、用图解法求解下面线性规划问题 图解如下：T可知，目标函数在 B(4, 2)处取得最大值，故原问题的最优解为X (4,2),目标函数最大值为*_ _ _ _z2*43*214。二、单纯型法(15)1、用单纯型法求解下面线性规划问题的解max z= 3x i+3x2+4x33xi 4x2 5x340at 6xi 4x23x366s.t.xi, x2, x3 0解：加入松弛变量 x4, x5,得到等效的标准模型：max z= 3x1+3x 2+4x3+。x 4+0 x 53x1 4x25x3 x440s.t.6x14x23x3x5 6

16、6xj0, j1,2,5列表计算如一r：33400CBXBb9 Lx1x2x3x4x50x44034(5)1080x566643012200000334to04x383/54/511/5040/30x542(21/5)8/503/511012/516/544/503/5 t -1/50-4/5043x3x121004/712/7-1/718/210-1/75/2138324/745/71/703/705/7-1/7X*= (10, 0, 2, 0, 0) Tmax z = 3X10+4X2 =382、用单纯型法求解卜面线性规划问题的解maxz =70x 1+120x29xi 4x2 3604x

17、1 6x2 200s.t.3xi 10x2 300x1, x20解：加入松弛变量 x3, x4, x5,得到等效的标准模型: max z =70x 1+120x2+0 x 3+0 x 4+0 x 5s.t.列表计算如下：CBXBb70x1120x20x30x40x59 L0x336094100900x420046010100/30x53003(10)001300000070120 t000400/10x324039/5010-2/53100/10x420(11/5 )001-3/51120x2303/101001/1010036120001234 t000120x31860/1100139/1

18、119/1170x1100/111005/11-3/11120x2300/11010-3/222/11701200170/1130/11000-170/1130/11*1003001860TX二（，0，0)11111110030043000max z =70 x+ 120X =1111113、用单纯型法求解下面线性规划问题的解2x1 2x2 3000max z = 4x 1+3x2s.t.解：加入松弛变量 x3,5x1 2.5x2 4000 x1500x1 , x20x4, x5,得到等效的标准形式:2x1 2x2 x33000max z= 4x 1+3x2 + 0 x3+0 x4+0 x 5

19、s.t.5x1 2.5x2 x4 4000x1% 500xj0, j 1,2,.,5用表解形式的单纯形法求解，列表计算如下:43000CBXBbx1x2x3x4x59 L0x33000221003000/2 =15000x4400052.50104000/5 =8000X5500(1)0001500/1 =500000004 t30000X320000210-22000/2 =10000X415000(2.5)01-51500/2.5 =6004X1500100014000403 t00-40X3800001-0.8(2)800/2 =4003X26000100.4-24X1500100015

20、00/1 =5004301.2-2000-1.22 t0X5400000.5-0.413X21400011-0.404X110010-0.50.40460040301-10.4-0.400据上表，X*= ( 100, 1400, 0, 0, 400) Tmax z =4、用单纯型法求解卜面线性规划问题的解4X 100+3 X 1400=460max z =10x 1+6X2+4X3s.t.解：加入松弛变量 X4, X5, X6,得到等效的标准模型:max z =10x 1+6X2+4X3+0 x 4+0 x 5+0 x 6XiX2X3X410010Xi4X2 5x3X5600s.t.2x12

21、X26 X3X6 300X0,j 1,2,6列表计算如下:1064000CBXBb° Lx1x2 x3 x4x5x60x41001111001000x5600(10)45010600x630022600115000000010t640000x4400(3/5) 1/21-1/100200/310X16012/51/201/1001500x618006/5501/51150104501002t 10- 106x2200/3015/65/3-1/6010X1100/3101/6 2/31/600x6100004-20110620/3 10/32/30一008/3 10/30 2/3_ 1

22、00 200,0, 0, 0, 100) T.max z =10x100+6x 200=22005、用单纯型法求解下面线性规划问题的解 用单纯形法求解，并指出问题的解属于哪一类。 解：（1）、将原问题划为标准形得：3x1 x2x3 X4 =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)

23、 T为唯一最优解Max Z=4*15-2*5=506、用单纯形法求解下述LP问题。解：引入松弛变量 X3、X4 ,化为标准形式：构造单纯形表，计算如下：2.510001535105010520122.510009019/51 3/545/192.5212/501/55000-1/2145/19015/19 3/192.520/1910 2/195/19000-1/2由单纯形表，可得两个最优解X (2,0,9,0) T、X(20/19,45 /19,0,0) T,所以两点之间的所有解都是最优解，即最优解集合为：X (1) (1 )X，其中01。7、用单纯形法解线性规划问题maxz 2x1 x25

24、X2156x12x224Xix25Xi0解：化为标准型maxz 2xi X2 0x3 0x4 0x55x2X3156x12x2x424xix2x55xi 50列出单纯形表C21000CBXbx1x2乂3乂4乂50乂3150510040乂4246201050乂5511001-Z0210000乂3150510032x1411/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、

25、用单纯型法求解下面线性规划问题的解max z xi x2x12x222x1x22x1x24x1 0 x2 0解:C11000CBXbXiX2X3X4X50X321121000X42-2101020X54-11001-Z0110001Xi21-21000X460-32100X560-1101-Z-203-100把表格还原为线性方程令 X 3=0此时，若让X2进基，则会和基变量 X1同时增加，使目标函数值无限增长，所以本题无界9、用单纯型法求解下面线性规划问题的解C24000CBXbbX1X2X3X4X50X381210040X441001030X5301001-Z0240000X321010-2

26、20X441001044X2301001-Z-122000-42xi21010-20x4200-1124x2301001-Z-2000-2002xi4100100x5100-1/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 3x15x2x142x2123x1 2x218xi0x20解：列表如下C35000CBXbbx1x2x3乂4x50x341010060乂4120201090x51832001-Z0350000x341010045x

27、260101/2030X56300-11-Z-30300-5/200X360011/3-1/35X220101/203Xi2100-1/31/3-Z-20000-3/2-1X*=(2,6,6,0,0)'Z*=3611、用单纯型法求解下面线性规划问题的解解：化为标准型单纯型表如下：C21000CBXbbX1X2X3X4X50X31505100一0X4246201040X55110015Z0210000X3150510032X1411/301/60120X5102/30-1/613/2Z001/30-1/300X315/20015/4-15/22X17/21001/4-1/21X23/20

28、10-1/43/2Z17/2000-1/4-1/2由些可得，问题的最优解为 Xi=7/2, x2=3/2 ,最优值 max z=17/212、用大M法求解如下线性规划模型：min z =5x 1 + 2x2+4x3解：用大M法，先化为等效的标准模型：max z / = 5xi 2x2 4x3s.t.增加人工变量*6、*7,得到：max z/ = 5xi 2x2 4x3 M<6 Me?s.t大M法单纯形表求解过程如下：-5-2一 400一 M一 MCBXBbx1x2x3x4x5x6x79 L一 Mx64(3)12-10104/3一 Mx71063501015/3-9M-4M-7MMM一 M

29、一 M9M- 5 t4M- 27M- 4一 M一 M00-5x14/311/32/3 1/301/30一 Mx720111-211-M一-5-M- 5/310/3-2M+5/3M2M- 5/3-M2M- 5/30M- 1/3Mk 2/3t一 M3M+5/30-5x15/311/25/60-1/601/610/30x410(1/2)1/21 1/211/22-5 5/2 25/605/60-5/601/2 t1/60-5/6一 MM+5/652x12/3101/3-11/311/3x2201121-21一-5-2-11/311/311/32200-1/3-1 1/3-M+1-M+1/330, 0

30、,0)T2,最优目标函数值 min z = max z / =()=3313、用大M法求解如下线性规划模型：min z =540x 1+450X2+ 720X3解：用大M法，先化为等效的标准模型：max z/ = 540X1 450X2720X3s.t.增加人工变量X6、X7,得到：maX z/ = 540Xi 450X2 720X3 Mx M*s.t大M法单纯形表求解过程如下:CBXBb 540x1 450x2-720x30x40x5一 Mx6一 Mx79 L一 Mx670359-101070/3一 Mx730(9)530-10130/9=10/312M-10M-12MMM一 M一 M12M

31、h 540t10Mh 45012Mh720一 M一 M00一 Mx660010/3(8)-11/31 1/360/8=2.5一x110/315/91/30-1/901/910/3/1540/3=10-300+10/3-8MM - M/3+60 M M/3-60M180-150+10/3 8M-5400MM/3-600- M/3+60Mt15/2/5一x315/205/121-1/81/241/8-1/24/12720=185/6/5/一x15/61(5/12 )01/24-1/8-1/241/812540=2- 540-572-720475/12 - 135/275/2135/20125t01

32、35/2 -475/12 135/2 -M 75/2 -Mx320/3-1011/61/61/61/6 720 450x2212/5101/10-3/10-1/103/10一- 360-450-7207515-75 155700-18000-75-1575-M15-M20.该对偶问题的最优解是 x= (0, 2, 0, 0) T最优目标函数值min z = 一 ( 5700) =570014、用单纯形法求解线性规划问题化成标准形式有加入人工变量则为列出单纯形表C-30100一 M-MCbXbbX1X2X3X4X5X6X70X441111000-MX61-21-10-110-MX79031000

33、1-Z10M-2M-34M10-M000X4330211-100X21-21-10-110-MX7660403-31-Z6M6M-304M+103M-4M00X400001-1/2-1/21/20X23011/30001/3-3Xi1102/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、用单纯形

34、法求解线性规划问题解化为标准形式有 列表计算G-3-200MCBXbX1X2X3X4X50X32211002MX512340-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、写出下述线性规划的对偶问题maXzx1 4x23x32x13x25X323x1X26X31X1X2X34x10x20x3无约束解3、写出下列线性规划的对偶问题min z25x12x2 3x3X1X2X31X12x2X31

35、2x1X2X31x1 0X20 X3无约束解：maxw v1 y2 y3ViV22 y325yi2 y2y32Viy2y33y10y2 0 y3无约束 4、写出下列线性规划的对偶问题max z 2x1 x2 4x32x13x2x313x1x2x34x1x33x10x20x3无约束? 对偶性质1、已知线性规划问题如下:Max Z= Xi 3X2已知该问题的解为(2, 4)利用对偶性质写出对偶问题的最优解。解：该问题的对偶问题为:将X= (2, 4) T代入原问题可知：X1X2 > 1为严格不等式，所以y2 0由对偶问题性质可知：50yi 4y314解之得：y yi 1/5所以 Y= (1/

36、5,0, 1) TMin Z=14-2、已知线性规划问题j用图解法求对偶问题的解；利用(卜的结果及对偶性质求原问题解。“ 一 ,*8 1、答案：(对偶问题的最优解为 Y(,);5 5(依据z*=w*及互补松弛性，有 X4=0,且解得愿问题最优解 X*=(7/5,0,1/5,0)。3、已知线性规划问题已知其对偶问题的最优解为*4*3 *% 一，丫2 ，最优值为z5。试用对偶理论找出原问题的最优解。55解先写出它的对偶问题y1s.t.y y232 yl 3y3 5y y223y1 v 23*将y1，y2的值代入约束条件，得,，为严格不等式；设原问题的最优解为*X(X1 ,X5),由互* *补松弛性

37、得X2X3 X4 0。因y1,y2 0;原问题的两个约束条件应取等式，故有* ,*,求解后得到X11,X51 ；故原问题的最优解为*_X 1 0 0 0 1'；最优值为 w 5。4、已知下列问题的最优解为X*=(1/7,11/7),用互补松弛定理求其对偶问题的最优解。解：第一步，写出对偶问题LP : maX z X1 2x23x1 X22X1 2x2 3X1 3x2 1x1,x2 0第二步，将LP, DP都化为标准型LP : max z x12x23xix2xisX1 2x2x2Sxi 3x2x3SDP : min w 2yi23yi3yiix1, x2 0xiS,2S,3s 0|y1

38、第三步：将最优解代入标准型中，确定松弛变量取值第四步：利用互补松弛定理Y*=0Yis=0第五步：将» 3yl则有yi3y2 y3y2y3yisi2y23y3y2S20 y2 0y30 yis,2s oY2s=0Y3*=0Ys=0y2i45yiy2一2y2277Y2s=0代入约束条件对偶问题的最优解为 Y*=(4/7,5/7,0)'maxz x1 x2 x1x25、已知线性规划问题：122x1x2xi,x2, x3题无最优解。证明：首先看到该问题存在可行解，例如 X3,试用对偶理论证明上述线性规划问乂3i00 0 0,而上述问题的对偶问题为：min w 2 yl y2Yi2y2iYiy2iyiy20yi, y20由第一约束条件可知对偶问题无