线性规划-大M法两阶段法与几种特殊情况

.,1,1-4线性规划-大M法、两阶段法及几种特殊情况,SchoolofBusinessECUST,3.3单纯形法3.3.1单纯形法的一般思路+例子3.3.2单纯形表结构+例子3.3.3单纯形法的计算步骤3.3.4单纯形法的矩阵描述3.4大M法3.5两阶段法4几种特殊情况4.1无可行解4.2无界解4.3多重最优解4.4进基变量的相持4.5出基变量的相持,SchoolofBusinessECUST,3.4大M法一般问题的初始基本可行解,SchoolofBusinessECUST,标准化,SchoolofBusinessECUST,添加人工变量,SchoolofBusinessECUST,添加人工变量,SchoolofBusinessECUST,SchoolofBusinessECUST,解：首先将原LP问题转化为标准型，引入非负变量x3，x4，x5,例：考虑下面的LP问题,SchoolofBusinessECUST,系数矩阵：,初始可行基？,大M法：构造一个单位矩阵来作初始可行基,如何构造？,通过添加人工变量,SchoolofBusinessECUST,添加人工变量x6,x7,SchoolofBusinessECUST,添加人工变量之后，系数矩阵变为：,单位矩阵，可作初始可行基,变量x6,x7是为了构造单位阵，而人为增加的，要保证最优解满足原约束，在问题的最优解中，这两个变量必须取0值。为了达到这种效果，我们将目标函数改写为：,其中，M为充分大的正数,显然，为了保证Z取最大值，x6,x7必然取0,SchoolofBusinessECUST,为什么可以这样转化？,=0,=0,原问题的最优解,SchoolofBusinessECUST,-,01-1/2-1/201/21/2,3/2,X2,2,10-1/21/201/2-1/2,1/2,X1,-1,-,-110-1001,1,X2,2,1/2,20-1101-1,1,X6,-M,1/1,-110-1001,1,X7,-M,2/1,11-10010,2,X6,-M,001/23/20-1/2-M-3/2-M,j,001/21/21-1/2-1/2,3/2,X5,0,1+2M0-M2+M00-2-2M,j,2/1,100110-1,2,X5,0,-12+2M-M-M000,j,3/1,0100100,3,X5,0,X1x2x3x4x5x6x7,b,XB,CB,-12000-M-M,C,0100100,3,X2,2,100110-1,2,X4,0,11-10010,2,X2,2,20-1101-1,1,X4,0,-,01-1/2-1/201/21/2,3/2,X2,2,1/2/1/2,10-1/21/201/2-1/2,1/2,X1,-1,-1000-2-M-M,j,-10101-10,1,X3,0,-30200-2-M-M,j,-10101-10,1,X5,0,001/23/20-1/2-M-3/2-M,j,3/2/1/2,001/21/21-1/2-1/2,3/2,X5,0,X1x2x3x4x5x6x7,b,XB,CB,-12000-M-M,C,最优解最优值,大M法的基本步骤,通过加入人工变量，构造初始可行基；在目标函数中赋予人工变量很大的罚系数M，建立辅助线性规划问题；利用单纯形法，求解上述辅助线性规划问题，若：有最优解：如果最优解的基变量中不含有非零人工变量，则最优解中剔除掉人工变量部分，构成原问题的最优解；如果最优解的基变量中仍含有非零人工变量，则原问题无可行解；无界解：如果最终单纯形表中基变量不含有非零人工变量，则原问题为无界解；否则，如果最终单纯形表中基变量含有非零人工变量，则原问题为无可行解。,例：求解下列线性规划问题,引入人工变量，并利用大M法求解,解：首先将问题化为标准型,C,-3-2-1000-M-M,CB,XB,b,x1x2x3x4x5x6x7x8,0-M-M,x4x7x8,643,1111000010-10-101001-100-101,6/1-3/1,Z,-3+M-2+M-1-2M0-M-M00,0-M-2,x4x7x2,343,1021010-110-10-101001-100-101,3/14/1-,Z,Z,-3+M0-3-M0-M-202-M,-3-M-2,x1x7x2,313,1021010-100-3-1-1-11101-100-101,003-3M3-M-M1-M0-1,在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人工变量x7=1为基变量，所以原线性规划不存在可行解。,例求解下列线性规划问题：,变标准型,添加人工变量利用大M法,C,x1x2x3x4x5x6,1-100-M-M,0.51-10104,110-1013,XB,x5x6,CB,-M-M,1+1.5M2M-1-M-M00,b,4/13/1,-0.50-111-11,110-1013,x5x2,-M-1,1/1-,2-0.5M0-M-1+M01-2M,-0.50-111-11,0.51-10104,x4x2,0-1,-4/0.5,1.50-101-M-M,-0.50-111-1,0.51-1010,x4x2,0-1,14,-4/0.5,1.50-101-M-M,C,x1x2x3x4x5x6,1-100-M-M,XB,CB,b,01-212-15,12-20208,x4x1,01,0-320-M-2-M,非基变量x3对应的检验数0,并且该非基变量对应的系数列向量的全部系数0，技术系数均0,SchoolofBusinessECUST,4.3无穷多（多重）最优解,SchoolofBusinessECUST,当前基本可行解：(0,0,150,20,300),Z=0,SchoolofBusinessECUST,当前基本可行解：(75/2,0,75/2,20,0),Z=300,SchoolofBusinessECUST,当前基本可行解：(30,12,0,8,0),Z=300,SchoolofBusinessECUST,无穷多最优解的判别准则,所有检验数存在非基变量，检验数=0,SchoolofBusinessECUST,解的判别：若是对应于基Bk=(P1,P2,.,Pm)的基可行解，对于一切j=m+1,.,n,均有检验数，则为最优解；若是对应于基Bk=(P1,P2,.,Pm)的基可行解，对于一切j=m+1,.,n,均有检验数，并且存在某个非基变量(比如xm+r)的检验数，则该线性规划问题有无穷多最优解；若是对应于基Bk=(P1,P2,.,Pm)的基可行解，若存在某个非基变量(比如xm+r)的检验数，并且对i=1,2,m,均有，则该线性规划问题有无界解(无最优解)。,SchoolofBusinessECUST,利用大M法，求解辅助线性规划问题，若：有最优解：如果最优解的基变量中不含有非零人工变量，则最优解中剔除掉人工变量部分，构成原问题的最优解；如果最优解的基变量中仍含有非零人工变量，则原问题无可行解；无界解：如果最终单纯形表中基变量不含有非零人工变量，则原问题为无界解；否则，如果最终单纯形表中基变量含有非零人工变量，则原问题为无可行解。,4.4进基变量的相持,当进基变量发生相持的情况时，可任意选择其中一个非基变量进基。,4.5出基变量的相