对偶单纯形法¶
在单纯形法中, 我们解决了这样的线性优化问题:
给定常量矩阵 \(A\), 向量 \(\mathbf{b}\), \(\mathbf{c}\) 与一个非负的变量向量 \(\mathbf{x}\), 求在 \(A\mathbf{x} \leq \mathbf{b}\) 的情况下, \(\mathbf{c}^T\mathbf{x}\) 的最大值.
我们给出的方法利用了这样的矩阵:
对于 \(m\times n\) 的矩阵 \(A\) 而言, 这相当于引入了 \(m\) 个松弛变量, 并以他们为第一个基解. 但是, 这会导致这些松弛变量恰好等于 \(\mathbf{b}\). 如果 \(\mathbf{b}\) 中含有负数, 那么它不是基可行解, 单纯形法就失效了.
对偶单纯形法 (dual simplex algorithm) 可以在这种情况下找到一个可行解, 并且保持 \(\mathbf{c}^T\mathbf{x}\) 的值不变. (当然, 在换基的时候, \(\mathbf{c}\) 中的数可以变, 但最后的结果不会改变.) 特别地, 如果你已经获取了一个最优解, 但它不在可行域内, 你就可以用对偶单纯形法找到一个最优的可行解.
算法流程¶
假设松弛完毕之后, 我们的约束变为了 \(A\mathbf{x} = \mathbf{b}\), 而目标则是 \(\mathbf{c}^T\mathbf{x}\). 在单纯形法中, 我们每次换基都分为两步:
- 确定替入变量 (\(c\) 中对应系数最大的变量);
- 确定替出变量 (\(x_{B_i}/A_{ik}\) 最大的变量).
在对偶单纯形法中, 我们的执行顺序恰好相反: 先替出, 再替入.
我们一般选择 \(b_i\) 值最小的变量 \(x_{B_i}\) 替出.
替入时, \(x_{B_i}\) 的值将会从 \(b_i\) 增加到 \(0\). 这意味着替入变量 \(x_k\) 的值将会从 0 变为 \(b/A_{ik}\). 为了使替入的变量非负, 我们要求 \(A_{ik} < 0\). 如果找不到这样的 \(A_{ik}\), 那就说明原问题无解. 进一步地, 我们一般选择 \(c_k / A_{ik}\) 最小的变量替入. 其实我并不太理解为什么, 不过至少这个选择是安全的.
只需要不断地换基, 直到 \(b\) 的每个元素都非负, 我们就获得了一个可行解.