单纯形法算法详解

用处

单纯形法是一种线性规划迭代算法，能够在有限步内找到线性规划问题的最优解(如果解存在的话)。

算法步骤

以下述线性规划问题为例： $$\begin{aligned} \max z = 2x_{1} + 3x_{2} \\ \text{s.t.} \quad \left\{ \begin{aligned} x_{1} + 2x_{2} &\le 8 \\ 4x_{1} &\le 16 \\ 4x_{2} &\le 12 \\ x_{1}, x_{2} &\ge 0 \end{aligned} \right. \end{aligned}$$ 其中，第一行是线性目标，大括号里面的内容是约束条件。

化为标准型

• 确定线性目标是求的max问题，如果是min问题，则将等号两边都乘以-1，从而转变为max问题。

• 确定最后一行的每一个x都大于等于0，如果有小于等于的x，则将那个x变成两个大于等于0的数的相减。 ​例如：如果$x_{1}\le0$，则$x_{1}$可以化成$x_{1}^{'}-x_{1}^{''}$。 ​转换以后将最后一行变成$x_{1}^{'}\ge 0, x_{1}^{''}\ge 0, x_{2}\ge 0$，将最后一行以外约束条件里面的$x_{1}$也变成$x_{1}^{'}-x_{1}^{''}$。

• 确定最后一行以外的约束条件都是$\le$，如果有$\ge$，则不等号两边乘以-1从而变号为$\le$。

• 单纯形法硬性要求后续约束条件化成的矩阵中存在单位矩阵，所以对于没有单位矩阵的情况，需要手动凑单位矩阵。除最后一行以外的约束条件有几行，就增加几个额外的大于等于0的变量用于凑单位矩阵。 例如：上述线性规划问题凑完以后的结果为： $$\begin{aligned} \max z = 2x_{1} + 3x_{2} + 0x_{3} + 0x_{4} + 0x_{5} \\ \text{s.t.} \quad \left\{ \begin{array}{rcl} x_{1} + 2x_{2} + x_{3} & = & 8 \\ 4x_{1} + x_{4} & = & 16 \\ 4x_{2} + x_{5} & = & 12 \\ x_{1}, x_{2}, x_{3}, x_{4}, x_{5} & \ge & 0 \end{array} \right. \end{aligned}$$ 增加了三个新的变量$x_{3}, x_{4}, x_{5}$,这样不仅凑出了单位矩阵(后续解释)，而且还去掉了不等号。

• 将其余每一行缺失的变量都用0补上，得到最终化为标准型的结果为： $$\begin{aligned} \max z = 2x_{1} + 3x_{2} + 0x_{3} + 0x_{4} + 0x_{5} \\ \text{s.t.} \quad \left\{ \begin{matrix} x_{1} + 2x_{2} + x_{3} & = & 8 \\ 4x_{1} + x_{4} & = & 16 \\ 4x_{2} + x_{5} & = & 12 \\ x_{1}, x_{2}, x_{3}, x_{4}, x_{5} & \ge & 0 \end{matrix} \right. \end{aligned}$$

列出初始单纯形表

$c_{j}$			2	3	0	0	0	$\theta _{i}$
$c_{B}$	基	b	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$
0	$x_{3}$	8	1	2	1	0	0
0	$x_{4}$	16	4	0	0	1	0
0	$x_{5}$	12	0	4	0	0	1
$\sigma_{j}$

规则如下：

1. 列数等于变量的个数。

2. 行数等于大括号中多变量的式子的个数。

3. $c_{j}$

   行的数字根据目标函数中各变量的系数找。

4. 每个变量所在列的数字根据大括号中多变量式子中该变量的系数找。

5. 找出变量下方已填写数字构成的矩阵中的单位矩阵，依次将单位矩阵对应的变量写在“基”那一列的下面。

6. 将5中找到的变量上方的数字依次写在$c_{j}$那一列的下面。

7. 将大括号中多变量式子右侧数字依次填到b那一列的下面。

找出可行解

令“基”所在列的变量与b所在列的数字对应相等，再令其他变量等于0。

即$X^{(0)}=(0,0,8,16,12)$。

求出检验数

$c_{j}$			2	3	0	0	0	$\theta _{i}$
$c_{B}$	基	b	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$
0	$x_{3}$	8	1	2	1	0	0
0	$x_{4}$	16	4	0	0	1	0
0	$x_{5}$	12	0	4	0	0	1
$\sigma_{j}$			2	3	0	0	0

检验数$\sigma_{j}$计算公式如下：

$\sigma_{j}=c_{j}-(c_{B1}\cdot x_{j1}+c_{B2}\cdot x_{j2}+...)$

例如：$\sigma_{1}=c_{1}-(c_{B1}\cdot x_{11}+c_{B2}\cdot x_{12}+c_{B3}\cdot x_{13})=2-(0\cdot 1+0\cdot 4+0\cdot 0)=2$

判断最优解

观察一下$\sigma_{j}$这一行的数字看一下是否都$\le$0，

若这些数字都$\le$，则找到的可行解是最优解。

若这些数字有>0的，则该可行解不是最优解，需继续进行下一步。

获取入基变量

找到$\sigma_{j}$行最大的数字那一列对应的变量$x_{a}$作为入基变量。

在本例中，此时的最大$\sigma_{j}$为3，其对应的变量是$x_{2}$。

获取出基变量

求出$\theta_{i}=b_{i}\div x_{ai}$,其中$x_{ai}$是入基变量对应的那一列。

若$\theta\ge 0$，则把$\theta$的值填到表中；

若$\theta\le 0$，则不用把$\theta$的值填到表中；

若$\theta$无意义，则不用把$\theta$填到表中。

注意：若求出的$\theta$都$\le$0，则该线性规划问题的解为无解解。

$c_{j}$			2	3	0	0	0	$\theta _{i}$
$c_{B}$	基	b	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$
0	$x_{3}$	8	1	2	1	0	0	4
0	$x_{4}$	16	4	0	0	1	0	$\times$
0	$x_{5}$	12	0	4	0	0	1	3
$\sigma_{j}$			2	3	0	0	0

在本例中： $$\begin{aligned} \theta_{1} &= \frac{b_{1}}{x_{21}} = \frac{8}{2} = 4 \\ \theta_{2} &= \frac{b_{2}}{x_{22}} = \frac{16}{0} \quad \text{(无意义)} \\ \theta_{3} &= \frac{b_{3}}{x_{23}} = \frac{12}{4} = 3 \end{aligned}$$

找到表中$\theta_{i}$最小值对应“基”列的变量$x_{b}$作为出基变量。

在本例中，最小的$\theta_{i}$是$\theta_{3}$，故其对应的变量$x_{5}$作为出基变量。

绘制下一轮单纯形表

在原基础上对单纯形表进行扩展:

$c_{j}$			2	3	0	0	0	$\theta _{i}$
$c_{B}$	基	b	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$
0	$x_{3}$	8	1	2	1	0	0	4
0	$x_{4}$	16	4	0	0	1	0	$\times$
0	$x_{5}$	12	0	4	0	0	1	3
$\sigma_{j}$			2	3	0	0	0
$\sigma_{j}$

处理出入基变量

找到上一轮中入基变量对应列和出基变量对应行交叉的数字m并填入新一轮的表中。(本轮中的m是4)

在新表中用$x_{a}$(入基)上面的数字代替$x_{b}$(出基)前面的数字，用$x_{a}$代替$x_{b}$，其余变量不变。(本例中用$x_{2}$替换“基”中的$x_{5}$)

$c_{j}$			2	3	0	0	0	$\theta _{i}$
$c_{B}$	基	b	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$
0	$x_{3}$	8	1	2	1	0	0	4
0	$x_{4}$	16	4	0	0	1	0	$\times$
0	$x_{5}$	12	0	4	0	0	1	3
$\sigma_{j}$			2	3	0	0	0
0	$x_{3}$
0	$x_{4}$
3	$x_{2}$			4
$\sigma_{j}$

矩阵运算

对$x_{1}\text{、}x_{2}...x_{n}$与b列组成的矩阵进行运算，将m变成1，同列其他元素变成0，形成一个新的矩阵，将该矩阵中的数字填入表格中对应的位置形成新的单纯新表。

$c_{j}$			2	3	0	0	0	$\theta _{i}$
$c_{B}$	基	b	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$
0	$x_{3}$	8	1	2	1	0	0	4
0	$x_{4}$	16	4	0	0	1	0	$\times$
0	$x_{5}$	12	0	4	0	0	1	3
$\sigma_{j}$			2	3	0	0	0
0	$x_{3}$	2	1	0	1	0	-1/2
0	$x_{4}$	16	4	0	0	1	0
3	$x_{2}$	3	0	1	0	0	1/4
$\sigma_{j}$

找出可行解

和之前一样，得到可行解为：$X^{(1)}=(0,3,2,16,0)$。

继续迭代

接下来继续计算检验数判断最优解获取入基/出基变量绘制下一轮单纯形表处理出入基变量矩阵运算找出可行解计算检验数……

之后就是一直按照上述步骤进行迭代，直到检验数全部小于等于0，则说明此时可行解是最优解。

$c_{j}$			2	3	0	0	0	$\theta _{i}$
$c_{B}$	基	b	$x_{1}$	$x_{2}$	$x_{3}$	$x_{4}$	$x_{5}$
0	$x_{3}$	8	1	2	1	0	0	4
0	$x_{4}$	16	4	0	0	1	0	$\times$
0	$x_{5}$	12	0	4	0	0	1	3
$\sigma_{j}$			2	3	0	0	0
0	$x_{3}$	2	1	0	1	0	-1/2	2
0	$x_{4}$	16	4	0	0	1	0	4
3	$x_{2}$	3	0	1	0	0	1/4	$\times$
$\sigma_{j}$			2	0	0	0	-3/4
2	$x_{1}$	2	1	0	1	0	-1/2	$\times$
0	$x_{4}$	8	0	0	-4	1	2	4
3	$x_{2}$	3	0	1	0	0	1/4	12
$\sigma_{j}$			0	0	-2	0	1/4
2	$x_{1}$	4	1	0	0	1/4	0
0	$x_{5}$	4	0	0	-2	1/2	1
3	$x_{2}$	2	0	1	1/2	-1/8	0
$\sigma_{j}$			0	0	-3/2	0	0

第四轮迭代中检验数全部小于等于0，所以计算结束。

此时可行解为$X^{(3)}=(4,2,0,0,4)$。

即本线性规划问题的最优解为$X^{(*)}=(4,2,0,0,4)$。