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

线性规划大M法两阶段法与几种特殊情况o3.3 单纯形法形法 o 3.3.1 单纯形法的一般思路形法的一般思路+例子例子o 3.3.2 单纯形表形表结构构+例子例子o 3.3.3 单纯形法的形法的计算步算步骤o 3.3.4 单纯形法的矩形法的矩阵描述描述o 3.4 大大M法法o 3.5 两两阶段法段法o4 几种特殊情况几种特殊情况o 4.1 无可行解无可行解o 4.2 无界解无界解o 4.3 多重最多重最优解解o 4.4 进基基变量的相持量的相持o 4.5 出基出基变量的相持量的相持23.4 3.4 大大M M法法一般一般问题的初始基本可行解的初始基本可行解 maxz=4x1+2x2-3x3+5x4s.t.2x1-x2+x3+2x450(1)3x1-x3+2x480(2)x1+x2+x4=60(3)x1,x2,x3,x403标准化准化 maxz=4x1+2x2-3x3+5x4s.t.2x1-x2+x3+2x4x5=50(1)3x1-x3+2x4+x6=80(2)x1+x2+x4=60(3)x1,x2,x3,x4,x5,x604添加人工添加人工变量量 maxz=4x1+2x2-3x3+5x4-Mx7-Mx8s.t.2x1-x2+x3+2x4x5+x7=50(1)3x1-x3+2x4+x6=80(2)x1+x2+x4x8=60(3)x1,x2,x3,x4,x5,x6,x7,x805添加人工添加人工变量量 minz=4x1+2x2-3x3+5x4+Mx7+Mx8s.t.2x1-x2+x3+2x4x5+x7=50(1)3x1-x3+2x4+x6=80(2)x1+x2+x4x8=60(3)x1,x2,x3,x4,x5,x6,x7,x8067解：首先将原LP问题转化为标准型，引入非负变量x3，x4，x5例：考虑下面的LP问题8系数矩阵：初始可行基？初始可行基？大大M法：构造一个法：构造一个单位矩位矩阵来作初始可行基来作初始可行基如何构造？如何构造？通通过添加人工添加人工变量量9添加人工变量x6,x710添加人工变量之后，系数矩阵变为：单位矩位矩阵，可作初始可行基可作初始可行基变量x6,x7是为了构造单位阵，而人为增加的，要保证最优解满足原约束，在问题的最优解中，这两个变量必须取0值。为了达到这种效果，我们将目标函数改写为：其中，M为充分大的正数显然，为了保证Z取最大值，x6,x7必然取011为什么可以什么可以这样转化？化？=0=0原原问题的最的最优解解12-0 1 -1/2 -1/2 0 1/2 1/23/2X22 1 0 -1/2 1/2 0 1/2 -1/21/2X1-1-1 1 0 -1 0 0 11X221/2 2 0 -1 1 0 1 -11X6-M1/1 -1 1 0 -1 0 0 11X7-M2/1 1 1 -1 0 0 1 02X6-M 0 0 1/2 3/2 0 -1/2-M -3/2-Mj 0 0 1/2 1/2 1 -1/2 -1/23/2X50 1+2M 0 -M 2+M 0 0 -2-2Mj2/1 1 0 0 1 1 0 -12X50 -1 2+2M -M -M 0 0 0j3/1 0 1 0 0 1 0 03X50 X1 x2 x3 x4 x5 x6 x7bXBCB -1 2 0 0 0 -M -MC13 0 1 0 0 1 0 03X22 1 0 0 1 1 0 -12X40 1 1 -1 0 0 1 02X22 2 0 -1 1 0 1 -11X40-0 1 -1/2 -1/2 0 1/2 1/23/2X221/2/1/2 1 0 -1/2 1/2 0 1/2 -1/21/2X1-1 -1 0 0 0 -2 -M -Mj -1 0 1 0 1 -1 01X30 -3 0 2 0 0 -2-M -Mj -1 0 1 0 1 -1 01X50 0 0 1/2 3/2 0 -1/2-M -3/2-Mj3/2/1/2 0 0 1/2 1/2 1 -1/2 -1/23/2X50 X1 x2 x3 x4 x5 x6 x7bXBCB -1 2 0 0 0 -M -MC最最优解解 最最优值大M法的基本步骤o通过加入人工变量，构造初始可行基；o在目标函数中赋予人工变量很大的罚系数M，建立辅助线性规划问题；o利用单纯形法，求解上述辅助线性规划问题，若：n有最优解：如果最优解的基变量中不含有非零人工变量，则最优解中剔除掉人工变量部分，构成原问题的最优解；如果最优解的基变量中仍含有非零人工变量，则原问题无可行解；n无界解：如果最终单纯形表中基变量不含有非零人工变量，则原问题为无界解；否则，如果最终单纯形表中基变量含有非零人工变量，则原问题为无可行解。例：求解下列例：求解下列线性性规划划问题引入人工引入人工变量，量，并利用大并利用大M 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 -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为基基变量，所以原量，所以原线性性规划不存在可行解。划不存在可行解。o例 求解下列线性规划问题：变标准型添加人工变量利用大M法Cx1x2x3x4x5x61-100-M-M0.51-10104110-1013XBx5x6CB-M-M1+1.5M2M-1-M-M00b4/13/1-0.50-111-11110-1013x5x2-M-11/1-2-0.5M0-M-1+M01-2M-0.50-111-110.51-10104x4x20-1-4/0.51.50-101-M-M-0.50-111-10.51-1010 x4x20-114-4/0.51.50-101-M-MCx1x2x3x4x5x61-100-M-MXBCBb01-212-1512-20208x4x1010-320-M-2-M非基变量x3对应的检验数0,并且该非基变量对应的系数列向量的全部系数0，技，技术系数均系数均 0404.3 4.3 无无穷多（多重）最多（多重）最优解解 maxz=8x1+5x2s.t.3x1+5x2150(1)x220(2)8x1+5x2300(3)x1,x2041当前基本可行解：当前基本可行解：(0,0,150,20,300),Z=042当前基本可行解：当前基本可行解：(75/2,0,75/2,20,0),Z=30043当前基本可行解：当前基本可行解：(30,12,0,8,0),Z=30044无无穷多最多最优解的判解的判别准准则所有所有检验数数存在非基存在非基变量，量，检验数数=045o解的判别：若 是对应于基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,均有 ，则该线性规划问题有无界解(无最优解)。46o利用大M法，求解辅助线性规划问题，若：n有最优解：如果最优解的基变量中不含有非零人工变量，则最优解中剔除掉人工变量部分，构成原问题的最优解；n如果最优解的基变量中仍含有非零人工变量，则原问题无可行解；n无界解：如果最终单纯形表中基变量不含有非零人工变量，则原问题为无界解；n否则，如果最终单纯形表中基变量含有非零人工变量，则原问题为无可行解。474.4 进基变量的相持o当进基变量发生相持的情况时，可任意选择其中一个非基变量进基。54b x4x3XB00CB cj003310210112x4 x3 x2 x1 3 3 0 04.5 出基变量的相持42b x4x3XB00CB cj003210210112x4 x3 x2 x1 2 3 0 0出基变量的相持o当发生出基变量相持的情况时，会产生退化解，从而导致中间的若干步换基迭代过程不能使目标函数值改善的情况，但最终一般仍可以得到最优解。o在极少数的情况下，出现退化解时，采用单纯形法迭代会陷入死循环，即数次迭代之后，又回到某个已经到达过的基本可行解。对于这种情况，处理的方法有：n摄动法n字典序法n Bland规则谢谢观赏谢谢观赏