[笔记] 线性规划 学习笔记

· · 算法·理论

参考资料：

Linear Programming

Introduction

给定一个基集 U，存在可行解集合 \mathcal{S}，是 U 的一些子集形成的“集合族”，有 w_i,i\in U，表示元素的价值。要找到 S\in \mathcal{S} 最小化或最大化 w(S):=\sum\limits_{i\in S}w_i。

一些例子：最短路问题、最小生成树问题、最大独立集、图的最大匹配、背包问题。

几乎所有组合优化问题 Combinatorial Optimization Problem 都可以等价地写成一个整数规划问题 Integer Program（IP），就是变量 x_i\in\{0,1\} 表示是否选择 i，约束是解在可行解集合中，目标是最优化 \sum w_ix_i。

而 IP 问题很难，一般是 NP-Hard 的，但我们可以把松弛 relax 成 x\in\{0,1\}\implies 0\leq x_i\leq 1，变成一个线性规划问题 Linear Program（LP）问题。

对于一些问题，\text{LP}\equiv \text{IP}，我们就获得了精确算法 Exact Algorithms。而一些问题 \text{LP}\not\equiv \text{IP}，我们只能通过解决 LP 问题得到一个分数解，然后设计算法把解取整变成一个整数解，这就是近似算法 Approximation Algorithms。

线性规划问题的一个例子：

\begin{aligned} \min\quad 7x_1+4x_2& \quad \text{s.t.}\\ x_1+x_2&\geq 5\\ x_1+2x_2&\geq 6\\ 4x_1+x_2&\geq 8\\ x_1,x_2&\geq 0 \end{aligned}

最优解是 x_1=1,x_2=4 得到 7\times 1+4\times 4=23。

以下是线性规划的标准形式：

\begin{aligned} \min\quad c_1x_1+c_2x_2+\dots+c_n x_n& \quad \text{s.t.}\\ a_{1,1}x_1 + a_{1,2}x_2 + \cdots + a_{1,n}x_n&\geq b_1 \\ a_{2,1}x_1 + a_{2,2}x_2 + \cdots + a_{2,n}x_n&\geq b_2 \\ \vdots \qquad \vdots \qquad \vdots \qquad \vdots \qquad \\ a_{m,1}x_1 + a_{m,2}x_2 + \cdots + a_{m,n}x_n&\geq b_m \\ x_1,x_2,\cdots,x_n&\geq 0 \end{aligned}

其中 n 是变量个数，m 是限制个数。

写成：

x := \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} \in \mathbb{R}^n c := \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{pmatrix} \in \mathbb{R}^n A := \begin{pmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{pmatrix} \in \mathbb{R}^{m \times n} b := \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix} \in \mathbb{R}^m

那么有：

\begin{aligned} \min\quad c^{\mathsf T}x& \quad \text{s.t.}\\ Ax&\geq b\\ x&\geq 0 \end{aligned}

所有的线性规划都可以转化成标准形式。

我们称满足 Ax\geq b,x\geq 0 的 x 的集合为可行域 Feasible Region，可行域其实是一个多面体 Polyhedron。如果一个多面体中，每一个坐标方向都有上界和下界，那么这个多面体就是一个多胞体 Polytope。

如果满足以下条件，则称 x 是

存在 $\lambda_1, \lambda_2, \dots, \lambda_t \in [0,1]$，使得 $$ \lambda_1 + \lambda_2 + \cdots + \lambda_t = 1, $$ 且 $$ \lambda_1 x^{(1)} + \lambda_2 x^{(2)} + \cdots + \lambda_t x^{(t)} = x. $$ 所有由 $x^{(1)}, x^{(2)}, \dots, x^{(t)}$ 的凸组合所构成的集合，称为这些点的**凸包** Convex Hull。 --- 设 $P$ 是一个多胞体，$x$ 是 $P$ 中的一个点。如果不存在其他两个不同的点 $x', x'' \in P$，使得 $x$ 是它们的一个凸组合，那么称 $x$ 是 $P$ 的一个**顶点** vertex，也叫做**极点** Extreme Point。 引理：一个多胞体有有限多个顶点，并且它等于这些顶点的凸包。 引理：设 $x \in \mathbb{R}^n$ 是一个 $n$ 维多胞体的一个极点。 那么，在定义该多胞体的约束中，存在 $n$ 条约束，使得把这 $n$ 条约束中的“不等式”改成“等式”后，得到的线性方程组唯一解就是 $x$。 引理：如果一个线性规划的可行域是一个多胞体，那么它的最优值一定可以在该多胞体的某个顶点处取得。 一些特殊情况，如在最小化的线性规划问题中： - 如果可行域为空，最小值是 $\infty$。 - 如果可行域 unbounded，也就是存在方向使目标函数可以无限减小，最小值是 $-\infty$。 ## Methods for Solving Linear Programs 常见的三种算法： 单纯形法：Simplex Method，指数级复杂度，实际运行效率很快。 椭球法：Ellipsoid Method，多项式复杂度，实际运行效率很慢。**他不能直接求解，而是判定是否有解。** 内点法：Interior Point Method，多项式复杂度，实际运行效率很快。 --- 单纯形法，Dantzig 提出。 其本质其实是，在顶点上进行游走，来改进目标函数的值，每次切换一个顶点。 我们先引入松弛变量把 $Ax\geq b$ 转化为 $Ax-s=b$ 其中 $s\geq 0$。 然后我们不妨令 $x_{n+i}:=s_i$，我们可以整理出一套 $x_{n+i}$ 关于 $x_j(j\leq n)$ 的线性组合。把 $x_{n+i}$ 称为**基变量** basic variable，$x_j(j\leq n)$ 称为**非基变量** non-basic variable。我们先令非基变量为 $0$，则可以得到基变量的取值，这是我们的基础解（但是不一定是可行解）。 我们选取那些能改进目标函数的非基变量替换基变量，来尽可能减小目标函数的取值。可以解不等式算出每个非基变量对于每个基变量而言，最紧的限制。然后找到最优的那个，把非基变量替换成基变量，得到和原来等价的式子，这个过程称之为**转轴** pivot。这次新的换来的基变量即为**入基变量** entering variable，变成非基变量的那个叫做**出基变量** leaving variable。重复这个过程，即可得到最优解。 当然，如果选不出可以替换的了，显然已经得到 Optimal Solution 了。 如果存在某个可以改进目标函数的非基变量，但是无法确认他的上界，就是怎么改都可以，那么目标函数就可以无限减小，于是就是 Unbounded。 至于基础解不是可行解，我们可以这样子进行补救：做两次单纯形，第一次求解一个可行性的线性规划问题，得到一个基础解，然后拿基础解做第二次线性规划问题。 我们得到形式为： $$ \begin{aligned} \min\quad c^{\mathsf T}x& \quad \text{s.t.}\\ Ax&= b\\ x&\geq 0 \end{aligned} $$ 初始问题，我们先求解： $$ \begin{aligned} \min\quad 1^{\mathsf T}a& \quad \text{s.t.}\\ Ax+a&= b\\ x,a&\geq 0 \end{aligned} $$ 然后求解这个问题。显然若 $b\geq 0$ 可以直接取 $a=b$ 作为可行的基础解，而对于 $b<0$ 的情况，我们不妨左右两边乘上 $-1$，因为我们形式是 $Ax=b$ 了所以不会影响。 如果这个问题求解出来答案不是 $0$ 则为 Infeasible。 另外，实际上可以取一个充分大的数 $M$ 改成求解： $$ \begin{aligned} \min\quad c^{\mathsf T}x+M1^{\mathsf T}a& \quad \text{s.t.}\\ Ax+a&= b\\ x,a&\geq 0 \end{aligned} $$ 另外，单纯形法的复杂度是指数级的，但是效率很优秀。关于复杂度的证明需要参考**平滑分析** Smoothed Analysis。 --- 椭球法，Khachiyan 提出。 椭球法是用来判定的，而不可以直接求解。但是他证明了线性规划是 P 问题。 具体流程是这样的：先找到一个很大的椭球，至少要包含可行域。然后取椭球的中心点。这时候我们需要一个**分离预言机** Separation Oracle，给定椭球的中心 $x$ 判断 $x$ 是否在可行域中。若不在，返回一个分离超平面把 $x$ 和可行域分开。然后分离出来的椭球的某一部分，找到另一个完全包含这一部分的椭球，重复这个操作。 具体的一些流程还需要一些关于 LP 问题规模以及椭球相关的知识，但是椭球法有点 useless，主要意义是证明了 LP 是 P 问题，这里就不展开了。 至于有了椭球法之后，我们就可以通过一些手段调用椭球法求出答案。一个笨办法是二分答案，哈哈。但是有更深刻的东西，后文写完对偶相关的内容会介绍。 --- 内点法，Karmarkar 提出。 LP 最优值在凸多面体上一定在**某个顶点**，但可行域内部到顶点的路径可以用连续函数描述。核心就是设计一个函数，让他按照函数走，走不出边界但是可以接近最优解。 而内点法仍然需要一个初始解，类似于单纯形法即可。 内点法相比单纯形的优势是更快，而且中途停止迭代的话得出的解疑似优于单纯形法（？）知乎上看到的，不一定保真。 --- 上述算法都和整数大小还有精度等相关。至于 LP 能不能在强多项式时间内解决，目前还是个 Open Problem。 ## Linear Programming Duality 回到原来的例子： $$ \begin{aligned} \min\quad 7x_1+4x_2& \quad \text{s.t.}\\ x_1+x_2&\geq 5\\ x_1+2x_2&\geq 6\\ 4x_1+x_2&\geq 8\\ x_1,x_2&\geq 0 \end{aligned} $$ 最优解是 $x_1=1,x_2=4$ 得到 $7\times 1+4\times 4=23$。 我们如何证明这是下界呢？ $$ 7x_1+4x_2\geq 3(x_1+x_2)+(4x_1+x_2)\geq 3\times 5+8=23 $$ 这个线性规划的对偶形式是： $$ \begin{aligned} \max\quad 5y_1+6y_2+8y_3& \quad \text{s.t.}\\ y_1+y_2+4y_3&\leq 7\\ y_1+2y_2+y_3&\leq 4\\ y_1,y_2,y_3&\geq 0 \end{aligned} $$ 写成矩阵形式，则有原形式为： $$ \begin{aligned} \min\quad c^{\mathsf T}x& \quad \text{s.t.}\\ Ax&\geq b\\ x&\geq 0 \end{aligned} $$ 对偶形式为： $$ \begin{aligned} \max\quad b^{\mathsf T}y& \quad \text{s.t.}\\ A^{\mathsf T}y&\leq c\\ y&\geq 0 \end{aligned} $$ 在本例中有： $$ A = \begin{pmatrix} 1 & 1 \\ 1 & 2 \\ 4 & 1 \end{pmatrix} $$ $$ b = \begin{pmatrix} 5 \\ 6 \\ 8 \end{pmatrix} $$ $$ c = \begin{pmatrix} 7\\ 4 \end{pmatrix} $$ 设 $P$ 为原线性规划的答案，$D$ 为对偶线性规划问题的答案，则有： - **弱对偶定理** Weak Duality Theorem：$D\leq P

弱对偶定理证明很简单。

设 x^* 为原线性规划问题的解，y^*为对偶线性规划问题的解：

D=b^{\mathsf T}y^*\leq (Ax^*)^{\mathsf T}y^*=(x^*)^{\mathsf T}A^{\mathsf T}y^*\leq (x^*)^{\mathsf T}c=c^{\mathsf T}x^*=P

强对偶定理的证明要略花一些笔墨：

事实：如果一个点 x 不属于多面体 \mathcal P，那么存在一个超平面将 x 与 \mathcal P 分开。

引理 Farkas Lemma：Ax=b,x\geq 0 无可行解，当且仅当存在 y 使得 y^{\mathsf T} A \geq 0 且 y^{\mathsf T} b \lt 0 可行。

记该超平面为 $y^{\mathsf T} z = g$，则对于所有 $x \geq 0$ 有：$y^{\mathsf T} b \lt g$ 且 $y^{\mathsf T}Ax \gt g$。 由此可得：$g < 0$ 且 $y^ A \geq 0$。 因此：$y^{\mathsf T}b < g < 0$。

引理 Farkas Lemma 的变形：Ax\leq b,x\geq 0 无可行解，当且仅当存在 y 使得 y^{\mathsf T} A \geq 0 且 y^{\mathsf T} b\lt 0 且 y\geq 0 可行。

改写为等价形式：Ax+x'=b，x,x'\geq 0。

即 (A,I)\begin{pmatrix}x\\x'\end{pmatrix}=b,\begin{pmatrix}x\\x'\end{pmatrix} \geq 0。

根据 Farkas 引理，存在 y 使得 y^{\mathsf T}(A,I)\geq 0,y^{\mathsf T}b\lt 0。

等价于 y^{\mathsf T}A\geq 0,y\geq 0,y^{\mathsf T}b\lt 0。

对于任意 \varepsilon > 0，方程组 \begin{pmatrix}-A & c^{\mathsf T} \end{pmatrix} x \le \begin{pmatrix}-b \\ P - \varepsilon \end{pmatrix}, x \geq 0无可行解。

根据 Farkas 引理，存在 y \in \mathbb{R}^m, y \geq 0 和 \alpha \geq 0，使得 (y^{\mathsf T}, \alpha) \begin{pmatrix}-A & c^{\mathsf T} \end{pmatrix} \geq 0, (y^{\mathsf T}, \alpha) \begin{pmatrix}-b \\ P - \varepsilon \end{pmatrix} < 0。

我们可以证明 \alpha > 0。不失一般性，假设 \alpha = 1，则有：-y^{\mathsf T} A + c^{\mathsf T} \geq 0,- y^{\mathsf T} b + P - \varepsilon < 0。

等价于 A^{\mathsf T} y \le c, b^{\mathsf T} y > P - \varepsilon。

由于该结论对任意 \varepsilon > 0 都成立，因此D > P - \varepsilon \implies D = P，因为 D \leq P。

回忆一下椭球法的那个 Oracle。对于 LP 问题：

\begin{aligned} \min\quad c^{\mathsf T}x& \quad \text{s.t.}\\ Ax&\leq b\\ x&\geq 0 \end{aligned}

可以这样调用 Oracle 3 次得出解：

  1. 检查原始可行性：询问问题 Ax\leq b,x\geq 0 是否有解。若无则 Infeasible。

  2. 检查对偶可行性：询问问题 A^{\mathsf T}y\leq c,y\geq 0 是否有解。若无则 Unbounded。

  3. 询问问题：

    \begin{aligned} c^{\mathsf{T}}x&\leq b^{\mathsf{T}} y\\ Ax&\leq b\\ x&\geq 0\\ A^{\mathsf{T}}y&\leq c\\ y&\geq 0 \end{aligned}

    根据强对偶定理，这个问题必然有解 (x^*,y^*) 对应原始问题和对偶问题的最优解。

所以椭球法其实证明了 LP 问题是 P 问题。

Integral Polytopes: Exact Algorithms Using LP

如果一个多胞体 P\subseteq \mathbb{R}^n 的极点全在 \mathbb{Z}^n 中，则称 P 是 Integral Polytope。这个我也不知道怎么翻译是对的。

有一些 COP 的限制形成了 Integral Polytope，那么他的最优解就都是整数，可以直接用 LP 解决。

二分图最大权匹配的 IP 形式是：

\begin{aligned} \min\quad \sum\limits_{e\in E} w_ex_e& \quad \text{s.t.}\\ \sum\limits_{e\in \delta(v)}x_e&\leq 1\quad \forall v\in L\cup R\\ x_e&\in \{0,1\}\quad \forall e\in E \end{aligned}

而他的 LP形式，就是把：

x_e\in \{0,1\}\quad \forall e\in E

换为：

x_e\geq 0\quad \forall e\in E

定理：二分图匹配的 LP 可行域是 Integral Polytope。

选一个 x 在可行域 P 中

相当于证明：若 x 不是整点则能推到 x 不是极点。

而极点不能被凸组合出来，所以等价于不是整点的话，找到 x',x''\in P，且 x'\neq x''，且 x=\frac{1}{2}(x'+x'') 即可。

  • 第一种情况：那些 0\lt x_e\lt 1 的边出现了环。

    我们对环用蓝色和红色染色。对于 x'，给每条蓝边 +\epsilon，红边 -\epsilon。对于 x''，给每条蓝边 -\epsilon，红边 +\epsilon。

  • 第二种情况：那些 0\lt x_e\lt 1 的边形成了森林（就是无环）。

    我们把叶子拿出来，选一条从叶子到叶子的路径，用蓝色红色染色。对于 x'，给每条蓝边 +\epsilon，红边 -\epsilon。对于 x''，给每条蓝边 -\epsilon，红边 +\epsilon。

所以不是整点的点我们总能找到 x',x'' 凸组合出来。那么极点就一定都是整点了。

一个 s\text{-}t\ \text{flow} 是一个满足如下限制的向量 f\in \mathbb{R}^E_{\geq 0}：

\forall e\in E,0\leq f(e)\leq c_e\\ \forall v\in V\setminus\{s,t\},\sum\limits_{e\in \delta^\text{in}(v)} f(e)=\sum\limits_{e\in \delta^\text{out}(v)} f(e)

而一个流的权值定义为 \operatorname{val}(f):=\sum\limits_{e\in \delta^\text{out}(s)} f(e)=\sum\limits_{e\in \delta^\text{in}(t)} f(e)。

最大流的 LP 形式是：

\begin{aligned} \max\quad \sum\limits_{e\in \delta^\text{in}(t)} x_e& \quad \text{s.t.}\\ x_e&\leq c_e\quad &\forall e\in E\\ \sum\limits_{e\in \delta^\text{in}(v)} x_e-\sum\limits_{e\in \delta^\text{out}(v)} x_e&=0\quad &\forall v\in V\setminus\{s,t\}\\ x_e&\geq 0\quad &\forall e\in E \end{aligned}

定理：网络流的 LP 可行域是 Integral Polytope。

任选一个 s\text{-}t\ \text{flow} x，包含 0\lt x_e\lt 1 的边集叫做 E'。

那么每个 v\notin \{s,t\} 都必须有 0 条或者 \geq 2 条边在 E' 中（1 条的话显然整数和分数之间不会流守恒）。

忽略掉 E' 中边的方向，那么他含有一个环或者存在一条 s\text{-}t 的路径。

那么把环或者路径拿出来整体 +\epsilon 或 -\epsilon。

而最大流的 LP 可以写成这样：

\begin{aligned} \max\quad d^{\mathsf T}x& \quad \text{s.t.}\\ \begin{pmatrix}B'\\-B'\\I\end{pmatrix}x&\leq \begin{pmatrix}0\\0\\c\end{pmatrix}\\ x&\geq 0 \end{aligned}

其中 B\in\mathbb{R}^{|V|\times |E|}：

\begin{aligned} B_{v,e}=\begin{cases} +1&,e\in \delta^{\text{in}}(v)\\ -1&,e\in \delta^{\text{out}}(v)\\ 0&,\text{otherwise} \end{cases} \end{aligned} $$ d_e=\begin{cases}1&,e\in \delta^{\text{in}}(t)\\0&,\text{otherwise}\end{cases} $$ 然后删掉 $s,t$ 两行得到 $B'$。于是限制是 $B'x=0$，拆成大于号小于号各一条。 最小割的 LP 形式如下： $$ \begin{aligned} \min\quad \sum\limits_{e\in E}c_ey_e& \quad \text{s.t.}\\ \pi_v-\pi_u+y_{(u,v)}&\geq 0\quad &\forall (u,v)\in E\\ \pi_s-\pi_t&\geq 1\\ y_e&\geq 0\quad &\forall e\in E \end{aligned} $$ 看起来很不像。我们先把上面的照搬过来，得到的应该是： $$ \begin{aligned} \min\quad 0^{\mathsf T}u+0^{\mathsf T}v+c^{\mathsf T}y& \quad \text{s.t.}\\ (B')^{\mathsf T}u+(-B')^{\mathsf T}v+I^{\mathsf T}y&\geq d\\ u,v,y&\geq 0 \end{aligned} $$ 而我们在引入一个 $\pi:=u-v$ 得到 $(B')^{\mathsf T}\pi +y\geq d$。 而这个 $[(B')^{\mathsf T}\pi]_e=\pi_v-\pi_u$，于是就和最小割的对偶形式一样了。至于冒出来的那个 $\pi_s-\pi_t\geq 1$ 其实是因为之前写的不规范导致的，不能简单的刻画为 $B$ 删掉两行，要换个写法，不过感觉意义不大就不明确了。 因此最大流-最小割定理通过强对偶定理以及刚刚的转化也显然得证了。通过这样的对偶手法，我们还可以证明二分图最大匹配等于最小点覆盖。 --- 加权区间调度问题，即 $n$ 个活动，活动 $i$ 在 $[s_i,f_i)$ 时刻存在，并且有 $w_i\gt 0$ 的权重。两个活动 $i,j$ 可以参加当且仅当 $[s_i,f_i)$ 和 $[s_j,f_j)$ 无交。最大化选择的活动的 $w_i$ 之和。 这个是经典的 DP 题。 他的 LP 形式是： $$ \begin{aligned} \min\quad \sum\limits_{i\in [n]}x_iw_i& \quad \text{s.t.}\\ \sum\limits_{i\in[n]:t\in[s_i,f_i)} x_i&\leq 1\quad &\forall t\in [T]\\ x_i\geq 0 \end{aligned} $$ 定理：加权区间调度问题的 LP 可行域是 Integral Polytope。 定义一个矩阵 $A\in \mathbb{R}^{m\times n}$ 是**全幺模**（Tototally Unimodular TUM）矩阵，当且仅当 $A$ 的每个子方阵的行列式都在 $\{-1,0,1\}$ 中。 给出一条定理一条引理： - 如果一个多胞体 $P$ 是 $Ax\geq b,x\geq 0$ 的可行域，并且 $A$ 是 TUM 矩阵，$b$ 是 Integral 的，则 $P$ 是 Integral Polytope。 - 一个矩阵 $A\in\{0,1\}^{m\times n}$ 如果 $1$ 在每一列中形成一个区间，则 $A$ 是 TUM 矩阵。 因此不难看出，$A$ 是 TUM 矩阵，所以这个 LP 是一个 Integral Polytope。 证明懒了，这里再给出几条别的引理： - 如果 $A'\in \{0,\pm 1\}^{n\times n}$ 满足 $A'$ 每行最多一个 $1$ 最多一个 $-1$，那么 $\det(A')\in\{0,\pm 1\}$。 - 如果 $A\in \{0,\pm 1\}^{m\times n}$ 满足 $A$ 每行最多一个 $1$ 最多一个 $-1$，那么 $A$ 是 TUM 矩阵。证出上一条显然可以得到。故而可以得到推论：$s\text{-}t\ \text{flow}$ 的 LP 可行域是 Integral Polytope。 - 二分图的“边-点关联矩阵”是 TUM 矩阵。故而可以得到推论：二分图最大权匹配的 LP 可行域是 Integral Polytope。 --- 最小费用流的 LP 形式，其中 $b$ 表示一个点的出流减入流最多是多少： $$ \begin{aligned} \min\quad \sum\limits_{e}w_ex_e& \quad \text{s.t.}\\ x_e&\leq c_e\\ \sum\limits_{e\in \delta^\text{out}(v)} x_e-\sum\limits_{e\in \delta^\text{in}(v)} x_e&\leq b_v\\ x_e&\geq 0 \end{aligned} $$ 设 $z_{e}$ 是边流量约束的对偶变量，$p_u$ 是点流量约束的对偶变量，那么有： $$ \begin{aligned} \max\quad \sum\limits_{u}-b_up_u-\sum\limits_{e}c_ez_e& \quad \text{s.t.}\\ p_v-p_u-z_{(u,v)}&\leq w_{(u,v)}\\ p_u,z_e&\geq 0 \end{aligned} $$ 注意到，$z_e$ 只会在一条限制里出现，所以 $c_e$ 非负的时候，$z_e$ 显然要取到下界 $\max\{0,p_v-p_u-w_{(u,v)}\}$。 然后负号提出去就是求 $-\min \sum\limits_{u}b_up_u+\sum\limits_{e}c_e\max\{0,p_v-p_u-w_{(u,v)}\}$。 另外，如果要求流出减流入恰好是 $b$，那么 $p$ 非负的限制就没了，因为一个 $=$ 要拆成两个相反的约束，对偶之后就是两个相减的变量也就是取值任意。 所以如果题目出现的是这个形式的式子就可以转成费用流求解。 $c_e$ 可以设为 $\infty$，使得 $\max\{0,p_v-p_u-w_{(u,v)}\}$ 变为 $p_v-p_u-w_{(u,v)}\leq 0$ 即为 $p_u+w_{(u,v)}\geq p_v$ 的限制。 $\max\{0,p_u-p_v\}+\max\{0,p_v-p_u\}$ 可以得到 $|p_u-p_v|$。 另外，网络流输出方案可以参考 [费用流线性规划对偶的构造方案 - 洛谷专栏](https://www.luogu.com/article/3xwk963b)。 ## Examples in OI ### P3337 [ZJOI2013] 防守战线 他的 LP 形式是： $$ \begin{aligned} \min\quad \sum\limits_{i\in[1,n]}C_ix_i& \quad \text{s.t.}\\ \sum\limits_{i\in [l_j,r_j]} x_i&\geq D_j\\ x_i&\geq 0 \end{aligned} $$ 我们令 $p_i=\sum\limits_{j\in [1,i]}x_j$，则我们其实是要最小化 $\sum\limits_{i\in[1,n]}C_i(p_i-p_{i-1})$，等价于 $\sum\limits_{i\in[1,n]}p_i(C_i-C_{i+1})$。而限制就转化为 $p_{r}-p_{l-1}\geq D$ 和 $p_i-p_{i-1}\geq 0$。 而 $p_{r}+(-D)\geq p_{l-1}$ 和 $p_{i}+(-0)\geq p_{i-1}$ 的东西，可以转化为 $\infty\max\{0,p_{l-1}-p_{r}-(-D)\}$ 和 $\infty\max\{0,p_{i-1}-p_i\}$。 所以其实就是在最小化 $\sum p_i(C_i-C_{i+1})+\sum \infty\max\{0,p_{l-1}-p_{r}-(-D)\}+\sum \infty\max\{0,p_{i-1}-p_i\}$，那么建图跑费用流即可。 具体的就是 $r\xrightarrow{(\infty,-D)} l-1$ 和 $i\xrightarrow{(\infty,0)} i-1$。 而回忆一下我们的 $p_i$，在线性规划里是什么？是点流量约束的对偶变量。我们最小化的 $\sum b_up_u$ 在这里体现的是 $p_i(C_i-C_{i+1})$，说明这个 $C_i-C_{i+1}$ 就是，每个点的出流减入流的上界，那么 $C_i-C_{i+1}\geq 0$ 的时候，连 $s\xrightarrow{(C_i-C_{i+1},0)} i$，否则连 $i\xrightarrow{(C_{i+1}-C_i,0)} t$。这个所谓的 $s,t$ 只是我们为了实现 MCMF 而加上去的，他本质就是给每个点加了一个免费的入流或者免费的出流，所以 $C_i-C_{i+1}\geq 0$ 意义就是我出流随便多少，不超过 $C_{i}-C_{i+1}$ 即可，那么我们 $s\xrightarrow{} i$ 的不超过 $C_{i}-C_{i+1}$ 即可。 跑完费用流求出来的是最小值的相反数，我们输出的时候取相反数即可。 <https://www.luogu.com.cn/record/257881230> 实现的时候费用流好像要写原始对偶才能过。 ### P3980 [NOI2008] 志愿者招募 他的 LP 形式是： $$ \begin{aligned} \min\quad \sum\limits_{j\in[1,m]}c_jx_j& \quad \text{s.t.}\\ \sum\limits_{i\in [s_j,t_j]} x_j&\geq a_i\\ x_j&\geq 0 \end{aligned} $$ 写出它的对偶形式： $$ \begin{aligned} \max\quad \sum\limits_{i\in[1,n]}a_iy_i& \quad \text{s.t.}\\ \sum\limits_{i\in [s_j,t_j]} y_i&\leq c_j\\ y_i&\geq 0 \end{aligned} $$ 用现实意义可以理解成，$y_i$ 是我低 $i$ 天招一个人摊下来要多少钱”。 虽然形式和上一题一样，但是完全照着上一题的推出来会发现有负环跑不动。 那么我们倒着建即可，令 $p_i=\sum\limits_{j\in[i,n]}y_j$，则我们其实是要最大化 $\sum\limits_{i\in[1,n]}a_i(p_i-p_{i+1})$，等价于 $\sum\limits_{i\in[1,n]}p_i(a_{i}-a_{i-1})$，然后等价于最小化 $\sum\limits_{i\in[1,n]}p_i(a_{i-1}-a_{i})$ 然后取相反数。而限制就转化为 $p_{s}-p_{t+1}\leq c$ 和 $p_i-p_{i+1}\geq 0$。 而 $p_{t+1}+c\geq p_{s}$ 和 $p_{i}+(-0)\geq p_{i+1}$ 的东西，可以转化为 $\infty\max\{0,p_{s}-p_{t+1}-c\}$ 和 $\infty\max\{0,p_{i+1}-p_i\}$。 所以其实就是在最小化 $\sum p_i(a_{i-1}-a_i)+\sum \infty\max\{0,p_{s}-p_{t+1}-c\}+\sum \infty\max\{0,p_{i+1}-p_i\}$，那么建图跑费用流即可。 具体的就是 $t+1\xrightarrow{(\infty,c)} s$ 和 $i\xrightarrow{(\infty,0)} i+1$，然后 $a_i-a_{i-1}\geq 0$ 的时候连 $s\xrightarrow{} i$，否则连 $i\xrightarrow{}t$。 这次的答案不用再取相反数了，过程里两个取相反数抵消了。 <https://www.luogu.com.cn/record/257937972> ### 教寺院训练营 模拟赛 R5 A. 放犬多 他的 LP 形式是： $$ \begin{aligned} \max\quad \sum\limits_{e\in E}w_ex_e& \quad \text{s.t.}\\ \sum\limits_{e\in \operatorname{Path}(u_j,v_j)} x_e&\leq c_j\\ x_e&\geq 0 \end{aligned} $$ 我们令 $p_u$ 表示 $1\to u$ 路径上的 $x_e$ 之和，我们最大化的就是 $\sum\limits_{u\neq root}w_u(p_u-p_{fa_u})$，转化到 $\sum\limits_{u}p_u(w_{(u,fa_u)}-\sum\limits_{v\in \operatorname{son}(u)}w_{(u,v)})$。 所以其实是最小化 $\sum\limits_{u}p_u[(\sum\limits_{v\in \operatorname{son}(u)}w_{(u,v)})-w_{(u,fa_u)}]

然后对于限制的话，不妨令 u 是 v 的祖先，就变成了 p_v-p_u\leq c_j，然后 p_{fa_u}-p_u\leq 0。

所以这个可以转化为，\infty\max\{0,p_v-p_u-c_j\} 和 \infty\max\{p_{fa_u}-p_u\}。

所以我们就可以连边 u\xrightarrow{(\infty,c_j)}v 和 u\xrightarrow{(\infty,0)}fa_u。

至于 b_u:=(\sum\limits_{v\in \operatorname{son}(u)}w_{(u,v)})-w_{(u,fa_u)}，b_u\geq 0 时候连 s\xrightarrow{(b_u,0)}u，否则连 u\xrightarrow{(-b_u,0)} t。

然后仍然在这张图上跑 MCMF 即可。

https://www.luogu.com.cn/record/258155763

QOJ5036 卑鄙的下毒人

本质是在最小化 \sum \infty\max\{0,p_{i-1}-p_i\}+k(p_n-p_0),\sum\max\{0,p_{l-1}-p_r-(-a)\}。

建图 i-1\xrightarrow{(\infty,0)} i，l-1\xrightarrow{(1,-a)}r，s\xrightarrow{(k,0)}0，n\xrightarrow{(k,0)} t 跑 MCMF。

但是数据范围导致硬上 Dinic 肯定过不去，注意到 k\leq5 最多增广 5 次就结束了，可以考虑原始对偶。由于图显然都是小的连大的是个 DAG，所以最开始的求一次最短路可以用拓扑排序代替 SPFA。

https://qoj.ac/submission/1932739

QOJ4899 机器

先推一下最大费用循环流的 LP 形式：

\begin{aligned} \max\quad \sum\limits_{e}w_ex_e& \quad \text{s.t.}\\ x_e&\leq c_e\\ \sum\limits_{e\in \delta^\text{out}(v)} x_e-\sum\limits_{e\in \delta^\text{in}(v)} x_e&=0\\ x_e&\geq 0 \end{aligned}

对偶得到：

\begin{aligned} \min-\sum\limits_{e}c_ez_e& \quad \text{s.t.}\\ p_v-p_u-z_{(u,v)}&\leq w_{(u,v)}\\ z_e&\geq 0 \end{aligned}

注意，因为原来的限制是 =，所以这里 p_u 没有限制，这是因为 = 要拆成 \leq 和 \geq，而这样一组合 p_u 就被写成了两个变量相减就没有限制了。

还是 z_e 只在一条式子里出现，所以必然要顶到上界也就是 \max\{0,p_v-p_u-w_{(u,v)}\}，然后其实本质上在最小化 -\sum\limits_{(u,v)}c_{(u,v)}\times \max\{p_v-p_u-w_{(u,v)}\}，也就是最小化 \sum\limits_{(u,v)}c_{(u,v)}\times \max\{p_u+w_{(u,v)}-p_v\}。

所以这个题最小化的其实是：

\sum \infty\max\{0,p_u+(h_u-h_v)-p_v\}+\sum \max\{0,p_s+(-a_{i,j})-p_i\}+\sum \max\{0,p_i+(-b_{i,j})-p_s\}

认为 p_s=0，那么后两个式子可以表达成一个 f_i(p_i) 形式，前一个式子不妨令 p':=p+h 那么相当于是要求 p'_u\leq p'_v。

然后这个其实是一个广义的保序回归。好像是可以证明，如果函数是凸的并且和指数函数凸的方向一致，就可以跑保序回归的那个做法。

所以，我们直接整体二分这个东西，然后每次只要决策这些点取到 mid 还是 mid+1。这个是一个最小权闭合子图，我们取反变成求最大权闭合子图。

这个是经典问题，val_i\geq 0 就连 s\xrightarrow{val_i}i 否则连 i\xrightarrow{-val_i}t，如果限制是 u 选了 v 也一定要选，连 u\xrightarrow{\infty}v。

本题中，我们看做所有点都先选 mid，然后选一些点改成 mid+1。对于限制 p'_u\leq p'_v 的，则选择了 u 必须要选择 v。

建图求最大流，最后残量网络上和 s 相连的点就选 mid+1，别的都选 mid。

求完之后分治下去继续求即可

https://qoj.ac/submission/1935165

CF1765J Hero to Zero

设第 i 列减掉了 p_i，第 j 列减掉了 q_j，那么在最小化：

\sum p_i+\sum q_j+\sum (c_{i,j}-p_i-q_j)

即：

(\sum c_{i,j})-(n-1)(\sum p_i+\sum q_j)

那么目标就是最大化 \sum p_i+\sum q_j，限制只是 p_i+q_j\leq c_{i,j}。

注意，p_i,q_j 没有限制，说明是两个变量相减的形式，那么我们对偶之后会得到等式。

通过写作矩阵的标准形式，我们可以直观得到对偶的结果：

\begin{aligned} \min\quad \sum c_{i,j}x_{i,j}& \quad \text{s.t.}\\ \sum\limits_{1\leq j\leq n} x_{i,j}&=1\quad &\forall 1\leq i\leq n\\ \sum\limits_{1\leq i\leq n} x_{i,j}&=1\quad &\forall 1\leq j\leq n\\ x_{i,j}&\geq 0 \end{aligned}

这个是典型的二分图匹配的线性规划形式，也可以轻松证明这个矩阵其实是 TUM 矩阵，所以直接做就是精确解了。由于 c_{i,j}=|a_i-b_j|，这个最小值显然是 a,b 各自排序之后对位匹配。

复杂度瓶颈在排序。 <https://codeforces.com/contest/1765/submission/358878013> ### ABC224H Security Camera 2 LP 形式显然为： $$ \begin{aligned} \min\quad \sum a_ix_i+\sum b_jy_j& \quad \text{s.t.}\\ x_i+y_j&\geq c_{i,j}\\ x_i,y_j&\geq 0 \end{aligned} $$ 对偶得到： $$ \begin{aligned} \max\quad \sum c_{i,j}z_{i,j}& \quad \text{s.t.}\\ \sum\limits_{L+1\leq j\leq L+R}z_{i,j}&\leq a_i\quad &\forall 1\leq i\leq L\\ \sum\limits_{1\leq i\leq L}z_{i,j}&\leq b_j\quad &\forall L+1\leq j\leq L+R\\ z_{i,j}&\geq 0 \end{aligned} $$ 不是哥们这不是我们费用流的原始形式吗？ 建图 $s\xrightarrow{(a_i,0)}i$，$j\xrightarrow{(b_j,0)}t$，$i\xrightarrow{(\infty,-c_{i,j})}j$ 跑最小费用最大流，然后答案取相反数即可。 <https://atcoder.jp/contests/abc224/submissions/72621015> ### CF605C Freelancer's Dreams LP 形式为： $$ \begin{aligned} \min\quad \sum z_i& \quad \text{s.t.}\\ \sum a_iz_i&\geq p\\ \sum b_iz_i&\geq q\\ z_i&\geq 0 \end{aligned} $$ 对偶变成： $$ \begin{aligned} \max\quad px+qy& \quad \text{s.t.}\\ a_ix+b_iy&\leq 1\\ x,y&\geq 0 \end{aligned} $$ 注意到，$x$ 确定则 $y$ 一定是取到 $\min\{\frac{1-a_ix}{b_i}\}$。 而 $px$ 是一个线性函数，$q\min\{\frac{1-a_ix}{b_i}\}$ 是多个线性函数取 $\min$，我们有结论，多个线性函数取 $\min$ 最后是一个上凸函数，上凸函数加上线性函数也还是上凸函数，所以可以在上凸壳上二分斜率找最值点。 <https://codeforces.com/contest/605/submission/359030020>