第一章线性规划与单纯型法 ·第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
解在上述问题的约束条件中加入松弛变 量x4,剩余变量x5,人工变量x6x7’得到 min2=-3x1+x2+3+0x4+0k3+h6+k, x1-2x+3+ =11 -4x1+x2+2x3 =3 -2X1 +3 X1,2,3,x4,X5,X6,X7≥0 M是一个任意大的正数
解 在上述问题的约束条件中加入松弛变 量x4，剩余变量x5，人工变量x6,x7，得到 ⎪⎪⎩ ⎪⎪⎨⎧ ≥ − + =+ =+−++− ++− = −= + + + + + + 0,,,,,, 2 1 24 3 2 11 3min 00 7654321 1 3 7 321 65 4321 7654321 xxxxxxx x x x xxxxx xxxx MxMxxxxxxz M是一个任意大的正数
因本例的目标函数是要求min,所以用所有cj- z≥0来判别日标函数是否实现了最小化. 表1-6单纯形法表 Ci -3 1 1 0 0 M M CB XB b Xi X2 X3 X4 X5 X6 X1 0 X4 11 1 -2 1 1 0 0 11 M X6 3 -4 1 2 0 -1 1 0 3/2 M X1 -2 1 1+ Ci-Zi -3+6M 1-M 1-3M 0 M 0 0
因本例的目标函数是要求min，所以用所有cjzj ≥ 0来判别目标函数是否实现了最小化. 表1-6单纯形法表 cj → -3 1 1 0 0 M M CB XB b x1 x2 x3 x 4 x 5 x 6 x 7 θ i 0 M M x4 x6 x7 11 3 1 1 -4 -2 -2 1 0 1 2 1 1 0 0 0 -1 0 0 1 0 0 0 1 11 3/2 1 cj-zj -3+6M 1-M 1-3M 0 M 0 0
在最终计算结果表中，最优解是：(4,1,9,0,0)zmin-2 -3 1 0 M M 0 CB XB b X1 X2 X3 X4 X5 X6 X] 0 X4 10 3 -2 0 1 0 0 -1 M X6 1 0 [1] 0 0 -1 1 -2 1 1 X3 1 -2 0 1 0 0 0 1 Ci-Zi -1 1-M 0 0 M 0 3M-1 X4 12 [3] 0 0 1 -2 2 -5 4 1 X2 1 0 1 0 0 -1 1 -2 1 X3 1 -2 0 1 0 0 0 1 Ci-Zi -1 0 0 0 1 M-1 M+1 -3 Xi 4 1 0 0 1/3 -2/3 2/3 -5/3 1 X2 1 0 1 0 0 -1 1 -2 1 X3 9 0 0 1 2/3 -4/3 4/3 -7/3 Ci-Zi 2 0 0 0 1/3 1/3 M-1/3 M-2/3
在最终计算结果表中，最优解是：(4,1,9,0,0)zmin=-2 cj → -3 1 1 0 0 M M C B XB b x 1 x2 x 3 x4 x5 x6 x 7 θ 0 M 1 x4 x6 x3 10 1 1 3 0 -2 -2 [1] 0 0 0 1 1 0 0 0 -1 0 0 1 0 -1 -2 1 1 cj-zj -1 1-M 0 0 M 0 3M-1 0 1 1 x4 x2 x3 12 1 1 [3] 0 -2 0 1 0 0 0 1 1 0 0 -2 -1 0 2 1 0 -5 -2 1 4 cj-zj -1 0 0 0 1 M-1 M+1 -3 1 1 x1 x2 x3 4 1 9 1 0 0 0 1 0 0 0 1 1/3 0 2/3 -2/3 -1 -4/3 2/3 1 4/3 -5/3 -2 -7/3 cj-zj 2 0 0 0 1/3 1/3 M-1/3 M-2/3
2. 两阶段法 ·用电子计算机求解含人工变量的线性规 划问题时，只能用很大的数来代替M,这 就可能造成计算上的错误。故介绍两阶 段法求线性规划问题 ·第一阶段：不考虑原问题是否存在基可 行解；给原线性规划问题加入人工变 量，并构造仅含人工变量的目标函数和 要求实现最小化
2. 两阶段法 • 用电子计算机求解含人工变量的线性规 划问题时，只能用很大的数来代替M，这 就可能造成计算上的错误。故介绍两阶 段法求线性规划问题。 • 第一阶段：不考虑原问题是否存在基可 行解；给原线性规划问题加入人工变 量，并构造仅含人工变量的目标函数和 要求实现最小化
第一阶段： 不考虑原问题是否存在基可行解；给原线性规划问 题加入人工变量，并构造仅含人工变量的目标函数 和要求实现最小化。 目标函数 min0=xn+1+…+Xn+m+0x1+0x2+…+0xn 411X1+412X2+…+4mXn+Xm+1 -b %21X1+22X2+…+2n火n +Xn+2 =b2 约束条件 . LmS1+0m2X2+…+AmnXn +Xn+m =bm X1,七2，，Xn,Xn+1,…,火n+m≥0
第一阶段： 1 1 2 11 1 12 2 1 1 1 21 1 22 2 2 2 2 11 2 2 1 2 1 min 0 0 0 ,, , , ,, 0 + + + + + + + = ++ + + ++ ⎧ + ++ + = ⎪ + ++ + = ⎪ ⎪ ⎨ ⎪ + ++ += ⎪ ⎪ ≥ ⎩ " " "" "" """ """" "" "" " n n m n nn n n n n m m mn n nm m n n nm x x xx x ax ax ax x b ax ax a x x b ax ax ax x b xx x x x 目标函数 约束条件 ω 不考虑原问题是否存在基可行解；给原线性规划问 题加入人工变量，并构造仅含人工变量的目标函数 和要求实现最小化