第一章 线性规划

(Linear Programming, LP)概概 述述 线性规划问题的提出最早是线性规划问题的提出最早是19391939年由前苏联数年由前苏联数学家康托洛维奇在研究铁路运输的组织问题、学家康托洛维奇在研究铁路运输的组织问题、工业生产的管理问题时提出来的。工业生产的管理问题时提出来的。 19471947年，美国学者丹西格（年，美国学者丹西格（G.B.DantzigG.B.Dantzig）提）提出了线性规划问题的单纯形方法。出了线性规划问题的单纯形方法。 线性规划理论最为成熟、应用最为广泛线性规划理论最为成熟、应用最为广泛 第一节 线性规划问题及其数学模型一、问题提出一、问题提出（生产计划问题）某企业利用（生产计划问题）某企业利用A、B、C三种资源，三种资源，在计划期内生产甲、乙两种产品，已知生产单位产在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？何安排生产计划使企业利润最大？ 产产 品品资资 源源甲甲乙乙资源限制资源限制ABC120111300kg400kg250kg单位产品利润单位产品利润(元元/件件)50100 决策变量决策变量：x1、x2分别代表甲、乙两分别代表甲、乙两种产品的生产数量。种产品的生产数量。目标函数：目标函数：max z=50 x1+100 x2约束条件：约束条件： x1 + x2300 2x1 + x2400 x2250即有：即有： max z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20称之为上述问题的数学模型。称之为上述问题的数学模型。 例例2 靠近某河流有两个化工厂，流经第一化工厂的河流靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天流量为每天500万万m3，在两个工厂之间有一条流量为，在两个工厂之间有一条流量为200万万m3的支流。两化工厂每天排放某种有害物质的工业污的支流。两化工厂每天排放某种有害物质的工业污水分别为水分别为2万万m3和和1.4万万m3。从第一化工厂排出的工业污。从第一化工厂排出的工业污水流到第二化工厂以前，有水流到第二化工厂以前，有20%可以自然净化。环保要可以自然净化。环保要求河流中工业污水含量不能大于求河流中工业污水含量不能大于0.2%。两化工厂处理工。两化工厂处理工业污水的成本分别为业污水的成本分别为1000元元/万万m3和和800元元/万万m3。现在。现在要问在满足环保要求的条件下，每厂各应处理多少工业要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小污水，使这两个工厂处理工业污水的费用最小.工厂工厂1工厂工厂2200万万m3500万万m3 决策变量决策变量：x1、x2分别代表工厂分别代表工厂1和工厂和工厂2处处理污水的数量理污水的数量(万万m3)。 则目标函数：则目标函数：min z=1000 x1+800 x2 约束条件：约束条件：第一段河流（工厂第一段河流（工厂1工厂工厂2之间）：之间）： (2x1)/500 0.2%第二段河流：第二段河流： 0.8(2x1) +(1.4x2)/7000.2%此外有：此外有： x12； x21.4 化简有：化简有： min z=1000 x1+800 x2 x1 1 0.8x1 + x2 1.6 x1 2 x21.4 x1、x20称之为上述问题的数学模型。称之为上述问题的数学模型。 从上述两个例子，我们可以总结出线性规划从上述两个例子，我们可以总结出线性规划的数学模型的一般形式。的数学模型的一般形式。max(min) z=c1x1+c2x2+cnxn 目标函数目标函数 a11x1+a12x2+a1nxn= (,) b1 a21x1+a22x2+a2nxn= (,) b2 约束条件约束条件 am1x1+am2x2+amnxn= (,) bm x1，x2，xn0 模型特点：目标函数模型特点：目标函数(Objective function)与与约束条件约束条件(Constraint)均为线性的；目标函均为线性的；目标函数实现极大化或极小化。数实现极大化或极小化。 第二节第二节 线性规划图解法线性规划图解法 (Graphical Solution)一、基本概念一、基本概念 可行解可行解(Feasible Solution)任一满足约束条任一满足约束条件的一组决策变量的数值；件的一组决策变量的数值； 可行域可行域(Feasible Region)所有可行解组成所有可行解组成的集合，也称为可行解集；的集合，也称为可行解集； 目标函数等值线目标函数等值线(Objective function line)为于同一直线上的点，具有相同的目标函数值；为于同一直线上的点，具有相同的目标函数值；二、图解法步骤二、图解法步骤(Procedure)（1）画出线性规划问题的可行域；）画出线性规划问题的可行域；（2）画出两条目标函数等值线；）画出两条目标函数等值线；（3）平行移动目标函数等值线，使目标函数在可）平行移动目标函数等值线，使目标函数在可行域范围内达到最优。行域范围内达到最优。三、图解法举例三、图解法举例例例1 max Z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20 x2x1z* =27500z1=50 x1+100 x2=0BOACDz2=14000该问题有唯一最优解该问题有唯一最优解x1=50=50；x2=250=250 x1 + x23002x1 + x2400 x2250例例2 max Z=50 x1+50 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20 x2x1z1=50 x1+50 x2=0B点和点和C点所代表的坐点所代表的坐标同时为最优解，即该标同时为最优解，即该问题有问题有无穷多最优解无穷多最优解BOACDx1 + x23002x1 + x2400 x2250max Z=50 x1+100 x2z* =27500z2=15000例例3 max z =x1+x2 x1x2 1 x1 + 2x20 x1、x20 问题有无界解问题有无界解 (unbounded)例例4 min z =x1+x2 x1x2 1 x1 + 2x20 x1、x20 有唯一最优解有唯一最优解111z=32z=5OA2x1xx1x2 1x1 + 2x20例例4 max z =x1+x2 x1 + 2x21 x1 + x22 x1、x20 问题无可行解问题无可行解 (no feasible solution)直直 观观 结结 论论1) 可行域可以是个凸多边形，可能无界，也可可行域可以是个凸多边形，可能无界，也可能为空；能为空；2) 若线性规划问题的最优解存在，它一定可以若线性规划问题的最优解存在，它一定可以在可行域的某一个顶点上得到；在可行域的某一个顶点上得到；3) 若在两个顶点上同时得到最优解，则该两点若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即连线上的所有点都是最优解，即LP有无穷多有无穷多最优解；最优解；4) 若可行域非空有界，则一定有最优解。若可行域非空有界，则一定有最优解。四、线性规划问题的标准形式四、线性规划问题的标准形式(Standard form) 规定如下形式的线性规划数学模型为规定如下形式的线性规划数学模型为LP标准形式。标准形式。max z=c1x1+c2x2+cnxn 目标函数目标函数 a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 约束条件约束条件 am1x1+am2x2+amnxn= bm x1，x2，xn0 特点：特点：Zmax；约束条件为等号；变量非负；约束条件为等号；变量非负；右端常数项大等于零。右端常数项大等于零。上述标准形式的线性规划模型还可写成如下一些形式上述标准形式的线性规划模型还可写成如下一些形式: :(1) (2) njjj=1nijjij=1jmaxz =c xa x = bi = 1, . ,mx0 j = 1, . ,n0njjj=1jm axz = cXp x= bxj = 1, . ,n (3) (5)0njjj=1jmaxz = cXp x = bxj = 1, . ,nm axz = cXAX = bX0Xmaxz =cX R = X AX =b,X0R R (4) 五、化非标准形为标准形五、化非标准形为标准形（1）若）若min f=cX 此时可令：此时可令：z =f，则，则max z=min f =cX，这样处理所得最优解不变；这样处理所得最优解不变；举例：举例： min z =x1x2 2x1 + x22 x1 + x21 x1、x20 max f =x1+ x2z=-1/2f=0f=1/2z=0f=-z=8/3（1/3，4/3）(2)约束条件为约束条件为“”时，时，aijxjbi aijxj + xn+i = bi xn+i 松弛变量松弛变量(slack variable)；(3)约束条件为约束条件为“”时，时，aijxj bi aijxj xn+i = bi xn+i 过剩变量过剩变量(surplus variable)；这样处理所得最优解不变这样处理所得最优解不变；max z =x1+10 x2 x1 + 2x2100 x1、x20 max z =x1+10 x2 x1 + 2x2 + x3=100 x1、x200（4）若）若xk为无限制，为无限制， 则令则令xk=xk1xk2，其中其中xk1、xk20（5）若）若bi 0举例举例: 化下列线性规划为标准形化下列线性规划为标准形 max z=2x1+2x24x3 x1 + 3x23x3 30 x1 + 2x24x380 x1、x20，x3无限制无限制max z=2x1+2x24x3+4x3” x1 + 3x23x3+3x3” x4 = 30 x1 + 2x24x3+ 4x3” + x5 = 80 x1、x2 、x3、x3” 、x4、x5 0第三节第三节 线性规划问题解的性质线性规划问题解的性质 (Properties of Solution of LP) 一、线性规划问题的基本概念一、线性规划问题的基本概念(concepts)对于标准形式的线性规划：对于标准形式的线性规划： max z=cX （a） AX=b X0 （b）1.可行解可行解(feasible solution)满足约束条件（满足约束条件（b）的）的点点X=（x1，x2，xn）T称为该称为该LP的一个可行解；的一个可行解；2.最优解最优解(optimal solution)使目标函数值达到最大使目标函数值达到最大的可行解的可行解3基基、基变量、非基变量、基变量、非基变量 (base, basic variable, nonbasic variable) 设约束方程的系数矩阵设约束方程的系数矩阵A中，有中，有m个线性无关的列向量，个线性无关的列向量， 且设且设 B=（P1，P2，Pm）线性无关，线性无关，则称则称B为为该该LP的一个基；的一个基； 相应的相应的 P1，P2，Pm为基向量为基向量； 与之对应的变量与之对应的变量 x1，x2，xm基变量基变量，记为：，记为：XB= （x1，x2，xm）T ； 其余的向量为其余的向量为非基向量非基向量，记为：，记为：N=（Pm+1，Pm+2，Pn）； 其余的变量为其余的变量为非基变量非基变量 ，记为：，记为：XN=（xm+1，xm+2，xn）T；4 4基本解基本解 ( (basic solutionbasic solution) )将将AX=b改写改写 （B，N）（）（XB，XN）T=b有：有： BXB=bNXN令令 XN=0得到得到 BXB=b 线性方程组。线性方程组。由于由于B中各列向量线性无关，因此解此方程组有唯一解中各列向量线性无关，因此解此方程组有唯一解即：即： XB= （x10，x20，xm0）T于是得到于是得到AX=b的一个确定的解：的一个确定的解： X0=（XB，XN）T =（x10，x20，xm0，0，0，0）T称称X0为该线性规划对应与基为该线性规划对应与基B的一个的一个基本解基本解。同样，在同样，在A中任选中任选m个线性无关的列向量都可以组成一个基，个线性无关的列向量都可以组成一个基，对应基一个基本解。对于一个对应基一个基本解。对于一个LP最多有多少呢？从最多有多少呢？从n个中个中选选m个进行组合，即：个进行组合，即：Cnm=n！/（nm）！）！m！因此，基本解是有限的。因此，基本解是有限的。举例：找出下列举例：找出下列LP所有的基及其对应的基本解所有的基及其对应的基本解 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20解：化为标准型解：化为标准型 max z=6x1+4x2+0 x3+0 x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0ABCDEOx1x22x1+3x2 =1004x1 + 2x2 =120基本解如下表基本解如下表 基基基本解基本解可行可行否否目标值目标值对应图对应图中的点中的点B1=(P1，P2)B2=(P1，P3)B3=(P1，P4)B4=(P2，P3)B5=(P2，P4)B6=(P3，P4)X1=(20，20，0，0)TX2=(30，0，40，0)TX3=(50，0，0，80)TX4=(0，60，80，0)TX5=(0，100/3，0，160/3)TX6=(0，0，100，120)T 200180400/30BCDEAO二、线性规划的基本定理二、线性规划的基本定理(Theorems)1.定义定义 凸集凸集设设K是是n维欧氏空间的一个点集，若任意两点维欧氏空间的一个点集，若任意两点X(1)K，X(2)K的连线上所有的点的连线上所有的点X=X（1）+（1）X（2）K，（01），则称，则称K为凸集。为凸集。2.定理定理1 若线性规划存在可行域，则其可行域若线性规划存在可行域，则其可行域R=X|AX=b，X0是凸集。是凸集。3.定理定理2 线性规划问题的可行解线性规划问题的可行解X=（x1，x2，xn）T为基可行为基可行解的充要条件是：解的充要条件是：X的非零分量所对应的系数列向量是线性无关的非零分量所对应的系数列向量是线性无关的。的。4.定理定理3 如果线性规划有可行解，则一定有基可行解。如果线性规划有可行解，则一定有基可行解。5.定理定理4 线性规划问题的基可行解对应于可行域的顶点。线性规划问题的基可行解对应于可行域的顶点。6.定理定理5 若线性规划问题的可行域非空有界，则线性规划问题的最若线性规划问题的可行域非空有界，则线性规划问题的最优解一定可以在其可行域的某个顶点上得到；优解一定可以在其可行域的某个顶点上得到；第四节第四节 单纯形法单纯形法 (simplex method) 基本思想基本思想：在有限的基可行解中寻找最优解。即，从初始基：在有限的基可行解中寻找最优解。即，从初始基可行解出发，转换到另一个基可行解，使目标值增大，直到达到可行解出发，转换到另一个基可行解，使目标值增大，直到达到最优解，或判断出无最优解为止。最优解，或判断出无最优解为止。一、引例一、引例 用单纯形方法求解下列线性规划用单纯形方法求解下列线性规划 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20解：化为标准型解：化为标准型 max z=6x1+4x2+0 x3+0 x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0（1）找初始可行基：）找初始可行基：B1=（P3，P4）现成的初始可行基；现成的初始可行基；此时，此时， XB=（x3，x4）T，XN=（x1，x2）T用用XN表示表示Z和和XB有：有： max z=6x1+4x2 x3 =1002x13x2 +x4 =1204x12x2令令 XN=(0,0)T有有 XB=(100,120)T则有：则有： X（1）=（0，0，100，120）T为对应于基为对应于基B1的基可行解。的基可行解。问：问： X（1）是否最优呢？是否最优呢？否否因为：因为： x1和和x2在目标函数中的系数为正，当在目标函数中的系数为正，当x1，z；x2，z。且：且： 称非基变量在目标函数中的系数为称非基变量在目标函数中的系数为检验数检验数。（2）寻找可行基）寻找可行基B2，使其对应的基可行解，使其对应的基可行解X（2）能使目标函数值增加。能使目标函数值增加。选：选： x10则有：则有： X（2）=（x1，0，x3，x4）T要使为要使为X（2）基可行解，基可行解，x3，x4中必有一个为零，而另一个大等于零。中必有一个为零，而另一个大等于零。只要取只要取 x1=min100/2，120/4=30就有就有 x3=40，x4=0这样这样 X（2）=（30，0，40，0）T因为因为 P1，P3线性无关，因此，线性无关，因此，B2=（P1，P3）为一个基为一个基而而 X（2）为对应于为对应于B2的基可行解的基可行解此时此时 XB=（x1，x3）T，XN=（x2，x4）T用用XN表示表示Z和和XB有：有： max z=180+2x2（3/2）x4 x1 = 30（1/2）x2（1/4）x4 x3 = 40 2 x2 +（1/2）x4问：问： X（2）是否最优呢？是否最优呢？否否因为：因为： x2在目标函数中的系数为正，当在目标函数中的系数为正，当x2，z。（3）寻找可行基）寻找可行基B3，使其对应的基可行解，使其对应的基可行解X（3）能使目标函数值增加。能使目标函数值增加。选：选： x20则有：则有： X（3）=（x1，x2，x3，0）T要使为要使为X（3）基可行解，基可行解，x1，x3中必有一个为零，而另一个大等于零。中必有一个为零，而另一个大等于零。只要取只要取 x2=min30/（1/2），），40/2=20就有就有 x1=20，x3=0这样这样 X（3）=（20，20，0，0）T因为因为 P1，P2线性无关，因此，线性无关，因此，B3=（P1，P2）为一个基为一个基而而 X（3）为对应于为对应于B3的基可行解的基可行解此时此时 XB=（x1，x2）T，XN=（x3，x4）T用用XN表示表示Z和和XB有：有： max z=2001/2）x3（5/4）x4 x1 =20 +（1/4）x3 （3/8）x4 x2 =20 （1/2）x3 +（1/4）x4问：问： X（3）是否最优呢？是否最优呢？是，是，求解过程求解过程：从引例可以总结出求解过程：（：从引例可以总结出求解过程：（1）找出初始基及其基可行）找出初始基及其基可行解；（解；（2）判断是否为最优解，是停止，否则转下一步；（）判断是否为最优解，是停止，否则转下一步；（3）转换可）转换可行基，并求出相应的基可行解，使目标函数值有所改进，转（行基，并求出相应的基可行解，使目标函数值有所改进，转（2）。）。二、单纯形方法二、单纯形方法 1检验数检验数( evaluation index)检验数检验数用非基变量表示目标函数后，非基变量在目标函数中的系数用非基变量表示目标函数后，非基变量在目标函数中的系数 设有标准形式的线性规划问题：设有标准形式的线性规划问题：max z=cX；AX=b，X0； 现假定现假定 A中存在一可行基中存在一可行基B 又设又设 B=（P1，P2，Pm）；且；且B为单位阵为单位阵 这样这样 AX=b可以描述成如下形式，也就是用非基变量表示基变量可以描述成如下形式，也就是用非基变量表示基变量 x1 + a1,m+1xm+1 + + a1nxn=b1 x2 + a2,m+1xm+1 + + a2nxn=b2 xm + am,m+1xm+1 + + amnxn=bm即即 从上述约束方程中可以得到对应于基从上述约束方程中可以得到对应于基B的基可行解的基可行解 X=（b1，b2，bm，0，0）Tniiijjj=m+1x = b -a xi = 1,.,m 用非基变量表示目标函数有：用非基变量表示目标函数有： 令令 有有 式中式中 j为基可行解为基可行解X的检验数。的检验数。更一般性：更一般性： nmnjjiijjj=1i=1j=m+1z=cx =cx +cxmnniiijjjji=1j=m+1j=m+1mnmiijiijji=1j=m+1i=1=c (b -a x )+c x=c b +(c -c a )xmm0iijjiiji=1i=1z =cb; =c -c an0jjj = m + 1z = z+x0iijjiijiIiIz =cb; =c -ca0jjjJz=z +x2 2最优性检验最优性检验(optimality testing) 判别定理判别定理1：设：设X为线性规划的一个基可行解，且为线性规划的一个基可行解，且对于一切对于一切jJ（J为非基变量的下标集）有为非基变量的下标集）有j0，则则X为线性规划的最优解；为线性规划的最优解； 判别定理判别定理2：设：设X为线性规划的一个基可行解，且为线性规划的一个基可行解，且对于一切对于一切jJ（J为非基变量的下标集）有为非基变量的下标集）有j0，同时有某个非基变量的检验数同时有某个非基变量的检验数k=0（kJ），则，则该线性规划有无穷多最优解；该线性规划有无穷多最优解； 判别定理判别定理3：设：设X为线性规划的一个基可行解，若为线性规划的一个基可行解，若有有k0（kJ），且，且Pk0，则该线性规划问题具，则该线性规划问题具有无界解（无最优解）。有无界解（无最优解）。3 3 单纯形表单纯形表(simplex tableau)对于线性规划：对于线性规划：max z=z0 + m+1xm+1 + + nxn x1 + a1,m+1xm+1 + + a1nxn=b1 x2 + a2,m+1xm+1 + + a2nxn=b2 xm + am,m+1xm+1 + + amnxn=bm x1，x2，xn0列如下单纯形表：列如下单纯形表：CjC1C2CmCm+1CnbCBXBx1x2xmxm+1xnc1x1100a1,m+1a1nb1c2x2010a2,m+1a2nb2cmxm001am,m+1amnbm -z0000m+1n-z0 单纯形表的说明与功能：单纯形表的说明与功能：（1）一个基对应一个单纯形表，且单纯形表中必须有一个初始单位）一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基。基。（2）从单纯表中，可立即得到一个基可行解，如上表中：）从单纯表中，可立即得到一个基可行解，如上表中： X=（b1，b2，bm，0，0）T为基可行解。为基可行解。（3）很容易计算检验数，并可判别上述基可行解是否为最优解或线）很容易计算检验数，并可判别上述基可行解是否为最优解或线性规划问题无最优解。性规划问题无最优解。 4. 4. 单纯形法计算步骤单纯形法计算步骤（1）找出初始可行基，建立初始单纯形表；）找出初始可行基，建立初始单纯形表；（2）计算检验数，若对于一切）计算检验数，若对于一切jJ有有j0，则已得到线性规划的最则已得到线性规划的最优解，可停止计算，否则转下一步；优解，可停止计算，否则转下一步；（3）若有）若有k0（kJ），），且且Pk0，则该线性规划问题具有无界解，则该线性规划问题具有无界解（无最优解），停止计算，否则转下一步；（无最优解），停止计算，否则转下一步；（4）根据）根据maxj|j0=k，确定确定xk为换入变量；为换入变量； 按按规则确定换出变量，即规则确定换出变量，即 =bi/aik|aik0=bs/ask，对应的，对应的xs为换出变量，转下一步；为换出变量，转下一步；（5）以）以ask为主元素进行迭代，得新的单纯形表，转（为主元素进行迭代，得新的单纯形表，转（2）三、单纯形法解题举例三、单纯形法解题举例 例例1：用单纯形法求解：用单纯形法求解 max z=6x1+4x2 2x1 + 3x2100 4x1 + 2x2120 x1、x20 解：化为标准型解：化为标准型 max z=6x1+4x2+0 x3+0 x4 2x1 + 3x2 + x3 =100 4x1 + 2x2 +x4 =120 x1、x2，x3，x4 0找初始可行基：找初始可行基：B1=（P3，P4）现成的初始可行基；现成的初始可行基； 从表中有：从表中有：X（1）=（0，0，100，120）T为对应于为对应于基基B1的基可行解，显然不是最优解；的基可行解，显然不是最优解； 根据根据maxj|j0=1，确定，确定x1为换入变量；为换入变量； 按按规则确定换出变量，即：规则确定换出变量，即：=bi/aik|aik0=120/4，对应的，对应的x4为换出变量；为换出变量；Cj6 4 0 0b CBXBx1 x2 x3 x4 0 0 x3x4 2 3 1 04 2 0 1100120100/2120/4(min) z6 4 0 00 列初始单纯形表列初始单纯形表 以以4为主元素进行迭代，得新的单纯形表：为主元素进行迭代，得新的单纯形表： 从表中有：从表中有：X（2）=（30，0，40，0）T为对应于基为对应于基B2的基可行解，显然不是最优解；的基可行解，显然不是最优解； 根据根据maxj|j0=2，确定确定x2为换入变量；为换入变量； 按按规则确定换出变量，即：规则确定换出变量，即：=bi/aik|aik0=40/2，对应的，对应的x3为换出变量；为换出变量； Cj CB 0 6XBx3x1Z6 x10104 x221/210 x31000 x4-1/21/4-3/8b 403018040/230/(1/2) 表中表中j0，j=1，4， 因此得最优解：因此得最优解：X*=（20，20，0，0）T，Z*=200Cj6400bCBXBx1x2x3x446x1x2011/2-1/410-1/4 3/82020Z00-1/2-5/4200以以2为主元素进行迭代，得新的单纯形表：为主元素进行迭代，得新的单纯形表：将上述计算列在一个表中为：将上述计算列在一个表中为： Cj6400b CB XB x1x2x3x4 0 x3 2310100100/2 0 x4 4201120120/4(min) z 64000 0 x3021-1/24040/2(min) 6 x111/201/43030/(1/2) Z 010-3/2180 4 x2011/2-1/420 6 x110-1/43/820 Z00 -1/2-5/4200例例2：用单纯形法求解：用单纯形法求解 max z=50 x1+100 x2 x1 + x2300 2x1 + x2400 x2250 x1、x20Cj50100000b CBXB x1 x2X3x4x5 0 x311100300300/1 0 x421010400400/1 0 x501001250250/1(min) z501000000 0 x31010-15050/1(min) 0 x42001-1150150/2 100 x201001250 Z50000-10025000 50 x11010-1500 0 x400-21150 100 x2010-01250 Z00-500-5027500 例例3：用单纯形法求解：用单纯形法求解 max z=2x1+x2 x1 + x25 2x15x210 x1、x20 2=6 0，且，且P20，故该线性规划有无界解。，故该线性规划有无界解。Cj2100b CBXB x1x2x3x4 0 x3-11105100/2 0 x42-50110120/4(min) z21000 0 x30-3/211/21040/2(min) 2x11-5/201/2530/(1/2) Z060-110 例例4：用单纯形法求解：用单纯形法求解 max z=6x1+2x2+10 x3+8x4 5x1 + 6x24x34x420 3x13x2 +2x3 + 8x425 4x12x2 + x3 + 3x410 x1、x2、x3、x407=340, p70,故该故该LP有无解解有无解解Cj62108000bCBXB x1x2x3x4x5x6x70 x556-4-4100200 x63-328010250 x74-21300110 z6210800000 x521-208104600 x6-510201-2510 x34-21300110 Z-34220-2200-101000 x5110012120702x2-510201-2510 x3-601702-320 Z7600-660-2234210四、极小化问题四、极小化问题(Minimization Problem) 若标准形式的线性规划问题的目标函数是极小化形式，则问题若标准形式的线性规划问题的目标函数是极小化形式，则问题的判别准则就会有所改变。这样三个判别定理如下的判别准则就会有所改变。这样三个判别定理如下： 判别定理判别定理1：设：设X为线性规划的一个基可行解，且对于一切为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有为非基变量的下标集）有j 0，则，则X为线性规划的最优解；为线性规划的最优解； 判别定理判别定理2：设：设X为线性规划的一个基可行解，且对于一切为线性规划的一个基可行解，且对于一切jJ（J为非基变量的下标集）有为非基变量的下标集）有j 0，同时有某个非基变量的检，同时有某个非基变量的检验数验数k=0（kJ），则该线性规划有无穷多最优解；，则该线性规划有无穷多最优解； 判别定理判别定理3：设：设X为线性规划的一个基可行解，若有为线性规划的一个基可行解，若有k 0（kJ），且，且Pk0，则该线性规划问题具有无界解（无最优，则该线性规划问题具有无界解（无最优解）。解）。 上述单纯形法的基础是线性规划问题有初始基可行上述单纯形法的基础是线性规划问题有初始基可行解。有些线性规划问题化为标准形式以后，就存在解。有些线性规划问题化为标准形式以后，就存在初始可行基，如约束条件全部为初始可行基，如约束条件全部为“”的线性规划的线性规划问题。对于标准形式的线性规划问题，若约束方程问题。对于标准形式的线性规划问题，若约束方程系数矩阵中不存在现成的初始可行基，则不能简单系数矩阵中不存在现成的初始可行基，则不能简单的用上述单纯形法，而通常采用所谓的人工变量法。的用上述单纯形法，而通常采用所谓的人工变量法。人工变量法一般有大人工变量法一般有大M M法和两阶段法。法和两阶段法。五、人工变量法五、人工变量法(Artificial Variable Method)（一）大（一）大M法法(Big M method) 对于标准形式的线性规划问题（问题对于标准形式的线性规划问题（问题A） max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 am1x1+am2x2+amnxn= bm x1，x2，xn0 若其约束方程的系数矩阵中不存在现成的初始可行基，则引入所谓的若其约束方程的系数矩阵中不存在现成的初始可行基，则引入所谓的人工变量xn+1，xn+m构造如下形式的线性规划问题（问题构造如下形式的线性规划问题（问题B） max z=c1x1+c2x2+cnxnMxn+1Mxn+m a11x1+a12x2+a1nxn+xn+1 = b1 a21x1+a22x2+a2nxn +xn+2 = b2 am1x1+am2x2+amnxn +xn+m = bm x1，x2，xn，xn+1，xn+m0 问题问题B中中M为任意大的正数。显然问题为任意大的正数。显然问题B存在现成的单位基，存在现成的单位基，且初始基可行解中，以人工变量为基变量。且初始基可行解中，以人工变量为基变量。 关于问题关于问题B的几点结论：的几点结论： （1）问题）问题B要实现极大化，必须将人工变量从基变量中换出，要实现极大化，必须将人工变量从基变量中换出，否则目标函数不可能实现极大化；否则目标函数不可能实现极大化； （2）若在求解问题）若在求解问题B的过程中，已将人工变量从基变量中换出，的过程中，已将人工变量从基变量中换出，则已得到问题则已得到问题A的一个基可行解，可继续求解，以获得问题的一个基可行解，可继续求解，以获得问题A的最优解或判别问题的最优解或判别问题A无最优解；无最优解； （3）若求解问题）若求解问题B已得到最优解，但最优解的基变量中含有不已得到最优解，但最优解的基变量中含有不为零人工变量，则问题为零人工变量，则问题A无可行解；无可行解； （4）若求解问题）若求解问题B已得到最优解，且最优解的基变量中不含有已得到最优解，且最优解的基变量中不含有人工变量，则问题人工变量，则问题B的最优解就是问题的最优解就是问题A的最优解。的最优解。 例：用单纯形法（大例：用单纯形法（大M法）求解法）求解 max z=3x12x2x3 x1 2x2 + x3 11 4x1 + x2 +2x3 3 2x1 x3 = 1 x1、x2、x30 解：化为标准形式，并引入人工变量，构造如下模型：解：化为标准形式，并引入人工变量，构造如下模型： max z=3x12x2x3Mx6Mx7 x12x2 + x3 + x4 = 11 4x1 + x2 +2x3 x5 + x6 = 3 2x1 x3 +x7 = 1 x1、x2、x30 列表计算：列表计算：Cj3-1-100-M-Mb CBXB x1 x2x3x4x5x6x70 x41-21100011-Mx6-4120-1103-Mx7-20100011 z3-6M-1+M-1+3M0-M00 0 x43-20100-110-Mx60100-11-21-1x3-20100011 Z1-1+M00-M0-3M+1 0 x43001-22-512-1x20100-11-21-1x3-20100011 z1000-1-M+1-M-1 3x11001/3-2/32/3-5/34-1x20100-1121-1x30012/3-4/34/3-7/39 Z000-1/3-1/3-M+1/3-M+2/32（二）两阶段法（二）两阶段法对于标准形式的线性规划问题（问题对于标准形式的线性规划问题（问题A） max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn= b1 a21x1+a22x2+a2nxn= b2 am1x1+am2x2+amnxn= bm x1，x2，xn0若其约束方程的系数矩阵中不存在现成的初始可行基，则引入若其约束方程的系数矩阵中不存在现成的初始可行基，则引入所谓的人工变量所谓的人工变量xn+1，xn+m构造如下辅助线性规划问题构造如下辅助线性规划问题（问题（问题C） min w =xn+1 + + xn+m a11x1+a12x2+a1nxn+xn+1 = b1 a21x1+a22x2+a2nxn +xn+2 = b2 am1x1+am2x2+amnxn +xn+m = bm x1，x2，xn，xn+1，xn+m0 关于问题关于问题C的几点结论的几点结论：（1）由于问题）由于问题C为极小化问题，且目标函数有下界，因此问题为极小化问题，且目标函数有下界，因此问题C肯定有最优解；肯定有最优解；（2）求解问题）求解问题C已得到其最优解，若问题已得到其最优解，若问题C最优解所对应目标最优解所对应目标函数值函数值w0，则原问题，则原问题A无可行解，若问题无可行解，若问题C所对应目标函数所对应目标函数值值w =0，则已得到原问题，则已得到原问题A的一个基可行解；的一个基可行解； 因此问题的求解有如下两阶段：因此问题的求解有如下两阶段：第一阶段第一阶段 用单纯形法求解辅助线性规划问题用单纯形法求解辅助线性规划问题C，若问题，若问题C的目的目标函数值标函数值w = 0，则得到原线性规划问题的基可行解，于是转，则得到原线性规划问题的基可行解，于是转向第二阶段。若问题向第二阶段。若问题C的目标函数值的目标函数值w0，则原线性规划问题，则原线性规划问题无可行解，计算停止；无可行解，计算停止；第二阶段第二阶段 把第一阶段的辅助线性规划问题把第一阶段的辅助线性规划问题C的最优解作为原问的最优解作为原问题的初始基可行解，用单纯形法继续求解。题的初始基可行解，用单纯形法继续求解。用两阶段法求例用两阶段法求例1.15解解: 构造辅助线性规划问题构造辅助线性规划问题 min w =x6 + x7x12x2 + x3 + x4 = 114x1 + x2 +2x3 x5 + x6 = 32x1 + x3 +x7 = 1x1、x2、x3、x4、x5、x6、x70利用单纯形法求解该辅助线性规划问题（极小化为标利用单纯形法求解该辅助线性规划问题（极小化为标准形式）如表准形式）如表113。 表表113Cj0000011b CBXB x1x2x3x4x5x6x70 x41-211000111x6-4120-11031x7-20100011 -w6-1-30100-40 x43-20100-1101x60100-11-210 x3-20100011 -w0-100103-10 x43001-22-512-1x20100-11-21-1x3-20100011 -w00000110第五节第五节 线性规划的计算机求解线性规划的计算机求解(Computer Solution for LP)(Computer Solution for LP)一、用计算机求解下列线性规划问题一、用计算机求解下列线性规划问题max z =50 x1+100 x2 x1 + x2 = 300 2x1 + x2 = 400 x2 = 250 x1、x20二、派公司生产计划问题的二、派公司生产计划问题的LPLP模型与计算机求解模型与计算机求解 派公司计划生产高中价位的高尔夫袋。生产过程为：派公司计划生产高中价位的高尔夫袋。生产过程为：1.切割并印染原材料；切割并印染原材料；2.缝合；缝合；3.成型；成型；4.检查和包装。检查和包装。各过程单位用时、总用时及产品单位利润如下表：如各过程单位用时、总用时及产品单位利润如下表：如何生产使公司利润最大？何生产使公司利润最大？过程过程生产耗时生产耗时总时间总时间标准袋标准袋高档袋高档袋切割并印染切割并印染缝合缝合成型成型检查和包装检查和包装7/101/211/1015/62/31/4630600708135单位产品利润单位产品利润109解：很显然，若设解：很显然，若设x1、x2分别代表标分别代表标准袋和高档袋的生产数量准袋和高档袋的生产数量,则问题的数学模型为：则问题的数学模型为： max z=10 x1+9x2 7/10 x1 + x2 =630 1/2 x1 + 5/6 x2 =600 x1 + 2/3 x2 =708 1/10 x1 + 1/4 x2 = 125 x1 + x2 = 350 2x1+ x2 =600 x1、x20第一章第一章 结束结束