《1-4-线性规划-大M法、两阶段法与几种特殊情况》由会员分享，可在线阅读，更多相关《1-4-线性规划-大M法、两阶段法与几种特殊情况（50页珍藏版）》请在金锄头文库上搜索。
1、1-4 1-4 线性规划线性规划- -大大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
2、.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+
3、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法：构造一个单位矩阵来作初始可行基法：构造一个单位矩阵来作初始可行基如何构造？如何构造？通过添加人工变量通过
4、添加人工变量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
5、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
6、 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最优解最
7、优解 最优值最优值14大M法的基本步骤o通过加入人工变量，构造初始可行基；o在目标函数中赋予人工变量很大的罚系数M，建立辅助线性规划问题；o利用单纯形法，求解上述辅助线性规划问题，若：n有最优解：如果最优解的基变量中不含有非零人工变量，则最优解中剔除掉人工变量部分，构成原问题的最优解；如果最优解的基变量中仍含有非零人工变量，则原问题无可行解；n无界解：如果最终单纯形表中基变量不含有非零人工变量，则原问题为无界解；否则，如果最终单纯形表中基变量含有非零人工变量，则原问题为无可行解。1516例：求解下列线性规划问题例：求解下列线性规划问题引入人工变量，引入人工变量，并利用大并利用大M M法求解法求
8、解解：解：首先将问题化为标准型首先将问题化为标准型17C -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
9、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为基变量，所以原线性规划不存在可行解。为基变量，所以原线性规划不存在可行解。18o例 求解下列线性规划问题：变标准型添加人工变量利用大M法19Cx1x2x3x4x5x61-100-M-M0.51-10104110-1013XBx5x6CB-M-M1+1.5M2M-1-M-M00b4
10、/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-M20-0.50-111-10.51-1010x4x20-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
11、+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, 均有检验数 ，则 为最优解；若 是对应于基
12、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无界解：如果最终单纯形表中基变
13、量不含有非零人工变量，则原问题为无界解；n否则，如果最终单纯形表中基变量含有非零人工变量，则原问题为无可行解。474.4 进基变量的相持o当进基变量发生相持的情况时，可任意选择其中一个非基变量进基。54b x4x3XB00CB cj003310210112x4 x3 x2 x1 3 3 0 0484.5 出基变量的相持42b x4x3XB00CB cj003210210112x4 x3 x2 x1 2 3 0 049出基变量的相持o当发生出基变量相持的情况时，会产生退化解，从而导致中间的若干步换基迭代过程不能使目标函数值改善的情况，但最终一般仍可以得到最优解。o在极少数的情况下，出现退化解时，采用单纯形法迭代会陷入死循环，即数次迭代之后，又回到某个已经到达过的基本可行解。对于这种情况，处理的方法有：n摄动法n字典序法n Bland规则50
