(精品)第五章单纯形法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五章 单纯形法,一、问题的提出,二、单纯形法的基本思路和原理,三、单纯形法的表格形式,四、人工变量法,五、几种特殊情况,一、问题的提出,图解法只能解决二维的线性规划问题，那更多变量的问题怎么办？,(jsj),通过代数算法搜寻最优解。,单纯形法，就是这样的一种代数搜寻法。,线性规划问题的解一般有无穷多个，如果不缩小搜寻范围，工作量太大！,我们首先将最优解缩小在一个有限的范围。,一、问题的提出,回顾图解法，我们知道：最优解必定在可行域的顶点上取得，而顶点的个数总是有限的。,多维线性规划问题的可行域也存在有限个顶点。,如果能够从一个顶点开始，通过某种方式向更优顶点转移，总会找到最优点。,首先面临的问题：,如何通过代数方法找到第一个顶点？,一、问题的提出,图解法中的例,1.5,模型为：,Max z= 50x,1,+100 x,2,s.t,. 1x,1,+1x,2,300 2x,1,+1 x,2,400 0x,1,+1 x,2,250 x,1,0,，,x,2,0,一、问题的提出,从其标准形的解向量开始研究：,Max z= 50x,1,+100 x,2,s.t,. 1x,1,+1x,2,+1x,3,+0x,4,+0x,5,300 2x,1,+1x,2,+0x,3,+1x,4,+0x,5,400 0x,1,+1x,2,+0x,3,+0x,4,+1x,5,250,x,j,0 (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,，且非负。,X,1,X,2,O(0,0),A(0,250),B(50,250),C(100,200),D(200,0),一、问题的提出,既然顶点解向量中有两个变量取值为,0,，而标准形中又有三个约束方程，是否可以直接通过这种方式找顶点？,如令,x,1,0,，,x,2,0,，则,x,3,300,，,x,4,400,，,x,5,250,可得到解（,0,，,0,，,300,，,400,，,250,）,一、问题的提出,又如：令,x,3,0,，,x,5,0,，,由约束条件：,x,1,+x,2,+x,3,300,2x,1,+x,2,+x,4,400,x,2,+x,5,250,可得到解（,50,，,250,，,0,，,50,，,0,）,一、问题的提出,若令,x,2,0,，,x,5,0,，会怎样？,由约束方程可知：,x,1,+x,2,+x,3,300 x,1,+x,3,300,2x,1,+x,2,+x,4,400 2x,1,+x,4,400,x,2,+x,5,250 0,250,？,显然不能得到相应的解。,一、问题的提出,为什么令,x,2,0,，,x,5,0,时不能得到解？,因为其余三个变量的系数列向量为,该矩阵是非可逆矩阵，即去掉,x,2,和,x,5,后的三个约束方程线性相关，这种情况下得不到解。,一、问题的提出,既然如此，如果我们在技术矩阵中取出三列，组成一个可逆阵，令其余两列对应的变量为零，则一定可以得到一个解。,一、问题的提出,如，取,1,、,2,、,3,列得到：,此矩阵为可逆阵，故令,x,4,0,，,x,5,0,，一定可以得到一个解。,对应的解为（,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),基本解,是,x,3,x,5,p,3,p,5,x,1,x,2,x,4,p,1,p,2,p,4,B,2,=(,p,1,p,2,p,4,),是,x,3,x,4,p,3,p,4,x,1,x,2,x,5,p,1,p,2,p,5,B,3,=(,p,1,p,2,p,5,),是,x,1,x,2,p,1,p,2,x,3,x,4,x,5,p,3,p,4,p,5,B,10,=(,p,3,p,4,p,5,),否,x,1,x,3,p,1,p,3,x,2,x,4,x,5,p,2,p,4,p,5,B,9,=(,p,2,p,4,p,5,),否,x,1,x,4,p,1,p,4,x,2,x,3,x,5,p,2,p,3,p,5,B,8,=(,p,2,p,3,p,5,),是,x,1,x,5,p,1,p,5,x,2,x,3,x,4,p,2,p,3,p,4,B,7,=(,p,2,p,3,p,4,),否,x,2,x,3,p,2,p,3,x,1,x,4,x,5,p,1,p,4,p,5,B,6,=(,p,1,p,4,p,5,),是,x,2,x,4,p,2,p,4,x,1,x,3,x,5,p,1,p,3,p,5,B,5,=(,p,1,p,3,p,5,),x,2,x,5,p,2,p,5,x,1,x,3,x,4,p,1,p,3,p,4,B,4,=(,p,1,p,3,p,4,),否,x,4,x,5,p,4,p,5,x,1,x,2,x,3,p,1,p,2,p,3,B,1,=(,p,1,p,2,p,3,),是否可行,非基变量,非基向量,基变量,基向量,基,一、问题的提出,基本解可能可行，也可能不可行。,满足非负约束条件的基本解叫,基本可行解,，相应的基称为,可行基,。,否则为,非可行基,。,一、问题的提出,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),X,1,X,2,O(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),一、问题的提出,线性规划解的集合关系：,基本解,最优解,基本可行解,可行解,一、问题的提出,显然，将搜索范围控制在基本可行解内，将大大减少搜索工作量。,但是，即使取得一个基，得到的解还不一定可行。,如何才能保证取得一个可行基呢？,一、问题的提出,总结：,1,、可行域顶点对应的解必为基本可行解：有,n-m,个变量取值为,0,，满足非负条件。,2,、一个基对应一组基本解，可能可行，也可能不可行；,3,、最优解必定在基本可行解中；,二、单纯形法的基本思路和原理,单纯形法的基本思路：,首先找到一个顶点；,然后判断它是否最优；,如果不是，则通过更换顶点的方式找到更优的顶点；,直到找到最优顶点。,二、单纯形法的基本思路和原理,第一步：找到一个顶点,（初始基本可行解）,二、单纯形法的基本思路和原理,思考：,1,、令,n-m,个变量为,0,（非基变量）是否一定可以找到？,答案：不一定。,如例中,x,2,0,，,x,5,0,时不能得到解。,可行的办法：找到一个基。,二、单纯形法的基本思路和原理,2,、一个基是否一定对应可行域顶点？,答案：不一定。必须是可行基。,一般来说，判断一个基是否是可行基，需要在求出其基本解后才能判断。,二、单纯形法的基本思路和原理,3,、那有没有办法在求出解之前保证我们取得的基为可行基？,解决办法：保证,右端项非负,，找到一个,单位矩阵,，必定是一个可行基。,二、单纯形法的基本思路和原理,如范例系数阵：,存在,3,阶单位阵（初始可行基）,右端项非负,二、单纯形法的基本思路和原理,基本可行解为,（,0,，,0,，,300,，,400,，,250,）,此可行基称为,初始可行基,。,对应的解称为,初始基本可行解,。,初始基本可行解在上页矩阵中一目了然。,二、单纯形法的基本思路和原理,第二步：最优性检验,二、单纯形法的基本思路和原理,对应于每一组基本解，目标函数都可以表示成非基变量的函数，称为,典式,。,如：初始基本可行解,（,0,，,0,，,300,，,400,，,250,）,其非基变量为,x,1,，,x,2,目标函数为,Max z= 50x,1,+100 x,2,二、单纯形法的基本思路和原理,典式,Z= 50x,1,+100 x,2,如果,x,1,增加,1,，,Z,会怎样？,答案：,Z,增加,50,。,如果,x,2,的值增加,1,，,Z,会怎样？,答案：,Z,增加,100,。,二、单纯形法的基本思路和原理,x,1,，,x,2,的取值是否有增加的可能？,分析：该解中非基变量,x,1,，,x,2,的取值为,0,，其值完全有可能增加。,说明此时目标函数值还有增加的可能，没有达到最优。,二、单纯形法的基本思路和原理,再如：基本,解（,50,，,250,，,0,，,50,，,0,）,其非基变量为,x,3,，,x,5,由约束方程可得：,x,1,50-x,3,+x,5,x,2,250 -x,5,目标函数为,Max z= 50x,1,+100 x,2,27500-50x,3,-50x,5,二、单纯形法的基本思路和原理,典式,Z= 27500-50x,3,-50x,5,如果,x,3,增加,1,，,Z,会怎样？,答案：,Z,减少,50,。,如果,x,5,的值增加,1,，,Z,会怎样？,答案：,Z,减少,50,。,可见要使,Z,增加，只有使,x,3,和,x,5,减少。,二、单纯形法的基本思路和原理,x,3,，,x,5,的取值是否有减少的可能？,分析：该解中非基变量,x,1,，,x,2,的取值为,0,，其值不可能再减少。,所以,Z,值不可能再增加。,说明此基本解对应的目标函数值已经达到最优。,二、单纯形法的基本思路和原理,由以上分析，可见，完全可以由典式中的系数来判断解是否最优。,如：,Z= 50x,1,+100 x,2,系数,0,，未达到最优；,Z= 27500-50x,3,-50x,5,系数,0,计算,Q,i,b,i,/,a,ik,令,Q,l,=min,Q,i,则,x,l,为出基变量，,a,lk,为主元,否,某非基变量检验数为零,唯一最优解,无界解,无可行解,无穷多最优解,是,是,是,否,否,