第一章 线性规划.ppt

《第一章 线性规划.ppt》由会员分享，可在线阅读，更多相关《第一章 线性规划.ppt（60页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章第一章线性规划线性规划概概 述述线性规划问题的提出最早是线性规划问题的提出最早是19391939年由前苏联数年由前苏联数学家康托洛维奇在研究铁路运输的组织问题、学家康托洛维奇在研究铁路运输的组织问题、工业生产的管理问题时提出来的。工业生产的管理问题时提出来的。19471947年，美国学者丹西格（年，美国学者丹西格（G.B.DantzigG.B.Dantzig）提）提出了线性规划问题的单纯形方法。出了线性规划问题的单纯形方法。线性规划理论最为成熟、应用最为广泛线性规划理论最为成熟、应用最为广泛 第一节 线性规划问题及其数学模型一、问题提出一、问题提出例例例例1 1（生产计划问题）某企业利用

2、（生产计划问题）某企业利用A、B、C三种资源，三种资源，在计划期内生产甲、乙两种产品，已知生产单位产在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？何安排生产计划使企业利润最大？产产品品资资源源甲甲乙乙资源限制资源限制ABC120111300kg400kg250kg单位产品利润单位产品利润(元元/件件)50100决决策策变变量量：x1、x2分分别别代代表表甲甲、乙乙两两种产品的生产数量。种产品的生产数量。目标函数：目标函数：maxz=50 x1+100 x2约束条件：约束条件：x1

3、+x23002x1+x2400 x2250即有：即有：maxz=50 x1+100 x2 x1+x23002x1+x2400 x2250 x1、x20称之为上述问题的数学模型。称之为上述问题的数学模型。例例2靠靠近近某某河河流流有有两两个个化化工工厂厂，流流经经第第一一化化工工厂厂的的河河流流流流量量为为每每天天 500万万m3，在在两两个个工工厂厂之之间间有有一一条条流流量量为为 200万万m3的的支支流流。两两化化工工厂厂每每天天排排放放某某种种有有害害物物质质的的工工业业污污水水分分别别为为 2万万m3和和1.4万万m3。从从第第一一化化工工厂厂排排出出的的工工业业污污水水流流到到第第二

4、二化化工工厂厂以以前前，有有 20%可可以以自自然然净净化化。环环保保要要求求河河流流中中工工业业污污水水含含量量不不能能大大于于 0.2%。两两化化工工厂厂处处理理工工业业污污水水的的成成本本分分别别为为 1000元元/万万m3和和800元元/万万m3。现现在在要要问问在在满满足足环环保保要要求求的的条条件件下下，每每厂厂各各应应处处理理多多少少工工业业污污水水，使使 这这 两两 个个 工工 厂厂 处处 理理 工工 业业 污污 水水 的的 费费 用用 最最 小小.工厂工厂1工厂工厂2200万万m3500万万m3决决策策变变量量：x1、x2分分别别代代表表工工厂厂1和和工工厂厂2处处理污水的数

5、量理污水的数量(万万m3)。则目标函数：则目标函数：minz=1000 x1+800 x2约束条件：约束条件：第一段河流（工厂第一段河流（工厂1工厂工厂2之间）：之间）：(2x1)/5000.2%第二段河流：第二段河流：0.8(2x1)+(1.4x2)/7000.2%此外有：此外有：x12；x21.4化简有：化简有：minz=1000 x1+800 x2 x110.8x1+x21.6 x12 x21.4 x1、x20称之为上述问题的数学模型。称之为上述问题的数学模型。从上述两个例子，我们可以总结出线性规划从上述两个例子，我们可以总结出线性规划的数学模型的一般形式。的数学模型的一般形式。max(

6、min)z=c1x1+c2x2+cnxn目标函数目标函数a11x1+a12x2+a1nxn=(,)b1a21x1+a22x2+a2nxn=(,)b2约束条件约束条件am1x1+am2x2+amnxn=(,)bmx1，x2，xn0模型特点：目标函数模型特点：目标函数(Objectivefunction)与与约束条件约束条件(Constraint)均为线性的；目标函均为线性的；目标函数实现极大化或极小化。数实现极大化或极小化。第二节第二节线性规划图解法线性规划图解法(GraphicalSolution)一、基本概念一、基本概念可可行行解解(FeasibleSolution)任任一一满满足足约约束束

7、条条件的一组决策变量的数值；件的一组决策变量的数值；可可行行域域(FeasibleRegion)所所有有可可行行解解组组成成的集合，也称为可行解集；的集合，也称为可行解集；目目标标函函数数等等值值线线(Objectivefunctionline)为于同一直线上的点，具有相同的目标函数值；为于同一直线上的点，具有相同的目标函数值；二、图解法步骤二、图解法步骤(Procedure)（1）画出线性规划问题的可行域；）画出线性规划问题的可行域；（2）画出两条目标函数等值线；）画出两条目标函数等值线；（3）平平行行移移动动目目标标函函数数等等值值线线，使使目目标标函函数数在在可可行域范围内达到最优。行域

8、范围内达到最优。三、图解法举例三、图解法举例例例1maxZ=50 x1+100 x2 x1+x23002x1+x2400 x2250 x1、x20 x2x1z*=27500z1=50 x1+100 x2=0BOACDz2=14000该问题有唯一最优解该问题有唯一最优解x1=50=50；x2=250=250 x1+x23002x1+x2400 x2250例例2maxZ=50 x1+50 x2 x1+x23002x1+x2400 x2250 x1、x20 x2x1z1=50 x1+50 x2=0B点和点和C点所代表的坐点所代表的坐标同时为最优解，即该标同时为最优解，即该问题有问题有无穷多最优解无穷

9、多最优解BOACDx1+x23002x1+x2400 x2250maxZ=50 x1+100 x2z*=27500z2=15000例例3maxz=x1+x2x1x21x1+2x20 x1、x20问题有无界解问题有无界解(unbounded)例例4minz=x1+x2x1x21x1+2x20 x1、x20有唯一最优解有唯一最优解111z=32z=5OAx1x21x1+2x20例例4maxz=x1+x2x1+2x21 x1+x22 x1、x20问题无可行解问题无可行解(nofeasiblesolution)直直 观观 结结 论论1)可行域可以是个凸多边形，可能无界，也可可行域可以是个凸多边形，可能

10、无界，也可能为空；能为空；2)若线性规划问题的最优解存在，它一定可以若线性规划问题的最优解存在，它一定可以在可行域的某一个顶点上得到；在可行域的某一个顶点上得到；3)若在两个顶点上同时得到最优解，则该两点若在两个顶点上同时得到最优解，则该两点连线上的所有点都是最优解，即连线上的所有点都是最优解，即LP有无穷多有无穷多最优解；最优解；4)若可行域非空有界，则一定有最优解。若可行域非空有界，则一定有最优解。四、线性规划问题的标准形式四、线性规划问题的标准形式(Standardform)规定如下形式的线性规划数学模型为规定如下形式的线性规划数学模型为LP标准形式。标准形式。maxz=c1x1+c2x

11、2+cnxn目标函数目标函数a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2约束条件约束条件 am1x1+am2x2+amnxn=bmx1，x2，xn0特特点点：Zmax；约约束束条条件件为为等等号号；变变量量非非负负；右端常数项大等于零。右端常数项大等于零。上述标准形式的线性规划模型还可写成如下一些形式上述标准形式的线性规划模型还可写成如下一些形式:(1)(2)(3)(5)(4)五、化非标准形为标准形五、化非标准形为标准形（1）若）若minf=cX 此时可令：此时可令：z=f，则，则maxz=minf=cX，这样处理所得最优解不变；这样处理所得最优解不变；举例

12、：举例：minz=x1x22x1+x22x1+x21x1、x20maxf=x1+x2z=-1/2f=0f=1/2z=0f=-z=8/3（1/3，4/3）(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（

13、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第三节第三节线性规划问题解的性质线性规划问题解的性质(PropertiesofSolutionofLP)一、线性规划问题的基本概念一、线性规划问题的基本概念(concep

14、ts)对于标准形式的线性规划：对于标准形式的线性规划：maxz=cX（a）AX=bX0（b）1.可行解可行解(feasiblesolution)满足约束条件（满足约束条件（b）的点的点X=（x1，x2，xn）T称为该称为该LP的一个可行解；的一个可行解；2.最优解最优解(optimalsolution)使目标函数值达到最大使目标函数值达到最大的可行解的可行解3基基、基变量、非基变量、基变量、非基变量 (base,basic variable,nonbasic variable)设约束方程的系数矩阵设约束方程的系数矩阵A中，有中，有m个线性无关的列向量，个线性无关的列向量，且设且设B=（P1，P

15、2，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线性方程组

16、。线性方程组。由于由于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）

17、！）！m！因此，基本解是有限的。因此，基本解是有限的。举例：找出下列举例：找出下列LP所有的基及其对应的基本解所有的基及其对应的基本解maxz=6x1+4x22x1+3x21004x1+2x2120 x1、x20解：化为标准型解：化为标准型maxz=6x1+4x2+0 x3+0 x42x1+3x2+x3=1004x1+2x2+x4=120 x1、x2，x3，x40 ABCDEOx1x22x1+3x2=1004x1+2x2=120基本解如下表基本解如下表基基基本解基本解可行可行否否目标值目标值对应图对应图中的点中的点B1=(P1，P2)B2=(P1，P3)B3=(P1，P4)B4=(P2，P3)

18、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二、线性规划的基本定理二、线性规划的基本定理(Theorems)1.定义定义凸集凸集设设K是是n维欧氏空间的一个点集，若任意维欧氏空间的一个点集，若任意两点两点X(1)K，X(2)K的连线上所有的点的连线上所有的点X=X（1）+（1）X（2）K，（01），则称，则称K为凸集。为凸集。2.定理定理1若线性规划存在可行域，则其可行

19、若线性规划存在可行域，则其可行域域R=X|AX=b，X0是凸集。是凸集。3.定理定理2线性规划问题的可行解线性规划问题的可行解X=（x1，x2，xn）T为基可行为基可行解的充要条件解的充要条件是：是：X的非零分量所对应的系数列向量是线性无关的。的非零分量所对应的系数列向量是线性无关的。4.定理定理3如果线性规划有可行解，则一定有基可行解。如果线性规划有可行解，则一定有基可行解。5.定理定理4线性规划问题的基可行解对应于可行域的顶点。线性规划问题的基可行解对应于可行域的顶点。6.定理定理5若线性规划问题的可行域非空有界，则线性规划问题的最若线性规划问题的可行域非空有界，则线性规划问题的最优解一定

20、可以在其可行域的某个顶点上得到；优解一定可以在其可行域的某个顶点上得到；第四节第四节 单纯形法单纯形法 (simplex method)基本思想基本思想：在有限的基可行解中寻找最优解。即，从初始基：在有限的基可行解中寻找最优解。即，从初始基可行解出发，转换到另一个基可行解，使目标值增大，直到达到可行解出发，转换到另一个基可行解，使目标值增大，直到达到最优解，或判断出无最优解为止。最优解，或判断出无最优解为止。一、引例一、引例用单纯形方法求解下列线性规划用单纯形方法求解下列线性规划maxz=6x1+4x22x1+3x21004x1+2x2120 x1、x20解：化为标准型解：化为标准型maxz=

21、6x1+4x2+0 x3+0 x42x1+3x2+x3=1004x1+2x2+x4=120 x1、x2，x3，x40（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在目标函

22、数中的系数为正，当在目标函数中的系数为正，当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线性无关，因此

23、，线性无关，因此，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。（3）寻找可行基）寻找可行基B3，使其对应的基可行解，使其对应的基可行解X（3）能使目标函数值增加。能使目标函数值增加。选：选：x20则有：则有：X（3）=（x1，x2，x3，

24、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）x

25、4问：问：X（3）是否最优呢？是否最优呢？是，是，求解过程求解过程：从引例可以总结出求解过程：（：从引例可以总结出求解过程：（1）找出初始基及其基可行）找出初始基及其基可行解；（解；（2）判断是否为最优解，是停止，否则转下一步；（）判断是否为最优解，是停止，否则转下一步；（3）转换可）转换可行基，并求出相应的基可行解，使目标函数值有所改进，转（行基，并求出相应的基可行解，使目标函数值有所改进，转（2）。）。二、单纯形方法二、单纯形方法 1检验数检验数(evaluationindex)检验数检验数用非基变量表示目标函数后，非基变量在目标函数中的系数用非基变量表示目标函数后，非基变量在目标函数中的

26、系数设有标准形式的线性规划问题：设有标准形式的线性规划问题：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用非基变量表示目标函数有：用非基变量表示目

27、标函数有：令令有有式中式中j为基可行解为基可行解X的检验数。的检验数。更一般性：更一般性：2 2最优性检验最优性检验(optimality testing)判别定理判别定理1：设：设X为线性规划的一个基可行解，且对为线性规划的一个基可行解，且对于一切于一切j J（J为非基变量的下标集）有为非基变量的下标集）有j0，则，则X为线性规划的最优解；为线性规划的最优解；判别定理判别定理2：设：设X为线性规划的一个基可行解，且对为线性规划的一个基可行解，且对于一切于一切j J（J为非基变量的下标集）有为非基变量的下标集）有j0，同时，同时有某个非基变量的检验数有某个非基变量的检验数k=0（k J），则该

28、线性，则该线性规划有无穷多最优解；规划有无穷多最优解；判别定理判别定理3：设：设X为线性规划的一个基可行解，若有为线性规划的一个基可行解，若有k0（k J），且，且Pk0，则该线性规划问题具有无，则该线性规划问题具有无界解（无最优解）。界解（无最优解）。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+1CnbCBXBx

29、1x2xmxm+1xnc1x1100a1,m+1a1nb1c2x2010a2,m+1a2nb2cmxm001am,m+1amnbm-z0000m+1n-z0单纯形表的说明与功能：单纯形表的说明与功能：（1）一个基对应一个单纯形表，且单纯形表中必须有一个初始单位）一个基对应一个单纯形表，且单纯形表中必须有一个初始单位基。基。（2）从单纯表中，可立即得到一个基可行解，如上表中：）从单纯表中，可立即得到一个基可行解，如上表中：X=（b1，b2，bm，0，0）T为基可行解。为基可行解。（3）很容易计算检验数，并可判别上述基可行解是否为最优解或线）很容易计算检验数，并可判别上述基可行解是否为最优解或线性

30、规划问题无最优解。性规划问题无最优解。4.4.单纯形法计算步骤单纯形法计算步骤（1）找出初始可行基，建立初始单纯形表；）找出初始可行基，建立初始单纯形表；（2）计算检验数，若对于一切）计算检验数，若对于一切j J有有j0，则已得到线性规划的最优则已得到线性规划的最优解，可停止计算，否则转下一步；解，可停止计算，否则转下一步；（3）若有）若有k0（k J），），且且Pk0，则该线性规划问题具有无界解，则该线性规划问题具有无界解（无最优解），停止计算，否则转下一步；（无最优解），停止计算，否则转下一步；（4）根据）根据maxj|j0=k，确定确定xk为换入变量；为换入变量；按按规则确定换出变量，即

31、规则确定换出变量，即=bi/aik|aik0=bs/ask，对应的，对应的xs为换出变量，转下一步；为换出变量，转下一步；（5）以）以ask为主元素进行迭代，得新的单纯形表，转（为主元素进行迭代，得新的单纯形表，转（2）三、单纯形法解题举例三、单纯形法解题举例例例1：用单纯形法求解：用单纯形法求解maxz=6x1+4x22x1+3x21004x1+2x2120 x1、x20解：化为标准型解：化为标准型maxz=6x1+4x2+0 x3+0 x42x1+3x2+x3=1004x1+2x2+x4=120 x1、x2，x3，x40找初始可行基：找初始可行基：B1=（P3，P4）现成的初始可行基；现成

32、的初始可行基；从表中有：从表中有：X（1）=（0，0，100，120）T为对应于为对应于基基B1的基可行解，显然不是最优解；的基可行解，显然不是最优解；根据根据maxj|j0=1，确定，确定x1为换入变量；为换入变量；按按规则确定换出变量，即：规则确定换出变量，即：=bi/aik|aik0=120/4，对应的，对应的x4为换出变量；为换出变量；Cj6400bCBXBx1x2x3x400 x3x423104201100120100/2120/4(min)z64000列初始单纯形表列初始单纯形表以以4为主元素进行迭代，得新的单纯形表：为主元素进行迭代，得新的单纯形表：从表中有：从表中有：X（2）=

33、（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表中表中j0，j=1，4，因此得最优解：因此得最优解：X*=（20，20，0，0）T，Z*=200Cj6400bCBXBx1x2x3x446x1x2011/2-1/410

34、-1/43/82020Z00-1/2-5/4200以以2为主元素进行迭代，得新的单纯形表：为主元素进行迭代，得新的单纯形表：将上述计算列在一个表中为：将上述计算列在一个表中为：Cj6400bCBXBx1x2x3x40 x32310100100/20 x44201120120/4(min)z640000 x3021-1/24040/2(min)6x111/201/43030/(1/2)Z010-3/21804x2011/2-1/4206x110-1/43/820Z00-1/2-5/4200例例2：用单纯形法求解：用单纯形法求解maxz=50 x1+100 x2 x1+x23002x1+x2400

35、 x2250 x1、x20Cj50100000bCBXBx1x2X3x4x50 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例例3：用单纯形法求解：用单纯形法求解maxz=2x1+x2 x1+x252x15x210 x1、x20 2=60，且，且P20，故该线性规划有

36、无界解。，故该线性规划有无界解。Cj2100bCBXBx1x2x3x40 x3-11105100/20 x42-50110120/4(min)z210000 x30-3/211/21040/2(min)2x11-5/201/2530/(1/2)Z060-110例例4：用单纯形法求解：用单纯形法求解maxz=6x1+2x2+10 x3+8x45x1+6x24x34x4203x13x2+2x3+8x4254x12x2+x3+3x410 x1、x2、x3、x407=340,p70,故该故该LP有无解解有无解解Cj62108000bCBXBx1x2x3x4x5x6x70 x556-4-4100200

37、x63-328010250 x74-21300110z6210800000 x521-208104600 x6-510201-2510 x34-21300110Z-34220-2200-101000 x5110012120702x2-510201-2510 x3-601702-320Z7600-660-2234210四、极小化问题四、极小化问题(Minimization Problem)若标准形式的线性规划问题的目标函数是极小化形式，则问题若标准形式的线性规划问题的目标函数是极小化形式，则问题的判别准则就会有所改变。这样三个判别定理如下的判别准则就会有所改变。这样三个判别定理如下：判别定理判别

38、定理1：设：设X为线性规划的一个基可行解，且对于一切为线性规划的一个基可行解，且对于一切j J（J为非基变量的下标集）有为非基变量的下标集）有j0，则，则X为线性规划的最优解；为线性规划的最优解；判别定理判别定理2：设：设X为线性规划的一个基可行解，且对于一切为线性规划的一个基可行解，且对于一切j J（J为非基变量的下标集）有为非基变量的下标集）有j0，同时有某个非基变量的检，同时有某个非基变量的检验数验数k=0（k J），则该线性规划有无穷多最优解；，则该线性规划有无穷多最优解；判别定理判别定理3：设：设X为线性规划的一个基可行解，若有为线性规划的一个基可行解，若有k0（k J），且，且Pk

39、0，则该线性规划问题具有无界解（无最优，则该线性规划问题具有无界解（无最优解）。解）。上上述述单单纯纯形形法法的的基基础础是是线线性性规规划划问问题题有有初初始始基基可可行行解解。有有些些线线性性规规划划问问题题化化为为标标准准形形式式以以后后，就就存存在在初初始始可可行行基基，如如约约束束条条件件全全部部为为“”“”的的线线性性规规划划问问题题。对对于于标标准准形形式式的的线线性性规规划划问问题题，若若约约束束方方程程系系数数矩矩阵阵中中不不存存在在现现成成的的初初始始可可行行基基，则则不不能能简简单单的的用用上上述述单单纯纯形形法法，而而通通常常采采用用所所谓谓的的人人工工变变量量法法。人

40、工变量法一般有大人工变量法一般有大M M法和两阶段法。法和两阶段法。五、人工变量法五、人工变量法(Artificial Variable Method)（一）大（一）大M法法(BigMmethod)对于标准形式的线性规划问题（问题对于标准形式的线性规划问题（问题A）maxz=c1x1+c2x2+cnxna11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0若其约束方程的系数矩阵中不存在现成的初始可行基，则引入所谓的若其约束方程的系数矩阵中不存在现成的初始可行基，则引入所谓的人工变量xn+1，xn+m构造如下形式

41、的线性规划问题（问题构造如下形式的线性规划问题（问题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问题问题B中中M为任意大的正数。显然问题为任意大的正数。显然问题B存在现成的单位基，存在现成的单位基，且初始基可行解中，以人工变量为基变量。且初始基可行解中，以人工变量为基变量。关于问题关于问题B的几点结论：的几点结论：（1）问题）问题B要实现极大化，必须将人工变量从基变量中换出，要实现极大化，必

42、须将人工变量从基变量中换出，否则目标函数不可能实现极大化；否则目标函数不可能实现极大化；（2）若在求解问题）若在求解问题B的过程中，已将人工变量从基变量中换出，的过程中，已将人工变量从基变量中换出，则已得到问题则已得到问题A的一个基可行解，可继续求解，以获得问题的一个基可行解，可继续求解，以获得问题A的最优解或判别问题的最优解或判别问题A无最优解；无最优解；（3）若求解问题）若求解问题B已得到最优解，但最优解的基变量中含有不已得到最优解，但最优解的基变量中含有不为零人工变量，则问题为零人工变量，则问题A无可行解；无可行解；（4）若求解问题）若求解问题B已得到最优解，且最优解的基变量中不含有已得

43、到最优解，且最优解的基变量中不含有人工变量，则问题人工变量，则问题B的最优解就是问题的最优解就是问题A的最优解。的最优解。例：用单纯形法（大例：用单纯形法（大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列表计算：列表计算：Cj3-1-100-M-MbCBXBx1x2x3x4x5x6x

44、70 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（二）两阶段法（二）两阶段法对于标准形式的线性规划问题（问题对于标准形式的线性规划问题

45、（问题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，

46、xn+1，xn+m0关于问题关于问题C的几点结论的几点结论：（1）由于问题）由于问题C为极小化问题，且目标函数有下界，因此问题为极小化问题，且目标函数有下界，因此问题C肯定有最优解；肯定有最优解；（2）求解问题）求解问题C已得到其最优解，若问题已得到其最优解，若问题C最优解所对应目标函最优解所对应目标函数值数值w0，则原问题，则原问题A无可行解，若问题无可行解，若问题C所对应目标函数值所对应目标函数值w=0，则已得到原问题，则已得到原问题A的一个基可行解；的一个基可行解；因此问题的求解有如下两阶段：因此问题的求解有如下两阶段：第一阶段第一阶段用单纯形法求解辅助线性规划问题用单纯形法求解辅助线性

47、规划问题C，若问题，若问题C的目标的目标函数值函数值w=0，则得到原线性规划问题的基可行解，于是转向，则得到原线性规划问题的基可行解，于是转向第二阶段。若问题第二阶段。若问题C的目标函数值的目标函数值w0，则原线性规划问题无，则原线性规划问题无可行解，计算停止；可行解，计算停止；第二阶段第二阶段把第一阶段的辅助线性规划问题把第一阶段的辅助线性规划问题C的最优解作为原问的最优解作为原问题的初始基可行解，用单纯形法继续求解。题的初始基可行解，用单纯形法继续求解。用两阶段法求例用两阶段法求例1.15解解:构造辅助线性规划问题构造辅助线性规划问题minw=x6+x7x12x2+x3+x4=114x1+

48、x2+2x3x5+x6=32x1+x3+x7=1x1、x2、x3、x4、x5、x6、x70利用单纯形法求解该辅助线性规划问题（极小化为标利用单纯形法求解该辅助线性规划问题（极小化为标准形式）如表准形式）如表113。表表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第五节

49、第五节 线性规划的计算机求解线性规划的计算机求解(Computer Solution for LP)(Computer Solution for LP)一、用计算机求解下列线性规划问题一、用计算机求解下列线性规划问题maxz=50 x1+100 x2x1+x2=3002x1+x2=400 x2=250 x1、x20二、派公司生产计划问题的二、派公司生产计划问题的LPLP模型与计算机求解模型与计算机求解派公司计划生产高中价位的高尔夫袋。生产过程为：派公司计划生产高中价位的高尔夫袋。生产过程为：1.切割并印染原材料；切割并印染原材料；2.缝合；缝合；3.成型；成型；4.检查和包装。检查和包装。各过

50、程单位用时、总用时及产品单位利润如下表：如各过程单位用时、总用时及产品单位利润如下表：如何生产使公司利润最大？何生产使公司利润最大？过程过程生产耗时生产耗时总时间总时间标准袋标准袋高档袋高档袋切割并印染切割并印染缝合缝合成型成型检查和包装检查和包装7/101/211/1015/62/31/4630600708135单位产品利润单位产品利润109解解：很很显显然然，若若设设x1、x2分分别别代代表表标标准袋和高档袋的生产数量准袋和高档袋的生产数量,则问题的数学模型为：则问题的数学模型为：maxz=10 x1+9x2 7/10 x1+x2=6301/2x1+5/6x2=600 x1+2/3x2=7