运筹学_第1章_线性规划习题.doc

第一章 线性规划习题1.1 （生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？表11 产 品 单耗资 源甲乙资源限制ABC120111300kg400kg250kg单位产品利润（元/件）50100解：设x1、x2分别代表甲、乙两种产品的生产数量（件），z表示公司总利润。依题意，问题可转换成求变量x1、x2的值，使总利润最大，即max z=50x1+100x2且称z=50x1+100x2为目标函数。同时满足甲、乙两种产品所消耗的A、B、C三种资源的数量不能超过它们的限量，即可分别表示为 x1 + x23002x1 + x2400x2250且称上述三式为约束条件。此外，一般实际问题都要满足非负条件，即x10、x20。这样有max z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x20工厂1工厂2200万m3500万m3图11习题1.2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的总费用最小。解：设x1、x2分别代表工厂1和工厂2处理污水的数量(万m3)。则问题的目标可描述为min z=1000x1+800x2约束条件有第一段河流（工厂1工厂2之间）环保要求 (2x1)/500 0.2%第二段河流（工厂2以下河段）环保要求0.8(2x1) +(1.4x2)/7000.2%此外有x12； x21.4化简得到min z=1000x1+800x2x1 10.8x1 + x2 1.6x1 2x21.4x1、x20x2z*=50x1+100x2=27500x1 + x2300x1x22502x1 + x2400z1=50x1+100x2=0BOACD图12z2=14000习题1.3 max z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x20用图解法求解。解：如图12中的B点，即问题的最优解为x1*=50；x2*=250，相应的最优值为z*=27500，且该问题有唯一最优解。111z=42z=6OA图13习题1.4 max z=2x1+2x2x1x2 1x1 + 2x2 0x1、x2 0用图解法求解。解：图13中阴影部分就是该问题的可行域，显然该问题的可行域是无界的。两条虚线为目标函数等值线，它们对应的目标值分别为2和4，可以看出，目标函数等值线向右移动，问题的目标值会增大。但由于可行域无界，目标函数可以增大到无穷。称这种情况为无界解或无最优解。习题1.5 化下列线性规划为标准形 max z=2x1+2x24x3x1 + 3x23x3 30x1 + 2x24x380x1、x20，x3无限制解：按照上述方法处理，得该线性规划问题的标准形为 max z=2x1+2x24x31+4x32x1 + 3x23x31 + 3x32x4 = 30x1 + 2x24x31 + 4x32 + x5 = 80x1、x2，x31，x32，x4，x5 0例1.6 用单纯形法求解max z=50x1+100x2x1 + x23002x1 + x2400x2250x1、x20解：首先将问题化为标准形式，然后将整个计算过程列在一个表中（表19）。 表19Cj50100000b CBXB x1 x2x3x4x5 0x311100300 0x421010400 0x501001250z501000000 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*=27500例1.7 用单纯形法求解max z=2x1+x2x1 + x252x15x210x1、x20解：用单纯形表实现如表110 表110Cj2100b CBXB x1x2x3x4 0x3-11105 0x42-5011010/4(min)z21000 0x30-3/211/210 2x11-5/201/25z060-1102=6 0，且p20，故该线性规划有无界解（无最优解）。例1.8 用单纯形法（大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 = 114x1 + x2 +2x3 x5 + x6 = 32x1 + x3 +x7 = 1x1、x2、x3、x4、x5、x6、x70用单纯形进行计算，计算过程见表111。 表111Cj3-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-123x11001/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*=2例1.9 用单纯形法（大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用单纯形法计算，过程列于表112中。从表中可以看出，虽