线性规划对偶

刚刚去瞅了眼 HLPP，又去瞅了眼 KM，感叹还是学理论好。

概念

线性规划是在对一些实数变量的线性不等关系约束下，求解一个线性表达式的最值的过程。

标准型：

$\max:\sum_jc_jx_j\\\text{s.t. }\forall i,\sum_ja_{i,j}x_j\le b_i\\\forall j,x_j\ge 0$

大于零其实是不重要的，你可以平移你的变量范围，体现在 $a,b$ 上。

同理， $\max/\min$ ，大于小于也不重要。

标准型线性规划可以对偶为如下问题：

$\min:\sum_ib_iy_i\\\text{s.t. }\forall j,\sum_ia_{i,j}y_i\ge c_j\\\forall i,y_i\ge 0$

有些时候一个问题的对偶问题会更好求一点，因为它可能会从一个没性质的问题变成一个流。

我们可以把对偶原理写成向量和矩阵描述的简洁形式：

$\max c\cdot x:Ax\le b,x\ge 0\iff\min b^T\cdot y:A^T y\ge c^T,y\ge 0$

可以理解为转化后 $A,b,c$ 全都变成了原来的转置， $b^T,c^T,y$ 都是列向量。

但暴力写出矩阵然后转置是极为低效的做法，并且对偶后的标准型也长成了一坨，很难化简。

（有的时候限制是多种多样的，但我们仍然给它们一个新的标号方式使得它们是上图中 $Ax\le b$ 的形式，但对偶后你可能需要设多种变量，每条限制都需要对应一个变量，这些变量的最优化形式和原先限制的形式相同，所以如果原先限制的形式不同，那最优化这一步容易乱了阵脚。）

从在 OI 中更易上手的线性规划对偶这篇文章里，我们能找到一种很好的对偶方法，无需化成标准型，以下是摘抄。

工业化流程：

Step 1.

写出原始的限制，将所有限制移项，整理成 $sth\le 0$ 的形式。

Step 2.

给每条限制设定一个变元乘子 $\lambda_i$ （可以理解为 $y_i$ ），乘上这个限制，加到要最优化的东西里面，并设定该变元乘子的范围。

设定 $\lambda$ 范围规则：若 $\min c_ix_i$ 则添加 $\lambda_i\ge 0$ ， $\max$ 则添加 $\lambda_i\le 0$ 。

Step 3.

将 $L(\lambda,x)$ 化成关于 $x$ 的主元式，并只保留这个式子的常数项（抹掉所有含 $x$ 的项），常数项就是我们要最优化的关于 $\lambda$ 的式子，优化方向与 $x$ 相反，含 $x$ 的项中 $x$ 前面的系数就是新的限制，求 $\min$ 时系数 $\ge 0$ ，求 $\max$ 时系数 $\le 0$ 。

解释/好的理解

上面的工业化流程你肯定看的云里雾里，下面是我对其的一些理解。

观察我们将所有限制和最优化的东西混合起来的这个柿子，我们称它为 $L(\lambda,x)$ ，假设原题目要求我们 $\min c_ix_i$ ，我们来考虑 $\max_\lambda\min_xL(\lambda,x)$ 。

为什么要考虑这个奇怪的东西呢，线性规划对偶是把一个 $\min$ 问题变成一个 $\max$ 问题，所以我们要利用拮抗的两维来达到某种平衡。

你可以将其看作一个二元博弈，外层决策者为了不让内层决策者达到 $-\infty$ 的目的，会对自己的 $\lambda$ 设定一些范围。

你可以将外层决策者看作~~古希腊~~掌管限制的神，这些限制每个都发挥了至关重要的作用，以至于只要有一个限制消失了，内层决策者就可以让答案达到无穷优。

他为了不让内层决策者跳出他所框定的限制，他利用不等式的可加性创造出了 $L(\lambda,x)$ ，并自己下场设定 $\lambda$ ，并且他的优化方向和内层决策者（也就是原题的最优化方向）是相反的，很容易直观理解，外层决策者越劣化 $L(\lambda,x)$ ，就证明内层决策者越好地遵循了限制。

由此我们可以看到 Step 2 中 $\lambda$ 正负性的道理，求 $\min$ 可以看作二分答案后判断 $\le mid$ ，而不等式只有同向才有可加性，所以求 $\min$ 时 $\lambda\ge 0$ ，求 $\max$ 时 $\lambda\le 0$ ，这保证了不等式的方向。

下文我们不妨认为内层决策者的方向是最小化。

此时外层决策者如何最大化这个式子呢？首先他化成了关于 $x$ 的主元式，接下来，他首先要避免某个 $x$ 前面的系数 $<0$ ，因为如果这样的话内层决策者可以轻松把这个式子变成 $-\infty$ ，所以 $x$ 前面的系数就成为了新的 $\lambda$ 的限制。

然后它会想办法最大化常数项，这是因为首先内层决策者可以让式子的值等于常数项，其次由于 $x$ 前面的系数都 $\ge 0$ ，所以如果式子的值不等于常数项，必定对内层决策者来说会更劣，所以在 $\lambda$ 满足限制的前提下，内层决策者一定会让式子的值变成常数项。

所以问题转化成了对 $\lambda$ 的相反方向的最优化问题。

关于对偶的一个例子，可以去在 OI 中更易上手的线性规划对偶查看。

#D. 安装软件包

给定 $n$ 个待安装的软件包，每个软件包有一个安装时间 $t_i$ 。

给定一个 $n$ 个点 $m$ 条边的有向无环图表示软件包之间的依赖关系（可能存在重边）。一条从 $u$ 到 $v$ 的有向边表示软件包 $u$ 必须在软件包 $v$ 安装完成之后开始安装。在满足这些条件的前提下，没有依赖关系的软件包可以并行安装。

对于每个软件包 $i$ ，都可以用 $c_i$ 的代价将其安装时间减小 1，但不可超过负数。

现在，给定一个预算 $w$ ，求在支出的条件不大于 $w$ 的前提下，安装完所有软件包所需的最小时间。

$n\le 55,m\le 400,t_i\le 10^3,c_i\le 10^4$ 。

二分答案后最小化代价，神秘最优化问题，尝试写成线性规划的形式，设 $P$ 是 DAG 上的路径集合， $x_i$ 表示第 $i$ 个点降了多少。

$\min \sum_ic_ix_i\\s.t.\forall p\in P,\sum_{i\in p}(t_i-x_i)\le mid\\x_i\le t_i\\x_i\ge 0$

来给限制分配变量 $y,z$ ，我们写出 $L(y,z,x)$ ：

$\begin{aligned}L(y,z,x)&=\sum_{p\in P}y_p(\sum_{i\in p}(t_i-x_i)-mid)+\sum _iz_i(x_i-t_i)+\sum_i c_ix_i\\&=\sum_ix_i(c_i+z_i-\sum_{x\in p\in P}y_p)+\sum_{p\in P}y_p(\sum_{i\in p}t_i-mid)-\sum_iz_it_i\end{aligned}$

所以新的问题是：

$\max\sum_{p\in P}y_p(\sum_{i\in p}t_i-mid)-\sum_iz_it_i\\s.t.\sum_{i\in p\in P}y_p\le c_i+z_i\\y\ge0,z\ge 0$

线性规划对偶多数时候要么转成流，要么转成贪心，肯定不会对偶完了再跑网络单纯形。

考虑给这个东西赋予一个意义。

DAG 上，我们要路径覆盖，每覆盖一条都会收获 $\sum t_i-mid$ 的价值，每个点有经过次数限制 $c_i$ ，每多经过一次就要花费 $t_i$ 的代价。

考虑拆点费用流，每单位流量表示覆盖一次，每个点拆成入点出点，入点向出点连 $c_i$ 的费用 $t_i$ 边，连 $\infty$ 的费用为 $0$ 的边， $S$ 向每个入点连 $\infty$ 的免费边，出点向 $T$ 连 $\infty$ 的费用为 $mid$ 的边，原图中的边都是 $\infty$ 的免费边。

这个图的最大费用流（不是最大费用最大流）就是答案。