《线性规划-大M法、两阶段法与几种特殊情况.ppt》由会员分享，可在线阅读，更多相关《线性规划-大M法、两阶段法与几种特殊情况.ppt（50页珍藏版）》请在三一办公上搜索。
1、1,1-4 线性规划-大M法、两阶段法及几种特殊情况,School of BusinessECUST,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 出基变量的相持,3,3.4 大M法一般问题的初始基本可行解,4,标准化,5,添加人工变量,6,添加人工变量,7,School of BusinessECUST,解：首先将原LP问题转化为标准型，引入非负变量x3
2、，x4，x5,例：考虑下面的LP问题,School of BusinessECUST,系数矩阵：,初始可行基？,大M法：构造一个单位矩阵来作初始可行基,如何构造？,通过添加人工变量,School of BusinessECUST,添加人工变量x6,x7,School of BusinessECUST,添加人工变量之后，系数矩阵变为：,单位矩阵，可作初始可行基,变量x6,x7是为了构造单位阵，而人为增加的，要保证最优解满足原约束，在问题的最优解中，这两个变量必须取0值。为了达到这种效果，我们将目标函数改写为：,其中，M为充分大的正数,显然，为了保证Z取最大值，x6,x7必然取0,School o
3、f BusinessECUST,为什么可以这样转化？,=0,=0,原问题的最优解,School of BusinessECUST,-,0 1-1/2-1/2 0 1/2 1/2,3/2,X2,2,1 0-1/2 1/2 0 1/2-1/2,1/2,X1,-1,-,-1 1 0-1 0 0 1,1,X2,2,1/2,2 0-1 1 0 1-1,1,X6,-M,1/1,-1 1 0-1 0 0 1,1,X7,-M,2/1,1 1-1 0 0 1 0,2,X6,-M,0 0 1/2 3/2 0-1/2-M-3/2-M,j,0 0 1/2 1/2 1-1/2-1/2,3/2,X5,0,1+2M 0-M
4、 2+M 0 0-2-2M,j,2/1,1 0 0 1 1 0-1,2,X5,0,-1 2+2M-M-M 0 0 0,j,3/1,0 1 0 0 1 0 0,3,X5,0,X1 x2 x3 x4 x5 x6 x7,b,XB,CB,-1 2 0 0 0-M-M,C,0 1 0 0 1 0 0,3,X2,2,1 0 0 1 1 0-1,2,X4,0,1 1-1 0 0 1 0,2,X2,2,2 0-1 1 0 1-1,1,X4,0,-,0 1-1/2-1/2 0 1/2 1/2,3/2,X2,2,1/2/1/2,1 0-1/2 1/2 0 1/2-1/2,1/2,X1,-1,-1 0 0 0-2-
5、M-M,j,-1 0 1 0 1-1 0,1,X3,0,-3 0 2 0 0-2-M-M,j,-1 0 1 0 1-1 0,1,X5,0,0 0 1/2 3/2 0-1/2-M-3/2-M,j,3/2/1/2,0 0 1/2 1/2 1-1/2-1/2,3/2,X5,0,X1 x2 x3 x4 x5 x6 x7,b,XB,CB,-1 2 0 0 0-M-M,C,最优解 最优值,大M法的基本步骤,通过加入人工变量，构造初始可行基；在目标函数中赋予人工变量很大的罚系数M，建立辅助线性规划问题；利用单纯形法，求解上述辅助线性规划问题，若：有最优解：如果最优解的基变量中不含有非零人工变量，则最优解中剔
6、除掉人工变量部分，构成原问题的最优解；如果最优解的基变量中仍含有非零人工变量，则原问题无可行解；无界解：如果最终单纯形表中基变量不含有非零人工变量，则原问题为无界解；否则，如果最终单纯形表中基变量含有非零人工变量，则原问题为无可行解。,例：求解下列线性规划问题,引入人工变量，并利用大M法求解,解：首先将问题化为标准型,C,-3-2-1 0 0 0-M-M,CB,XB,b,x1 x2 x3 x4 x5 x6 x7 x8,0-M-M,x4x7x8,643,1 1 1 1 0 0 0 01 0-1 0-1 0 1 00 1-1 0 0-1 0 1,6/1-3/1,Z,-3+M-2+M-1-2M 0-
7、M-M 0 0,0-M-2,x4x7x2,343,1 0 2 1 0 1 0-11 0-1 0-1 0 1 00 1-1 0 0-1 0 1,3/14/1-,Z,Z,-3+M 0-3-M 0-M-2 0 2-M,-3-M-2,x1x7x2,313,1 0 2 1 0 1 0-10 0-3-1-1-1 1 10 1-1 0 0-1 0 1,0 0 3-3M 3-M-M 1-M 0-1,在以上最优单纯形表中，所有非基变量检验数都小于零，但在该表中人工变量x7=1为基变量，所以原线性规划不存在可行解。,例 求解下列线性规划问题：,变标准型,添加人工变量利用大M法,C,x1 x2 x3 x4 x5 x
8、6,1-1 0 0-M-M,0.5 1-1 0 1 0 4,1 1 0-1 0 1 3,XB,x5x6,CB,-M-M,1+1.5M 2M-1-M-M 0 0,b,4/13/1,-0.5 0-1 1 1-1 1,1 1 0-1 0 1 3,x5x2,-M-1,1/1-,2-0.5M 0-M-1+M 0 1-2M,-0.5 0-1 1 1-1 1,0.5 1-1 0 1 0 4,x4x2,0-1,-4/0.5,1.5 0-1 0 1-M-M,-0.5 0-1 1 1-1,0.5 1-1 0 1 0,x4x2,0-1,14,-4/0.5,1.5 0-1 0 1-M-M,C,x1 x2 x3 x4
9、x5 x6,1-1 0 0-M-M,XB,CB,b,0 1-2 1 2-1 5,1 2-2 0 2 0 8,x4x1,0 1,0-3 2 0-M-2-M,非基变量x3对应的检验数0,并且该非基变量对应的系数列向量的全部系数=0,辅助线性规划问题无界解,原问题无界解,3.5 两阶段法,大M法实际上是利用单纯形法直接求解原问题的辅助线性规划问题，然后再根据最终能否将人工变量全部赶出基变量，来判断原问题和辅助线性规划问题之间解的对应关系。两阶段法则将原线性规划问题的求解分为两个阶段：第一阶段，寻找原问题的初始基可行解或判断原问题无可行解；第二阶段，寻找原问题最优解或判断原问题无界。,第一阶段，寻找原
10、问题的初始基可行解或判断原问题无可行解；在原线性规划问题中引入人工变量后，构造一个新的线性规划问题(辅助问题)，其中系数矩阵中包含单位阵，目标函数是极小化人工变量之和(为了使人工变量取0值)；用单纯形方法求解辅助问题，若求得的基可行解可使目标函数达到最小值0(人工变量均取0)，则我们就找到了原问题的初始基可行解；若辅助问题的目标函数不能达到最小值0，则原问题无可行解，求解过程结束。,第二阶段，寻找原问题的最优解或或判断原问题无界。在第一阶段得到的最终单纯形表基础上，划去人工变量所在的列，引入原问题的目标函数，对原问题进行求解。,School of BusinessECUST,例：用两阶段法求解
11、线性规划问题。解：首先将问题化为标准型添加人工变量x6,x7,构造辅助线性规划如下：,School of BusinessECUST,0 1-1/2-1/2 0 1/2 1/2,3/2,X2,0,1 0-1/2 1/2 0 1/2-1/2,1/2,X1,0,-,-1 1 0-1 0 0 1,1,X2,0,1/2,2 0-1 1 0 1-1,1,X6,-1,1/1,-1 1 0-1 0 0 1,1,X7,-1,2/1,1 1-1 0 0 1 0,2,X6,-1,0 0 0 0 0-1-1,0 0 1/2 1/2 1-1/2-1/2,3/2,X5,0,2 0-1 1 0 0-2,2/1,1 0 0
12、 1 1 0-1,2,X5,0,0 2-1-1 0 0 0,3/1,0 1 0 0 1 0 0,3,X5,0,x1 x2 x3 x4 x5 x6 x7,b,XB,CB,0 0 0 0 0-1-1,C,辅助问题的最优解：,School of BusinessECUST,于是我们找到了原问题的一个基可行解,由上表可知，通过若干次初等行变换，原问题的约束方程组已变换成包含一个单位矩阵的约束方程组该约束方程组可作为第二阶段初始约束方程组，将目标函数则还原成原问题的目标函数，可继续利用单纯形表求解。,School of BusinessECUST,-1 0 0 0-2,1 0 0 1 1 0 1 0 0
13、 1-1 0 1 0 1,231,X4X2X3,020,-3 0 2 0 0,2 0-1 1 0 1 1-1 0 0-1 0 1 0 1,121,X4X2X5,020,0 0 1/2 3/2 0,1/2/1/2-3/2/1/2,1 0-1/2 1/2 0 0 1-1/2-1/2 0 0 0 1/2 1/2 1,1/23/23/2,X1X2X5,-120,x1 x2 x3 x4 x5,b,XB,CB,-1 2 0 0 0,C,可得最优解，目标函数值maxZ=6，与用大M法的结果完全相同。,4 单纯形法计算中的几个特殊情况,4.1 无可行解(可行域为空集)在用大M法计算过程中，判断问题达到最优解或
14、无界解之后，在基变量中仍含有非零的人工变量；在用两阶段法计算过程中，第一阶段的辅助问题无法使目标函数值达到零，即基变量中存在非零的人工变量。4.2 无界解存在某个非基变量的检验数大于零，而该非基变量的系数矩阵列的所有元素均小于等于零。,4.3 多重最优解所有非基变量的检验数均小于等于零，并且至少存在一个非基变量的检验数等于零。4.4 进基变量的相持4.5 出基变量的相持,31,4.1无可行解,32,当前基本可行解：(0,0,0,3,4),Z=-4M,33,当前基本可行解：(0,3,0,0,1),Z=-M-3,34,无可行解的判别准则,最优解时，人工变量仍为基变量，且人工变量不为,35,4.2
15、无界解,36,当前基本可行解：(0,0,0,0,4,3),Z=-7M,37,当前基本可行解：(0,3,0,0,1),Z=-M-3,38,当前基本可行解：(0,4,0,1,0),Z=-4,39,当前基本可行解：(8,0,0,5,0),Z=8,40,无界解的判别准则,存在非基变量，检验数0，技术系数均 0,41,4.3 无穷多（多重）最优解,42,当前基本可行解：(0,0,150,20,300),Z=0,43,当前基本可行解：(75/2,0,75/2,20,0),Z=300,44,当前基本可行解：(30,12,0,8,0),Z=300,45,无穷多最优解的判别准则,所有检验数存在非基变量，检验数=
16、0,School of BusinessECUST,解的判别：若 是对应于基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,均有，则该线性规划问题有无界解(无最优解)。,利用大M法，求解辅助线性规划问题，若：有最优解：如果最优解的基变量中不含有非零
17、人工变量，则最优解中剔除掉人工变量部分，构成原问题的最优解；如果最优解的基变量中仍含有非零人工变量，则原问题无可行解；无界解：如果最终单纯形表中基变量不含有非零人工变量，则原问题为无界解；否则，如果最终单纯形表中基变量含有非零人工变量，则原问题为无可行解。,School of BusinessECUST,4.4 进基变量的相持,当进基变量发生相持的情况时，可任意选择其中一个非基变量进基。,4.5 出基变量的相持,出基变量的相持,当发生出基变量相持的情况时，会产生退化解，从而导致中间的若干步换基迭代过程不能使目标函数值改善的情况，但最终一般仍可以得到最优解。在极少数的情况下，出现退化解时，采用单纯形法迭代会陷入死循环，即数次迭代之后，又回到某个已经到达过的基本可行解。对于这种情况，处理的方法有：摄动法字典序法 Bland规则,
