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

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

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

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