《管理运筹学》02-4两阶段法和大m法

第二节单纯形法,SimplexMethod,一、单纯形法原理及步骤二、用向量矩阵描述单纯形法原理三、单纯形表四、两阶段法和大M法五、退化和循环,两阶段法和大M法,当不能通过转化标准形式使约束方程系数矩阵中出现单位矩阵时，此时可以通过添加人工变量的方法，人为地使系数矩阵中出现一个单位矩阵，以它作为初始可行基。例如:设一线性规划问题的约束为人工变量法有两种方法：两阶段法和大M法。,引进变量X4,X5,基中不包含单位矩阵，因此无法直接获得初始可行基。,两阶段法和大M法,X=(x1,x2,xn)T,引进人工变量Xa=(xn+1,xn+2,xn+m)T,基础可行解X=0,Xa=b,非原问题的基础可行解,两阶段法和大M法,基本思想：人造解X0不是原LP问题的基本可行解。但若能通过单纯形法的迭代步骤，将虚拟的人工变量都替换出去，都变为非基变量（即人工变量xn+1=xn+2=xn+m=0），则X0的前n个分量就构成原LP问题的一个基本可行解。反之，若经过迭代，不能把人工变量都变为非基变量，则表明原LP问题无可行解。,两阶段法和大M法,两阶段法阶段求解辅助问题,构造辅助问题,(1)若辅助问题的最优基B全部在A中，即Xa全部是非基变量（minz=0），则B为原问题的一个可行基。转阶段;(2)若辅助问题的最优目标函数值minz0，则至少有一个人工变量留在第一阶段问题最优解的基变量中，这时原问题无可行解。,两阶段法和大M法,阶段求解原问题以阶段的最优基B作为原问题的初始可行基，求解原问题，得到原问题的最优基和最优解。,例1求解以下线性规划问题。,两阶段法和大M法,引进松弛变量x3，x4，x50，得到,增加人工变量x6，x70，构造辅助问题，并进入第一阶段求解。,两阶段法和大M法,标准化并写出辅助问题的系数矩阵表：,消去目标函数中基变量x6、x7的系数，得到初始单纯形表并进行单纯形变换：,x2进基,X7离基,Cj0000011,两阶段法和大M法,x1进基,X6离基,第一阶段最优，z=0,Cj0000011,-,两阶段法和大M法,在第一阶段最优单纯形表换入原问题的目标函数，去掉人工变量x6、x7以及相应的列，得到第二阶段的系数矩阵表：,消去基变量x1、x2在目标函数中的系数，得到第二阶段问题的单纯形表：,x4进基,X1离基,Cj-12000,两阶段法和大M法,x3进基,X5离基,问题的最优解为X=(x1,x2,x3,x4,x5)T=(0,3,1,2,0)T，maxz=6，即minz=-6。,Cj-12000,两阶段法和大M法,第一阶段：在原问题的可行域外部进行基变换，第一阶段结束后进入可行域,第二阶段：从可行域内部的的一个极点B（原问题的一个可行基）开始，在可行域内部进行基变换,基迭代路线,两阶段法和大M法,大M法的基本步骤如下：（1）引进松弛变量，使约束条件成为等式；（2）如果约束条件的系数矩阵中不存在一个单位矩阵，则引进人工变量；（3）在原目标函数中，加上人工变量，每个人工变量的系数为一个充分大的正数M；（4）用单纯形表求解以上问题，如果这个问题的最优解中有人工变量是基变量，则原问题无可行解。如果最优解中所有人工变量都离基，则得到原问题的最优解。,两阶段法和大M法,例2求解以下线性规划问题。,引进松弛变量x4，x5并标准化,两阶段法和大M法,引进人工变量x6，x70，在目标函数中增加人工变量,列出系数矩阵表,两阶段法和大M法,消去基变量x6、x7在目标函数中的系数,x1进基,X6离基,x3进基,X7离基,Cj-2-3-100-M-M,两阶段法和大M法,已获得最优解，最优解为：（x1，x2，x3，x4，x5，x6，x7）(8，0，16，0，0，0，0)，maxz=-32，即minz=32,Cj-2-3-100-M-M,退化和循环,定义2-6设B是线性规划的一个可行基，XB=B-1b=(xB1,xB2,xBi,xBm)T是这个基础解中的基变量。如果其中至少有一个分量xBi=0(i=1,2,m)，则称此基础可行解是退化的。,退化的结构对单纯形迭代会有不利的影响。当迭代进入一个退化极点时，可能出现以下情况：(1)进行进基、离基变换后，虽然改变了基，但没有改变极点，目标函数当然也不会改进。进行若干次基变换后，才脱离退化极点，进入其他极点。这种情况会增加叠代次数，使单纯形法收敛的速度减慢。(2)在十分特殊的情况下，退化会出现基的循环，一旦出现这样的情况，单纯形叠代将永远停留在同一极点上，因而无法求得最优解。,退化和循环,对此，Bland提出了一个避免循环的方法，在选择进基变量和离基变量时作了以下规定：（1）在选择进基变量时，在所有检验数zj-cj0的非基变量中选取下标最小的进基；（2）当有多个变量同时可作为离基变量时，选择下标最小的那个变量离基。这样就可以避免出现循环。当然，用Bland的方法，由于选取进基变量时不再考虑检验数zj-cj绝对值的大小，将会导致收敛速度的降