线性规划对偶
stripe_python
·
·
算法·理论
对实数变量 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})。
::::::