对偶原理小记
cainiaoshanglu
·
·
算法·理论
对偶原理是线性规划中的一个类似 trick 的东西，给出了线性规划问题的一个转化思路。其基本形式为：
\max w^{\mathrm{T}}x,\,Ax \preceq c,\,x \succeq \vec{0}
对应：
\min c^{\mathrm{T}}y,\,A^{\mathrm{T}}y \succeq w,\,y \succeq \vec{0}
这两个线性规划问题互为对偶问题。注意 \max,\min 和 \preceq,\succeq 的互换，同时不要忘记变量与 \vec{0} 的偏序关系。
当对偶问题与原问题的最优解同时存在时，两者的解相等。当原问题无解时对偶问题无界，反之亦然。这使得我们可以在解决一个问题时同时解决其对偶问题。
考虑最大流与最小割，我们可以尝试说明其对偶性，从而得到他们相等的经典结论。对于最大流，我们令 x_e \geq 0 为 e \in E 上的流量，则可以得到以下约束：
\forall u \in V\setminus\set{S,T} , \sum_{e\in I_u} x_e-\sum_{e\in O_u} x_e \leq 0
以及
\forall u \in V\setminus\set{S,T} , \sum_{e\in O_u} x_e-\sum_{e\in I_u} x_e \leq 0
还有
\forall e \in E,\,x_e \leq cap_e
所求为：
\max \sum_{e \in I_T} x_e
考虑将其对偶，则令 p_u \geq 0 对应第一类约束，q_u \geq 0 对应第二种约束，a_e \geq 0 对应第三种约束，则有约束：
\forall e=(u\rightarrow v) \in E, -p_u+p_v+q_u-q_v+a_e\geq [v=T]
而所求为：
\min \sum_{e \in E} cap_ea_e
但我们没有考虑 S,T 的特殊地位。若 u=S，约束改写作：
\forall e=(S\rightarrow v) \in E,\, p_v-q_v+a_e\geq [v=T]
$$\forall e=(u\rightarrow T) \in E,\,-p_u+q_u+a_e\geq 1$$
此时考虑一条从 $S$ 到 $T$ 的简单路径 $P$，将其上的边对应的约束加起来，可以得到：
$$ \sum_{e\in P} a_e\geq 1$$
即在这条路径上至少有一条边被选择。此时我们发现这个模型对应的正好是最小割，自此我们得到了最大流与最小割的对偶关系。
另外一个例子是 [luogu P6631](https://www.luogu.com.cn/problem/P6631)，对于三种操作分别设立变量 $x_{l,r},y_{l,r},z_{l,r}$，则可以列出约束：
$$ \forall i=2k,\sum_{l\leq i\leq r} x_{l,r}+z_{l,r}\geq a_i$$
$$ \forall i=2k,\sum_{l\leq i\leq r} -x_{l,r}-z_{l,r}\geq -a_i$$
$$ \forall i=2k+1,\sum_{l\leq i\leq r} x_{l,r}+y_{l,r}\geq a_i$$
$$ \forall i=2k+1,\sum_{l\leq i\leq r} -x_{l,r}-y_{l,r}\geq -a_i$$
所求为：
$$ \min \sum_{l,r} x_{l,r}+y_{l,r}+z_{l,r}$$
考虑其对偶，设四种约束对应 $p_i,q_i,u_i,v_i$，则所求为：
$$ \max \sum_{i=2k} a_i(p_i-q_i)+\sum_{i=2k+1} a_i(u_i-v_i)$$
对应约束为：
$$\forall \,l\leq r, \sum_{\substack{i=2k\\l\leq i\leq r}} (p_i-q_i)+\sum_{\substack{i=2k+1\\l\leq i\leq r}} (u_i-v_i) \leq 1$$
$$\forall \,l\leq r,\sum_{\substack{i=2k+1\\l\leq i\leq r}} (u_i-v_i) \leq 1,\sum_{\substack{i=2k\\l\leq i\leq r}} (p_i-q_i) \leq 1$$
设
$$f_i=\begin{cases}
p_i-q_i,i=2k\\
u_i-v_i,i=2k+1
\end{cases}$$
改写上述结果：
$$\forall \,l\leq r, \sum_{l\leq i\leq r} f_i \leq 1,\sum_{\substack{i=2k\\l\leq i\leq r}} f_i \leq 1,\sum_{\substack{i=2k+1\\l\leq i\leq r}} f_i \leq 1$$
$$ \max \sum a_if_i$$
注意到到约束形状类似最大子段和，于是我们可以进行 dp：令 $dp_{i,j,k,l}$ 表示当前已经考虑了前 $i$ 个元素，而且当前 $f$ 最大后缀和是 $j$，偶数位置最大后缀和是 $k$，奇数位置最大后缀和是 $l$ 时 $\sum a_if_i$ 的最大值。如果我们承认 $f$ 只能取整数（可以通过说明约束系数矩阵为全幺模矩阵证明），则显然 $j,k,l\in\set{0,1}$，进一步得到 $f_i\in\set{-1,0,1}$，所以这个 dp 是线性的。