对偶原理小记

对偶原理是线性规划中的一个类似 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]$ $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，对于三种操作分别设立变量 $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$ 设