线性规划对偶

· · 算法·理论

对实数变量 x_1 \sim x_n,称线性规划 / LP 问题的标准形式为

\begin{aligned} \min \quad & \sum_{i=1}^n c_i x_i\\ \text{s.t.}\quad & \sum_{i=1}^n a_{j,i}x_i=b_j\ge 0,\quad \forall j\in[1,m]\\ & x_i\ge 0,\quad \forall i\in[1,n] \end{aligned}

用自然语言表述问题,给定 m 条限制 \sum \limits_{i=1}^n a_{j,i}x_i \ge 0,构造一组正实数 x_1 \sim x_n 最小化 \sum \limits_{i=1}^n c_ix_i。

对其他形式的 LP 问题,可以等价变形为标准形。

对标准形线性规划,设系数矩阵 A=(a_{j,i}),LP 问题可以表述为

\min \{c^T \vec{x} : A\vec{x} =\vec{b} \ge 0,\vec{x} \ge 0\}

称 LP 问题 \max\{b^T \vec{y}: A^T\vec{y} \le c\} 是对偶问题。一般地

\begin{aligned} \max \quad & \sum_{j=1}^m b_j y_j\\ \text{s.t.}\quad & \sum_{j=1}^m a_{j,i}y_j\le c_i,\quad \forall i\in[1,n]\\ & y_j\in\mathbb R,\quad \forall j\in[1,m] \end{aligned}

弱对偶定理 必有 \max\{b^T \vec{y}: A^T\vec{y} \le c\} \le \min \{c^T \vec{x} : A\vec{x} =\vec{b} \ge 0,\vec{x} \ge 0\}。

强对偶定理 只要原问题或对偶问题之一可行,必有 \max\{b^T \vec{y}: A^T\vec{y} \le c\} = \min \{c^T \vec{x} : A\vec{x} =\vec{b} \ge 0,\vec{x} \ge 0\}。

在 OI 中,我们假想 LP 问题和对偶问题等价,将 LP 对偶视作最优化问题的转化手法。

另外,OI 中列出的 LP 问题常有 x \in \mathbb{Z} 的约束,称为整数规划。一般整数规划是 NP-Hard 的。我们假想 LP 形式存在整数最优解,忽略 x\in \mathbb{Z} 的限制进行求解。

CF605C Freelancer's Dreams

给定 n 个任务 (a_i,b_i),你可以对 i 任务分配 x_i 实数时间,要求 \sum\limits_{i=1}^n a_ix_i \ge p \land \sum\limits_{i=1}^n b_ix_i \ge q。最小化 \sum \limits_{i=1}^n x_i 并输出,精度要求 10^{-6}。

::::::success[题解]

题意即求解下述 LP 问题

\begin{aligned} \min \quad & \sum_{i=1}^n x_i\\ \text{s.t.}\quad & \sum_{i=1}^n a_ix_i\ge p\\ & \sum_{i=1}^n b_ix_i\ge q\\ & x_i\ge 0,\quad \forall i\in[1,n] \end{aligned}

取对偶

\begin{aligned} \max \quad & py_1+qy_2\\ \text{s.t.}\quad& a_iy_1+b_iy_2 \le 1,\quad \forall i \in [1,n] \\ & y_1,y_2 \ge 0 \end{aligned}

对固定的 y_1,函数 py_1+qy_2 关于 y_2 单增,故 y_2 必取 \max。由 \forall i, a_iy_1+b_iy_2 \le 1 移项推知

y_2 \le \min_{i=1}^n\dfrac{1-a_iy_1}{b_i}

将目标函数写成以 y_1 为自变量的形式

\begin{aligned} f(y_1)&= py_1+q \times \min_{i=1}^n\dfrac{1-a_iy_1}{b_i} \end{aligned}

对 y_1 的约束为 y_1,y_2 \ge 0。令 \forall i, 1-a_iy_1 \ge 0 解得 y_1 上界。

容易发现 f(y_1) 关于 y_1 上凸,三分求峰即可。复杂度 O(n \log \frac{1}{\epsilon})。

::::::