线性规划（Linear Programming）：单纯形

线性规划（Linear Programming）：单纯形
- 基本思路
- 单纯形表
  - 解法
    - 例
- 人工变量法
  - 大M法
    - 例
  - 两阶段法

基本思路

单纯形：指0维中的点，1维中的线段，2维中的三角形，3维中的四面体， $n$ 维空间中的有 $n+1$ 个顶点的多面体。

一般线性规划问题具有线性方程组的变量数大于方程个数，这时有不定的解。但可以从线性方程组中找出一个个的单纯形，每一个单纯形可以求得一组解，然后再判断该解使目标函数值是增大还是变小，决定下一步选择的单纯形。进行迭代，直到目标函数实现最大值或最小值为止。

st=>start: 开始 op1=>operation: 确定初始基 cond=>condition: 最优解？ op2=>operation: 基变换、迭代 op3=>operation: 计算max或min ed=>end: 结束 st->op1->cond cond(no)->op2->cond cond(yes)[sd]->op3->ed

单纯形表

$A = \left[\begin{array}{c} B_{m×n} + I_{m×m} \end{array}\right]$ ，明显 $I$ 满足作为一个基的条件，我们一般选为初始基，故基变量系数初始值一般为0。

$X_B$ ：基变量
$C_B$ ：基变量系数
$n$ ：决策变量个数
$m$ ：基变量个数
$σ_j$ ：检验系数 $σ_j = c_j - \sum\limits_{i=1}^{m} c_{n+i} ⋅ a_{ij}$

解法

Step1：选
- 选出 $σ$ 最大的列 $j$ 作为进基。
- 从列 $j$ 中选出 $x_{ij}＞0$ 且 $\dfrac{b_i}{x_{ij}}$ （ $x_{ij}$ 为0则视为无穷大）最小的行 $i$ 为离基。
- $i$ 、 $j$ 的交叉点为主元 $a_{ij}$ 。
Step2：消
- $\dfrac{row(i)}{a_{ij}}$
- $\underset{k\ in\ row,k≠i}{for} [row(k) - a_{kj}row(i)]$
Step3：换
- 行 $i$ ， $x_B$ 更换为进基变量
- 行 $i$ ， $C_B$ 更换为进基 $c_j$
Step4：重新计算 $σ$ 。
Step5：重复上述操作，直到每列都满足 $σ≤0$ 。此时 $x_B$ 列的变量即等于 $b$ 列的值。

例

$\max \,\,\, z = 2x_1 + 3x_2$
$\begin{cases} x_1 + 2x_2 ≤ 80 \\ 4x_1 ≤ 160 \\ 4x_2 ≤ 120 \\ x_1, x_2 ≥ 0 \end{cases}$

解

$\max \,\,\, z = 2x_1 + 3x_2 + 0x_3 + 0x_4 + 0x_5$
$\begin{cases} x_1 + 2x_2 + x_3 = 80 \\ 4x_1 + x_4 = 160 \\ 4x_2 + x_5 = 120 \\ x_1, x_2, x_3, x_4, x_5 ≥ 0 \end{cases}$


	$c_j$	2	3	0	0	0
$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$b$
0	$x_3$	1	2	1	0	0	80
0	$x_4$	4	0	0	1	0	160
0	$x_5$	0	4	0	0	1	120
	$σ_j$	2	3	0	0	0

$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
0	$x_3$	1	0	1	0	$-\frac{1}{2}$	20
0	$x_4$	4	0	0	1	0	160
3	$x_2$	0	1	0	0	$\frac{1}{4}$	30
	$σ_j$	2	0	0	0	$-\frac{3}{4}$

$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
2	$x_1$	1	0	1	0	$-\frac{1}{2}$	20
0	$x_4$	0	0	-4	1	2	80
3	$x_2$	0	1	0	0	$\frac{1}{4}$	30
	$σ_j$	0	0	-2	0	$\frac{1}{4}$

$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$
2	$x_1$	1	0	0	$\frac{1}{4}$	0	40
0	$x_5$	0	0	-2	$\frac{1}{2}$	1	40
3	$x_2$	0	1	$\frac{1}{2}$	$-\frac{1}{8}$	0	20
	$σ_j$	0	0	$-\frac{3}{2}$	$-\frac{1}{8}$	0

取最优解时 $x_1=40$ 、 $x_2=20$ 、 $x_5=40$

$z = 2x_1 + 3x_2 + 0x_3 + 0x_4 + 0x_5 = 80 + 60 = 140$

人工变量法

当化为标准型后，可能无法找到单位矩阵作为初始基。
在引入人工变量前，已是等式，所以人工变量的最终取值必须为0，否则原问题无最优解。

大M法

在目标函数中，给人工变量赋一个充分大的系数—— $M$ 。由于人工变量为基变量，对目标函数来讲是不经济的，所以应尽快地用非人工变量把人工变量从基中替换出来。这个充分大的系数无须赋予一个特定的值。

在最大化（Max）问题中，用 $-M$ 来表示费用系数；
在最小化（Min）问题中，用 $M$ 来表示收益系数。

$M$ 是一个充分大的正数。

例

$\min \,\,\, ω = -3x_1 + x_2 + x_3$
$\begin{cases} x_1 - 2x_2 + x_3 ≤ 11 \\ -4x_1 + x_2 + 2x_3 ≥ 3 \\ 2x_1 - x_3 = -1 \\ x_1, x_2, x_3 ≥ 0 \end{cases}$

解

Step1：化为标准型

$\max \,\,\, z = 3x_1 - x_2 - x_3 + 0x_4 + 0x_5$
$\begin{cases} ①: x_1 - 2x_2 + x_3 + x_4 = 11 \\ ②: -4x_1 + x_2 + 2x_3 - x_5 = 3 \\ ③: -2x_1 + x_3 = 1 \\ x_1, x_2, x_3, x_4, x_5 ≥ 0 \end{cases}$

Step2：构造 $M$ （②、③）

$\max \,\,\, z = 3x_1 - x_2 - x_3 + 0x_4 + 0x_5 - Mx_6 -Mx_7$
$\begin{cases} ①: x_1 - 2x_2 + x_3 + x_4 = 11 \\ ②: -4x_1 + x_2 + 2x_3 - x_5 + x_6 = 3 \\ ③: -2x_1 + x_3 + x_7 = 1 \\ x_1, x_2, x_3, x_4, x_5 ≥ 0 \end{cases}$

Step3：使用单纯形法解该问题（ $x_6$ 、 $x_7$ 优先当离基）


	$c_j$	3	-1	-1	0	0	$-M$	$-M$
$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$	$b$
0	$x_4$	1	-2	1	1	0	0	0	11
$-M$	$x_6$	-4	1	2	0	-1	1	0	3
$-M$	$x_7$	-2	0	1	0	0	0	1	1
	$σ_j$	3-6 $M$	-1+ $M$	-1+3 $M$	0	$-M$	0	0

$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$	$b$
0	$x_4$	3	-2	0	1	0	0	-1	10
$-M$	$x_6$	0	1	0	0	-1	1	-2	1
-1	$x_3$	-2	0	1	0	0	0	1	1
	$σ_j$	1	-1+ $M$	0	0	$-M$	0	1-3 $M$

$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$	$b$
0	$x_4$	3	0	0	1	-2	2	-5	12
-1	$x_2$	0	1	0	0	-1	1	-2	1
-1	$x_3$	-2	0	1	0	0	0	1	1
	$σ_j$	1	0	0	0	-1	1- $M$	-1- $M$

$C_B$	$X_B$	$x_1$	$x_2$	$x_3$	$x_4$	$x_5$	$x_6$	$x_7$	$b$
3	$x_1$	1	0	0	$\frac{1}{3}$	$-\frac{2}{3}$	$\frac{2}{3}$	$-\frac{5}{3}$	4
-1	$x_2$	0	1	0	0	-1	1	-2	1
-1	$x_3$	0	0	1	$\frac{2}{3}$	$-\frac{4}{3}$	$\frac{4}{3}$	$-\frac{7}{3}$	9
	$σ_j$	0	0	0	$-\frac{1}{3}$	$-\frac{1}{3}$	$-M+\frac{1}{3}$	$-M+\frac{2}{3}$	$z=2$

两阶段法

运用计算机计算时，为避免 $M$ 可能带来的麻烦，把LP问题的求解分为两个阶段来进行。

第一阶段：先求解一个目标函数只包含人工变量的人造LP问题，即令极小值目标函数中人工变量的系数取某个正的常数（通常为1），而其他变量的系数为0。
第二阶段：从第一阶段得到的基可行解出发，求原问题的最优解。