求出一个初始基本可行解，判断其是否最优，若不是最优，再换一个基本可行解并判断，直到得出最优解 / 无最优解

# 判断检验数（针对目标函数求 max，且无人工变量的情况）

所有检验数都满足 $\sigma_j\le0$ $σ_{j} \leq 0$ ，得到最优解，其中
- 若所有非基变量的检验数均小于零，则为唯一最优解
- 若存在非基变量的检验数为零，则为多重解
若存在检验数 $\sigma_k>0$ ，且其对应的变量 $x_k$ 的系数列向量 $P_k\le0$ ，则为无界解

# 例题

当没有足够基变量的时候，手动添加人工变量 $x_i,~...,~x_j$
如果系数矩阵中不存在单位矩阵，则加入非负的人工变量，构造一个单位矩阵。
若线性规划有最优解，则人工变量必定为 $0$ ，为使人工变量为 $0$ ，就要使人工变量从基变量中出基变为非基变量

原问题	人工变量在目标函数中的系数	求解原理
目标函数求 $max$	$-M$ （ $M$ 为任意大的正数）	目标函数要实现最大化，必须把人工变量从基变量中换出
目标函数求 $min$	$M$ （ $M$ 为任意大的正数）	目标函数要实现最小化，必须把人工变量从基变量中换出

所有检验数都满足 $\sigma_j\le0$ $σ_{j} \leq 0$ ，且基变量中无人工变量，得到最优解，其中
- 若所有非基变量的检验数均小于零，则为唯一最优解
- 若存在非基变量的检验数为零，则为多重解
所有检验数都满足 $\sigma_j\le0$ ，但基变量中含有非零的人工变量，则无可行解
若存在检验数 $\sigma_k>0$ ，且其对应的变量 $x_k$ 的系数列向量 $P_k\le0$ ，则为无界解

大 $M$ 法和单纯型法没有啥区别，只是在初始时没有一个单位矩阵，加了人工变量的单纯型法

决策变量：原问题未知变量 $+$ 松弛变量 $+$ 人工变量
目标函数
- 单倍人工变量和 $x_i+...+x_j$ 求最小值 $\to$ 在找入基变量的时候，找的是最小值入
- 单倍人工变量和 $-1*(x_i+...+x_j)$ 求最大值 $\to$ 在找入基变量的时候，找的是最大值入
- 出基变量的都是选择最小的那个，并且仅考虑系数为正的约束
约束条件：原问题加入人工变量后的约束条件
- 若得到最优目标函数为零，说明原问题有基可行解，可以进行第二阶段计算
- 反正，说明原问题无可行解，停止计算

多重解：存在非基变量的检验数为零
- 求得一个最优解 $x_1^*$ 后，以检验数为零的非基变量为进基变量，再进行一次单纯形法迭代运算得到 $x_2^*$
- 由 $x_1^*,~x_2^*$ 的线性组合 $x^*=ax_1^*+(1-a)x_2^*,~0 \le a \le 1$
无界解
- 极大值问题：存在检验数 $\sigma_k > 0$ ，其对应变量 $x_k$ 的系数列向量 $a_{ik}$ 均 $\le 0$
- 极小值问题：存在检验数 $\sigma<0$ ，其对应变量 $x_k$ 的系数列向量 $a_{ik}$ 均 $\le 0$
退化解：模型中存在多余的约束条件
- 用最小 $\theta_i$ 比值确定出基变量时候，存在两个及以上的最小比值
不可行解：模型中有相互矛盾的约束条件
- 基变量中含有非零的人工变量

找出满足约束条件的基解并判断哪些是基可行解，并确定哪一个是最优解

找出（各系数列向量线性独立）的基矩阵
令其余非基变量为 $0$ $0$ ，求解出基变量的值，组合起来便是基解
- 如果求出的基变量的值满足约束条件，则是基可行解
- 反之是基不可行解
将得出的基可行解代入目标函数，得出的所有值中，最大的便是最优解