详细揭秘如何使用 对哦 原理

博客园好像渲染不明白这么多 Latex，不管了。typora 万岁。

参考资料：How to take the Dual of a Linear Program

将多元函数最优化问题改写为其对偶问题是一个机械的过程，下面以最优化方向为 \(\min\) 进行对偶为例，若最优化方向为 \(\max\) 则取反。

最优化问题可以从一个很随意的形式开始，对 \(x_i\) 的线性组合可能存在 \(\leq\)、\(\geq\)、\(=\) 三种约束的一种，注意限制不能是严格的。将所有约束转化为只有 \(\leq 0\) 和 \(=0\) 两种情况。这是对偶的第一步。

接下来，对于每条约束，设置乘子变量 \(\lambda_i\)。若限制为 \(\leq0\)，则 \(\lambda_i\geq0\)，否则不做约束，将 \(\lambda_i\) 乘上对应约束左边的式子，加到需要最优化的函数上，这样你得到了一个关于 \(\lambda_i\) 和 \(x_i\) 的多元函数 \(L(\lambda,x)\)，\(\lambda\) 和 \(x\) 都有对应的限制。

现在，\(\max_{\lambda}\min_xL(\lambda,x)\) 这个式子和原最优化问题的解相同。现在的 \(L(\lambda,x)\) 是以 \(\lambda\) 为主元，将其变形成以 \(x\) 为主元。随后删去包含 \(x\) 的项，相应的添加关于 \(\lambda_i\) 线性组合限制：

• \(x_i\geq0\)，限制为 \(\geq0\)。
• \(x_i\leq0\)，限制为 \(\leq0\)。
• \(x_i\) 自由，限制为 \(=0\)。

这样变成了一个关于 \(\lambda_i\) 在 \(\max\) 方向上的最优化问题。强对偶定理指出，在原最优化问题存在最优解的情况下，对偶问题一定存在可行解。

---

可能有一些问题，比如 \(\max_{\lambda}\min_xL(\lambda,x)\) 为什么和原最优化问题的解相同，这部分先略过一下。

大概就是需要放缩一下。和拉格朗日乘数法比较像？有空再写。

---

2025.12.18 省选模拟赛 T3，作为例子演示一下。

\[\min\limits_{X_{i,j}\geq0}\sum\limits_i\sum\limits_j-X_{i,j}\\ \forall1\leq i\leq2n,\sum\limits_{j=1}^nX_{i,j}\leq A_i\\ \forall1\leq j\leq n,\sum\limits_{i=1}^{2n}X_{i,j}\leq B_j\\ \forall1\leq i,j\leq n,X_{i,j}\leq C_i\\ \forall n+1\leq i\leq2n,1\leq j\leq n,X_{i,j}\leq D_j \]

对于每个限制设置变量：

\[\max\limits_{a_i,b_i,c_{i,j},d_{i,j}\geq0}\min_{X_{i,j}\geq0}\sum\limits_i\sum\limits_j-X_{i,j}+\sum\limits_ia_i(-A_i+\sum\limits_jX_{i,j})+\sum\limits_jb_j(-B_j+\sum\limits_iX_{i,j})+\sum\limits_{i=1}^n\sum\limits_jc_{i,j}(-C_i+X_{i,j})+\sum\limits_{i=n+1}^{2n}\sum\limits_jd_{i,j}(-D_j+X_{i,j}) \]

展开：

\[\max\limits_{a_i,b_i,c_i,d_i\geq0}\min\limits_{X_{i,j}\geq0}\sum\limits_{i=1}^n\sum\limits_jX_{i,j}(a_i+b_j+c_{i,j}-1)+\sum\limits_{i=n+1}^{2n}\sum\limits_jX_{i,j}(a_i+b_j+d_{i,j}-1)+\sum\limits_i-a_iA_i+\sum\limits_j-b_jB_j+\sum\limits_{i=1}^n\sum\limits_{j}-c_{i,j}C_i+\sum\limits_{i=n+1}^{2n}\sum\limits_j-d_{i,j}D_j \]

添加限制：

\[\min\limits_{a_i,b_i,c_i,d_i\geq0}\sum\limits_ia_iA_i+\sum\limits_jb_jB_j+\sum\limits_{i=1}^n\sum\limits_{j}c_{i,j}C_i+\sum\limits_{i=n+1}^{2n}\sum\limits_jd_{i,j}D_j\\ \forall1\leq i,j\leq n,a_i+b_j+c_{i,j}-1\geq0\\ \forall n+1\leq i\leq 2n,j,a_i+b_j+d_{i,j}-1\geq0 \]

这个问题本质就是，可以用 \(A_i\) 的代价覆盖第 \(i\) 行，\(B_j\) 的代价覆盖第 \(j\) 列，\(C_i\) 的代价覆盖第 \(1\leq i\leq n\) 行的某个格子，\(D_j\) 的代价覆盖后 \(n\) 行第 \(j\) 列的某个格子，要求每个格子至少覆盖一次。从这里可以看出我们将限制和贡献进行了对偶。另一种更加广为人知的对偶方式也可以处理这道题，那种方式更能体现对偶的本质。但有时候那样对偶不太好处理。

有时候对偶的难点通常不在于对偶，而在于对偶之后。