考虑将单纯形法的求解过程用矩阵进行描述，对于已经引入松弛变量的 LP 问题，其约束条件
目标函数
联立消去 \(X_B\) 得
其中 \(C_N-C_BB^{-1}N\) 就是所谓的检验数 \(\sigma\)。
因此，单纯形表可以描述为
| 基变量 \(X_B\) | 非基变量 \(X_N\) | 右侧 RHS | |
|---|---|---|---|
| 系数矩阵 | \(I\) | \(B^{-1}N\) | \(B^{-1}b\) |
| 检验数 | \(0\) | \(C_N-C_BB^{-1}N\) | \(-C_BB^{-1}b\) |
任意时刻各个部分的核心是某个已知矩阵的部分左乘一个 \(B^{-1}\)，因此求解的核心在于快速地维护 \(B^{-1}\)。
以下我们设 \(P_k\) 是 \(x_k\) 对应的原始系数矩阵的那一列。
我们有递推式
其中 \(E_i\) 是把一个单位矩阵中，第 \(j\) 列替换为 \(\xi_i\) 后的结果，其中 \(j\) 表示本次新换入的基在 \(B_i\) 中对应第 \(j\) 列，\(\xi_i\) 由本次换入变量在换入前 \(B_{i-1}^{-1}N_{i-1}\) 中对应的列 \((a_1,a_2,...,a_m)\) 变换得到，设 \(l\) 是换出变量对应的行，则
于是，
换入变量求解根据检验数
中找最小值下标即可得到，换出变量根据 \(\theta\) 法则求
即可得到。
原文：https://www.cnblogs.com/mollnn/p/14771316.html