单纯形法的矩阵描述

考虑将单纯形法的求解过程用矩阵进行描述，对于已经引入松弛变量的 LP 问题，其约束条件

\[BX_B+NX_N=b \tag{1} \]

目标函数

\[C_BX_B+C_NX_N=z \tag{2} \]

联立消去 \(X_B\) 得

\[z=C_BB^{-1}b+(C_N-C_BB^{-1}N)X_N \tag{3} \]

其中 \(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\) 对应的原始系数矩阵的那一列。

我们有递推式

\[B_{i}^{-1}=E_iB_{i-1}^{-1} \tag{4} \]

其中 \(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\) 是换出变量对应的行，则

\[\xi_i = (-\frac {a_1} {a_l}, ...,\frac 1 {a_l},...,- \frac {a_m} {a_l}) \tag{5} \]

于是，

\[B_i^{-1}=(e_1,...,e_{j-1},\xi_i,e_{j+1},...,e_m)B^{-1}_{i-1} \tag{6} \]

换入变量求解根据检验数

\[\sigma_i = C_{N_i}-C_{B_i}B_i^{-1}N_i \tag{7} \]

中找最小值下标即可得到，换出变量根据 \(\theta\) 法则求

\[\theta = \displaystyle\min_l \{ \frac {B_i^{-1}b} {B_i^{-1}P_k} | B_i^{-1}P_k >0\} \tag{8} \]

即可得到。