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

11-4 1-4 线性规划线性规划-大大M M法、两阶段法及几种特殊情况法、两阶段法及几种特殊情况School of BusinessECUSTo3.3 3.3 单纯形法单纯形法 o 3.3.1 3.3.1 单纯形法的一般思路单纯形法的一般思路+例子例子o 3.3.2 3.3.2 单纯形表结构单纯形表结构+例子例子o 3.3.3 3.3.3 单纯形法的计算步骤单纯形法的计算步骤o 3.3.4 3.3.4 单纯形法的矩阵描述单纯形法的矩阵描述o 3.4 3.4 大大MM法法o 3.5 3.5 两阶段法两阶段法o4 4 几种特殊情况几种特殊情况o 4.1 4.1 无可行解无可行解o 4.2 4.2 无界解无界解o 4.3 4.3 多重最优解多重最优解o 4.4 4.4 进基变量的相持进基变量的相持o 4.5 4.5 出基变量的相持出基变量的相持School of BusinessECUST3.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,x40School of BusinessECUST标准化标准化 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,x60School of BusinessECUST添加人工变量添加人工变量 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,x80School of BusinessECUST添加人工变量添加人工变量 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,x80School of BusinessECUST42-3500MMBCBX1x2x3x4x5x6x7x8xbM7x2-112-10105006x30-12010080M8x1101000160j4-3M2-3-M 5-3MM000 School of BusinessECUST121212212max22-1 3,0Zxxxxxxxx x 解：首先将原LP问题转化为标准型，引入非负变量x3，x4，x51212312425-2-1 3 0,1,2,3,4ax,m52jZxxxxxxxxxxjx例：考虑下面的LP问题School of BusinessECUST1212312425-2-1 3 0,1,2,3,4ax,m52jZxxxxxxxxxxjx系数矩阵：111 0 01 101 00100 1A 初始可行基？初始可行基？大大M法：构造一个单位矩阵来作初始可行基法：构造一个单位矩阵来作初始可行基如何构造？如何构造？通过添加人工变量通过添加人工变量School of BusinessECUST1212312425-2-1 3 0,1,2,3,4ax,m52jZxxxxxxxxxxjx添加人工变量x6,x7123612312471242525-2-2-1-1 3 3 0,1,2,3,4,5 0,1,2,.,7jjxxxxxxxxxxxxxxxxxxxjxjSchool of BusinessECUST添加人工变量之后，系数矩阵变为：111 0 0 1 01 101 0 010100 10 0A 单位矩阵，单位矩阵，可作初始可行基可作初始可行基变量x6,x7是为了构造单位阵，而人为增加的，要保证最优解满足原约束，在问题的最优解中，这两个变量必须取0值。为了达到这种效果，我们将目标函数改写为：1267max2ZxxMxMx 其中，M为充分大的正数显然，为了保证Z取最大值，x6,x7必然取0School of BusinessECUST123612312126124712425275-2-2-1-1 3 3 0,1,2,3,4,5 0,1,2,.max2max2.jjxxxxxxxxxxxxxxxxxxxZxxZxxMxMxjxj ,7为什么可以这样转化？为什么可以这样转化？1234567,TXx x x x x x x=0=0原问题的最优解原问题的最优解School of BusinessECUST-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 -MC 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最优解最优解 最优值最优值X0,3,1,2,0TZ6大M法的基本步骤o 通过加入人工变量，构造初始可行基；o 在目标函数中赋予人工变量很大的罚系数M，建立辅助线性规划问题；o 利用单纯形法，求解上述辅助线性规划问题，若：n有最优解：如果最优解的基变量中不含有非零人工变量，则最优解中剔除掉人工变量部分，构成原问题的最优解；如果最优解的基变量中仍含有非零人工变量，则原问题无可行解；n无界解：如果最终单纯形表中基变量不含有非零人工变量，则原问题为无界解；否则，如果最终单纯形表中基变量含有非零人工变量，则原问题为无可行解。例：求解下列线性规划问题例：求解下列线性规划问题1231231323123min Z=3x+2x+xxxx6x -x4.x-x3x,x,x 0st12378123413572368MMmaxZ=-3x-2x-x-x-xx+x+x+x =6x -x -x +x =4 x -x -x +x=3xj0,j=1,2,8.引入人工变量，引入人工变量，并利用大并利用大M M法求解法求解78x,x1231234135236maxZ=-3x-2x-xx+x+x+x =6x -x -x =4 x -x -x =3xj0,j=1,2,6.解：解：首先将问题化为标准型首先将问题化为标准型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 例 求解下列线性规划问题：12121212max0.54.3,0zxxxxstxxx x121231241234max0.54.3,0zxxxxxstxxxx x x x125612351246123456max0.54.3,0zxxMxMxxxxxstxxxxx x x x x x变标准型添加人工变量利用大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,并且该非基变量对应的系数列向量的全部系数00，技术系数均技术系数均 0 0School of BusinessECUST4.3 4.3 无穷多（多重）最优解无穷多（多重）最优解 maxz=8x1+5x2s.t.3x1+5x2150(1)x220(2)8x1+5x2300(3)x1,x20School of BusinessECUST85000 x1x2x3x4x5RHS比值比值035100150150/300101020-085001300300/885000 x5检验数检验数x3x4当前基本可行解：当前基本可行解：(0,0,150,20,300),Z=0School of BusinessECUST85000 x1x2x3x4x5RHS比值比值0025/810-3/875/200101020815/8001/875/20000-1x3x4x1检验数检验数当前基本可行解：当前基本可行解：(75/2,0,75/2,20,0),Z=300School of BusinessECUST85000 x1x2x3x4x5RHS比值比值5018/250-3/2512000-8/2513/258810-5/2505/25300000-1x1检验数检验数x2x4当前基本可行解：当前基本可行解：(30,12,0,8,0),Z=300School of BusinessECUST无穷多最优解的判别准则无穷多最优解的判别准则所有检验数所有检验数存在非基变量，检验数存在非基变量，检验数=0=0School of BusinessECUSTo 解的判别：n若 是对应于基B Bk=(P1,P2,.,Pm)的基可行解，对于一切 j=m+1,.,n,均有检验数 ，则 为最优解；n若 是对应于基 B Bk=(P1,P2,.,Pm)的基可行解，对于一切 j=m+1,.,n,均有检验数 ，并且存在某个非基变量(比如xm+r)的检验数 ，则该线性规划问题有无穷多最优解；n若 是对应于基 B Bk=(P1,P2,.,Pm)的基可行解，若存在某个非基变量(比如xm+r)的检验数 ，并且对i=1,2,m,均有 ，则该线性规划问题有无界解(无最优解)。12,.,0,.,0TkmXb bb kX0j 12,.,0,.,0TkmXb bb0j0m r 12,.,0,.,0TkmXb bb0m r,0i m raSchool of BusinessECUSTo 利用大M法，求解辅助线性规划问题，若：n有最优解：如果最优解的基变量中不含有非零人工变量，则最优解中剔除掉人工变量部分，构成原问题的最优解；n如果最优解的基变量中仍含有非零人工变量，则原问题无可行解；n无界解：如果最终单纯形表中基变量不含有非零人工变量，则原问题为无界解；n否则，如果最终单纯形表中基变量含有非零人工变量，则原问题为无可行解。4.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规则