第五章-单纯形法ppt课件.ppt

第五章 单纯形法一、问题的提出一、问题的提出二、单纯形法的基本思路和二、单纯形法的基本思路和原理原理三、单纯形法的表格形式三、单纯形法的表格形式四、人工变量法四、人工变量法五、几种特殊情况五、几种特殊情况一、问题的提出v图解法只能解决二维的线性规划问题，那更多图解法只能解决二维的线性规划问题，那更多变量的问题怎么办？变量的问题怎么办？(jsj)v通过代数算法搜寻最优解。通过代数算法搜寻最优解。v单纯形法，就是这样的一种代数搜寻法。单纯形法，就是这样的一种代数搜寻法。v线性规划问题的解一般有无穷多个，如果不缩线性规划问题的解一般有无穷多个，如果不缩小搜寻范围，工作量太大！小搜寻范围，工作量太大！v我们首先将最优解缩小在一个有限的范围。我们首先将最优解缩小在一个有限的范围。一、问题的提出v回顾图解法，我们知道：最优解必定在可行域的顶回顾图解法，我们知道：最优解必定在可行域的顶点上取得，而顶点的个数总是有限的。点上取得，而顶点的个数总是有限的。v多维线性规划问题的可行域也存在有限个顶点。多维线性规划问题的可行域也存在有限个顶点。v如果能够从一个顶点开始，通过某种方式向更优顶如果能够从一个顶点开始，通过某种方式向更优顶点转移，总会找到最优点。点转移，总会找到最优点。v首先面临的问题：首先面临的问题：v如何通过代数方法找到第一个顶点？如何通过代数方法找到第一个顶点？一、问题的提出图解法中的例图解法中的例1.5模型为：模型为：Max z=50 x1+100 x2 s.t.1x1+1x2300 2x1+1 x2400 0 x1+1 x2250 x1 0，x2 0一、问题的提出从其标准形的解向量开始研究：从其标准形的解向量开始研究：Max z=50 x1+100 x2 s.t.1x1+1x2+1x3+0 x4+0 x5300 2x1+1x2+0 x3+1x4+0 x5400 0 x1+1x2+0 x3+0 x4+1x5250 xj 0 (j=1,2,3,4,5)一、问题的提出v顶点对应的解向量有何代顶点对应的解向量有何代数特征？数特征？vO(0,0,300,400,250)vA(0,250,50,150,0)vB(50,250,0,50,0)vC(100,200,0,0,50)vD(200,0,100,0,50)v答案：都有两个变量取值答案：都有两个变量取值为为0，且非负。，且非负。X1X2O(0,0)A(0,250)B(50,250)C(100,200)D(200,0)一、问题的提出v既然顶点解向量中有两个变量取值为既然顶点解向量中有两个变量取值为0，而标准形中又有三个约束方程，是否，而标准形中又有三个约束方程，是否可以直接通过这种方式找顶点？可以直接通过这种方式找顶点？如令如令x10，x20，则，则x3300，x4400，x5250可得到解（可得到解（0，0，300，400，250）一、问题的提出又如：令又如：令x30，x50，由约束条件：由约束条件：x1+x2+x33002x1+x2+x4400 x2+x5250可得到解（可得到解（50，250，0，50，0）一、问题的提出若令若令x20，x50，会怎样？，会怎样？由约束方程可知：由约束方程可知：x1+x2+x3300 x1+x3300 2x1+x2+x4400 2x1+x4400 x2+x5250 0250？显然不能得到相应的解。显然不能得到相应的解。一、问题的提出为什么令为什么令x20，x50时不能得到解？时不能得到解？因为其余三个变量的系数列向量为因为其余三个变量的系数列向量为该矩阵是非可逆矩阵，即去掉该矩阵是非可逆矩阵，即去掉x2和和x5后的三个约束后的三个约束方程线性相关，这种情况下得不到解。方程线性相关，这种情况下得不到解。一、问题的提出v既然如此，如果我们在技术矩阵中取出三列，既然如此，如果我们在技术矩阵中取出三列，组成一个可逆阵，令其余两列对应的变量为组成一个可逆阵，令其余两列对应的变量为零，则一定可以得到一个解。零，则一定可以得到一个解。一、问题的提出v如，取如，取1、2、3列得到：列得到：v此矩阵为可逆阵，故令此矩阵为可逆阵，故令x40，x50，一定可，一定可以得到一个解。以得到一个解。v对应的解为（对应的解为（75，250，-25，0，0）。）。一、问题的提出基的概念：基的概念：已知已知A是约束条件的是约束条件的mn阶系数矩阵，阶系数矩阵，其秩为其秩为m。设设B是是A矩阵中的一个非奇异（可逆）的矩阵中的一个非奇异（可逆）的mm阶子矩阵，则称阶子矩阵，则称B为线性规划问题为线性规划问题的一个的一个基基。B由由A中的中的m个线性无关列向量组成。个线性无关列向量组成。一、问题的提出一个基对应一组概念：一个基对应一组概念：非基变量非基变量基变量基变量基向量基向量非基向量非基向量对应基本解：（对应基本解：（0，0，300，400，250）一、问题的提出(0,0,300,400,250)(0,300,0,100,-50)(0,400,-100,0,150)(0,250,50,150,0)(300,0,0,-200,-50)(200,0,100,0,50)不存在不存在(100,200,0,0,50)(50,250,0,50,0)(75,250,-25,0,0)基本解基本解是是x3,x5p3,p5x1,x2,x4p1,p2,p4B2=(p1,p2,p4)是是x3,x4p3,p4x1,x2,x5p1,p2,p5B3=(p1,p2,p5)是是x1,x2p1,p2x3,x4,x5p3,p4,p5B10=(p3,p4,p5)否否x1,x3p1,p3x2,x4,x5p2,p4,p5B9=(p2,p4,p5)否否x1,x4p1,p4x2,x3,x5p2,p3,p5B8=(p2,p3,p5)是是x1,x5p1,p5x2,x3,x4p2,p3,p4B7=(p2,p3,p4)否否x2,x3p2,p3x1,x4,x5p1,p4,p5B6=(p1,p4,p5)是是x2,x4p2,p4x1,x3,x5p1,p3,p5B5=(p1,p3,p5)x2,x5p2,p5x1,x3,x4p1,p3,p4B4=(p1,p3,p4)否否x4,x5p4,p5x1,x2,x3p1,p2,p3B1=(p1,p2,p3)是否可行是否可行非基非基变量变量非基非基向量向量基变量基变量基向量基向量基基一、问题的提出基本解可能可行，也可能不可行。基本解可能可行，也可能不可行。满足非负约束条件的基本解叫满足非负约束条件的基本解叫基本可行基本可行解解，相应的基称为，相应的基称为可行基可行基。否则为否则为非可行基非可行基。一、问题的提出vA：(0,250,50,150,0)vB：(50,250,0,50,0)vC：(100,200,0,0,50)vD：(200,0,100,0,50)vO：(0,0,300,400,250)vE：(75,250,-25,0,0)vF：(0,300,0,100,-50)vG：(0,400,-100,0,150)vH：(300,0,0,-200,-50)X1X2O(0,0)A(0,250)B(50,250)C(100,200)D(200,0)G(0,400)E(75,250)F(0,300)H(300,0)一、问题的提出v线性规划解的集合关系：线性规划解的集合关系：基基本本解解最最优优解解基基本本可可行行解解可可行行解解一、问题的提出v显然，将搜索范围控制在基本可行显然，将搜索范围控制在基本可行解内，将大大减少搜索工作量。解内，将大大减少搜索工作量。v但是，即使取得一个基，得到的解但是，即使取得一个基，得到的解还不一定可行。还不一定可行。v如何才能保证取得一个可行基呢？如何才能保证取得一个可行基呢？一、问题的提出总结：总结：1、可行域顶点对应的解必为基本可行解：、可行域顶点对应的解必为基本可行解：有有n-m个变量取值为个变量取值为0，满足非负条件。，满足非负条件。2、一个基对应一组基本解，可能可行，、一个基对应一组基本解，可能可行，也可能不可行；也可能不可行；3、最优解必定在基本可行解中；、最优解必定在基本可行解中；二、单纯形法的基本思路和原理单纯形法的基本思路：单纯形法的基本思路：首先找到一个顶点；首先找到一个顶点；然后判断它是否最优；然后判断它是否最优；如果不是，则通过更换顶点的方式找到如果不是，则通过更换顶点的方式找到更优的顶点；更优的顶点；直到找到最优顶点。直到找到最优顶点。二、单纯形法的基本思路和原理第一步：找到一个顶点第一步：找到一个顶点 （初始基本可行解）（初始基本可行解）二、单纯形法的基本思路和原理思考：思考：1、令、令n-m个变量为个变量为0（非基变量）是否（非基变量）是否一定可以找到？一定可以找到？答案：不一定。答案：不一定。如例中如例中x20，x50时不能得到解。时不能得到解。可行的办法：找到一个基。可行的办法：找到一个基。二、单纯形法的基本思路和原理2、一个基是否一定对应可行域顶点？、一个基是否一定对应可行域顶点？答案：不一定。必须是可行基。答案：不一定。必须是可行基。一般来说，判断一个基是否是可行基，一般来说，判断一个基是否是可行基，需要在求出其基本解后才能判断。需要在求出其基本解后才能判断。二、单纯形法的基本思路和原理3、那有没有办法在求出解之前保证我们、那有没有办法在求出解之前保证我们取得的基为可行基？取得的基为可行基？解决办法：保证解决办法：保证右端项非负右端项非负，找到一个，找到一个单位矩阵单位矩阵，必定是一个可行基。，必定是一个可行基。二、单纯形法的基本思路和原理如范例系数阵：如范例系数阵：存在存在3阶单位阵阶单位阵（初始可行基）（初始可行基）右端项非负右端项非负二、单纯形法的基本思路和原理基本可行解为基本可行解为（0，0，300，400，250）此可行基称为此可行基称为初始可行基初始可行基。对应的解称为对应的解称为初始基本可行解初始基本可行解。初始基本可行解在上页矩阵中一目了然。初始基本可行解在上页矩阵中一目了然。二、单纯形法的基本思路和原理第二步：最优性检验第二步：最优性检验二、单纯形法的基本思路和原理对应于每一组基本解，目标函数都可以对应于每一组基本解，目标函数都可以表示成非基变量的函数，称为表示成非基变量的函数，称为典式典式。如：初始基本可行解如：初始基本可行解（0，0，300，400，250）其非基变量为其非基变量为x1，x2目标函数为目标函数为Max z=50 x1+100 x2二、单纯形法的基本思路和原理典式典式Z=50 x1+100 x2如果如果x1增加增加1，Z会怎样？会怎样？答案：答案：Z增加增加50。如果如果x2的值增加的值增加1，Z会怎样？会怎样？答案：答案：Z增加增加100。二、单纯形法的基本思路和原理x1，x2的取值是否有增加的可能？的取值是否有增加的可能？分析：该解中非基变量分析：该解中非基变量 x1，x2的取值为的取值为0，其值完全有可能增加。，其值完全有可能增加。说明此时目标函数值还有增加的可能，说明此时目标函数值还有增加的可能，没有达到最优。没有达到最优。二、单纯形法的基本思路和原理再如：基本再如：基本解（解（50，250，0，50，0）其非基变量为其非基变量为x3，x5由约束方程可得：由约束方程可得：x150-x3+x5 x2250-x5目标函数为目标函数为Max z=50 x1+100 x2 27500-50 x3-50 x5二、单纯形法的基本思路和原理典式典式Z=27500-50 x3-50 x5如果如果x3增加增加1，Z会怎样？会怎样？答案：答案：Z减少减少50。如果如果x5的值增加的值增加1，Z会怎样？会怎样？答案：答案：Z减少减少50。可见要使可见要使Z增加，只有使增加，只有使x3和和x5减少。减少。二、单纯形法的基本思路和原理x3，x5的取值是否有减少的可能？的取值是否有减少的可能？分析：该解中非基变量分析：该解中非基变量 x1，x2的取值为的取值为0，其值不可能再减少。，其值不可能再减少。所以所以Z值不可能再增加。值不可能再增加。说明此基本解对应的目标函数值已经达说明此基本解对应的目标函数值已经达到最优。到最优。二、单纯形法的基本思路和原理由以上分析，可见，完全可以由典式中由以上分析，可见，完全可以由典式中的系数来判断解是否最优。的系数来判断解是否最优。如：如：Z=50 x1+100 x2系数系数0，未达到最优；，未达到最优；Z=27500-50 x3-50 x5系数系数0计算计算Qibi/aik令令Ql=min Qi 则则xl为出为出基变量，基变量，alk为主元为主元否否某非基变某非基变量检验数量检验数为零为零唯一最唯一最优解优解无无界界解解无可无可行解行解无穷多无穷多最优解最优解是是是是是是否否否否