运筹学04-线性规划III-rev.pptVIP

大M法的基本步骤 通过加入人工变量，构造初始可行基； 在目标函数中赋予人工变量很大的罚系数M，建立辅助线性规划问题； 利用单纯形法，求解上述辅助线性规划问题，若： 有最优解：如果最优解的基变量中不含有非零人工变量，则最优解中剔除掉人工变量部分，构成原问题的最优解；如果最优解的基变量中仍含有非零人工变量，则原问题无可行解； 无界解：如果最终单纯形表中基变量不含有非零人工变量，则原问题为无界解；否则，如果最终最终单纯形表中基变量含有非零人工变量，则原问题为无可行解。 例4.6 求解下列线性规划问题： 4.4 两阶段法 大M法实际上是利用单纯形法直接求解原问题的辅助线性规划问题，然后再根据最终能否将人工变量全部赶出基变量，来判断原问题和辅助线性规划问题之间解的对应关系。 两阶段法则将原线性规划问题的求解分为两个阶段： 第一阶段，寻找原问题的初始基可行解或判断原问题无可行解； 第二阶段，寻找原问题最优解或判断原问题无界。 第一阶段，寻找原问题的初始基可行解或判断原问题无可行解； 在原线性规划问题中引入人工变量后，构造一个新的线性规划问题(辅助问题)，其中系数矩阵中包含单位阵，目标函数是极小化人工变量之和(为了使人工变量取0值)； 用单纯形方法求解辅助问题，若求得的基可行解可使目标函数达到最小值0(人工变量均取0)，则我们就找到了原问题的初始基可行解； 若辅助问题的目标函数不能达到最小值0，则原问题无可行解，求解过程结束。 第二阶段，寻找原问题的最优解或或判断原问题无界。 在第一阶段得到的最终单纯形表基础上，划去人工变量所在的列，引入原问题的目标函数，对原问题进行求解。 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 -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 最优解 最优值 例4.5：求解下列线性规划问题 引入人工变量　　　， 并利用大M法求解 解： 　首先将问题化为标准型 C -3 -2 -1 0 0 0 -M -M CB XB b x1 x2 x3 x4 x5 x6 x7 x8 θ 0 -M -M x4 x7 x8 6 4 3 1 1 1 1 0 0 0 0 1 0 -1 0 -1 0 1 0 0 1 -1 0 0 -1 0 1 6/1 - 3/1 Z’