以前学了很多次都没学明白，今天再来看看。
本文不会涉及单纯形法的知识点讲解，大部分题目侧重于线性规划对偶。
同样本文不会涉及相关知识点的证明，或是线性规划解的整数性说明，毕竟这只是一个总结性的文章。
拉格朗日对偶部分没学会，暂鸽。
线性规划标准型
对于任意线性规划，容易通过简单的变形使其变为以下形式（无限制的变量拆为两个非负变量作差）：
\[\max c^T x\\Ax\leqslant b\\x\geqslant 0 \]两个变量的线性规划：每条限制对应一个半平面，会交出一个不一定封闭的平面凸形，而最值可以看作最大化某直线纵截距，凸包二分即可。
整数线性规划
其要求自变量取到整数，这是 NP-hard 问题。不过很多情况下，我们遇到的线性规划问题都有整数最优解。
全幺模矩阵
若矩阵 \(A\) 满足任意子式值均为 \(\{-1,0,1\}\)，我们称其全幺模矩阵。
在 OI 中，一个充分的判定方法是：系数在 \(\{-1,0,1\}\) 内，每列至多两个非零位置，且若某列有两个非零位置，将对应行连边，得到的图是二分图。
若约束为全幺模矩阵，整数线性规划可以看作普通线性规划求解。
任何最大流、最小费用最大流的线性规划都是全幺模矩阵。
标准型的对偶
我们定义一标准型线性规划的对偶为：
\[\min y^Tb\\A^Ty\geqslant c\\y\geqslant 0 \]若 \(A\) 是 \(B\) 的对偶，那么 \(B\) 一定是 \(A\) 的对偶，称两者互为对偶。
对于某取等的限制，其改写成标准型后对偶会产生两个变量 \(y_1,y_2\)，我们需要最小化 \(b(y_1-y_2)\)，\(y_1-y_2\) 可以写成一无限制变量 \(y\)（即可以小于 \(0\)）。因此取等的限制与无限制变量之间是对偶关系，这样推对偶会更方便。
强对偶定理
我们不加证明地指出——
对于线性规划 \(P\)，假设其对偶形式为 \(D\)，以下有且仅有一条成立：
- \(P,D\) 均有最优解且最优解相等；
- \(P,D\) 均无最优解；
- 仅有一者有可行解，且有可行解的目标函数在约束下无界。
互补松弛定理
对于一组对偶线性规划 \(P,D\)，\(x,y\) 分别为 \(P,D\) 最优解等价于以下两者同时成立：
- 若 \(x_i>0\)，\(D\) 中对应的限制是紧的；
- 若 \(y_i>0\)，\(P\) 中对应的限制是紧的。
（事实上反向也成立）
简证：我们令松弛变量 \(x_s=b-Ax,y_s=A^Ty-c\)，根据强对偶定理有：
\[y^TAx+y^Tx_s=y^Tb=c^Tx=y^TAx-y_s^Tx\\\Leftrightarrow y^Tx_s+y_s^Tx=0 \]如何还原方案
根据前文提到的互补松弛定理，我们若求出对偶定理的最优解，讨论每个变量是否为零，这样就能对应到原问题某个限制是否紧。
若原问题形式较好，我们通过某种方法还原了方案，此时根据互补松弛定理，任意合法解均为最优解。
一些模型
最短路模型：
\[\max d_t-d_s\\d_y\leqslant d_x+c_{x,y}((x,y)\in E) \]最大流模型：（为了方便，我们加入边 \((t,s)\)，流量为 \(\infty\)，因此可以要求源汇也满足流量守恒）
\[\max f_{t,s}\\0\leqslant f_{x,y}\leqslant c_{x,y}((x,y)\in E)\\\sum_{(x,i)\in E}f_{x,i}=\sum_{(j,x)\in E}f_{j,x} \]最小费用流模型：
\[\min\sum w_{x,y}f_{x,y}\\0\leqslant f_{x,y}\leqslant c_{x,y}((x,y)\in E)\\\sum_{(x,i)\in E}f_{x,i}=\sum_{(j,x)\in E}f_{j,x} \]市面上的形式都引入了 \(b_x\) 这一变量表示 \(x\) 的出流量减入流量（可以看作一条连接源或汇的边），在这也记录一下：
\[\min\sum w_{x,y}f_{x,y}\\0\leqslant f_{x,y}\leqslant c_{x,y}((x,y)\in E)\\\sum_{(j,x)\in E}f_{j,x}-\sum_{(x,i)\in E}f_{x,i}=-b_x \]一些对偶
最小费用流模型的对偶：
令 \(z_{x,y}\) 为第一个限制的对偶变量，\(p_x\) 为第二个限制的对偶变量：
\[\max\sum -b_xp_x-\sum_{(x,y)\in E}c_{x,y}z_{x,y}\\p_y-p_x-z_{x,y}\leqslant w_{x,y}((x,y)\in E)\\z_{x,y}\geqslant 0((x,y)\in E)\\p_x\geqslant 0 \]消去 \(z_{x,y}\)，整理得：
\[\min\sum b_xp_x+\sum_{(x,y)\in E}c_{x,y}\max(0,p_y-p_x-w_{x,y}) \]最大费用循环流模型的对偶：
我们先写出最大费用循环流的线性规划
\[\max\sum_{(x,y)\in E} w_{x,y}f_{x,y}\\0\leqslant f_{x,y}\leqslant c_{x,y}((x,y)\in E)\\\sum_{(x,i)\in E}f_{x,i}=\sum_{(j,x)\in E}f_{j,x} \]对偶得：
\[\min\sum_{(x,y)\in E} c_{x,y}z_{x,y}\\p_x-p_y+z_{x,y}\geqslant w_{x,y}\\z_{x,y}\geqslant 0 \]同样地消去 \(z_{x,y}\)，整理得：
\[\min\sum_{(x,y)\in E}c_{x,y}\max(0,p_y-p_x+w_{x,y}) \]其等价于上面最小费用流添加汇点到源点的边后令所有 \(b_i=0\)，且令 \(w'_{x,y}\leftarrow w_{x,y}\) 的结果，与我们的认知相吻合。
根据对偶的结果，我们可以得知若题目所求为这些结果的式子，可以对偶，并使用费用流/最大费用循环流解决。
一些例题
以下的例题若不特殊说明，默认变量非负。
① P3337 [ZJOI2013] 防守战线
令变量 \(p_i\) 表示 \([1,i]\) 建的塔数量，写出线性规划：
\[\min \sum_i p_i(C_i-C_{i+1})\\p_{i+1}-p_i\geqslant 0\\p_{R_i}-p_{L_i-1}\geqslant D_i \]改写目标函数为：
\[\min \sum_i p_i(C_i-C_{i+1})+\sum_i\infty\max(0,-p_{i+1}+p_i)+\sum_i\infty\max(0,-p_{R_i}+p_{L_i-1}+D_i) \]使用上面的最小费用流模型解决。
② P3980 [NOI2008] 志愿者招募
写出线性规划：
\[\min \sum_i c_ix_i\\\sum_{l_j\leqslant i\leqslant r_j}x_j\geqslant a_i \]对偶得到：
\[\max\sum_i a_iy_i\\\sum_{i=l_j}^{r_j}y_i\leqslant c_j \]不过到了这一步好像只能单纯形？
也可以作前缀和变为上一题的形式然后再对偶，不过这应该是等价于直接做费用流的。
③ ABC224H Security Camera 2
写出线性规划：
\[\min\sum a_ix_i+\sum b_iy_i\\x_i+y_j\geqslant c_{i,j}((i,j)\in E) \]对偶得到：
\[\max\sum_{(i,j)\in E}c_{i,j}z_{i,j}\\\sum_{(u,i)\in E} c_{u,i}\leqslant a_u\\\sum_{(i,v)\in E}c_{i,v}\leqslant b_v \]经典的二分图最大费用流模型。
④ CF671D Roads in Yusland
首先有一种不需要线性规划的方法，也提一下：
令 \(f_x\) 为覆盖了 \(x\) 子树与其父边的方案数，但 \(f\) 之间无法直接转移。我们 dfs 整棵树，对于每棵子树维护出很多 \((c,t)\) 表示覆盖完这棵树后继续向上覆盖 \(t\) 步，最小代价是 \(c\)。
对于 \(y\in \operatorname{son}(x)\)，考察 \(y\) 的二元组 \((c,t)\) 转移到 \(x\)，其产生的贡献是 \(c+\sum_{z\in \operatorname{son}(x),z\ne y}f_z\)，于是我们可以使用支持全局减，合并，维护最大值的左偏树来维护所有方案，复杂度 \(O(n\log n)\)。
写出线性规划：
\[\min \sum c_iz_i\\\sum_{(x_j,y_j)\ni i} z_j\geqslant 1 \]对偶得到：
\[\max \sum p_i\\\sum_{i\in (x_j,y_j)}p_i\leqslant c_j \]这就是经典的贪心了，要维护每条链被覆盖的次数，每个点贪心地减，同样使用左偏树做到 \(O(n\log n)\)。
⑤ HDU6974 Destinations
注意到问题可以被改写成：有 \(3m\) 条链，选择 \(m\) 条链使得互不相交（因为同一起点的路径两两相交），同时容易发现 \(m\) 是上界，我们将权值改为 \(\inf-v_i\)，即选择若干条不交链，最大化权值和。
写出线性规划：
\[\max \sum c_iz_i\\\sum_{(x_j,y_j)\ni i} z_j\leqslant 1 \]对偶得到：
\[\min\sum p_i\\\sum_{i\in (x_j,y_j)}p_i\geqslant c_j \]这是经典的树上延迟贪心，我们 dfs 整棵树，在 lca 处考察路径，若点权和不够就补上来，树状数组维护，复杂度 \(O(n\log n)\)。
⑥ P7246 手势密码
写出线性规划：
\[\min \sum_{u,v}z_{u,v}\\\sum_{(u,v)\ni i}z_{u,v}=a_i \]对偶得到：
\[\max\sum a_ip_i\\\sum_{i\in(u,v)}p_i\leqslant 1 \]其中 \(p_i\) 无正负限制。
于是直接令 \(f_{x,0/1}\) 表示从 \(x\) 子树出发，权值和最大的路径值为 \(0/1\) 的最大答案，容易发现 \(p_i\) 只会取 \(\{-1,0,1\}\)，复杂度 \(O(n)\)。
⑦ P6631 [ZJOI2020] 序列
dxm 论文推法好像麻烦了点，类似上一题，我们有一个更简单的推法（其中 \(S\) 为操作构成的集族）：
\[\min \sum_{T\in S}x_T\\\sum_{T\ni i}x_T=a_i \]对偶得到：
\[\max\sum a_ip_i\\\sum_{i\in T}p_i\leqslant 1 \]类似上一题地列出 dp，记录三类操作对应最大后缀和即可，容易发现值域 \(\{0,1\}\)，复杂度 \(O(n)\)。
⑧ XX Open Cup GP of Moscow C Circles
写出线性规划：
\[\max\sum x_i\\x_i+x_{i\bmod n+1}\leqslant s_i \]对偶得到：
\[\min\sum s_iy_i\\y_i+y_{i\bmod n+1}\geqslant 1 \]事实上可以证明，除了全为 \(0.5\) 的情况，其余时候均满足 \(y_i\in\{0,1\}\)，于是从前往后 dp 一下即可，环的限制不难拆，复杂度 \(O(n)\)。
⑨ CF1696G Fishingprince Plays With Array Again
写出线性规划：
\[\min\sum x_i+y_i\\Xx_i+Yx_{i-1}+Yy_i+Xy_{i-1}\geqslant a_i\\x_0=y_0=x_n=y_n=0 \]我们发现第三行限制事实上是没有必要的，因为这些操作都可以找到对应不劣的合法操作代替。
对偶得到：
\[\max \sum a_iz_i\\Xz_i+Yz_{i+1}\leqslant 1\\Yz_i+Xz_{i+1}\leqslant 1\\ \]不妨设 \(X\leqslant Y\)，事实上可以证明，\(z_i\) 的取值只有 \(\{0,\frac 1{X+Y},\frac 1Y\}\)，于是使用线段树维护矩阵乘法维护即可，复杂度 \(O(q\log n)\)。
⑩ P4642 [BJWC2008] 方程
线性规划式子在题面里就不列出来了，直接写出对偶形式：
\[\min z_1s+z_2t\\a_iz_1+b_iz_2\geqslant c_i \]这里的 \(z_1,z_2\) 无正负限制，于是预处理半平面交，询问在凸包上二分即可，复杂度 \(O((n+q)\log n)\)。
⑪ CODECHEF Chefbook
写出线性规划：
\[\max\sum p_iout_i-q_iin_i\\s_{x,y}\leqslant w_{x,y}+p_x-q_y\leqslant t_{x,y}((x,y)\in E) \]将 \(w_{x,y}\) 的影响消去，对偶得到：
\[\min\sum_{(x,y)\in E}-s'_{x,y}f_{x,y}+t'_{x,y}g_{x,y}\\-\sum_{(x,i)\in E}f_{x,i}+\sum_{(i,x)\in E}g_{i,x}\geqslant out_x\\\sum_{(x,i)\in E}f_{x,i}-\sum_{(i,x)\in E}g_{i,x}\geqslant-in_x \]容易转成前面提到的最小费用流模型，而这题还要求构造方案，使用前文提到的还原方法，问题变为了差分约束，任跑一组解即可。
⑫ bzoj3118 orz the mst
对于每条非树边，其限制为权值大于等于路径上所有边，容易写出：
\[\min\sum_{e\in T}b_ex_e+\sum_{e\not\in T}a_ex_e\\x_e+w_e\geqslant w_i-x_i(i\in P_e,e\not\in T) \]对偶得到：
\[\max\sum_{i\in P_e,e\not \in T}(w_i-w_e)y_{e,i}\\\sum_{i\in P_e}y_{e,i}\leqslant a_e(e\not\in T)\\\sum_{P_e\ni i}y_{e,i}\leqslant b_i(i\in T) \]暴力连边，经典的二分图费用流模型。
⑬ P4412 [SHOI2004] 最小生成树
上一题的子问题。
⑭ CF1765J Hero to Zero
先证明一个经典结论：在一张带权二分图中，最大带权匹配的权值和恰好为最小顶标和。
写出最大带权匹配的线性规划：
\[\max\sum_{(x,y)\in E}w_{x,y}z_{x,y}\\\sum_{(x,i)\in E}z_{x,i}\leqslant 1(x\in L)\\\sum_{(i,x)\in E}z_{i,x}\leqslant 1(x\in R) \]对偶得到：
\[\min\sum_{i\in L}p_i+\sum_{i\in R}q_i\\p_x+q_y\geqslant w_{x,y}((x,y)\in E) \]证毕。此时再回顾 ⑫，其无非是将最小顶标和对偶成了最大带权匹配问题。
回到这个问题，我们直接设 \(x_i,y_j\) 分别表示某一行/列操作数量，写出线性规划：
\[\min\sum x_i+y_i+\sum_{i,j}(c_{i,j}-x_i-y_j)=\sum c_{i,j}-(n-1)(\sum x_i+y_i)\\x_i+y_j\leqslant c_{i,j} \]这就是最小顶标和模型，对偶成最大匹配后容易使用贪心解决，复杂度 \(O(n\log n)\)。
⑮ 2022 集训队互测 Round 7 B 卑鄙的下毒人
令原材料毒药数量前缀和为 \(q_i\)，写出线性规划：
\[\min k(q_n-q_0)+\sum_i\max(0,a_i-(b_{R_i}-b_{L_i-1}))\\q_i\leqslant q_{i+1} \]式子很类似最大循环流模型，将 \(q_i\leqslant q_{i+1}\) 带上 \(\infty\) 的权值写入目标函数中，直接应用上面的式子得到建图：
- \((0,n,k,0)\)；
- \((R_i,L_i-1,1,a_i)\)；
- \((i+1,i,\infty,0)\)。
我们可以去除 \((0,n)\) 的边变为有源汇最大费用流，取负变成最小费用流，由于有负权，我们需使用原始对偶求解。第一轮的势能计算也可以不使用 spfa，因为此时图为 dag 可以直接递推。
⑯ CF1307G Cow and Exercise
写出线性规划：
\[\max z_n-z_1\\z_y\leqslant z_x+c_{x,y}+w_{x,y}((x,y)\in E)\\\sum_{(x,y)\in E}w_{x,y}\leqslant C \]对偶得到（注意 \(z\) 是不限制正负的变量，对偶后是取等的限制）：
\[\min\sum_{(x,y)\in E}c_{x,y}f_{x,y}+Cg\\\sum_{(x,i)\in E}f_{x,i}-\sum_{(i,x)\in E}f_{i,x}=\begin{cases}1&x=1\\-1&x=n\\0&\text{otherwise}\end{cases}\\-f_{x,y}+g\geqslant 0 \]其很类似最小费用流模型，稍微变形得到：
\[\min(\sum_{(x,y)\in E}c_{x,y}f_{x,y}+C)g\\\sum_{(x,i)\in E}f_{x,i}-\sum_{(i,x)\in E}f_{i,x}=\begin{cases}\frac 1g&x=1\\-\frac 1g&x=n\\0&\text{otherwise}\end{cases}\\f_{x,y}\leqslant 1 \]注意到 \(\sum_{(x,y)\in E}c_{x,y}f_{x,y}\) 为每条边流量在 \([0,1]\) 内的图，流量恰好为 \(\frac 1g\) 时最小费用流费用大小，即求：
\[\max\frac{\operatorname{mincost of flow}(h)+C}{h} \]虽然 \(h\) 是任意实数，可以证明对于任意区间 \([t,t+1](t\in\mathbb Z)\)，最值永远在边界取到。
众所周知，最小费用最大流是凸的，于是记录下每次增广结束后的流量与费用，其不重不漏地构成了凸壳上所有位置，每次询问暴力遍历凸壳即可，复杂度 \(O(nm^2+qm)\)。
⑰ loj#6511. 「雅礼集训 2018 Day8」B
二分答案，我们考虑最小化支出，写出线性规划：
\[\min \sum c_iz_i\\d_y\geqslant d_x+w_y-z_y((x,y)\in E)\\d_i\leqslant mid \]消去 \(z_i\) 可以发现这是最大费用循环流模型。
⑱ CF375E Red and Black Tree
有树形背包做法，这里仅讨论对偶做法，写出线性规划：
\[\min(1-c_i)z_i\\\sum_{\operatorname{dis}(x,i)\leqslant X}z_i\geqslant 1\\\sum z_i=m \]容易发现不会有 \(z_i\leqslant 1\)，对偶变为标准型，使用单纯型法解决。
⑲ 2021 集训队互测 Round 4 B 机器
标签：浅谈,min,线性规划,sum,geqslant,leqslant,对偶 From： https://www.cnblogs.com/xiaoziyao/p/17517642.html