第五章 单纯形法.ppt

第五章单纯形法,一、问题的提出二、单纯形法的基本思路和原理三、单纯形法的表格形式四、人工变量法五、几种特殊情况,一、问题的提出,图解法只能解决二维的线性规划问题，那更多变量的问题怎么办？(jsj)通过代数算法搜寻最优解。单纯形法，就是这样的一种代数搜寻法。线性规划问题的解一般有无穷多个，如果不缩小搜寻范围，工作量太大！我们首先将最优解缩小在一个有限的范围。,一、问题的提出,回顾图解法，我们知道：最优解必定在可行域的顶点上取得，而顶点的个数总是有限的。多维线性规划问题的可行域也存在有限个顶点。如果能够从一个顶点开始，通过某种方式向更优顶点转移，总会找到最优点。首先面临的问题：如何通过代数方法找到第一个顶点？,一、问题的提出,图解法中的例1.5模型为：Maxz=50 x1+100 x2s.t.1x1+1x23002x1+1x24000x1+1x2250 x10，x20,一、问题的提出,从其标准形的解向量开始研究：Maxz=50 x1+100 x2s.t.1x1+1x2+1x3+0x4+0x53002x1+1x2+0x3+1x4+0x54000x1+1x2+0x3+0x4+1x5250 xj0(j=1,2,3,4,5),一、问题的提出,顶点对应的解向量有何代数特征？O(0,0,300,400,250)A(0,250,50,150,0)B(50,250,0,50,0)C(100,200,0,0,50)D(200,0,100,0,50)答案：都有两个变量取值为0，且非负。,X1,X2,O(0,0),A(0,250),B(50,250),C(100,200),D(200,0),一、问题的提出,既然顶点解向量中有两个变量取值为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+x3300x1+x33002x1+x2+x44002x1+x4400 x2+x52500250？显然不能得到相应的解。,一、问题的提出,为什么令x20，x50时不能得到解？因为其余三个变量的系数列向量为该矩阵是非可逆矩阵，即去掉x2和x5后的三个约束方程线性相关，这种情况下得不到解。,一、问题的提出,既然如此，如果我们在技术矩阵中取出三列，组成一个可逆阵，令其余两列对应的变量为零，则一定可以得到一个解。,一、问题的提出,如，取1、2、3列得到：此矩阵为可逆阵，故令x40，x50，一定可以得到一个解。对应的解为（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,x5,p3,p5,x1,x2,x4,p1,p2,p4,B2=(p1,p2,p4),是,x3,x4,p3,p4,x1,x2,x5,p1,p2,p5,B3=(p1,p2,p5),是,x1,x2,p1,p2,x3,x4,x5,p3,p4,p5,B10=(p3,p4,p5),否,x1,x3,p1,p3,x2,x4,x5,p2,p4,p5,B9=(p2,p4,p5),否,x1,x4,p1,p4,x2,x3,x5,p2,p3,p5,B8=(p2,p3,p5),是,x1,x5,p1,p5,x2,x3,x4,p2,p3,p4,B7=(p2,p3,p4),否,x2,x3,p2,p3,x1,x4,x5,p1,p4,p5,B6=(p1,p4,p5),是,x2,x4,p2,p4,x1,x3,x5,p1,p3,p5,B5=(p1,p3,p5),x2,x5,p2,p5,x1,x3,x4,p1,p3,p4,B4=(p1,p3,p4),否,x4,x5,p4,p5,x1,x2,x3,p1,p2,p3,B1=(p1,p2,p3),是否可行,非基变量,非基向量,基变量,基向量,基,一、问题的提出,基本解可能可行，也可能不可行。满足非负约束条件的基本解叫基本可行解，相应的基称为可行基。否则为非可行基。,一、问题的提出,A：(0,250,50,150,0)B：(50,250,0,50,0)C：(100,200,0,0,50)D：(200,0,100,0,50)O：(0,0,300,400,250)E：(75,250,-25,0,0)F：(0,300,0,100,-50)G：(0,400,-100,0,150)H：(300,0,0,-200,-50),一、问题的提出,线性规划解的集合关系：,基本解,最优解,基本可行解,可行解,一、问题的提出,显然，将搜索范围控制在基本可行解内，将大大减少搜索工作量。但是，即使取得一个基，得到的解还不一定可行。如何才能保证取得一个可行基呢？,一、问题的提出,总结：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目标函数为Maxz=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+x5x2250-x5目标函数为Maxz=50 x1+100 x227500-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值不可能再增加。说明此基本解对应的目