单纯型法在求逆矩阵时的数值问题

求解线性规划的一个经典且成熟的算法是单纯形法，这也是很多线性规划求解器的一个核心算法。其中，在判断基解的出入基操作时，需要计算并判断非基变量的检验数的大小和正负符号，在计算检验数的时候需要通过约束条件，用非基变量的表达式替代基变量。

例如这样一般的约束形式：

$Ax=b$

将 $x$ 拆成基变量和非基变量，写成如下形式：

$B{x}_B+N{x}_N=b$

用非基变量表达式表示基变量，得到：

$x_B=B^{?1}(b?N{x}_N)$

可以看到，基变量的系数矩阵在左右乘以 $B$ 的逆矩阵而消掉，得到了 $x_B$ 的表达式，在这里，由于出现了逆矩阵，如果矩阵在求逆过程中有数值问题，例如前文说的四舍五入、计算机存储误差等，都可能会导致 $x_B$ 的值变得病态，最终也导致求出的检验数有较大错误。以最简单的方阵为例，$B=[m]\to B^{?1}=[1/m]$，这里如果 $m$ 是一个接近于 0 的数，则逆矩阵的值将会很畸形，导致结果变化很大。

且这种出入基的操作会累计重复这种错误，从而导致算法求解结果不正确或者搜索缓慢（无效入基操作，模型退化）。由于换基，这种错误并不会不断放大，因此相比其他的优化算法，线性规划单纯型法算是对数值问题的反应比较温和，而其他算法在表述和求解问题时，因更加注重模型参数、系数的准确性。