第一章线性规划与单纯型法 ·第5节单纯形法的进一步讨论 ·5.1人工变量法 ·5.2退化 ·5.3检验数的几种表示形式
第一章 线性规划与单纯型法 • 第 5节 单纯形法的进一步讨论 • 5.1 人工变量法 • 5.2 退化 • 5.3 检验数的几种表示形式
5.1人工变量法 设线性规划问题的约束条件 ∑Px,=b j=1 其中没有可作为初始基的单位矩阵，则分别给每一个 约束方程加入人工变量x1,,xm,得到 11X1+M12X2++1nXn+X+1 b M21X1+422X2++42mXn +X+2 =b2 amIx+am2x2++amxn +n+m 二bm X1,)Xn≥0；Xm+1,…,Xn+m≥0
⎪ ⎪ ⎪ ⎩ ⎪ ⎪ ⎪ ⎨ ⎧ ≥ ≥ +++ =+ +++ + = ++++ = + + + + + 0,,;0,, 1 1 2211 222121 2 2 2 212111 1 1 1 n m mn m m nmn mmn nn n nnn xxxx xaxaxa bx xxaxaxa b xxaxaxa b " " " " " " • 设线性规划问题的约束条件 • 其中没有可作为初始基的单位矩阵，则分别给每一个 约束方程加入人工变量 xn+1,…,xn+m，得到 5.1 人工变量法 ∑= = n j jj bxP 1
·以x1,,xn为基变量，便可得到一个 m×m单位矩阵。令非基变量x1,,X为零， 便可得到一个初始基可行解 Xo=(0,0,,0,b1,b2.,b)T 因为人工变量是后加入到原约束条件中的虚 拟变量，要求经过基的变换将它们从基变量 中逐个替换出来。 基变量中不再含有非零的人工变量，这表示 原问题有解。 若在最终表中当所有C;z,≤0，而在其中还有 某个非零人工变量，这表示原问题无可行解
• 以xn+1,…，xn+m为基变量，便可得到一个 m×m单位矩阵。令非基变量x 1,…,x n为零， 便可得到一个初始基可行解 X(0)=(0,0, …,0,b 1,b2, …,b m ) T • 因为人工变量是后加入到原约束条件中的虚 拟变量，要求经过基的变换将它们从基变量 中逐个替换出来。 • 基变量中不再含有非零的人工变量，这表示 原问题有解。 • 若在最终表中当所有c j-z j≤0，而在其中还有 某个非零人工变量，这表示原问题无可行解
1.大M法 ·在一个线性规划问题的约束条件中加进 人工变量后，要求人工变量对目标函数 取值不受影响；为此假定人工变量在目 标函数中的系数为(-M)M为任意大的正 数)， ·这样目标函数要实现最大化时，必须把 人工变量从基变量换出。否则目标函数 不可能实现最大化
1.大M法 • 在一个线性规划问题的约束条件中加进 人工变量后，要求人工变量对目标函数 取值不受影响；为此假定人工变量在目 标函数中的系数为(-M)(M为任意大的正 数)， • 这样目标函数要实现最大化时，必须把 人工变量从基变量换出。否则目标函数 不可能实现最大化
例8 试用大M法求解线性规划问题 min z=-3x+x2+x3 x1-2x2+x3≤11 -4x1+x2+2x3≥3 -2X1 +x3=1 X1,x2,x3≥0
例8 试用大M法求解线性规划问题 ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ − =+ ≥++− ≤+− = − + + 0,, 2 1 324 2 11 3min 321 1 3 321 321 321 xxx x x xxx xxx xxxz