线性规划与对偶问题入门

线性规划

线性规划（Linear Programming，LP），指目标函数与约束条件皆为线性不等式的最优化问题。

定义$m\times n$的矩阵$A$和向量$\textbf{b}=[b_1,\cdots,b_m]^T$，$\textbf{c}=[c_1,\cdots,c_n]^T$。

线性规划通常可以用矩阵的形式表示为：¹

$$\begin{array}{l} \text{maximize} & \textbf{c}^T\textbf{x}\\ \text{s.t.} & A\textbf{x}\le \textbf{b},\textbf{x}\ge 0 \end{array}$$

$\textbf{x} \ge 0$表示$\forall i, x_i\ge 0$。

每个线性规划问题（称为原问题）都可以变换为一个对偶问题。上述问题的对偶问题为：

$$\begin{array}{l} \text{minimize} & \textbf{b}^T\textbf{y} \\ \text{s.t.} & A^T\textbf{y}\ge \textbf{c}^T,\textbf{y}\ge 0 \end{array}$$

弱对偶定理：$\sum_{j=1}^nc_jx_j$的任意一组解小于等于$\sum_{i=1}^mb_iy_i$。

强对偶定理：$\sum_{j=1}^nc_jx_j$的最大值等于$\sum_{i=1}^mb_iy_i$的最小值（可以取等）。

理解线性规划与对偶

经济学角度²

原问题：企业 A 拥有$m$种资源，计划生产$n$种产品（有$n$个变量），目标是最大化总收入，但使用资源的预算不能超过资源总数（有$m$个约束）；

对偶问题：企业 B 想要收购这些资源，需要确定$m$种资源的报价（有$m$个变量），目标是最小化总成本，但企业 A 只有在卖资源的收益不低于卖产品的时候才会同意卖资源（$n$个约束）。

当然，你事先知道每种产品在单位数量下所耗资源的数量。

数学角度

原问题：给出$m\times n$的矩阵$A$（每一列的向量表示该产品所耗资源的数量），向量$\mathbf{c}=[c_1,\cdots,c_n]$（产品成本），向量$\mathbf{b}=[b_1,\cdots,b_m]^T$（每项资源的总量）。求向量$\mathbf{x}=[x_1,\cdots,x_n]^T$（生产产品的数量），在

$$A\mathbf{x}\le \mathbf{b}\\ \mathbf{x}\ge 0$$

的条件下，求

$$\max z=\mathbf{cx}$$

对于任意一个非负向量$\textbf{y}=[y_1,\cdots,y_m]^T$和可行解$\textbf{x}$，有

$$\textbf{y}^TA\textbf{x}\le \textbf{y}^T\textbf{b}$$

而对于任意一个满足

$$\textbf{c}\le \textbf{y}^TA$$

的非负向量$\textbf{y}$，有

$$\textbf{cx}\le \textbf{y}^TA\textbf{x}\le \textbf{y}^T\textbf{b}$$

这意味着，$\textbf{y}^T\textbf{b}$是原问题的一个上界。而最小的上界就是原问题目标函数的最优值。

把他们都置换一下，可以得到原问题的对偶问题：

$$A^T\textbf{y} \ge \textbf{c}^T\\ \textbf{y}\ge 0$$

求

$$\min w=\textbf{b}^T\textbf{y}$$

对偶方法推论

我们知道$A_i\textbf{x}\le b_i$会对偶成$y_i$，且$y_i\ge 0$。那么对于$A_i\textbf{x}\ge b_i$和$A_i\textbf{x}= b_i$的条件又如何对偶？

$A_i\textbf{x}\ge b_i$可以写成$-A_i\textbf{x}\le -b_i$，那么就可以照常对偶。

对于$A_i\textbf{x}= b_i$，我们可以写成两个条件$A_i\textbf{x}\le b_i$且$-A_i\textbf{x}\le -b_i$。这样会对偶出两个变量$y_i'$和$y_i''$。而他们的系数是恰好相反的，因此可以合并成$(y_i'-y_i'')$乘系数的形式。而$y_i'-y_i''$没有$\ge 0$的限制。因此我们可以将$A_i\textbf{x}= b_i$当作$A_i\textbf{x} \ge b_i$对偶得到变量$y_i$，然后消除$y_i \ge 0$的限制。

解题技巧

接下来介绍一点在 LP 问题转化过程中会用到的技巧。

引理 1：若$A\textbf{x}\ge \textbf{b}$且$\sum (A\textbf{x})_i=\sum \textbf{b}_i$，那么$A\textbf{x}=\textbf{b}$。用不等式组的话说，如果左右加起来相等，那么每个等式都取等。反之亦然。

经典线性规划问题及其对偶

最大流最小割定理

最大流和最小割问题是一对对偶问题。

最大流问题

变量：$f(u,v)\ge 0:(u,v)\in E,|f|>0$。

约束：

$$\begin{aligned} f(u,v) &\le c(u,v) & (u,v)\in E\\ \sum_{(v,u)\in E}f(v,u)-\sum_{(u,v)\in E}f(u,v) &\le 0 &u\in V\setminus\{s,t\} \\ |f|+\sum_{(v,s)\in E}f(v,s)-\sum_{(s,v)\in E}f(s,v) &\le 0 \\ -|f|+\sum_{(v,t)\in E}f(v,t) - \sum_{(t,v)\in E}f(t,v) &\le 0 \end{aligned}$$

求$\max |f|$。（这里$|f|$只是变量名，没有特别的运算意义）。

这里要说一点。原本的流量平衡是$\sum_{(v,u)\in E}f(v,u)-\sum_{(u,v)\in E}f(u,v)=0$。在上面的约束中，把 2,3,4 的左边（实际上一共$|V|$个条件）加起来，可以发现每条边被算了两次，和为$0$。而一堆小于等于$0$的数加起来是$0$，那么这些数全都是$0$。于是这个与流量平衡条件是等价的。

对偶过程

转化为对偶问题时，约束条件会对偶成变量，而条件的上界（右边）是变量的系数。

对于对偶变量系数向量，则是一个变量在每个约束中的系数顺次组成的向量。对偶变量乘上系数向量就构成了对偶约束条件（有变量个）的左部，而右部由原问题的变量系数（最大化中的系数）构成。

设条件 1 的对偶变量为$\{d_{u,v}\}$。条件 2,3,4 的对偶变量分别为$\{h_u\},h_s,h_t$。

• 对于变量$f(u^{\prime},v^{\prime}):u{^\prime},v^{\prime}\in V\setminus\{s,t\}$，它对偶出来的约束条件是$d_{u^{\prime},v^{\prime}}-h_{u^{\prime}}+h_{v^{\prime}}\ge 0$。
• 对于变量$f(v^{\prime},s)$，它对偶出来的约束条件是$d(v',s)-h_{v'}+h_s\ge 0$。
• 对于变量$f(s,v^{\prime})$，它对偶出来的约束条件是$d(s,v')-h_{s}+h_{v'}\ge 0$。
• 对于变量$f(v^{\prime},t)$，它对偶出来的约束条件是$d(v',t)-h_{v'}+h_t\ge 0$。
• 对于变量$f(t,v^{\prime})$，它对偶出来的约束条件是$d(t,v')-h_{t}+h_{v'}\ge 0$。

上述都可以总结为，变量$f(u,v)$，它对偶出来的约束条件是$d_{u,v}-h_{u}+h_{v}\ge 0$。

然后是变量$|f|$，它对偶出来的约束条件是$h_s-h_t\ge 1$。

于是我们就得到了对偶形式的问题。

变量：$d_{u,v}\ge 0:(u,v)\in E$，$h_u\ge 0:u\in V$。

约束：

$$\begin{aligned} d_{u,v}-h_u+h_v &\ge 0 & (u,v)\in E\\ h_s-h_t & \ge 1 \end{aligned}$$

求$\min \sum_{(u,v)\in E} c(u,v)d_{u,v}$。

转化为最小割问题

首先结合 1,4 可以得到$d_{u,v}\ge \max(h_u-h_v,0)$。而$h_s-h_t\ge 1$，为了最小化答案，不妨设$h_s=1,h_t=0$。并且$h_u$只会取整数（可以证明存在这样的最优解）。那么我们定义$S=\{u|h_u=1\},T=\{u|h_u=0\}$，显然$(S,T)$是原图的割。

而$\forall (u,v)\in E$，若$u\in S,v\in T$，则有$d_{u,v}=1$；其他情况$d_{u,v}=0$，这说明割边的贡献是 1，则$\min \sum_{(u,v)\in E} c(u,v)d_{u,v}$就是最小割的定义。因此对偶问题等价于最小割问题。

二分图最大权匹配

给出一个二分图$(V=L\cup R(L\cap R=\varnothing),E:u\in L,v\in R\;\forall (u,v)\in E)$，边权为$w$，求最大权匹配。

原问题

变量：$x(u,v)\ge 0:(u,v)\in E$。

约束：

$$\begin{aligned} x(u,v) &\le 1 & (u,v)\in E\\ \sum_{(u,v)\in E}x(u,v) & \le 1 & u\in L\\ \sum_{(v,u)\in E}x(v,u) &\le 1 & u\in R \end{aligned}$$

求$\max \sum_{(u,v)\in E}x(u,v)w(u,v)$。

容易证明$x(u,v)$只会取整数。因为$x(u,v)w(u,v)$是线性函数且始终过整点。因此最大值也一定是一个整点。另一个理解方式是，假设$|L|=1,|R|=3$，连了一个爪，那么我们一定可以找到一条边使得其边权大于等于总边权和的$\frac{1}{3}$，那么我们选这条边作为匹配即可。

因此上述 LP 形式与最大权匹配问题等价。

对偶问题

变量：$h_u\ge 0:u\in V,d_{u,v}\ge 0:(u,v)\in E$。

约束：

$$\begin{aligned} d_{u,v} + h_u + h_v &\ge w(u,v) & (u,v)\in E \end{aligned}$$

求$\min \sum_{(u,v)\in E} d_{u,v} + \sum_{u\in V}h_u$。

容易证明一定存在$d_{uv}=0\;\forall (u,v)\in E$的解。证明简单，对于所有$d_{u,v}$，设$x+y=d_{u,v}$，那么把$h_u$加$x$，把$h_v$加$y$，答案不变。

因此上述对偶问题可以简化。

简化对偶问题

变量：$h_u\ge 0:u\in V$。

约束：

$$\begin{aligned} h_u + h_v &\ge w(u,v) & (u,v)\in E \end{aligned}$$

求$\min \sum_{u\in V}h_u$。

这就是我们熟悉的 KM 算法的形式了。

费用流模型

接下来我们将介绍对偶算法里常用的网络流模型。

给出一个无源汇网络图$G=(V,E)$，每条边的容量是$c$，费用是$w$，同时每个结点有一个流量差度$e_i$，表示流入结点$i$的流量与流出结点$i$的流量的差。

考虑计算最大费用最大流。

原问题

变量：$f(u,v)\ge 0:(u,v)\in E$。

约束：

$$\begin{aligned} f(u,v) &\le c(u,v) & (u,v)\in E\\ \sum_{(v,u)\in E}f(v,u)-\sum_{(u,v)\in E}f(u,v) &= e_u & u\in V \\ \end{aligned}$$

求$\max \sum_{(u,v) \in E}f(u,v)w(u,v)$。

对偶问题

变量：$y_{u,v}\ge 0:(u,v)\in E, h_u:u\in V$。

约束：

$$\begin{aligned} y_{u,v}-h_u+h_v &\ge w(u,v) & (u,v)\in E \end{aligned}$$

求$\min \sum_{(u,v)\in E} c(u,v)y_{u,v} + \sum_{u\in V}h_ue_u$。

事实上，上述不等式等价于$y_{u,v}\ge \max (w(u,v)+h_u-h_v,0)$。由于我们要求最小值，因此我们可以不要$y_{u,v}$的变量了。

简化对偶问题

变量：$h_u:u\in V$。

求$\min \sum_{(u,v)\in E} c(u,v)\max(w(u,v)+h_u-h_v,0) + \sum_{u\in V}h_ue_u$。

换言之任何能够描述成上述形式的问题都可以使用线性规划和网络流解决。

网络流算法

如何具体地求出最大费用循环流？我们分析对偶问题的目的是，将题目转化为$y_{u,v}-h_u+h_v\ge w(u,v)$的 LP 形式，然后对偶成最大费用循环流。因此接下来介绍如何求出最大费用循环流。

首先我们是有直接求最小（大）费用循环流的算法的，参见 最大费用循环流的论文 or 这道题。速度甚至比普通的有源汇费用流算法更快。

接下来我们讨论把循环流转化为有源汇的费用流的算法。

我们的大致思路是，先把所有正权边满流。这样可以发现一定是最大费用，但不一定满足流量差度。那么我们把多于的流给退回去，求出最小费用的退流，就得到了最大费用循环流。

具体地，设$e'_u=\sum_{(v,u)\in E}f(v,u)-\sum_{(u,v)\in E}f(u,v)$。

1. 如果$e'_u = e_u$，则点$u$满足流量差度。

2. 如果$e'_u < e_u$，那么点$u$就多流出了$e_u - e'_u$的流量。

3. 如果$e'_u > e_u$，那么点$u$就多流入了$e'_u - e_u$的流量。

考虑建立新的图，新建源点$s$和汇点$t$。我们跑一次最小费用最大流来把不合法的因素消除。

• 对于$e'_u < e_u$的点，建立$(s,u),c(s,u)=e_u - e'_u,w(s,u)=0$的边。表示强行让你把多流的部分流出来。
• 对于$e'_u > e_u$的点，建立$(u,t),c(u,t)=e'_u - e_u,w(u,t)=0$的边。
• 对于原图上的边$(u,v)$：
  • 如果$w(u,v) > 0$，那么就直接在新图上建立它，表示我可以退这么多流。
  • 否则$w(u,v) \le 0$，这条就在新图上建立它的反向边，容量不变，费用变成相反数。因为它只能加流。也可以理解为，在新图上建立它，然后让它满流。

然后在新图上求出最小费用最大流，再用满流的方案减去它就是答案。

例题

Freelancer’s Dreams

有$n$种物品，第$i$个物品买$1$份有收益$(a_i,b_i)$（可以买实数份）。问最少买多少份物品使得$A$属性的和超过$p$,$B$属性的和超过$q$。

$n\le 10^5,1\le p,q,a_i,b_i\le 10^6$.

先写出原问题的 LP 形式：

变量：$x_i\ge 0:i\in[1,n]$。

约束：

$$\begin{aligned} \sum_{i=1}^na_ix_i &\ge p \\ \sum_{i=1}^nb_ix_i &\ge q \end{aligned}$$

求$\min \sum_{i=1}^nx_i$。

对偶一下得到：

变量：$A\ge 0,B\ge 0$。

约束：

$$\begin{aligned} Aa_i+Bb_i &\le 1 \end{aligned}$$

求$\max Ap + Bq$。

容易发现，约束就是半平面交，因此$B$是$A$的凸函数，则$Ap+Bq$也是凸的。则三分即可。

代码

ZJOI2013 防守战线

战线可以看作一个长度为$n$的序列，在序列第$i$号位置上建一座塔有$c_i$的花费，且一个位置可以建任意多的塔，费用累加计算。有$m$个区间$[l_i, r_i]$，要求在第$i$个区间的范围内要建至少$d_i$座塔。求最少花费。

$n\le 1000,m,d_i\le 10000$。

设$v_i$表示前$i$个位置上放了多少塔。则原问题可以描述为

$$\min\left( \sum_{i}\infty \max(d_i + v_{l_i - 1} - v_{r_i}, 0) + \sum_{i}\infty \max(v_{i - 1} - v_{i}, 0) + \sum_{i\ge 1} (v_i - v_{i - 1})c_i \right)$$

跑一个最大费用循环流即可。

代码

Cow and Exercise

给定$n$个点的带权有向简单图，$q$次询问（独立），每次给定$x$，可以把每条边增加一定的长度，但总共至多增加$x$，问点$1$到点$n$的最短路最大能是多少。

$n≤50,m\le n(n-1),q≤10^5$。

单组询问

首先写出原问题的 LP 形式。对于$x=X$的询问：

$$\begin{aligned} & \text{mininize} & & d_n-d_1 \\ & \text{s.t.} & & d_v \le d_u+w(u,v)+x_{u,v} \\ & & & \sum_{(u,v)\in E} x_{u,v} \le X \\ \end{aligned}$$

发现这个形式不太容易转化为最大费用循环流的模型。因为第二个条件比较烦。

则考虑二分，即求出最小代价使得最短路长度$\ge L$：

$$\begin{aligned} & \text{mininize} & & \sum_{(u,v)\in E} x_{u,v} \\ & \text{s.t.} & & d_v \le d_u+w(u,v)+x_{u,v} \\ & & & d_n-d_1 \ge L \\ \end{aligned}$$

那么显然$x_{u,v}$可以不要了，我们要求的就是

$$\min \left(\max(L+d_1-d_n,0)\infty + \sum_{(u,v)\in E}\max(d_v-d_u-w(u,v),0)\right)$$

这个可以用最大费用循环流解决。

多组询问

考虑到増广路算法中最大流对应最大费用的函数是凸的，因此我们把这个函数求出来。

具体地，我们发现上述模型在去掉了$n$连到$1$容量为$\infty$的边后，实际上就是一个最大费用最大流的问题。可以使用増广路算法。

而最大流显然不会超过$n$。因此设$f_i$表示最大流为$i$时的最大费用。这样很容易求。在増广的时侯每次只增加一个单位的流就可以求出$f_k$。那么原图的最大流就是

$$\max_{k} \{f_k+kL\}$$

因此我们的问题就变成了，二分$L$，判断$\max_{k} f_k+kL\ge x$是否成立。由于这个函数也是凸的，无脑$O(\log_2^2n)$是可以的。

更高明的做法是把上式化为$\forall k, L\le \frac{x-f_k}{k}$。这时相当于$L =\min_k \frac{x-f_k}{k}$，于是做一次三分（导数上二分）即可。时间复杂度$O(n^2m+q\log_2n)$。

代码

小结

在解决线性规划的问题中，要灵活运用对偶问题以及经典模型求解。

¹. https://zh.wikipedia.org/zh/%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92 ↩

². https://www.zhihu.com/question/26658861/answer/631753103 ↩