「学习笔记」线性规划

对偶问题

\[ \max \{ c^\intercal x \mid A x \leq b \} = \min \{ b^\intercal y \mid A^\intercal y \geq c \} \]

来道例题：

洛谷P3337 [ZJOI2013]防守战线

列出式子：
\[ \begin{aligned} & \mathrm{minimize} \ \sum_i c_i y_i \& s.t. \ \forall i \in [1, n], \ \sum_{l_i \leq j \leq r_i} y_j \geq d_i \& \forall i \in [1, n], \ y_i \geq 0 \end{aligned} \]
令 \(A^\intercal_{i,j} = [j \in [l_i, r_i]]\)，\(b = \begin{bmatrix} c_1 \\ c_2 \\ \vdots \\ c_n \end{bmatrix}\)，\(c =\begin{bmatrix} d_1 \\ d_2 \\ \vdots \\ d_n \end{bmatrix}\)，于是对偶之后为：
\[ \begin{aligned} & \mathrm{maximize} \ \sum_i d_i x_i \& s.t. \ \forall i \in [1, n], \ \sum_{j} A_{i, j} x_j \geq c_i \& \forall i \in [1, n], \ x_i \geq 0 \end{aligned} \]
同时 \(A\) 的列中有连续的 \(1\) 出现。

感觉很不错，于是加上松弛变量：
\[ \sum_{j} A_{i,j} x_j + y_i = c_i \]
差分后：
\[ \sum_{l_j = i} x_j - \sum_{r_j + 1 = i} x_j + y_i - y_{i - 1} = c_i - c_{i - 1} \]
移项得到：
\[ \sum_{l_j = i} x_j + c_{i - 1} + y_i = \sum_{r_j + 1 = i} x_j + c_i + y_{i - 1} \]
将等式看成一个点的流量平衡，于是就有这样的连边方案：

• 点集 \(V = {S, T, 1, 2, \cdots, n + 1}\)

• \(\forall i \in [1, n + 1]\)，连边 \((S, i, c_{i - 1}, 0)\)（即从 \(S\) 到 \(i\)，流量为 \(c_{i - 1}\)，费用为 \(0\)）和 \((i, T, c_i, 0)\)。
• \(\forall i \in [1, n]\)，连边 \((i + 1, i, \infty, 0)\) 表示松弛变量。

• 对任意区间 \([l_i, r_i]\)，连边 \((r_i + 1, l_i, \infty, d_i)\)。

于是上最大费用最大流即可，具体实现细节可以见代码。

未完待续。。。

「学习笔记」线性规划

原文：https://www.cnblogs.com/cj-xxz/p/12210557.html