运筹学习题集03

1、数学建模1、某织带厂生产A、B两种纱线和C、D两种纱带，纱带由专门纱线加工而成。这四种产品的产值、成本、加工工时等资料列表如下： 产品 项目ABCD单位产值 (元)1681401050406单位成本 (元)4228350140单位纺纱用时 (h)32104单位织带用时 (h)0020.5工厂有供纺纱的总工时7200h，织带的总工时1200h，列出线性规划模型。解：设A的产量为x1，B的产量为x2，C的产量为x3，D的产量为x4，则有线性规划模型如下：max f(x)=(168-42)x1 +(140-28)x2 +(1050-350)x3 +(406-140)x4=126 x1 +112 x2

2、 +700 x3 +266 x4s.t. 工厂1工厂2200万m3500万m32、靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。列出线性规划模型。解：设x1、x2分别代表工厂1和工厂2处

3、理污水的数量(万m3)。则问题的目标可描述为min z=1000x1+800x2x1 10.8x1 + x2 1.6x1 2x21.4x1、x203、红旗商场是个中型的百货商场，它对售货人员的需求经过统计分析如表所示。为了保证售货人员充分休息，售货人员每周工作五天，休息两天，并要求休息的两天是连续的，问应该如何安排售货人员的作息，既满足了工作需要又使配备的售货人员的人数最少？（只建模型，不求解）时 间所需售货员人数星期日28人星期一15人星期二24人星期三25人星期四19人星期五31人星期六28人解：设x1为星期一开始上班的人数，x2为星期二开始上班的人数，x7星期日开始上班的人数。 min

4、x1+x2+x3+x4+x5+x6+x7x3+x4+x5+x6+x728x4+x5+x6+x7+x115x5+x6+x7+x1+x224x6+x7+x1+x2+x325x7+x1+x2+x3+ x419x1+x2+x3+x4+x531x2+x3+x4+x5+x628x1、x2、x3、x4、x5、x6、x704、一个登山队员，他需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等，每种物品的重量及重要性系数见表所示，能携带的最大重量为25 kg，试选择该队员所应携带的物品。序号1234567物品食品氧气冰镐绳索帐篷照相器材通信设备重量kg55251023重要性系数20151614

5、8149解：引入01变量xi （i1，7）则01规划模型为：max z20x115x216x314x48x514x69x7s.t. 5x15x22x35x410x52x63x725xi0或1，i1，0，7标准化问题1、将下列线性规划化为标准形式 2、化下列线性规划为标准形max z=2x1+2x24x3x1 + 3x23x3 30x1 + 2x24x380x1、x20，x3无限制解：按照上述方法处理，得该线性规划问题的标准形为 max z=2x1+2x24x31+4x32x1 + 3x23x31 + 3x32x4 = 30x1 + 2x24x31 + 4x32 + x5 = 80x1、x2，x

6、31，x32，x4，x5 0图解法111z=42z=6OA图131、用图解法求解下面线性规划。 max z=2x1+2x2x1x2 1x1 + 2x2 0x1、x2 0解：图13中阴影部分就是该问题的可行域，显然该问题的可行域是无界的。两条虚线为目标函数等值线，它们对应的目标值分别为2和4，可以看出，目标函数等值线向右移动，问题的目标值会增大。但由于可行域无界，目标函数可以增大到无穷。称这种情况为无界解或无最优解。2、用图解法求解下述LP问题。解： 可知，目标函数在B(4, 2)处取得最大值，故原问题的最优解为，目标函数最大值为。3、 用图解法求解以下线性规划问题：（1）maxz=x1+3x2

7、s.t.x1+x210-2x1+2x212x1 7x1,x20 x2 10 (2,8) 6 x1 -6 0 7 10最优解为（x1,x2）=（2,8），max z=26(2)minz=x1-3x2s.t.2x1-x2£4x1+x2³3x2³5x1£4x1,x2³0 x2 5 3 x1 0 2 3 4最优解为 （x1，x2）=（0，5），min z=-15（3）maxz=x1+2x2s.t.x1-x2£1x1+2x2£4x1£3x1,x2³0 x2 2 x1 0 1 2 3 4多个最优解，两个最优极点为（x

8、1，x2）=（2，1），和(x1，x2)=(0，2)，max z=5（4）minz=x1+3x2s.t.x1+2x2³42x1+x2³4x1,x2³0 x2 x1=0 4 x4=0 2 x3=0 x2=0 x1 0 2 4 最优解为（x1，x2）=（4，0），min z=4单纯形法1、用单纯形法求解max z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x20解：首先将问题化为标准形式，然后将整个计算过程列在一个表中Cj50100000b CBXB x1 x2x3x4x5 0x311100300 0x421010400 0x501

9、001250z501000000 0x31010-150 0x42001-1150 100x201001250z50000-10025000 50x11010-150 0x400-21150 100x201001250z00-500-5027500由于j0（j=1，5），故X*=（50，250，0，50，0）T， Z*=275002、用单纯形法求解max z=2x1+x2x1 + x252x15x210x1、x20解：用单纯形表实现如表110 表110Cj2100b CBXB x1x2x3x4 0x3-11105 0x42-5011010/4(min)z21000 0x30-3/211/210

10、 2x11-5/201/25z060-1102=6 > 0，且p20，故该线性规划有无界解（无最优解）。3、用单纯形法（大M法）求解下列线性规划max z=3x12x2x3x12x2 + x3 114x1 + x2 + 2x3 32x1 + x3 = 1x1、x2、x30解：化为标准形式 max z=3x12x2x3x12x2 + x3 + x4 = 114x1 + x2 +2x3 x5 = 32x1 +x3 = 1x1、x2、x3 、x4、x50在第二、三个约束方程中分别加入人工变量x6、x7，构造如下线性规划问题max z=3x12x2x3Mx6Mx7x12x2 + x3 + x4

11、= 114x1 + x2 +2x3 x5 + x6 = 32x1 + x3 +x7 = 1x1、x2、x3、x4、x5、x6、x70用单纯形进行计算，计算过程见表Cj3-1-100-M-Mb CBXB x1 x2x3x4x5x6x70x41-21100011-Mx6-4120-1103-Mx7-20100011z3-6M-1+M-1+3M0-M004M0x43-20100-110-Mx60100-11-21-1x3-20100011z1-1+M00-M0-3M+1M+10x43001-22-512-1x20100-11-21-1x3-20100011z1000-1-M+1-M-123x1100

12、1/3-2/32/3-5/34-1x20100-1121-1x30012/3-4/34/3-7/39z000-1/3-1/3-M+1/3-M+2/32由于j0（j=1，7），且基变量中不含人工变量，故X*=（4，1，9）T， z*=24、用单纯形法（大M法）求解下列线性规划max z=3x1+2x22x1+ x2 23x1 +4 x2 12x1、x20解: 化为标准形式后引入人工变量x5得到 max z=3x1+2x2Mx52x1+ x2 +x3 = 23x1 +4 x2 x4+x5 =12x1、x50用单纯形法计算，过程列于表中。从表中可以看出，虽然检验数均小于或等于零，但基变量中含有非零的

13、人工变量x5=4，所以原问题无可行解。 3200-MbCBxBx1x2x3x4x50-Mx3x52314100-101212-z3+3M2+4M0-M012M2-Mx2x52-5101-40-10124-z-1-5M0-2-4M-M0-4+4M2、用单纯形法求解下述LP问题。解：首先将原问题转化为线性规划的标准型，引入松弛变量x3, x4,x5，可得：构造单纯形表，计算如下：230000812100401640010012040013230000210101/220164001043301001/420003/42210101/2080041243301001/41200201/4241001

14、/40040021/2132011/21/80003/21/80原问题的最优解为，目标函数最大值为。3、用单纯形法求解下述LP问题。解：首先将原问题转化为线性规划的标准型，引入松弛变量、，可得：构造单纯形表，计算如下：340004021104003013011034000305/301-1/3184101/3101/3305/300-4/3318103/5-1/54401-1/52/500-1-1由此可得，最优解为，目标函数值为。4、用单纯形法求解下述LP问题。解：引入松弛变量、，化为标准形式：构造单纯形表，计算如下：2.510001535105010520122.510009019/513/

15、545/192.5212/501/550001/2145/19015/193/192.520/19102/195/190001/2由单纯形表，可得两个最优解、，所以两点之间的所有解都是最优解，即最优解集合为：，其中。5、用单纯形法求解下述线性规划解：引入松弛变量、和，列单纯形表计算如下：1230000821810010413100101/308114001123000024/5-14/517/501-4/5032/51/10-3/10101/1004048/57/5-11/5002/5148/77/10-11/1000-3/1000160-528120141-3100100402-140-11

16、01-70-1002600-71-1/25/211010-110-1/23/22201-70-1/21/20000-1/2-1/2故，原问题的最优解为， ，其中。7、用单纯形法求解下述LP问题。解：构造单纯形表计算如下：340004021104003013011034000305/3011/3184101/3101/3305/3004/3318103/51/544011/52/50011故，最优解为，目标函数值为。8、用大M法求解下述LP问题解：先将原问题化为标准型，引入松弛变量，得：再引入人工变量、，得：构造单纯形表计算如下：2350MMM71110107M1025110153M+23-4M

17、2M-5-M00M207/21/21/211/24/72515/21/21/201/207M/2+8M/2-6M/2+10-3M/2-134/7011/71/72/7-1/7245/7106/7-1/75/71/700-50/7-1/7-M-16/7-M+1/7由此得，原问题的最优解为，目标函数最优值为102/7。9、用两阶段法求解下述LP问题解：先将原问题化为标准型，引入松弛变量，得：再引入人工变量、，得第一阶段的模型为：构造单纯形表，计算如下：00001117111010711025110153421001207/21/21/211/24/70515/21/21/201/207/21/21

18、/203/234/7011/71/72/7-1/7245/7106/7-1/75/71/7000011由此可得第一阶段的最优解，转入第二阶段，单纯形表如下：235034/7011/71/7245/7106/7-1/700-50/7-1/7由此得，原问题的最优解为，目标函数最优值为102/7。10、求解下述LP问题 解：用大M法求解。将原问题化为标准型，可得：在第三个等式约束中引入一个人工变量，可得：用单纯形表求解，可得：101512000M0953110009/501556150100-M521100-115/22M+10M+15M+1200-M0109/513/51/51/500090240

19、91611003/2M7/50-1/53/5-2/50-117/309-M/53M/5+10-2M/5-20-M0103/2139/8003/16-1/8000123/209/1611/161/1600-M1/20-43/800-7/16-3/80-11027/8-43M/800-21/8-7M/16-5/8-3M/8-M0所有变量的检验数均为负数或零，单纯形表计算完毕，但人工变量仍在基变量中，故原问题无可行解。写对偶问题1、写出下列线性规划问题的对偶问题 max z=2x1+2x24x3x1 + 3x2 + 3x3 304x1 + 2x2 + 4x380x1、x2，x30解：其对偶问题为mi

20、n w=30y1+ 80y2y1+ 4y2 23y1 + 2y2 23y1 + 4y2 4y1、y202、写出下列线性规划问题的对偶问题 min z=2x1+8x24x3x1 + 3x23x3 30x1 + 5x2 + 4x3 = 804x1 + 2x24x350x10、x20，x3无限制解：其对偶问题为max w=30y1+80 y2+50 y3 y1 y2 + 4 y3 23y1+5y2 + 2y3 83y1 + 4y24y3 =4y10，y2无限制，y30对偶的性质1、已知线性规划问题 max z=x1+2x2+3x3+4x4x1 + 2x2 + 2x3 +3x4202x1 + x2 +

21、 3x3 +2x420x1、x2，x3，x40其对偶问题的最优解为y1*=6/5，y2*=1/5。试用互补松弛定理求该线性规划问题的最优解。解：其对偶问题为min w=20y1+ 20y2y1 + 2y2 1 （1）2y1 + y2 2 （2）2y1 +3y2 3 （3）3y1 +2y2 4 （4）y1、y20将y1*=6/5，y2*=1/5代入上述约束条件，得（1）、（2）为严格不等式；由互补松弛定理可以推得x1*=0，x2*=0。又因y1*>0，y2*>0，故原问题的两个约束条件应取等式，所以2x3* +3x4* = 203x3* +2x4* = 20解得x3* = x4* =

22、 4。故原问题的最优解为 X*=（0，0，4，4）T2、已知线性规划的最优解为，试利用互补松弛定理，求对偶问题的最优解。解：原问题的对偶问题为：將代入原问题的约束条件，可得： （1）又由 （2）将结论（1）和（2）结合起来，可解得。3、已知线性规划问题其对偶问题的最优解为、，试用对偶理论求解原问题的最优解。解：原问题的对偶问题为：将对偶问题的最优解代入约束条件，可得： （1）又由 （2）将结论（1）和（2）结合起来，可得： ，解得 即原问题的最优解为。对偶单纯形法1、用对偶单纯形法求下面问题解：Cj ®4600min( zj - cj)/ai*jCBXBbx1x2x3x4ai*j&l

23、t;00x3-80-1(-2)104,3*0x4-75-3-101OBJ=0zj ®0000zj - cj-4-600Cj ®4600CBXBbx1x2x3x46x2401/21-1/200x4-35(-5/2)0-1/212/5*,6OBJ=240zj ®36-30zj - cj-10-30Cj ®4600CBXBbx1x2x3x46x23301-3/51/54x114101/5-2/5OBJ=254zj ®46-14/5-2/5zj - cj00-14/5-2/5最优解为x1 =14，x2 =33，目标函数值为254。2、用对偶单纯形法求解

24、下列线性规划 min z=4x1+2x2+6x32x1 +4x2 +8x3 244x1 + x2 + 4x38x1、x2，x30解：将问题改写成如下形式 max（z）=4x12x26x32x1 4x2 8x3 + x4 =244x1 x2 4x3 +x5 =8x1、x2，x3，x4，x50整个问题的计算过程列在表中。Cj42600bCBXBx1x2x3x4x50x4-2-4-810-240x5-4-1-401-8z-4-2-6000-4/-2-2/-4-6/-1000-2x21/212-1/4060x5-7/20-2-1/41-2z-30-2-1/20-120-3/(-7/2)0-2/-2(-

25、1/2)/(-1/4)0-2x2-310-1/214-6x37/4011/8-1/24z-1/200-1/4-1-32得到问题的最优解为X*=（0，4，4）T 最优值为z*=323、用对偶单纯形法求解解：先将原问题改写为：建立单纯形表计算如下：2340003121100421301234000105/21/211/22211/23/201/20410132/5011/52/51/5211/5107/51/52/5009/58/51/5故，原问题的最优解为，。灵敏度分析1、设某线性规划问题的初始单纯形表和最优单纯形表分别为Cj54300bCBXBx1x2x3x4x50x411110600x521

26、40180z543000Cj54300bCBXBx1x2x3x4x54x201-22-1405x1103-1120z00-4-3-1-260问：（1）c3在什么范围内变化，表中最优解不变？（2）c3从3变为8，求新的最优解解：（1）由于在最优单纯形表中，c3为非基变量的价格系数，因此其变化仅会影响到检验数3=4，因此当c33=4时，表中最优解不变。（2）当c3从3变为8时，则表中的检验数3从4变为1，即表中的最优解将发生变化，用单纯形法求解得到如表中所示的新的最优解。Cj54800bCBXBx1x2x3x4x54x201-22-1405x1103-1120z001-3-1-2604x22/31

27、04/3-1/3160/35x31/301-1/31/320/3z00-4-3-1-740/3即新的最优解为X*=（0，160/3，20/3）T。2、 max z=5x1+4x2  x1 +3x2 902x1  + x2 80  x1  + x2 45x1、x2，x30其初始单纯形表和最优单纯形表分别如表，试分析使最优基不变的b3的变化范围。（初始单纯形表）Cj54000bCBXBx1x2x3x4x50x313100900x421010800x51100145z540000（最优单纯形表）Cj54000bCBXBx

28、1x2x3x4x50x30012-5255x11001-1354x2010-1210z000-1-3-215解：由表可知，当B=（p3，p1，p2）时，有 当下式成立时，最优基不变。即 255b30，35b30，10+b30解不等式有 5b35此外，以B-1的第三列各元素去除最优单纯形表中右端常数项对应各列，用公式可直接求出b3，即同样可得 5b35因此，不影响最优基的b3的变化范围是40，50。运输问题1、用小元素法求下面运输问题（见表）的初始可行解，检验解的最优性，如果不是最优解，改进成最优解。销地产地B1B2B3B4B5产量A16948520A2106128730A365920940A4

29、213614360销量2515354530解：最小元素法20x143015101525530OBJ955 ß运费表 (检验数zij |wij )06094(15)8154-710-76-3128-67-356592069922136171436-4-4011-3迭代后的分配表xij 51530152525530OBJ850运费表 (检验数zij |wij )0609481540100641281745659132069922136101436-4-404-3答：x13=5, x14=15, x24=30, x32=15, x33=25, x41=25, x43=5, x45=30,

30、OBJ=850。2、运输问题的产销平衡表如下。用最小元素法给出运输问题的初始可行解，检验解的最优性，如果不是最优解，改进成最优解。 销地产地B1B2B3B4产量A1A2A3317119432101085749销量3656解：第一部，最小元素法 销地产地B1B2B3B4产量A1A2A333 171196 44 31 2103 1083 57 3 04 1 09 3销量36 05 4 06 3初始基可行解，x13 = 4, x14 = 3, x21 = 3, x23 = 1, x32 = 6, x34 = 5。运输费用为：Z=3×4+10×3 +1×3 +2×

31、;1+4×6+5×3=12+30+3+2+24+15=86第二步，解的最优性检验销地产地B1B2B3B4A131143310A2319128A37641035令自由变量u1 = 0 ，得：u1 = 0，v3 = 3，v4 = 10，u3 = -5，v2 = 9，u2 = -1，v1 = 2，则：11=C11 - (u1 + v1) = 3 ( 0 + 2 ) = 112=C12 - (u1 + v2) = 11 ( 0 + 9 ) = 222=C22 - (u2 + v2) = 9 ( -1 + 9 ) = 124=C24 - (u2 + v4) = 8 ( -1 + 10

32、 ) = -131=C31 - (u3 + v1) = 7 ( -5 + 2 ) = 1033=C33 - (u3 + v3) = 10 ( -5 + 3 ) = 12第三步，解的改进见表1中非基变量x24所在的闭回路，调整量为 = min3,1 = 1。调整过程见表2：销地产地B1B2B3B4A13114+133-110A23191-120+18A37641035销地产地B1B2B3B4A131153210A2319218A37641035由于非基变量的检验系数都大于等于零，因此该方案是最优方案，最优解为：x13 = 5，x14 = 2，x21 = 3，x24 = 1，x32 = 6，x34

33、 = 3，总运费为：3、用小元素法求下面运输问题（见表）的初始可行解，检验解的最优性，如果不是最优解，改进成最优解。 销 地产地B1B2B3B4产量A1376450A2243320A3838930销量40201525100100解：先用最小元素法求解。 销 地产地B1B2B3B4产量A120×525503764A220×××202433A3×2010×308389销量40201525用位势法对基可行解进行最优性检验。销 地产地B1B2B3B4产量行位势A12052550u13764A22020u22433A3201030u38389销

34、量40201525列位势v1v2v3v4取u1=0，解上述方程组得u1=0， u2=1， u3=2，v1=3，v2=1，v3=6，v4=4各非基变量的检验数为12 =c12（u1+v2）=7（0+1）= 4>022 =c22（u2+v2）=4（1+1）= 2>023 =c23（u2+v3）=3（1+6）= 2<024 =c24（u2+v4）=3（1+4）= 031 =c31（u3+v1）=8（2+3）= 3>034 =c34（u3+v4）=9（2+4）= 3>0由于23 =2<0，故表中基可行解不是最优解，并以x23为第一个顶点作闭回路，如下销 地产地B1B2B3B4产量A120525503764A220x23202433A32010308389销量40201525该闭回路上，偶数顶点上的基变量最小值为5，以该调整量进行调整得到如表销 地产地B1B2B3B4产量A12525503764A21552