资源描述：
《1-4 线性规划-大M法、两阶段法与几种特殊情况.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、11-4线性规划-大M法、两阶段法及几种特殊情况SchoolofBusinessECUST3.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出基变量的相持33.4大M法一般问题的初始基本可行解maxz=4x1+2x2-3x3+5x4s.t.2x1-x2+x3+2x4≥50(1)3x1-x3+2x480(2)x1+x2+x4=60(3)x1,x2,x3,x4
2、≥04标准化maxz=4x1+2x2-3x3+5x4s.t.2x1-x2+x3+2x4－x5=50(1)3x1-x3+2x4+x6=80(2)x1+x2+x4=60(3)x1,x2,x3,x4,x5,x6≥05添加人工变量maxz=4x1+2x2-3x3+5x4-Mx7-Mx8s.t.2x1-x2+x3+2x4－x5+x7=50(1)3x1-x3+2x4+x6=80(2)x1+x2+x4＋x8=60(3)x1,x2,x3,x4,x5,x6,x7,x8≥06添加人工变量minz=4x1+2x2-3x3+5x4+Mx7+Mx8s.t.2x1-x2
3、+x3+2x4－x5+x7=50(1)3x1-x3+2x4+x6=80(2)x1+x2+x4＋x8=60(3)x1,x2,x3,x4,x5,x6,x7,x8≥07SchoolofBusinessECUST解：首先将原LP问题转化为标准型，引入非负变量x3，x4，x5例：考虑下面的LP问题SchoolofBusinessECUST系数矩阵：初始可行基？大M法：构造一个单位矩阵来作初始可行基如何构造？通过添加人工变量SchoolofBusinessECUST添加人工变量x6,x7SchoolofBusinessECUST添加人工变量之后，系数矩阵
4、变为：单位矩阵，可作初始可行基变量x6,x7是为了构造单位阵，而人为增加的，要保证最优解满足原约束，在问题的最优解中，这两个变量必须取0值。为了达到这种效果，我们将目标函数改写为：其中，M为充分大的正数显然，为了保证Z取最大值，x6,x7必然取0SchoolofBusinessECUST为什么可以这样转化？=0=0原问题的最优解SchoolofBusinessECUST-01-1/2-1/201/21/23/2X2210-1/21/201/2-1/21/2X1-1--110-10011X221/220-1101-11X6-M1/1-110-1
5、0011X7-M2/111-100102X6-M001/23/20-1/2-M-3/2-Mσj001/21/21-1/2-1/23/2X501+2M0-M2+M00-2-2Mσj2/1100110-12X50-12+2M-M-M000σj3/101001003X50X1x2x3x4x5x6x7bXBCBθ-12000-M-MC01001003X22100110-12X4011-100102X2220-1101-11X40-01-1/2-1/201/21/23/2X221/2/1/210-1/21/201/2-1/21/2X1-1-1000-2
6、-M-Mσj-10101-101X30-30200-2-M-Mσj-10101-101X50001/23/20-1/2-M-3/2-Mσj3/2/1/2001/21/21-1/2-1/23/2X50X1x2x3x4x5x6x7bXBCBθ-12000-M-MC最优解最优值大M法的基本步骤通过加入人工变量，构造初始可行基；在目标函数中赋予人工变量很大的罚系数M，建立辅助线性规划问题；利用单纯形法，求解上述辅助线性规划问题，若：有最优解：如果最优解的基变量中不含有非零人工变量，则最优解中剔除掉人工变量部分，构成原问题的最优解；如果最优解的基变量中
7、仍含有非零人工变量，则原问题无可行解；无界解：如果最终单纯形表中基变量不含有非零人工变量，则原问题为无界解；否则，如果最终单纯形表中基变量含有非零人工变量，则原问题为无可行解。例：求解下列线性规划问题引入人工变量 ，并利用大M法求解解：首先将问题化为标准型C-3-2-1000-M-MCBXBbx1x2x3x4x5x6x7x8θ0-M-Mx4x7x86431111000010-10-101001-100-1016/1-3/1Z’-3+M-2+M-1-2M0-M-M000-M-2x4x7x23431021010-110-10-101001-1
8、00-1013/14/1-Z’Z’-3+M0-3-M0-M-202-M-3-M-2x1x7x23131021010-100-3-1-1-11101-100-1010
