2026-04-10
单纯形法
考虑一个等式线性规划问题：
- Minimize \(X=\sum c_ix_i\)，需要满足 \(x\ge 0\) 并且 \(Ax=b\).
单纯形法即为，提取 \(A\) 的线性无关列 \(B\)，其他线性相关变量可以直接设为 0，然后剩下的线性无关列直接解方程 \(x_B=B^{-1}b\).
这个很难是最优的，但是由于这个问题是凸的，所以直接爬山就行了：
- 作基变换，用一个非基变量替换一个基变量，得到新的可行解，使得目标函数不升.
如何检验当前解的最优性？考虑目标函数 \[ X=c^Tx=c^Tx+c^T_BB^{-1}(b-Ax)\\ = c^{T}B^{-1}b+(c^T-c^T_B B^{-1}A)x\\ \] 令检验数 \(\lambda^T=c^T-c_B^TB^{-1}A\). 如果 \(\lambda\ge 0\)，则证明为最优解；否则，如果存在 \(\lambda_k<0\) 并且 \(a_{i,k}\) 全部 \(<0\) 则无最优解（直接把 \(x_k\) 不断增大就可以达到 \(-\infty\)）；否则需要进行基变换，把 \(k\) 换入基中.
调换出来的需要尽量性价比高. 定义 \(\beta_i=B^{-1}b\)，那么性价比可以定义为 \(\theta_i=\beta_i/a_{i,k}\)，把 \(\theta_i\) 最小的给换走即可.
对偶思想与弱对偶引理
考虑如下的最简单的线性规划问题：
- Maximize \(X=\sum c_ix_i\)，但是需要满足 \(x_i\ge 0\) 并且有如下的限制：第 \(j\) 条限制是 \(\sum_i a_{j,i}x_i\le b_j\).
那么一个小学生想法就是，我们能不能给每个限制赋予一个系数 \(y_j\)，使得 \(\sum_j a_{j,i}y_j\ge c_i\)，那么我们把所有限制按权相加就得到了关于一个 \(\sum c_ix_i\) 的 Bound. 那么原问题的答案一定小于等于这个 Bound.
这就是对偶 (dual) 的思想. 我们把 \(y_i\) 的限制写下来，得到：
- 第 \(i\) 条限制是 \(\sum_j a_{j,i}y_j\ge c_i\)，并且需要满足所有 \(y_j\ge 0\).
- Minimize \(Y=\sum_j b_jy_j\).
根据我们之前的描述，一定有 \(Y\ge X\). 这个就是弱对偶引理.
线性代数的视角
我们考虑将刚才的这些文字推导落实到简洁严谨的数学语言上.
原问题很容易描述：\(A\in \R^{m\times n}\)，\(b\in \R ^m\)，\(c\in \R^n\)，我们有 Constraint \(Ax\le b\)，\(x\ge 0\)，并且需要 Maximizes \(c^Tx\).
我们赋予系数的这一个操作相当于就是取 \(y\in \R^m\)，把 Constraint 变成 \(y^TAx\le y^Tb\).
另一方面，只要 \(A^Ty\ge c\)，我们就有 \(c^Tx\le (A^Ty)^Tx=y^TAx\le y^Tb\).
于是得到对偶问题：Constraint \(A^Ty\ge c\)，\(y\ge 0\)，然后 Minimize \(b^Ty\).
上面的不等式也就是前面所述的弱对偶引理：\(c^Tx\le b^Ty\).
显然地，对偶问题的对偶仍为原问题.
强对偶引理与互补松弛
我们显然不满足上述的一个不等式形式，我们希望知道上述问题何时取等，以及如何用对偶来帮助我们解决问题.
我们引入松弛变量 \(u\)，将条件写成等式形式：\(Ax+Iu=b\)，\(x\ge 0,u\ge 0\)，即 \(b-Ax=u\)；另一方面，对于对偶条件，写 \(A^Ty-c=v\)，\(v\ge 0\).
我们考虑差值 \[ b^Ty-c^Tx=(Ax+u)^Ty-(A^Ty-v)^Tx\\ =(x^TA^Ty-y^TAx)+(u^Ty+v^Tx) \] 由于 \(x^TA^Ty\) 为标量显然对称. 所以差值为 \(u^Ty+v^Tx\). 由于所有向量都 \(\ge 0\)，所以取等条件一定是 \(u_jy_j=v_ix_i=0\). 这也就是线性规划问题的互补松弛 (complementary slackness). 互补松弛和等号成立是等价的.
首先从弱对偶引理可以直接得到一个推论：对于可行解 \(x^*,y^*\)，若 \(c^Tx^*=b^Ty^*\)，则 \(x^*,y^*\) 分别是问题的最优解.
我们在引入松弛变量后，就可以将 \((x\ u)\) 看作需要求解的变量，然后使用单纯形法来求解一个最优解 \(x^{*}\). 考虑此时的检验向量 \(\lambda\). \(x\) 所对应的检验向量 \(\lambda_x^T=c^{T}-c_B^TB^{-1}A\le 0\)，\(u\) 所对应的检验向量 \(\lambda_u^T=-c^T_BB^{-1}\le 0\).
我们可以令 \(y^T=c_B^TB^{-1}=-\lambda_u^T\ge 0\)，得到 \(A^Ty-c=-\lambda_x\ge 0\)，故 \(y\) 为对偶问题的可行解. 同时，\(y^Tb=c_B^TB^{-1}b=c^Tx\)，满足，故为最优解.
于是，我们得到强对偶引理：
- 原问题（或对偶问题）有最优解
- 等号成立 \(c^Tx^*=b^Ty^*\).
- 互补松弛 \(u_jy_j=v_ix_i=0\).
上述三者等价.
一个推论是：如果原问题无可行解，则对偶问题可以取 \(-\infty\)；另一方面，如果原问题可以取 \(+\infty\) 则对偶问题无可行解.