在 OI 中更易上手的线性规划对偶-526互联

怎么线性规划对偶？

我：写出约束，转为标准型，转置矩阵，对换目标与约束，整理。

zhy：直接给每一个变量设一个变元乘上去整理一下就可以了。

于是在网上查了一下资料，发现了这篇讲稿，感觉这个方式快捷多了啊，于是记了一下。

如果你看过算法导论之类的一些东西（有点记不清是不是这本书了），你发现上面讲解线性规划对偶时不是像网上一些东西一样直接提这个东西的机械改写方法：把线性规划写成矩阵然后再无脑转置，而是为每一条约束设置了一个变量，从原理角度入手线性规划对偶（这个东西和拉格朗日乘数法的思想很像不是吗）。

事实上你同样可以用这种方法导出另一种机械改写线性规划的方式，而且这种方式在实践中明显更加好用。尤其是 OI 中的线性规划对偶题，如果强行转化成标准型再对偶容易失去一些简洁的形式，然后就出现了“明明我对偶了但是看不出这个线性规划的组合意义怎么办”这种尴尬问题。

这个线性规划机械改写的方式如下：

Step 1.

首先明确你的线性规划的形式，你的形式并不经常是标准型，而这种方式并不要求是标准型才能开始对偶。对于每一个变量 $x_i$，你都可以有 $x_i\leq 0$、$x_i\geq 0$ 和无限制三种针对每个变量的特殊限制。以及一些其它的针对这些变量线性组合的约束。这些约束也可以选择是 $\leq$、$\geq$ 和 $=$ 中的一种。你的最优化目标可以是最大化也可以是最小化。

然后再进行一定的整理：将所有约束的右边清零。这个移个项就行了。

Step 2.

针对于每一条约束设一个乘子变量，假设叫做 $\lambda_i$。将每一条约束的左边乘上对应的 $\lambda_i$ 然后加到你的最优化目标上去。然后你就得到了关于 $x_i$ 与 $\lambda_i$ 的一个多元函数，设为 $L(\boldsymbol \lambda,\mathbf x)$。

然后为 $\lambda$ 添加特殊限制。如果 $\lambda_i$ 对应的约束是不等式，且最优化函数是求最小值，那么添加 $\lambda_i \geq 0$；如果是求最大值，添加 $\lambda_i \leq 0$（或者你只需要记 $\min$ 的情况，将所有变量取个反就转化到 $\max$ 的情况了）。如果 $\lambda_i$ 对应的约束是等式，则不添加关于 $\lambda_i$ 的特殊限制。

Step 3.

以下假设你的最优化目标是 $\min$，如果是 $\max$ 的话交换以下的 $\min$ 和 $\max$。考察这个奇怪的东西 $\max_{\boldsymbol \lambda} \min_{\mathbf x} L(\boldsymbol \lambda,\mathbf x)$。把它从关于 $ \lambda_i$ 主元的线性函数整理成由 $x_i$ 主元的线性函数。

Step 4.

我们为什么要在 $L$ 函数前添加 $\max \min$ 这样奇怪的东西呢？这是为了提醒我们接下来的一部操作。你可以把 $\min,\max$ 想像成一个双人玩家游戏，首先外层玩家先操作设定 $\boldsymbol \lambda$，内层玩家后操作设定 $\mathbf x$。为了防止内层玩家能够成功达到 $-\infin$，外层玩家设定的 $\boldsymbol \lambda$ 必须要满足一些约束。

比如说我们对于每个变量 $x_i$，如果有关这个 $x_i$ 的特殊限制是 $x_i\geq 0$，那么如果 $x_i$ 对应的系数是负数（这现在是 $\lambda_i$ 的某些线性组合加上一个常数），那么 $x_i$ 就可以取 $+\infin$ 从而让外层玩家输掉这个游戏。所以外层玩家会添加约束：$x_i$ 对应的系数非负。对于 $x_i\leq 0$ 和 $x_i$ 无限制的特殊限制，我们同理可以导出它们对应的约束分别是非正、$=0$。

（上面所有的讨论建立在最优化目标是取 $\min$ 的情况下，$\max$ 的情况只需要换成 $\min \max$ 同理推导一下就可以了！）

然后将所有与 $x_i$ 有关的项从 $L$ 函数中抹去。剩下的就是对偶线性规划的最优化目标。

实例

实操一下上面的过程，发现这本质上跟矩阵对偶得到的结果一模一样。在这个过程中，原约束对应对偶的变量，原变量对应对偶的约束，原特殊限制决定对偶约束的符号方向，原约束现在决定对偶的特殊限制。

你会发现这就避免了矩阵对偶方式中产生大量的无用的零。因为在实际做题的做题过程中你线性规划的约束矩阵大多是稀疏的。这个过程有了两个明显的优势：不用化标准型，不用整一大堆填充矩阵的零。而且在线性规划中有 $\sum$ 时可以直接带着 $\sum$ 走，组合意义更清晰！

我们就拿 Welcome to Tokyo 这道题举个例子。

这道题的原线性规划是：

\[\begin{aligned} \max &\sum_{i=1}^m b_i \\ s.t. \quad a_i &\leq 1\\ b_i &\leq 1\\ b_i &\leq \sum_{j\in [l_i,r_i]} a_j\\ \sum_i {a_i}&\leq k\\ a_i,b_i&\geq 0 \end{aligned} \]

特殊限制是 $a_i,b_i\geq 0$，清空约束右侧：

\[\begin{aligned} \max &\sum_{i=1}^m b_i \\ s.t. \quad a_i-1 &\leq 0\\ b_i-1 &\leq 0\\ b_i-\sum_{j\in [l_i,r_i]} a_j &\leq 0\\ \sum_{i=1}^n {a_i}-k&\leq 0\\ a_i,b_i&\geq 0 \end{aligned} \]

给四类限制分别添上乘子变量 $x_i,y_i,z_i,t\leq 0$（由于是 $\max$ 添加特殊限制：$\leq 0$）。乘上对应约束加进最优化目标得到 $L$ 函数：

\[\sum_{i=1}^m b_i+\sum_{i=1}^n x_i(a_i-1)+\sum_{i=1}^m y_i(b_i-1)+\sum_{i=1}^m z_i (b_i-\sum_{j\in [l_i,r_i]} a_j)+\sum_{i=1}^n ta_i-tk \]

整理成关于 $a_i,b_i$ 的形式：

\[\sum_{i=1}^n (t+x_i-\sum_{i\in [l_j,r_j]}z_j) a_i+\sum_{i=1}^m (y_i+z_i+1)b_i -x_i-y_i-tk \]

考虑到外层玩家需要避免内层玩家达到 $+\infin$，而所有的 $a_i,b_i$ 的特殊限制都是 $\geq 0$ 的。所以我们添加 $\leq 0$ 的约束：

\[\begin{aligned} \min &-\sum_{i=1}^n x_i-\sum_{i=1}^m y_i-kt \\ s.t. \quad t+x_i &\leq \sum_{i\in [l_j,r_j]} z_j\\ y_i+z_i &\leq -1\\ t,x_i,y_i,z_i &\leq 0 \end{aligned} \]

都是非正数，好不习惯！所有变量取个反先！

\[\begin{aligned} \min &\sum_{i=1}^n x_i+\sum_{i=1}^m y_i+kt \\ s.t. \quad t+x_i &\geq \sum_{i\in [l_j,r_j]} z_j\\ y_i+z_i &\geq 1\\ t,x_i,y_i,z_i &\geq 0 \end{aligned} \]

根据邓老师的说法这个对偶形式也是 unimodular 的。所以我们可以假定所有变量都取整数。显然下面那个式子取到 $y_i+z_i=1$ 最优。（因为两个变量对于最优化目标的贡献都是正的）

那么对于每个 $i$ 就只剩下 $y_i=1,z_i=0$ 或者 $y_i=0,z_i=1$ 两种选项。假设我们决策完了这一部分。选择 $z_i=1$ 相当于选一个区间，覆盖数轴上的一段点，每个点覆盖次数是 $c_i$。然后如果你决策了 $x_i$，那么 $t$ 一定尽可能往小了取，取 $\max_{i=1}^n c_i-x_i$。相当于你可以花一单位的代价缩减某个位置的覆盖次数。然后你会发现这样一个一个点去缩减限制好憨，你直接取消掉覆盖这些位置的一个区间代价也是一个单位。所以最优解中有 $x_i=0$。

问题完全转化成了从区间集合中选一个区间子集 $S$，用 $S$ 中的区间得到每个点被覆盖的次数 $c_i$，然后计算 $m-|S|+k\max_{i=1}^n c_i$ 的最小值。邓老师说这个问题增量贪心做就是对的。