单纯形法的求解步骤

由凸集的定理知，线性规划的最优解一定是基可行解，基可行解一定是凸集顶点上，而线性规划问题的可行域就是凸集，可行域就是可行解的集合。所以，为了求得最优解，就要找基可行解。

这就是为什么线性规划的步骤为：找基 - 求基解 - 验证是否为基可行解 - 验证是否是最优解 - 若不是最优解，迭代（基变换）。

首先，将线性规划问题转化为标准数学模型
其次，先找处一个初始基，并验证它是可行基
- 找基：找一个系数矩阵的最大满秩子方阵（ $m \times m$ 阶）
- 求基解：令非基变量为 0，则约束方程组成为一个 $m \times m$ 阶线性方程组，必有唯一解。求解现在的约束方程，所得为基解。
- 验证是否为基可行解：如果基解中所有基变量均满足非负约束，则该基解为基可行解。
检验是否为最优解：
- 所有 $σ_j ≤ 0$ ，则为当前即为最优解
- 所有 $σ_j ≤ 0$ ，但存在一个 $σ_j = 0$ ，则有无穷多最优解
- 存在 $σ_j > 0$ ，且对应非基变量 $x_j$ 的所有系数 $a_{ij} <0$ ，则无最优解
- 存在 $σ_j > 0$ ，且对应非基变量 $x_j$ 的系数中，存在 $a_{ij} >0$ ，则可以继续迭代
若可继续迭代，则进行基变换
- 确定换入变量：选择取得最大正数 $σ_j$ 的非基变量 $x_j$ ，作为换入变量
- 确定换出变量：选择取得最小正数 $θ_j=\frac{b_i}{a_{ij}}$ 的 $i$ 对应的基变量 $x_i$ ，作为换出变量
- 基变换：令 $x_j=θ，x_i=0$ ，并将新基变量的系数矩阵 $B$ 化为单位矩阵，得到新的基
- 重新验证：对新基重新 “求基解 - 验证是否为基可行解 - 验证是否为最优解...”，直到无法继续迭代为止

$σ_j$ 是基变换后目标函数的变动量。（所有 $σ_j≤ 0$ 意味着没有比现在更好的选择）
$θ$ 是非基变量的最小的正数取值。