线性规划对偶问题

· · 算法·理论

一个经典的线性规划问题如下：

有 n 个变量 x_1,\ldots,x_n，另有 m 个不等式，每个形如 \sum_j A_{i,j}x_j\le y_i，最大化 \sum_j B_jx_j。

在一些时候，直接求解这个问题是困难的，尤其是在变量比不等式多的时候，这种时候可以可以借助对偶的问题将变量和不等式数量交换。

如果 \max w=B\cdot x，Ax\le C，x\ge 0；\min w'=C\cdot x'，A^Tx'\ge B，x'\ge 0。

那么 \max w=\min w'。

这个式子有如下的意义：将不等式而不是变量做线性组合，企图组合出目标的 B\cdot x，所有这样线性组合的最小值就是原问题的答案。

假设最终第 i 个不等式的系数是 x'_i，那么最后就需要满足 \sum_i x'_iA_{i,j}\ge B_j，在此基础上最小化 \sum C_ix'_i，就可以得到原问题的上界也即答案。

为了满足目标形式，可能需要对原来的 x_i 的限制做一些小变换，具体的，若 x_i\le 0，则将 y=-x_i 作为新变量；若 x_i 无限制，则将 y-z=x_i，y,z\ge 0 作为新变量，若 x_i\in [l,r]，先使得 l=0，随后拆成 y-z\le r，z-y\le 0，y,z\ge 0。

例题：CF1696G

不考虑区间询问，记 t_{i,0/1} 为对 i 进行操作 0/1 的时间，则目标为最小化 \sum t_{i,0/1}，限制为：

这问题限制较少，通常难以解决，可以尝试用对偶问题转化：

目标变为最大化 \sum x_ia_i，限制为：

考虑 x_i 对 x_{i-1} 的限制，有 x_{i-1}\le \min((1-X\cdot x_i)/Y,(1-Y\cdot x_i)/X)，不放设 X<Y，那么当 x_i\le 1/(X+Y) 时取到第一项，否则取到后一项。

简单讨论可以发现，答案在 [0,1/(X+Y)] 和 (1/(X+Y),1/X] 上分别是一次函数，且当 x_i=1/(X+Y) 时不等式恰好是 x_{i-1}\le 1/(X+Y)，故可以只保留 x_i=0,1/(X+Y),1/X 三个取值，线段树维护矩阵即可。

复杂度 O(n+q\log n)。