运筹学5单纯形法.ppt

第五章 单纯形法,1. 线性规划问题的解 2 单纯形法 3 求初始基的人工变量法,1.线性规划问题的解,(1) 解的基本概念,定义 在线性规划问题中，约束方程组(2)的系数矩阵A(假定 )的任意一个 阶的非奇异(可逆)的子方阵B(即 )，称为线性规划问题的一个基阵或基。,基阵,非基阵,基 向 量,非 基 向 量,基变量,非基变量,令,则,定义 在约束方程组(2) 中，对于一个选定的基B，令所有的非基变量为零得到的解，称为相应于基B的基本解。,定义 在基本解中，若该基本解满足非负约束，即 ，则称此基本解为基本可行解，简称基可行解；对应的基B称为可行基。,定义 在线性规划问题的一个基本可行解中，如果所有的基变量都取正值，则称它为非退化解，如果所有的基本可行解都是非退化解。称该问题为非退化的线性规划问题；若基本可行解中，有基变量为零，则称为退化解，该问题称为退化的线性规划问题。,基本解中最多有m个非零分量。,基本解的数目不超过 个。,非可行解,解的集合：,可行解,基本解,最优解,基本可行解,解空间,例 现有线性规划问题,试求其基本解、基本可行解并判断是否为退化解。,解: (1)首先将原问题转化为标准型 引入松弛变量x3和x4,(2) 求基本解 由上式得,可能的基阵,由于所有|B| 0,所以有6个基阵和6个基本解。,对于基阵,令,则,对于基阵,令,则,为基本可行解，B13为可行基,为基本可行解，B12为可行基,对于基阵,令,则,对于基阵,令,则,对于基阵,令,则,对于基阵,令,则,为基本可行解，B24为可行基,为基本可行解，B34为可行基,0,A,B,C,D,E,1 基本解为边界约束方程的交点； 2 基对应于可行解可行域极点； 3 相邻基本解的脚标有一个相同。,例2 现有线性规划问题,试求其基本解、基本可行解并判断是否为退化解。,解: (1)首先将原问题转化为标准型 引入松弛变量x3和x4,(2) 求基本解 由上式得,可能的基阵,由于所有|B| 0，所以有6个基阵和6个基本解。,对于基阵,令,则,对于基阵,令,则,为基本可行解，B12为可行基,为基本可行解，B13为可行基,为退化解,对于基阵,令,则,对于基阵,令,则,为基本可行解，B23为可行基,为退化解,对于基阵,令,则,对于基阵,令,则,为基本可行解，B24为可行基,为基本可行解，B34为可行基,为退化解,0,A,B,C,(2) 解的基本性质,判别可行解为基可行解的准则,定理1 线性规划问题的可行解是基可行解的充要条件是它的非零向量所对应的列向量线性无关.,线性规划问题的基本定理:定理2和定理3,定理2 线性规划问题有可行解,则它必有基可行解.,定理3 若线性规划问题有最优解,则一定存在一个基可行解是它的最优解.,定理2 线性规划问题有可行解,则它必有基可行解.,证:设 为线性规划问题的一个可行解. 若 ,则它是一个基可行解,定理成立; 若 ,则令 的前k个分量为非零分量：,若上述分量所对应的列向量 线性无关,则它是一个基可行解,定理成立; 若 线性相关，从 出发， 必可找到线性规划问题的一个基可行解。,由于 线性相关，则存在一组不全为零的数 ， 使得,假定,令,若,令,(若,令,),(*),由(*)可知,即,与 相比， 的非零分量减少1个，若对应的k-1个列向量线性无关，则即为基可行解；否则继续上述步骤，直至剩下的非零变量对应的列向量线性无关。,几点结论,若线性规划问题有可行解,则可行域是一个凸多边形或凸多面体(凸集),且仅有有限个顶点(极点); 线性规划问题的每一个基可行解都对应于可行域上的一个顶点(极点); 若线性规划问题有最优解,则最优解必可在基可行解(极点)上达到; 线性规划问题的基可行解(极点)的个数是有限的,不会超过 个.,上述结论说明: 线性规划的最优解可通过有限次运算在基可行解中获得.,2 单纯形法,例1,(1)单纯形法的引入,解：(1)、确定初始可行解,B = ( P3 P4 P5 ) = I,令X1 = X2 =0,X(1) =(0, 0, 30, 60, 24)T Z(1) =0,(2)、判定解是否最优,Z=0+40X1+50X2 当 X1 从 0 或 X2 从 0 Z 从 0, X(1) 不是最优解,(3)、由一个基可行解另一个基可行解。, 50 40 选 X2 从 0，X1 =0,X2 = min ( 30/2 , 60/2 , 24/2 ) =12 X2 ：进基变量， X5 ：出基变量。,B2=( P3 P4 P2 ), 1/2 ， 代入 式， ，,令 X1 = X5 = 0 X(2) = ( 0, 12, 6, 36, 0 )T Z(2) = 600,(2) 判断, 400 X(2)不是最优解。,(3) 选X1从0， X5 =0,X1=min( 6/1 , 36/3 , 1 ) =6 X1进基， X3出基。,B3 =(P1 P4 P2 ),令X3 =X5 =0 X(3) =(6, 12, 0, 18, 0)T Z(3) =840,(2)“ 150 X(3)不是,(3)“ 选X5从0， X3 =0,X5=min( 18/2 , 12/1/2 ) =9 X5进基， X4出基。,B4=(P1 P5 P2 ),令X3 =X4 =0 X(4) =(15, 15/2 , 0, 0 ,9 )T Z(4) =975,0,(0,0),X2,X1,X(4),X(1),X(2),X(3),Z=40X1+50X2,单纯形法小结： 单纯形法是这样一种迭代算法如下图 当Zk中非基变量的系数的系数全为负值时，这时的基本可行解Xk即是线性规划问题的最优解，迭代结束。,X1,Z1,保持单调增,保持可行性,保持可行性,保持可行性,保持可行性,保持单调增,保持单调增,保持单调增,X2,X3,.,Xk,Z2,Z3,.,Zk,当Zk 中非基变量的系数的系数全为负值时，这时的基本可行解Xk 即是线性规划问题的最优解，迭代结束。,(2) 线性规划的典则形式,标准型,上式称为线性规划问题对应于基B的典则形式，简称典式。 约束方程组的系数矩阵中含有一个单位矩阵，并以其为基； 目标函数中不含基变量，只有非基变量。,检 验 数,(3) 最优性判别定理,在线性规划问题的典式中，设 X(0)=(x1,x2,xm,0,0) 为对应于基B 的一个基可行解，若有 j 0 ( j = m+1 , m+2 , , n ) 则X(0)是线性规划问题的最优解，基B为最优基。,证：设X为线性规划问题的一个可行解，必有 X 0 ，当 j 0， 则 X 0 Z*=CX(0) = Z(0) Z(0) + X =CX 故X(0)为线性规划问题的最优解。,在线性规划问题的典式中，设 X(0)=(x1,x2,xm,0,0) 为对应于基B 的一个基可行解，若有 j 0 ( j = m+1 , m+2 , , n ) 且 j+k = 0 则线性规划问题有无穷多个最优解。,无穷多最优解判别定理,在线性规划问题的典式中，设X(0) 为对应于基B 的一个基可行解，若某一非基变量xj+k的检验数 j+k 0 且对应的列向量 Pm+k=(a1,m+k,a2,m+k,am,m+k) 0 则线性规划问题具有无界解，即无有限最优解。,无界解判别定理,(4) 基可行解改进定理,在线性规划问题的典式中，设 X(0)=(x1,x2,xm,0,0) 为对应于基B 的一个基可行解，若满足以下条件： 某个非基变量的检验数 k 0 ( m+1 k n ); aik ( i = 1,2,m )不全小于或等于零，即至少有一个 aik 0 ( 1 k m ); bi 0( I = 1 , 2,m ),即X(0)为非退化的基可行解。 则从X(0)出发，一定能找到一个新的基可行解X(1)，使得 CX(1) CX(0) 。,(5) 单纯形表,将线性规划问题典式中各变量及系数填写在一张表格中，该表即为单纯形表。,单纯形方法的矩阵表示,对应I 式的单纯形表 I 表(初始单纯形表),对应B 式的单纯形表 B 表,迭代,当CN -CBB-1N0时，即为最优单纯形表,(1)、确定初始基域初始基本可行解,列出初始单纯形表,(3)、若有j 0，Pj 全 0，停止， 没有有限最优解； 否则转 (4),(2)、对应于非基变量检验数j全小于零。 若是，停止，得到最优解； 若否，转(3)。,(6) 单纯形法的迭代步骤,定Xr为出基变量，arm+k为主元。,由最小比值法求：,Max j = m+kXm+k 进基变量,j 0,(4)、,转(2),(5)、以arm+k为中心，换基迭代,从步骤(2)-(5)的每一个循环，称为一次单纯形迭代.,单纯形表计算步骤举例 给定线性规划问题,单纯形表计算步骤举例 给定线性规划问题,Max z = 50X1 + 30X2 s.t. 4X1+ 3X2 + X3 = 120 2X1+ X2 + X4 = 50 X1， X2 ，X3 ，X4 0,120/4,50/2,( ),x1,50,1,1/2,1/2,25,0,1,-2,20,0,5,0,-25,20,50,( ),x2,30,20,0,1,1,-2,15,1,0,-1/2,3/2,0,-5,-15,1250,1350,初始单纯形表,最优单纯形表,B-1,唯一最优解,最优值,例2,达到最优状态时，若存在非基变量为零，则为有无穷多最优解,例3,可以为零,例4,例5,无法获得初始基和初始基可行解,3 求初始基的人工变量法,求解线性规划问题的单纯形法第一步就是要找到一个初始可行基并求出初始基可行解，以它作为迭代的起点。 获得初始可行基及初始基可行解的途径主要有： (1) 试算法； (2) 人工变量法。 在约束方程组中的每一个没有单位向量的约束方程中人为加入一个变量，使系数矩阵中凑成一个单位方阵，以形成一个初始可行基阵。,约束条件： a11x1 + a12x2 + + a1nxn +xn+1= b1 a21x1 + a22x2 + + a2nxn +xn+2 = b2 . . . am1x1 + am2x2 + + amnxn +xn+m = bm x1 ，x2 ， ，xn , xn+1 , , xn+m 0,s.t,人工变量,人工基,等价否？,大M法,两阶段法,大M法与二阶段法的一些说明 由于人工变量在原问题的解中是不能存在的，应尽快被迭代出去，因此人工变量在目标函数中对应的价值系数应具有惩罚性，称为罚系数。 大M法实质上与原单纯型法一样，M可看成一个很大的常数 人工变量被迭代出去后就不会再成为基变量 当检验数都满足最优条件，但基变量中仍有人工变量，说明原线性规划问题无可行解 大M法手算很不方便，因此提出了二阶段法 计算机中常用大M法 二阶段法手算可能容易,二阶段法的求解过程,第一阶段的任务是将人工变量尽快迭代出去，从而找到一个没有人工变量的基本可行解 第二阶段以第一阶段得到的基础可行解为初始解，采用原单纯型法求解 若第一阶段结束时，人工变量仍在基变量中，则原问题无（可行）解 为了简化计算，在第一阶段重新定义价值系数