《运筹学》题库

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

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

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

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

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

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

7、80B11265C10370D21735450价格252045问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少只建立模型，不用计算。解：设购买甲、乙、丙三种营养物的数量分别为Xi、X2和X3,则根据题意可得如下线性规划模型：9、某公司生产的产品 A, B, C和D都要经过下列工序：包I、立铳、钻孔和装配。已知每单位产品所需工时及本月四道工序可用生产时间如下表所示：刨立铳钻孔装配AB.CD可用生产时间（小时）1800280030006000又知四种产品对利润贡献及本月最少销售需要单位如下:产品最少销售需要单位元/单位A1002B6003C5001D4004问该公司该如何安排生产使利

8、润收入为最大（只需建立模型）解：设生产四种产品分别 Xi,X2,X 3,x 4单位则应满足的目标函数为：max z=2 x i+3 X2+X3+ x 4满足的约束条件为：10、某航空公司拥有10架大型客机、15架中型客机和2架小型客机，现要安排从一机场到4城市的航行计划，有关数据如表1-5,要求每天到D城有2个航次（往返），到A,B,C城市各4个航次（往返），每架飞机每天只能完成一个航次，且飞行时间最多为18小时，求利润最大的航班计划客机类型到达城市飞行费用（元/次）飞行收入（元/次）飞行时间（h/d ）大型A600050001B700070002C8000100005D10000180001

9、0中型A100030002B200040004C400060008D20小型A200040001B350055002C600080006D19解：设大型客机飞往 A城的架次为X1A,中型客机飞往 A城的架次为X2A,小型客机飞往A城的架次为X3A,其余依此类推。资源限制 派出的大型客机架次不能超过 10架，表示为同理X2A X2B X2CX3A X3B X3C152班次约束飞往各城的班次要满足非负性约束Xj 0 且为整数；（i=1,2,3产A,B,C,D）目标函数为maxz 1000x1A 0x1B 2000x1c 8000Xid+2000x2A2000x2B 2000X2C 2000x3A

10、2000X3B 2000X3C 2 B2 C3A3 B3C11、AR1AR2AR4AR6联邦航空局的最大产量（每月生产的飞机数目）8171115建造飞机所需要的时间（天）47911每架飞机所需要的生产经理数目1122每架飞机的盈利贡献（千美元）6284103125CRISP公司下个月可以得到的生产经理的总数是60人。该公司的飞机制造设施可以同时在任何给定的时间生产多达9架飞机。因此，下一个月可以得到的制造天数是270天（9*30,每月按30天计算）。Jonathan Kuring是该公司飞机制造 管理的主任，他想要确定下个月的生产计划安排，以便使盈利贡献最大化。解：设人表示下个月生产 AR1型

11、飞机的数目，X2表示AR2型，X3表示AR4型，x,表 示AR6型目标函数： maxz 62x1 84x2 103x3 125x44xi 7x2 9x3 11x4270x1 x2 2x3 2x4 60Xi 8约束条件：x 17X3 11x4 15X1,X2,X3,X40Xi,X2, X3,X4 为整数12、永辉食品厂在第一车间用 1单位原料N可加工3单位产品A及2单位产品B,产品A可以按单位售价8元出售，也可以在第二车间继续加工，单位生产费用要增加6元，加工后单位售价增加 9元。产品B可以按单位售价7元出售，也可以在第三车间继续加工，单位生产费用要增加4元，加工后单位售价可增加 6元。3 个车

12、间每月最多有原料N的单位购入价为2元，上述生产费用不包括工资在内20 万工时，每工时工资元，每加工1 单位 N 需要工时，若A 继续加工，每单位需3 工时，如 B 继续加工，每单位需2 工时。原料N 每月最多能得到 10 万单位。问如何安排生产，使工厂获利最大解：设xi为产品A的售出量；X2为A在第二车间加工后的售出量；X3表示产品B的售出量；X4表示B在第三车间加工后的售出量；X5为第一车间所用原材料的数量，则目标函数为： maX z 8X1 9.5 X2 7X3 8X4 2.75 X5X5 1000003X2 2X4 1.5X5 200000约束条件：X1 X2 3X5 0X3 X4 2

13、X50X1,X2,X3,X4,X5 0?化标准形式(5)1、将下列线性规划模型化为标准形式min z x12x23x3xi又2X37xi又2X3234又22x35xi 0x20x3无约束maxz'x1 2x2 3(x4 x5) 0 x6 0 x7Xix2x4x5x67xix2x4x5x723xix22x35xi 70解：2、将下列线性规划模型化为标准形式解：3、将下列线性规划变为最大值标准形。解:? 图解法（ 5 ）1、用图解法求解下面线性规划 min z = 3x1+2x2解：可行解域为abcda ，最优解为b 点。由方程组2x1 4x222x20解出x1=11， x2=0*x1X*

14、=x2=（11， 0） Tmin z =3X 11+2X0= 332、用图解法求解下面线性规划min z =2x 1+x2解：从上图分析，可行解域为abcde,最优解为 e点。由方程组x1x2x1解出 x 1=5， x2=3*x1X*=（ 5， 3 ）x23、已知线性规划问题如下：.min z =Z *= 2 x 5+3=13Max Z= x1 3x2用图解法求解，并写出解的情况解：5xi+10X2=50由图可知:5xi 10X250Xl+X2=1解之得:Xi贝U max Z=2+3*4=14 4、用图解法求解下面线性规划问题解:5、用图解法求解下面线性规划问题图解如下:可知，目标函数在B(4

15、, 2)处取得最大值，故原问题的最优解为X* (4,2)T,目标函数最大值为z* 2*43*214。二、单纯型法(15)1、用单纯型法求解下面线性规划问题的解max z= 3x i+3x2+4x33x1 4x2 5x3 406x1 4x2 3x3 66 .x1,x2, x30解：加入松弛变量x4, x5,得到等效的标准模型:max z= 3x 1+3x2+4x3+0 x 4+0 x 53xi 4x2 5x3 x440.6x1 4x2 3x3x5 66xj 0, j 1,2,5列表计算如下:33400CBXBbx1x2x3x4x59 L0x44034(5)1080x566643012200000

16、334 t004x383/54/511/5040/30x542(21/5 )8/50-3/511012/516/544/503/5 t-1/50-4/504x3204/712/7-1/73x11018/210-1/75/21324/745/71/7380-3/70-5/7-1/7X=(10, 0, 2, 0, 0) T -.max z =3X10+4X2 =382、用单纯型法求解下面线性规划问题的解 max z =70x i+120X29xi 4x2 3604xi 6x2 200.3xi 10x2300x1, x2 0解：加入松弛变量X3, X4, X5,得到等效的标准模型:max z =70

17、x 1+120x2+0 x 3+0 x 4+0 x 5列表计算如下:CBXBb70x1120x20x30x40x59 L0x336094100900x420046010100/30x53003(10)001300x32400x420120x2300x31860/1170x1100/11120x2300/11. X二(10011，max z =7000070120 t039/501(11/5 )003/101036120034 t00001100010701200000T300186011 '110)X +120X11300 = 4300011 - 110000400/10-2/5310

18、0/11-3/5101/1010001201239/1119/115/11-3/11-3/222/11170/1130/11-170/1130/113、用单纯型法求解下面线性规划问题的解2x1 2x2 3000max z = 4x 1+3x2.5x1 2.5x2 4000x1500x1 , x20解：加入松弛变量x3, x4, x5,得到等效的标准形式:max z= 4x 1+3x2+0 x 3+0 x 4+0 x 5.2x1 5x1 x1Xj2x22.5x20，jx3x4x51,2,30004000500.,5用表解形式的单纯形法求解，列表计算如下*43000CBXBbxix2x3x4x59

19、 L0x33000221003000/2 =15000x4400050104000/5 =8000x5500(i)0001500/1 =500000004 t30000x320000210-22000/2 =10000x415000001-51500/ =6004xi500100014000403 t00-40x3800001(2)800/2 =4003X2600010-24xi50010001500/1 =500430-20002 t0x54000013X214000114X11001043104600 00-10据上表，X*= (100, 1400, 0, 0, 400) Tmax z =

20、 4X 100+3X 1400=460 4、用单纯型法求解下面线性规划问题的解max z =10x 1+6X2+4X3解：加入松弛变量X4, X5, X6,得到等效的标准模型:max z =10x 1+6X2+4X3+0 x 4+0 x 5+0 x 6X1 x2 x3 x410010x1 4x2 5x3X5600.2x1 2x2 6x3x6 300Xj 0,j 1,2,6列表计算如下:1064000CBXBbx1x2x3x4x5x69 L0x41001111001000x5600(10)45010600x630022600115000000010 t640000x4400(3/5 ) 1/21

21、-1/100200/310x16012/51/201/1001500x618006/550-1/51150104501002t 10- 106x2200/3015/65/3-1/6010x1100/3101/6 -2/31/600x6100004-20110620/3 10/32/30一008/3 10/30 2/3*100200_ T. X二(c ，0，0, 0, 100)33100200 2200max z=10X+6X=3335、用单纯型法求解下面线性规划问题的解用单纯形法求解，并指出问题的解属于哪一类。解：（1）、将原问题划为标准形得：3x1 x2 x3 x4 =604-22000b0

22、603111000101-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为唯一最优解Max Z=4*15-2*5=506、用单纯形法求解下述 LP问题。解：引入松弛变量X3、X4,化为标准形式：构造单纯形表，计算如下：100015351050105201210009019/51 3/545/19212/501/55000 1/

23、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 ,所以两点之间的所有解都是最优解，即最优解集合为：X(1)*出，其中01maxz 2x1 X25x2156x12x224X1x25x1 0x2 07、用单纯形法解线性规划问题解：化为标准型maxz 2x1 x2 0x3 0x4 0x55x2x3 156x12x2x4 24x1x2 x5 5x1 5 0列出单纯形表C21000CBXbXiX2X3X4X50x3150510040乂4246201050x5511001-Z0

24、210000x3150510032x1411/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、用单纯型法求解下面线性规划问题的解 max z x1 x2Xi2x222x1x22x1x24x1 0 x2 0解：C11000CBXbx1x2x3x4x50x3211210020x42-210100X54-11001-Z0110001Xi21-21000X460-32100X5

25、60-1101-Z-203-100把表格还原为线性方程令 X 3=0此时，若让X2进基，则会和基变量X1同时增加，使目标函数值无限增长，所以本题无界9、用单纯型法求解下面线性规划问题的解C24000CBXbbX1X2X3X4X50X381210040X441001030X5301001-Z0240000X321010-220X441001044X2301001-Z-122000-42X121010-20X4200-1124X2301001-Z-2000-2002x14100100x5100-1/21/214x22011/2-1/20-Z-2000-200Z*=20, X*=(2,3,0,2,0

26、)' Z*=20, X*=(4,2,0,0,1)max z 3x1 5x2x142x2123x12x218x10x2010、用单纯型法求解下面线性规划问题的解解：列表如下C35000CBXbbx1x2x3x4x50x341010060乂4120201090x51832001-Z0350000x341010045x260101/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、用单纯型法求解下面线性规划问题的解解：化为标准型单纯

27、型表如下：C21000CBXbbX1X2X3X4X50X31505100一0X4246201040X55110015Z0210000X3150510032X1411/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由些可得，问题的最优解为Xi=7/2 , X2=3/2 ,最优值max z=17/212、用大M法求解如下线性规划模型:min z =5x 1 + 2x2+4x3解：用大M法，先化为等效的 标准模型：max z = 5xi 2x

28、2 4x3.增加人工变量x6、X7,得到：max z/ = 5xi 2x2 4x3 M<6 M<7大M法单纯形表求解过程如下：-5-2-400MMCBXBb9 Lx1x2x3x4x5x6x7一 Mx64(3)1210104/3一 Mx7106350 1015/39M-4M-7MMMMM9M- 5t4M- 27M- 4M M00-5x14/311/32/3-1/301/30一 Mx72011-1-211-M一-5 -M- 5/3-2M+5/3 M 2M- 5/3 -M10/32M- 5/30M-1/3MM- 2/3- M - 3M+5/30t-5x15/311/25/60-1/601

29、/610/30x410(1/2)1/21 1/211/22-5 5/2-25/605/60-5/601/2 t1/60-5/6一 MM+5/65x12/3101/3-11/311/32x2201121-21一-5-211/311/311/322300-1/3-1-1/3M+1-M+1/3x*=(2a，2,0,0, 0) T最优目标函数值min z =-/一max z二一（一22)=22313、用大M法求解如下线性规划模型*min z=540x 1+450x2 + 720x3解：用大M法,先化为等效的标准模型：max z/ = 540xi一 450x2 一720x3增加人工变量X6、X7,得到：

30、max Z = - 540xi 450X2 720X3 Mx Mx大M法单纯形表求解过程如下：CBXBb-540-45072000M Mx1x2x3x4x5x6x79 L一 Mx670359-101070/3一 Mx730(9)530-10130/9=10/312M-10M-12MMM一 M一 M12M- 540t10M- 45012M-720一 M一 M00一 Mx660010/3(8)-11/31-1/360/8=10/3/1一540x110/315/91/30-1/901/9/3=10-300+10/3M-8M一180一 MM/3+60一 MM/3-600-150+10/3M8M-540

31、tMM/3-600M/3+6015/2/5一720x315/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-720一135/2475/12135/2 75/20125 t0135/2-475/12 135/2 -M75/2 M 720-450x3x220/32-1011/61/61/61/612/5101/10-3/10-1/103/10一5700.肉- 360450-7207515-75 15 18000-75-1575-M15-M寸偶问题的最优解是 x= (0, 2,0, 0

32、) T3最优目标函数值 min z = ( 5700) =570014、用单纯形法求解线性规划问题化成标准形式有加入人工变量则为列出单纯形表C-30100一 M-MCbXbbXiX2X3X4X5X6X70X441111000-MX61-21-10-110-MX790310001-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/20X40000

33、1-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、用单纯形法求解线性规划问题解化为标准形式有 列表计算C-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 说明原问题无解?

34、 写对偶问题(10)1、写出下列线性绘画问题的对偶问题解:2、写出下述线性规划的对偶问题maxzX1 4x23X32x13x25X323x1X26X31X1X2X34X10x20x3无约束解3、写出下列线性规划的对偶问题min z25x12x2 3x3X1X2X31X12x2X312x1X2X31X10X20 X3无约束解:maxwy1y2y3y1y22y325y12 y2y32y1y2y33y10V2 0y3无约束4、写出下列线性规划的对偶问题maxz2x1 x24x32x13x2X313x1X2X34X1X33Xi 0 X2 0 X3无约束? 对偶性质1、已知线性规划问题如下：Max Z=

35、 x1 3x2已知该问题的解为(2, 4)利用对偶性质写出对偶问题的最优解。解：该问题的对偶问题为：将X=(2,4)T代入原问题可知：xiX2>1为严格不等式，所以V20由对偶问题性质可知：50yi 4y3 14解之串：Vi 1/5所以 Y= (1/5 , 0, 1) TM Min Z=142、已知线性规划问题、用图解法求对偶问题的解；利用(b)的结果及对偶性质求原问题解。，一，、一，一八，*8 1答案：(对偶问题的最优解为Y(8,1)；5 5(依据z*=w*及互补松弛性，有 X4=0，且解得愿问题最优解 X*=(7/5,0,1/5,0)。3、已知线性规划问题已知其对偶问题的最优解为y*

36、 4,y2 3,最优值为z* 5。试用对偶理论找出原 55问题的最优解。解先写出它的对偶问题y12 y22yy232y1 3y3y V2 243yi V2 3y；,y；的值代入约束条件，得，为严格不等式；设原问题的最优解为x* (x*,x5),由互补松弛性得x2 x3 x； 0。因* *y1，y20；原问题的两个约束条件应取等式，故有求解后得到x*1,x5 1；故原问题的最优解为X 1 0 0 0 1;最优值为 w 5。4、已知下列问题的最优解为X*=(1/7,11/7),用互补松弛定理求其对偶问题的最优解。解：第一步，写出对偶问题第三步:将最优解代入标准型中,确定松弛变量取值第四步:利用互补

37、松弛定理3x1x2 x12x2S323y1V2y3y1 S1x1 2x2 3x2 1x2S3y2y23y3y2S2x1 3xx1,x2 0x3S1x1, x2 0 xs,：2s，3S 0y10V2 0V3 0y1S，2s0DP : min w2yiy3第二步,将LP, DP都化为标准型3y2LP : max z x1 2x2LP : maXxz x1 2x2Y*=0Yis=0Ys=0第五步：将Y3*=0Ys=0Ys=0代入约束条件则有 yy1 2y： 12V2对偶问题的最优解为Y*=(4/7,5/7,0)maxz x1 x25、已知线性规划问题：Xx2x32,试用对偶理论证明2x1x2x31x1，x2,x30上述线性规划问题无最优解。证明：首先看到该问题存在可行解，例如X 0 0 0,而上述问题的对偶问min w2y1y2y12 y21题为：y1y21y1y20y1，y20由第一约束条件可知对偶问题无可行解，因而无最优解。由此，原问题也无最优解。5、已知线性规划问题(1)写出其对偶问题；(2)用图解法求对偶问题的解；(3)利用(2)的结果及对偶性质求原问题解。解：(1)原线性规划问题可化为:其对偶问题为：(2)用图解法解得Y*