运筹学线性规划.pptx

2005年年7 7月月 龙子泉龙子泉概概 述述线性规划问题的提出最早是线性规划问题的提出最早是19391939年由前苏联年由前苏联数学家康托洛维奇在研究铁路运输的组织问数学家康托洛维奇在研究铁路运输的组织问题、工业生产的管理问题时提出来的。题、工业生产的管理问题时提出来的。19471947年，美国学者丹西格（）提出了线性规年，美国学者丹西格（）提出了线性规划问题的单纯形方法。划问题的单纯形方法。线性规划理论最为成熟、应用最为广泛线性规划理论最为成熟、应用最为广泛 第1页/共60页2005年年7 7月月 龙子泉龙子泉第一节第一节线性规划问题及其数学模型线性规划问题及其数学模型一、问题提出一、问题提出例例例例1 1（生产计划问题）某企业利用（生产计划问题）某企业利用A、B、C三种资三种资源，在计划期内生产甲、乙两种产品，已知生产源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？表，问如何安排生产计划使企业利润最大？产产品品资资源源甲甲乙乙资源限制资源限制ABC120111300kg400kg250kg单位产品利润单位产品利润(元元/件件)50100第2页/共60页2005年年7 7月月 龙子泉龙子泉决策变量：x1、x2分别代表甲、乙两种产品的生产数量。目标函数：maxz=50 x1+100 x2约束条件：x1+x23002x1+x2400 x2250即有：maxz=50 x1+100 x2 x1+x23002x1+x2400 x2250 x1、x20称之为上述问题的数学模型。第3页/共60页2005年年7 7月月 龙子泉龙子泉例例2靠靠近近某某河河流流有有两两个个化化工工厂厂，流流经经第第一一化化工工厂厂的的河河流流流流量量为为每每天天500万万m3，在在两两个个工工厂厂之之间间有有一一条条流流量量为为200万万m3的的支支流流。两两化化工工厂厂每每天天排排放放某某种种有有害害物物质质的的工工业业污污水水分分别别为为2万万m3和和 万万m3。从从第第一一化化工工厂厂排排出出的的工工业业污污水水流流到到第第二二化化工工厂厂以以前前，有有20%可可以以自自然然净净化化。环环保保要要求求河河流流中中工工业业污污水水含含量量不不能能大大于于0.2%。两两化化工工厂厂处处理理工工业业污污水水的的成成本本分分别别为为1000元元/万万m3和和800元元/万万m3。现现在在要要问问在在满满足足环环保保要要求求的的条条件件下下，每每厂厂各各应应处处理理多多少少工工业业污污水水，使使这这两两个个工工厂厂处处理理工工业业污污水水的的费费用用最最小小.工厂1工厂2200万m3500万m3第4页/共60页2005年年7 7月月 龙子泉龙子泉决策变量：x1、x2分别代表工厂1和工厂2处理污水的数量(万m3)。则目标函数：min z=1000 x1+800 x2约束条件：第一段河流（工厂1工厂2之间）：(2x1)/5000.2%第二段河流：0.8(2x1x2)/7000.2%此外有：x12；x2化简有：minz=1000 x1+800 x2 x11x1+x2 x12 x2 x1、x20称之为上述问题的数学模型。第5页/共60页2005年年7 7月月 龙子泉龙子泉从上述两个例子，我们可以总结出线性规划的数学模型的一般形式。从上述两个例子，我们可以总结出线性规划的数学模型的一般形式。max(min)z=c1x1+c2x2+cnxn 目标函数 a11x1+a12x2+a1nxn=(,)b1 a21x1+a22x2+a2nxn=(,)b2 约束条件 am1x1+am2x2+amnxn=(,)bm x1，x2，xn0模型特点：目标函数模型特点：目标函数(Objectivefunction)与约束条件与约束条件(Constraint)均为线性的；目标函数实现极大化或极小化。均为线性的；目标函数实现极大化或极小化。第6页/共60页2005年年7 7月月 龙子泉龙子泉第二节第二节线性规划图解法线性规划图解法(GraphicalSolution)一、基本概念一、基本概念可行解(Feasible Solution)任一满足约束条件的一组决策变量的数值；可行域(Feasible Region)所有可行解组成的集合，也称为可行解集；目标函数等值线(Objective function line)为于同一直线上的点，具有相同的目标函数值；二、图解法步骤二、图解法步骤(Procedure)（1）画出线性规划问题的可行域；（2）画出两条目标函数等值线；（3）平行移动目标函数等值线，使目标函数在可行域范围内达到最优。第7页/共60页2005年年7 7月月 龙子泉龙子泉三、图解法举例三、图解法举例例1maxZ=50 x1+100 x2 x1+x23002x1+x2400 x2250 x1、x20 x2x1z*=27500z1=50 x1+100 x2=0BOACDz2=14000该问题有唯一最优解x1=50；x2=250 x1+x23002x1+x2400 x2250第8页/共60页2005年年7 7月月 龙子泉龙子泉例2maxZ=50 x1+50 x2 x1+x23002x1+x2400 x2250 x1、x20 x2x1z1=50 x1+50 x2=0B点和C点所代表的坐标同时为最优解，即该问题有无穷多最优解BOACDx1+x23002x1+x2400 x2250maxZ=50 x1+100 x2z*=27500z2=15000第9页/共60页2005年年7 7月月 龙子泉龙子泉例3maxz=x1+x2x1x21x1+2x20 x1、x20问题有无界解问题有无界解(unbounded)例4minz=x1+x2x1x21x1+2x20 x1、x20有唯一最优解有唯一最优解111z=32z=5OAx1x21x1+2x20第10页/共60页2005年年7 7月月 龙子泉龙子泉例4maxz=x1+x2x1+2x21 x1+x22 x1、x20问题无可行解问题无可行解(nofeasiblesolution)第11页/共60页2005年年7 7月月 龙子泉龙子泉直直 观观 结结 论论可行域可以是个凸多边形，可能无界，也可能为空；若线性规划问题的最优解存在，它一定可以在可行域的某一个顶点上得到；若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即LP有无穷多最优解；若可行域非空有界，则一定有最优解。第12页/共60页2005年年7 7月月 龙子泉龙子泉四四、线线 性性 规规 划划 问问 题题 的的 标标 准准 形形 式式(Standardform)规定如下形式的线性规划数学模型为LP标准形式。max z=c1x1+c2x2+cnxn 目标函数 a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 约束条件 am1x1+am2x2+amnxn=bm x1，x2，xn0特点：Zmax；约束条件为等号；变量非负；右端常数项大等于零。问题：n m why？第13页/共60页2005年年7 7月月 龙子泉龙子泉上述标准形式的线性规划模型还可写成如下一些形式上述标准形式的线性规划模型还可写成如下一些形式:(1)(2)第14页/共60页2005年年7 7月月 龙子泉龙子泉(3)(5)(4)第15页/共60页2005年年7 7月月 龙子泉龙子泉 五、化非标准形为标准形五、化非标准形为标准形（1）若）若minf=cX此时可令：此时可令：z=f，则，则maxz=minf=cX，这样处理所得最优解不，这样处理所得最优解不变；变；举例：举例：minz=x1x22x1+x22x1+x21x1、x20maxf=x1+x2z=-1/2f=0f=1/2z=0f=-z=8/3（1/3，4/3）第16页/共60页2005年年7 7月月 龙子泉龙子泉(2)约束条件为约束条件为“”时，时，aijxjbiaijxj+xn+i=bixn+i松弛变量松弛变量(slackvariable)；(3)约束条件为约束条件为“”时，时，aijxjbiaijxjxn+i=bixn+i过剩变量过剩变量(surplusvariable)；这样处理所得最优解不变这样处理所得最优解不变；maxz=x1+10 x2 x1+2x2100 x1、x20maxz=x1+10 x2 x1+2x2+x3=100 x1、x200第17页/共60页2005年年7 7月月 龙子泉龙子泉（4）若）若xk为无限制，为无限制，则令则令xk=xk1xk2，其中其中xk1、xk20（5）若）若bi0举例举例:化下列线性规划为标准形化下列线性规划为标准形maxz=2x1+2x24x3 x1+3x23x330 x1+2x24x380 x1、x20，x3无限制maxz=2x1+2x24x3+4x3”x1+3x23x3+3x3”x4=30 x1+2x24x3+4x3”+x5=80 x1、x2、x3、x3”、x4、x50第18页/共60页2005年年7 7月月 龙子泉龙子泉第三节第三节线性规划问题解的性质线性规划问题解的性质(PropertiesofSolutionofLP)一、线性规划问题的基本概念一、线性规划问题的基本概念(concepts)对于标准形式的线性规划：maxz=cX（a）AX=bX0（b）可行解可行解(feasiblesolution)满足约束条件满足约束条件（b）的点）的点X=（x1，x2，xn）T称为该称为该LP的一个的一个可行解；可行解；1.最优解最优解(optimalsolution)使目标函数值达到使目标函数值达到最大的可行解最大的可行解第19页/共60页2005年年7 7月月 龙子泉龙子泉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；第20页/共60页2005年年7 7月月 龙子泉龙子泉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的一个基本解。第21页/共60页2005年年7 7月月 龙子泉龙子泉同样，在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 0第22页/共60页2005年年7 7月月 龙子泉龙子泉 ABCDEOx1x22x1+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)T200180400/30BCDEAO第23页/共60页2005年年7 7月月 龙子泉龙子泉二、线性规划的基本定理二、线性规划的基本定理(Theorems)定义定义凸集凸集设设K是是n维欧氏空间的一个点集，若任意维欧氏空间的一个点集，若任意两点两点X(1)K，X(2)K的连线上所有的点的连线上所有的点X=X（1）+（1）X（2）K，（，（01），则称，则称K为凸集。为凸集。定理定理1若线性规划存在可行域，则其可行域若线性规划存在可行域，则其可行域R=X|AX=b，X0是凸集。是凸集。定理定理2线性规划问题的可行解线性规划问题的可行解X=（x1，x2，xn）T为基为基可行解的充要条件是：可行解的充要条件是：X的非零分量所对应的系数列向量是的非零分量所对应的系数列向量是线性无关的。线性无关的。定理定理3如果线性规划有可行解，则一定有基可行解。如果线性规划有可行解，则一定有基可行解。定理定理4线性规划问题的基可行解对应于可行域的顶点。线性规划问题的基可行解对应于可行域的顶点。定理定理5若线性规划问题的可行域非空有界，则线性规划问题若线性规划问题的可行域非空有界，则线性规划问题的最优解一定可以在其可行域的某个顶点上得到；的最优解一定可以在其可行域的某个顶点上得到；第24页/共60页2005年年7 7月月 龙子泉龙子泉第四节第四节 单纯形法单纯形法 (simplex method)(教材第五章P162-168)基本思想基本思想：在有限的基可行解中寻找最优解。即，从初始：在有限的基可行解中寻找最优解。即，从初始基可行解出发，转换到另一个基可行解，使目标值增大，直基可行解出发，转换到另一个基可行解，使目标值增大，直到达到最优解，或判断出无最优解为止。到达到最优解，或判断出无最优解为止。一、引例一、引例用单纯形方法求解下列线性规划用单纯形方法求解下列线性规划maxz=6x1+4x22x1+3x21004x1+2x2120 x1、x20解：化为标准型解：化为标准型maxz=6x1+4x2+0 x3+0 x42x1+3x2+x3=1004x1+2x2+x4=120 x1、x2，x3，x40第25页/共60页2005年年7 7月月 龙子泉龙子泉（1）找初始可行基：）找初始可行基：B1=（P3，P4）现成的初始可行基；现成的初始可行基；此时，此时，XB=（x3，x4）T，XN=（x1，x2）T用用XN表示表示Z和和XB有：有：maxz=6x1+4x2x3=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。且：称非基变量在目标函数中的系数为检验数。第26页/共60页2005年年7 7月月 龙子泉龙子泉（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有：有：maxz=180+2x2（3/2）x4x1=30（1/2）x2（1/4）x4x3=402x2+（1/2）x4问：问：X（2）是否最优呢？是否最优呢？否否因为：x2在目标函数中的系数为正，当x2，z。第27页/共60页2005年年7 7月月 龙子泉龙子泉（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有：有：maxz=2001/2）x3（5/4）x4x1=20+（1/4）x3（3/8）x4x2=20（1/2）x3+（1/4）x4问：问：X（3）是否最优呢？是否最优呢？是，是，求解过程求解过程：从引例可以总结出求解过程：（：从引例可以总结出求解过程：（1）找出初始基及其基）找出初始基及其基可行解；（可行解；（2）判断是否为最优解，是停止，否则转下一步；）判断是否为最优解，是停止，否则转下一步；（3）转换可行基，并求出相应的基可行解，使目标函数值有所）转换可行基，并求出相应的基可行解，使目标函数值有所改进，转（改进，转（2）。）。第28页/共60页2005年年7 7月月 龙子泉龙子泉二、单纯形方法二、单纯形方法 1检验数检验数(evaluationindex)检验数检验数用非基变量表示目标函数后，非基变量在目标函数中的用非基变量表示目标函数后，非基变量在目标函数中的系数系数设有标准形式的线性规划问题：设有标准形式的线性规划问题：maxz=cX；AX=b，X0；现假定现假定A中存在一可行基中存在一可行基B又设又设B=（P1，P2，Pm）；且；且B为单位阵为单位阵这样这样AX=b可以描述成如下形式，也就是用非基变量表示基可以描述成如下形式，也就是用非基变量表示基变量变量x1+a1,m+1xm+1+a1nxn=b1x2+a2,m+1xm+1+a2nxn=b2xm+am,m+1xm+1+amnxn=bm即即从上述约束方程中可以得到对应于基从上述约束方程中可以得到对应于基B的基可行解的基可行解X=（b1，b2，bm，0，0）T第29页/共60页2005年年7 7月月 龙子泉龙子泉用非基变量表示目标函数有：用非基变量表示目标函数有：令令有有式中式中j为基可行解为基可行解X的检验数。的检验数。更一般性：第30页/共60页2005年年7 7月月 龙子泉龙子泉2 2最优性检验最优性检验(optimality testing)判别定理判别定理1：设：设X为线性规划的一个基可行解，为线性规划的一个基可行解，且对于一切且对于一切j J（J为非基变量的下标集）有为非基变量的下标集）有j0，则，则X为线性规划的最优解；为线性规划的最优解；判别定理判别定理2：设：设X为线性规划的一个基可行解，为线性规划的一个基可行解，且对于一切且对于一切j J（J为非基变量的下标集）有为非基变量的下标集）有j0，同时有某个非基变量的检验数，同时有某个非基变量的检验数k=0（k J），则该线性规划有无穷多最优解；，则该线性规划有无穷多最优解；判别定理判别定理3：设：设X为线性规划的一个基可行解，为线性规划的一个基可行解，若有若有k0（k J），且，且Pk0，则该线性规划问，则该线性规划问题具有无界解（无最优解）。题具有无界解（无最优解）。第31页/共60页2005年年7 7月月 龙子泉龙子泉3 3 单纯形表单纯形表(simplex tableau)对于线性规划：对于线性规划：maxz=z0+m+1xm+1+nxnx1+a1,m+1xm+1+a1nxn=b1x2+a2,m+1xm+1+a2nxn=b2xm+am,m+1xm+1+amnxn=bmx1，x2，xn0列如下单纯形表：CjC1C2CmCm+1CnbCBXBx1x2xmxm+1xnc1x1100a1,m+1a1nb1c2x2010a2,m+1a2nb2cmxm001am,m+1amnbm-z0000m+1n-z0第32页/共60页2005年年7 7月月 龙子泉龙子泉单纯形表的说明与功能：单纯形表的说明与功能：（1）一个基对应一个单纯形表，且单纯形表中必须有一个初始）一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基。单位基。（2）从单纯表中，可立即得到一个基可行解，如上表中：）从单纯表中，可立即得到一个基可行解，如上表中：X=（b1，b2，bm，0，0）T为基可行解。为基可行解。（3）很容易计算检验数，并可判别上述基可行解是否为最优解）很容易计算检验数，并可判别上述基可行解是否为最优解或线性规划问题无最优解。或线性规划问题无最优解。4.4.单纯形法计算步骤单纯形法计算步骤（1）找出初始可行基，建立初始单纯形表；）找出初始可行基，建立初始单纯形表；（2）计算检验数，若对于一切）计算检验数，若对于一切j J有有j0，则已得到线性规划的则已得到线性规划的最优解，可停止计算，否则转下一步；最优解，可停止计算，否则转下一步；（3）若有）若有k0（k J），），且且Pk0，则该线性规划问题具有无界，则该线性规划问题具有无界解（无最优解），停止计算，否则转下一步；解（无最优解），停止计算，否则转下一步；（4）根据）根据maxj|j0=k，确定确定xk为换入变量；为换入变量；按按规则确定换出变量，即规则确定换出变量，即=bi/aik|aik0=bs/ask，对应的，对应的xs为换出变量，转为换出变量，转下一步；下一步；（5）以）以ask为主元素进行迭代，得新的单纯形表，转（为主元素进行迭代，得新的单纯形表，转（2）第33页/共60页2005年年7 7月月 龙子泉龙子泉三、单纯形法解题举例三、单纯形法解题举例例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）现成的初始可行基；第34页/共60页2005年年7 7月月 龙子泉龙子泉从表中有：从表中有：X（1）=（0，0，100，120）T为对应为对应于基于基B1的基可行解，显然不是最优解；的基可行解，显然不是最优解；根据根据maxj|j0=1，确定，确定x1为换入变量；为换入变量；按按规则确定换出变量，即：规则确定换出变量，即：=bi/aik|aik0=120/4，对应的，对应的x4为换出变为换出变量；量；Cj6400bCBXBx1x2x3x400 x3x423104201100120100/2120/4(min)z64000列初始单纯形表第35页/共60页2005年年7 7月月 龙子泉龙子泉以以4为主元素进行迭代，得新的单纯形表：为主元素进行迭代，得新的单纯形表：从表中有：从表中有：X（2）=（30，0，40，0）T为对应于为对应于基基B2的基可行解，显然不是最优解；的基可行解，显然不是最优解；根据根据maxj|j0=2，确定确定x2为换入变量；为换入变量；按按规则确定换出变量，即：规则确定换出变量，即：=bi/aik|aik0=40/2，对应的，对应的x3为换出变量；为换出变量；Cj6400bCBXBx1x2x3x40 x3021-1/24040/26x111/201/43030/(1/2)Z010-3/8180第36页/共60页2005年年7 7月月 龙子泉龙子泉表中表中j0，j=1，4，因此得最优解：因此得最优解：X*=（20，20，0，0）T，Z*=200Cj6400bCBXBx1x2x3x446x1x2011/2-1/410-1/43/82020Z00-1/2-5/4200以2为主元素进行迭代，得新的单纯形表：第37页/共60页2005年年7 7月月 龙子泉龙子泉将上述计算列在一个表中为：Cj6400bCBXBx1x2x3x40 x32310100100/20 x44201120120/4(min)z640000 x3021-1/24040/2(min)6x111/201/43030/(1/2)Z010-3/81804x2011/2-1/4206x110-1/43/820Z00-1/2-5/4200第38页/共60页2005年年7 7月月 龙子泉龙子泉例2：用单纯形法求解maxz=50 x1+100 x2 x1+x23002x1+x2400 x2250 x1、x20第39页/共60页2005年年7 7月月 龙子泉龙子泉Cj50100000bCBXBx1x2X3x4x50 x311100300300/10 x421010400400/10 x501001250250/1(min)z5010000000 x31010-15050/1(min)0 x42001-1150150/2100 x201001250Z50000-1002500050 x11010-15000 x400-21150100 x2010-01250Z00-500-5027500第40页/共60页2005年年7 7月月 龙子泉龙子泉例例3：用单纯形法求解：用单纯形法求解maxz=2x1+x2 x1+x252x15x210 x1、x20 2=60，且P20，故该线性规划有无界解。Cj2100bCBXBx1x2x3x40 x3-11105100/20 x42-50110120/4(min)z210000 x30-3/211/21040/2(min)2x11-5/201/2530/(1/2)Z060-110第41页/共60页2005年年7 7月月 龙子泉龙子泉例4：用单纯形法求解maxz=6x1+2x2+10 x3+8x45x1+6x24x34x4203x13x2+2x3+8x4254x12x2+x3+3x410 x1、x2、x3、x407=340,p70,故该LP有无解解第42页/共60页2005年年7 7月月 龙子泉龙子泉Cj62108000bCBXBx1x2x3x4x5x6x70 x556-4-4100200 x63-328010250 x74-21300110z6210800000 x521-208104600 x6-510201-2510 x34-21300110Z-34220-2200-101000 x5110012120702x2-510201-2510 x3-601702-320Z7600-660-2234210第43页/共60页2005年年7 7月月 龙子泉龙子泉四、极小化问题四、极小化问题(Minimization Problem)若标准形式的线性规划问题的目标函数是极小化形式，则若标准形式的线性规划问题的目标函数是极小化形式，则问题的判别准则就会有所改变。这样三个判别定理如下问题的判别准则就会有所改变。这样三个判别定理如下：判别定理判别定理1：设：设X为线性规划的一个基可行解，且对于一切为线性规划的一个基可行解，且对于一切j J（J为非基变量的下标集）有为非基变量的下标集）有j0，则，则X为线性规划的最优为线性规划的最优解；解；判别定理判别定理2：设：设X为线性规划的一个基可行解，且对于一切为线性规划的一个基可行解，且对于一切j J（J为非基变量的下标集）有为非基变量的下标集）有j0，同时有某个非基变量，同时有某个非基变量的检验数的检验数k=0（k J），则该线性规划有无穷多最优解；，则该线性规划有无穷多最优解；判别定理判别定理3：设：设X为线性规划的一个基可行解，若有为线性规划的一个基可行解，若有k0（k J），且，且Pk0，则该线性规划问题具有无界解（无，则该线性规划问题具有无界解（无最优解）。最优解）。第44页/共60页2005年年7 7月月 龙子泉龙子泉上上述述单单纯纯形形法法的的基基础础是是线线性性规规划划问问题题有有初初始始基基可可行行解解。有有些些线线性性规规划划问问题题化化为为标标准准形形式式以以后后，就就存存在在初初始始可可行行基基，如如约约束束条条件件全全部部为为“”的的线线性性规规划划问问题题。对对于于标标准准形形式式的的线线性性规规划划问问题题，若若约约束束方方程程系系数数矩矩阵阵中中不不存存在在现现成成的的初初始始可可行行基基，则则不不能能简简单单的的用用上上述述单单纯纯形形法法，而而通通常常采采用用所所谓谓的的人人工工变变量量法法。人人工工变变量量法法一一般般有有大大M M法法和和两两阶阶段法。段法。五、人工变量法(ArtificialVariableMethod)第45页/共60页2005年年7 7月月 龙子泉龙子泉（一）大M法(Big M method)对于标准形式的线性规划问题（问题对于标准形式的线性规划问题（问题A）maxz=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0若其约束方程的系数矩阵中不存在现成的初始可行基，则引入所若其约束方程的系数矩阵中不存在现成的初始可行基，则引入所谓的谓的人工变量xn+1，xn+m构造如下形式的线性规划问题（问构造如下形式的线性规划问题（问题题B）maxz=c1x1+c2x2+cnxnMxn+1Mxn+ma11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2am1x1+am2x2+amnxn+xn+m=bmx1，x2，xn，xn+1，xn+m0第46页/共60页2005年年7 7月月 龙子泉龙子泉问题问题B中中M为任意大的正数。显然问题为任意大的正数。显然问题B存在现成的单位存在现成的单位基，且初始基可行解中，以人工变量为基变量。基，且初始基可行解中，以人工变量为基变量。关于问题关于问题B的几点结论：的几点结论：（1）问题）问题B要实现极大化，必须将人工变量从基变量中换要实现极大化，必须将人工变量从基变量中换出，否则目标函数不可能实现极大化；出，否则目标函数不可能实现极大化；（2）若在求解问题）若在求解问题B的过程中，已将人工变量从基变量中的过程中，已将人工变量从基变量中换出，则已得到问题换出，则已得到问题A的一个基可行解，可继续求解，以的一个基可行解，可继续求解，以获得问题获得问题A的最优解或判别问题的最优解或判别问题A无最优解；无最优解；（3）若求解问题）若求解问题B已得到最优解，但最优解的基变量中含已得到最优解，但最优解的基变量中含有不为零人工变量，则问题有不为零人工变量，则问题A无可行解；无可行解；（4）若求解问题）若求解问题B已得到最优解，且最优解的基变量中不已得到最优解，且最优解的基变量中不含有人工变量，则问题含有人工变量，则问题B的最优解就是问题的最优解就是问题A的最优解。的最优解。第47页/共60页2005年年7 7月月 龙子泉龙子泉例：用单纯形法（大例：用单纯形法（大M法）求解法）求解maxz=3x12x2x3 x12x2+x3114x1+x2+2x332x1x3=1 x1、x2、x30解：化为标准形式，并引入人工变量，构造如下模解：化为标准形式，并引入人工变量，构造如下模型：型：maxz=3x12x2x3Mx6Mx7 x12x2+x3+x4=114x1+x2+2x3x5+x6=32x1x3+x7=1 x1、x2、x30列表计算：列表计算：第48页/共60页2005年年7 7月月 龙子泉龙子泉Cj3-1-100-M-MbCBXBx1x2x3x4x5x6x70 x41-21100011-Mx6-4120-1103-Mx7-20100011z3-6M-1+M-1+3M0-M000 x43-20100-110-Mx60100-11-21-1x3-20100011Z1-1+M00-M0-3M+10 x43001-22-512-1x20100-11-21-1x3-20100011z1000-1-M+1-M-13x11001/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第49页/共60页2005年年7 7月月 龙子泉龙子泉（二）两阶段法（二）两阶段法对于标准形式的线性规划问题（问题对于标准形式的线性规划问题（问题A）maxz=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0若其约束方程的系数矩阵中不存在现成的初始可行基，则引若其约束方程的系数矩阵中不存在现成的初始可行基，则引入所谓的人工变量入所谓的人工变量xn+1，xn+m构造如下辅助线性规划构造如下辅助线性规划问题（问题问题（问题C）minw=xn+1+xn+ma11x1+a12x2+a1nxn+xn+1=b1a21x1+a22x2+a2nxn+xn+2=b2am1x1+am2x2+amnxn+xn+m=bmx1，x2，xn，xn+1，xn+m0第50页/共60页2005年年7 7月月 龙子泉龙子泉关于问题关于问题C的几点结论的几点结论：（1）由于问题）由于问题C为极小化问题，且目标函数有下界，因此为极小化问题，且目标函数有下界，因此问题问题C肯定有最优解；肯定有最优解；（2）求解问题）求解问题C已得到其最优解，若问题已得到其最优解，若问题C最优解所对应目最优解所对应目标函数值标函数值w0，则原问题，则原问题A无可行解，若问题无可行解，若问题C所对应目所对应目标函数值标函数值w=0，则已得到原问题，则已得到原问题A的一个基可行解；的一个基可行解；因此问题的求解有如下两阶段：因此问题的求解有如下两阶段：第一阶段第一阶段用单纯形法求解辅助线性规划问题用单纯形法求解辅助线性规划问题C，若问题，若问题C的目标函数值的目标函数值w=0，则得到原线性规划问题的基可行解，则得到原线性规划问题的基可行解，于是转向第二阶段。若问题于是转向第二阶段。若问题C的目标函数值的目标函数值w0，则原线，则原线性规划问题无可行解，计算停止；性规划问题无可行解，计算停止；第二阶段第二阶段把第一阶段的辅助线性规划问题把第一阶段的辅助线性规划问题C的最优解作为的最优解作为原问题的初始基可行解，用单纯形法继续求解。原问题的初始基可行解，用单纯形法继续求解。第51页/共60页2005年年7 7月月 龙子泉龙子泉用两阶段法求例用两阶段法求例解解:构造辅助线性规划问题构造辅助线性规划问题minw=x6+x7x12x2+x3+x4=114x1+x2+2x3x5+x6=32x1+x3+x7=1x1、x2、x3、x4、x5、x6、x70利用单纯形法求解该辅助线性规划问题（极小化为利用单纯形法求解该辅助线性规划问题（极小化为标准形式）如表标准形式）如表113。第52页/共60页2005年年7 7月月 龙子泉龙子泉 表113Cj0000011bCBXBx1x2x3x4x5x6x70 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第53页/共60页2005年年7 7月月 龙子泉龙子泉第五节第