LP_LEC-4-人工变量法.pdfVIP

§5 人工变量法（M方法和两阶段法） 1、确定初始可行基的大M法 线性规划问题的约束方程化成标准形之后，若 系数矩阵中不含单位矩阵，那么加入人工变量： xn+1 ，…，xn+m a x + a x x + b ⎧ 11 1 n n 1n +1 1 ⎪ a x +a x x + b ⎪ 21 1 n 2n n+2 2 ⎨ ⎪ ⎪ + + a x a x x b ⎩1m1 mn n n m m+ , x, x0, , x , x 0 ≥ ≥ n1 n +1 n m+ 2006-9-19 1 问题：加入人工变量以后，线性规划问题已经变 化成了一个新的线性规划问题，而我们要求求解 原线性规划问题，而原线性规划问题没有初始可 行基，没法进行下去。而加入了一些新的人工变 量以后虽然有了初始可行基，但问题又变成了一 个新的线性规划问题，怎么办？ M方法：在约束条件中，加入人工变量后，要求 目标函数不受影响？目标函数中人工变量的系数 取（-M ）。 为什么这样能行？ 2006-9-19 2 理由：目标函数实现最大化，就必须将人工变量从 基变量中换出，否则目标函数就不可能取得最大化。 人工变量是虚拟变量，加入原方程中是作为临 时基变量，经过基的旋转变换，将人工变量均能 换成非基变量，则所得解是最优解； 判别准则4-1 ：若在最终表中检验数小于零，而 且基变量中还有某个非零的人工变量，则原问题 无可行解。 2006-9-19 3 本质：将一个线性规划问题转化为一个新的线性 规划问题，但这两个线性规划问题与原线性规划 问题是等价的。 问题：如果是求最小化问题，M法该怎样加人工变 量的系数？ 2006-9-19 4 例1：用大M法求解如下线性规划问题。 z x xmin x 3 + − + 1 2 3 返回 x x x 2 11 − + ≤⎧