人工变量法

在一些模型中并不包含单位矩阵，为了得到一组基向量和初始可行解，在约束条件的等式左端添加一组虚拟变量，得到一组基向量。这种人为添加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解。

1. 大Ｍ法

大M法，通过引进人工变量，构造一个辅助的线性规划问题， 然后由辅助的线性规划问题找出原问题的第一个初始可行基，在此基础上，利用单纯形法求出原问题的最优解。

1.1. 题目

用大 M 法解下列线性规划

$$\max Z=3x_1+2x_2-x_3$$

$$\text{s.t.}\{\begin{array}{l}-4x_1+3x_2+x_3\ge 4\\ x_1-x_2+2x_3\le 10\\ -2x_1+2x_2-x_3=-1\\ x_i\ge 0,i=1,2,3\end{array}$$

1.2. 转化为标准型

首先将线性规划转换成标准型

$$\max Z=3x_1+2x_2-x_3+0x_4+0x_5$$

$$\text{s.t.}\{\begin{array}{l}-4x_1+3x_2+x_3-x_4=4\\ x_1-x_2+2x_3+x_5=10\\ 2x_1-2x_2+x_3=1\\ x_i\ge 0,i=1,2,\dots ,5\end{array}$$

画出其对应的单纯形表（如果这一步，还不会的话，可以参考单纯形法求解步骤：一个简单例子）

$C$	$C$	$C$	3	2	-1	0	0
$C_B$	基	$b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
		4	-4	3	1	-1	0
		10	1	-1	2	0	1
		1	2	-2	1	0	0
$\sigma$	$\sigma$	$\sigma$

在这个表的系数矩阵中，没有单位矩阵存在，所以无法直接进行求解，需要使用一些辅助手段–人工变量法。

1.3. 添加人工变量

$$\max Z=3x_1+2x_2-x_3+0x_4+0x_5-M{x}_6-M{x}_7$$

$$\text{s.t.}\{\begin{array}{l}-4x_1+3x_2+x_3-x_4+x_6=4\\ x_1-x_2+2x_3+x_5=10\\ 2x_1-2x_2+x_3+x_7=1\\ x_i\ge 0,i=1,2,\dots ,7\end{array}$$

$C$	$C$	$C$	3	2	-1	0	0	-M	-M
$C_B$	基	$b$	$x_1$	$x_2$	$x_3\downarrow$	$x_4$	$x_5$	$x_6$	$x_7$
-M	$x_6$	4	-4	3	1	-1	0	1	0
0	$x_5$	10	1	-1	2	0	1	0	0
-M	$\leftarrow x_7$	1	2	-2	[1]	0	0	0	1
$\sigma$	$\sigma$	$\sigma$	3-2M	2+M	-1+2M	-M	0	0	0

入基变量 $x_3$，出基变量 $x_7$；

$C$	$C$	$C$	3	2	-1	0	0	-M	-M
$C_B$	基	$b$	$x_1$	$x_2\downarrow$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$
-M	$\leftarrow x_6$	3	-6	[5]	0	-1	0	1	-1
0	$x_5$	8	-3	3	0	0	1	0	-2
-1	$x_3$	1	2	-2	1	0	0	0	1
$\sigma$	$\sigma$	$\sigma$	5-6M	5M	0	-M	0	0	1-M

入基变量 $x_2$，出基变量 $x_6$；

$C$	$C$	$C$	3	2	-1	0	0	-M	-M
$C_B$	基	$b$	$x_1\downarrow$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$
2	$x_2$	$\frac{3}{5}$	$-\frac{6}{5}$	1	0	$-\frac{1}{5}$	0	$\frac{1}{5}$	$-\frac{1}{5}$
0	$\leftarrow x_5$	$\frac{31}{5}$	[$\frac{3}{5}$]	0	0	$\frac{3}{5}$	1	$-\frac{3}{5}$	$-\frac{7}{5}$
-1	$x_3$	$\frac{11}{5}$	$-\frac{2}{5}$	0	1	$-\frac{2}{5}$	0	$\frac{2}{5}$	$\frac{3}{5}$
$\sigma$	$\sigma$	$\sigma$	5	0	0	0	0	-M	1-M

入基变量 $x_1$，出基变量 $x_5$；

$C$	$C$	$C$	3	2	-1	0	0	-M	-M
$C_B$	基	$b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$
2	$x_2$	13	0	1	0	1	2	1	-3
3	$x_1$	$\frac{31}{3}$	1	0	0	1	$\frac{5}{3}$	-1	$-\frac{7}{3}$
-1	$x_3$	$\frac{19}{3}$	0	0	1	0	$\frac{2}{3}$	0	$-\frac{1}{3}$
$\sigma$	$\sigma$	$\sigma$	0	0	0	-5	$-\frac{25}{3}$	1-M	$\frac{38}{3}$-M

因为 ${\sigma }_j\le 0$，对所有的 $j$ 成立，所以迭代结束。
最优解为

$$x^{\ast }=(\frac{31}{3},13,\frac{19}{3},0,0{)}^T,$$

$$Z^{\ast }=3x_1+2x_2-x_3=3\ast \frac{31}{3}+2\ast 13-\frac{19}{3}=\frac{152}{3}.$$

2. 两阶段法

在原来问题引入人工变量后分两个阶段求解线性规划问题的方法。其中，第一阶段在原来问题中引入人工变量，设法构造一个单位矩阵的初始可行基。在此基础上，建立辅助线性规划问题。然后运用单纯形法求解，直到辅助目标函数为0为止。第二阶段重新回到原来的问题，以第一阶段得到的可行基为初始可行基，运用单纯形法求出原来问题的解。

2.1. 步骤

1. 不考虑原问题是否存在基可行解，引进人工变量，构造辅助线性规划问题；
2. 用单纯形法求解辅助问题，若辅助问题的目标函数值 $Z\ne 0$，则原问题无可行解，停止计算；
3. 若辅助问题的目标函数值 $Z=0$，则将第一阶段计算得到的最终表，除去人工变量，将目标函数行的系数换为原问题的目标函数系数，作为第二阶段的初始表；
4. 使用单纯形法求解。

2.2. 题目

用两阶段法求解线性规划问题

$$\max Z=3x_1+2x_2-x_3$$

$$\text{s.t.}\{\begin{array}{l}-4x_1+3x_2+x_3\ge 4\\ x_1-x_2+2x_3\le 10\\ -2x_1+2x_2-x_3=-1\\ x_i\ge 0,i=1,2,3\end{array}$$

2.2.1. 转化为标准型

$$\max Z=3x_1+2x_2-x_3$$

$$\text{s.t.}\{\begin{array}{l}-4x_1+3x_2+x_3-x_4=4\\ x_1-x_2+2x_3+x_5=10\\ 2x_1-2x_2+x_3=1\\ x_i\ge 0,i=1,2,\dots ,5\end{array}$$

2.2.2. 添加人工变量

$$\max Z=3x_1+2x_2-x_3$$

$$\text{s.t.}\{\begin{array}{l}-4x_1+3x_2+x_3-x_4+x_6=4\\ x_1-x_2+2x_3+x_5=10\\ 2x_1-2x_2+x_3+x_7=1\\ x_i\ge 0,i=1,2,\dots ,7\end{array}$$

2.2.3. 两阶段

• 第一阶段

$$\min W=0x_1+0x_2+0x_3+0x_4+0x_5+x_6+x_7$$

$$⟺$$

$$\max -W=0x_1+0x_2+0x_3+0x_4+0x_5-x_6-x_7$$

$C$	$C$	$C$	0	0	0	0	0	-1	-1
$C_B$	基	$b$	$x_1$	$x_2$	$x_3\downarrow$	$x_4$	$x_5$	$x_6$	$x_7$
-1	$x_6$	4	-4	3	1	-1	0	1	0
0	$x_5$	10	1	-1	2	0	1	0	0
-1	$\leftarrow x_7$	1	2	-2	[1]	0	0	0	1
$\sigma$	$\sigma$	$\sigma$	-2	1	2	-1	0	0	0

入基变量 $x_3$，出基变量 $x_7$；

$C$	$C$	$C$	0	0	0	0	0	-1	-1
$C_B$	基	$b$	$x_1$	$x_2\downarrow$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$
-1	$\leftarrow x_6$	3	-6	[5]	0	-1	0	1	-1
0	$x_5$	8	-3	3	0	0	1	0	-2
0	$x_3$	1	2	-2	1	0	0	0	1
$\sigma$	$\sigma$	$\sigma$	-6	5	0	-1	0	0	-2

入基变量 $x_2$，出基变量 $x_6$；

$C$	$C$	$C$	0	0	0	0	0	-1	-1
$C_B$	基	$b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$
0	$x_2$	$\frac{3}{5}$	$-\frac{6}{5}$	1	0	$-\frac{1}{5}$	0	$\frac{1}{5}$	$-\frac{1}{5}$
0	$x_5$	$\frac{31}{5}$	$\frac{3}{5}$	0	0	$\frac{3}{5}$	1	$-\frac{3}{5}$	$-\frac{7}{5}$
0	$x_3$	$\frac{11}{5}$	$-\frac{2}{5}$	0	1	$-\frac{2}{5}$	0	$\frac{2}{5}$	$\frac{3}{5}$
$\sigma$	$\sigma$	$\sigma$	0	0	0	0	0	-1	-1

所有的人工变量都是非基变量，第一阶段结束。

• 第二阶段

$C$	$C$	$C$	3	2	-1	0	0
$C_B$	基	$b$	$x_1\downarrow$	$x_2$	$x_3$	$x_4$	$x_5$
2	$x_2$	$\frac{3}{5}$	$-\frac{6}{5}$	1	0	$-\frac{1}{5}$	0
0	$\leftarrow x_5$	$\frac{31}{5}$	[$\frac{3}{5}$]	0	0	$\frac{3}{5}$	1
-1	$x_3$	$\frac{11}{5}$	$-\frac{2}{5}$	0	1	$-\frac{2}{5}$	0
$\sigma$	$\sigma$	$\sigma$	5	0	0	0	0

入基变量 $x_1$，出基变量 $x_5$；

$C$	$C$	$C$	3	2	-1	0	0
$C_B$	基	$b$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
2	$x_2$	13	0	1	0	1	2
3	$x_1$	$\frac{31}{3}$	1	0	0	1	$\frac{5}{3}$
-1	$x_3$	$\frac{19}{3}$	0	0	1	0	$\frac{2}{3}$
$\sigma$	$\sigma$	$\sigma$	0	0	0	-5	$-\frac{25}{3}$

${\sigma }_j\le 0$， 对所有的 $j$ 都成立，因此求解结束。

最优解

$$x^{\ast }=(\frac{31}{3},13,\frac{19}{3},0,0{)}^T,$$

$$Z^{\ast }=3x_1+2x_2-x_3=3\ast \frac{31}{3}+2\ast 13-\frac{19}{3}=\frac{152}{3}.$$

3. 参考

1. 正气清风：(完整版)单纯形法、大M法
2. Homyee King：初始解----两阶段的单纯形法