强对偶性的证明
接续上次的讨论，我们已经得到了弱对偶性，这导出了最大匹配不大于最小点覆盖。然而需要了解的是，在二分图中二者相等，这就对应着强对偶性。
我们首先需要考察的是原问题和对偶问题是否存在可行解。我们会逐渐从松弛形过渡到标准形。
\(\textbf{引理 1. }\) 设 \(A\in \mathbb R^{n\times m}, \bm b\in \mathbb R^{m}\)，则下面两个叙述有且只有一个成立：
- \(A\bm x = \bm b\) 有解。
- \(A^{\mathsf T} \bm y = \bm 0,\ \bm b^{\mathsf T} \bm y = -1\) 有解。
我们可以从几何意义上解释该引理：若一个向量 \(\bm b\) 不存在于 \(A\) 的列张成 \(V\) 中，则其一定于一个正交于 \(V\) 的向量成钝角。
然后证明：
如果 \(1. 2.\) 同时成立，则 \(-1 = \bm b^{\mathsf T}\bm y = \bm x^{\mathsf T} A^{\mathsf T} \bm y = 0\)，这矛盾。
如果 \(1.\) 不成立，则向量 \(\bm b\) 不存在于 \(A\) 的列张成 \(V\) 中，即 \(\text{rank}([A \ \ \bm b]) = \text{rank}(A) + 1\)，从而矩阵
的秩也是 \(\text{rank}(A) + 1\)。因此 \([\bm 0 \ \ -1 ]^{\mathsf T}\) 可以被 \([A \ \ \bm b]^{\mathsf T}\) 线性表出，因此存在 \(\bm y\)。
证完。
\(\textbf{引理 2. }\text{(Farkas) }\) 设 \(A\in \mathbb R^{n\times m}, \bm b\in \mathbb R^{m}\)，则下面两个叙述有且只有一个成立：
- \(A\bm x = \bm b, \bm x \ge \bm 0\) 有解。
- \(A^{\mathsf T} \bm y \ge \bm 0,\ \bm b^{\mathsf T} \bm y \le 0\) 有解。
\(\text{Farkas}\) 引理是最优化理论的基石之一。
几何意义和引理 \(1\) 相似。\(A\bm x \text{ s.t. } \bm x\ge \bm 0\) 表出了 \(A\) 张成的一个凸锥。如果一个点不在凸锥内部，则这个点和凸锥一定能由一个超平面分开，且这个超平面过原点。这个超平面对应的方程是 \(\bm x^{\mathsf T}\bm y = 0\)。
然后证明：
如果 \(1. 2.\) 同时成立，则 \(0\le \bm x^{\mathsf T} A^{\mathsf T} \bm y = (Ax)^{\mathsf T} \bm y = \bm b^{\mathsf T}\bm y < 0\)，这矛盾。
如果 \(1.\) 不成立，则不妨设 \(A\bm x = \bm b\) 有解，但解不满足 $ \bm x \ge \bm 0$。无解的情况由引理 \(1\) 可知。
设 \(A = (\bm a_1, \bm a_2, \dots, \bm a_n)\)。现在对 \(n\) 作归纳法证明。
当 \(n = 1\) 时，条件为 \(x_1\bm a_1 = \bm b\) 有解，且 \(x_1 < 0\)。取 \(\bm y = -\bm b\)，则有 \(\bm a_1^{\mathsf T} \bm y = -\bm b^{\mathsf T} \bm b / x_1 > 0, \ \bm b^{\mathsf T}\bm y = - \bm b^{\mathsf T} \bm b < 0\)。
归纳。假设我们已经对 \(k < n\) 证明了原命题。由于 \(1.\) 不成立，所以 \(\sum_{i=1}^{n-1} x_i \bm a_i = \bm b\) 一定没有满足 \(\forall i < n, \ x_i \ge 0\) 的解（否则 \(x_n = 0\) 即可）。由归纳，\(\exists \bm v, \ \bm a_i^{\mathsf T} \bm v \ge 0(1\le i < n)\) 且 \(\bm b^{\mathsf T} \bm v < 0\)。假设 \(\bm a_n^{\mathsf T} \bm v \ge 0\) 则原命题成立，因此不妨假设 \(\bm a_n^{\mathsf T} \bm v < 0\)。
我们取
则易见 \(\sum_{i = 1}^{n-1} x_i \hat{\bm a_i} = \hat{\bm b}\) 也没有满足 \(\forall i,\ x_i \ge 0\) 的解。否则整理得到
\[\sum_{i=1}^{n-1} \bm a_i x_i+ \frac{1}{\bm a_n^{\mathsf T} \bm v} \left(\bm b^{\mathsf T} \bm v - \sum_{i=0}^{n-1}\bm a_i^{\mathsf T} \bm v x_i\right) \bm a_n = \bm b \]这与 \(1.\) 不成立矛盾。归纳得 \(\exists \bm w, \ \hat{\bm a_i}^{\mathsf T} \bm w \ge 0(1\le i < n)\) 且 \(\hat{\bm b}^{\mathsf T} \bm w < 0\)。
可以验证 \(\bm y = (a_n^{\mathsf T} \bm w)\bm v - (a_n^{\mathsf T}\bm v) \bm w\) 即为解。
证完。
\(\textbf{推论 1 }\) 设 \(A\in \mathbb R^{m\times n}, \bm b\in \mathbb R^{m}\)，则下面两个叙述有且只有一个成立：
- \(A\bm x\le \bm b,\ \bm x \ge \bm 0\) 有解。
- \(A^{\mathsf T}\bm y \ge \bm 0, \ \bm y\ge \bm 0, \ \bm b^{\mathsf T} \bm y < 0\) 有解。
证明：
如果 \(1. 2.\) 同时成立，则 \(0\le \bm x^{\mathsf T} A^{\mathsf T} \bm y = (Ax)^{\mathsf T} \bm y = \bm b^{\mathsf T}\bm y < 0\)，这矛盾。
如果 \(1.\) 不成立，可以通过转松弛形的方式转换等价形式。原问题等价于
\[[A \quad I_m]\left[ \begin{aligned} \bm x & \\ \bm x & ' \end{aligned} \right] = \bm b,\quad \bm x, \bm x' \ge \bm 0 \]无解。由 \(\text{Farkas}\) 引理，存在 \(y\) 使得
\[\left[ \begin{aligned} A^{\mathsf T} \\ I_m \end{aligned} \right]\bm y \ge \bm 0, \quad \bm b^{\mathsf T} \bm y < 0 \]证完。
我们需要的拼图都得到了，下一步就是证明强对偶性。
\(\textbf{定理 2} \text{(强对偶性)}\)
设线性规划的原问题和对偶如定义 \(1,3\) 形式，记为 \(P, D\)。下面的叙述有且仅有一个成立：
- \(P, D\) 均有最优解，且 \(P = D\)。
- \(P\) 有可行解，\(D\) 无可行解，且 \(P\) 的目标函数在约束条件下无界。
- \(D\) 有可行解，\(P\) 无可行解，且 \(D\) 的目标函数在约束条件下无界。
- \(P, D\) 均无可行解。
假设 \(P, D\) 均有可行解。根据弱对偶性，我们只需要证明
\[\begin{aligned} &A\bm x \le \bm b, \quad &\bm x \ge \bm 0 \\ &A^{\mathsf T} \bm y \ge \bm c, \quad & \bm y \ge \bm 0 \\ &\bm c^{\mathsf T}\bm x - \bm b^{\mathsf T} \bm y \ge 0 \end{aligned}\]有解；也就是系统
\[\left[\begin{aligned} &A &\ &0 \\ &0 &\ - &A^{\mathsf T} \\ -&\bm c^{\mathsf T} &\ &\bm b^{\mathsf T} \end{aligned}\right] \left[\begin{aligned} &\bm x \\ &\bm y \end{aligned}\right] \le \left[\begin{aligned} \bm b \\ -\bm c \\ 0 \end{aligned}\right] \quad \left[\begin{aligned} &\bm x \\ &\bm y \end{aligned}\right] \ge \bm 0 \]有解。
如果其无解，则根据推论 \(1\)，存在 \(\bm z,\bm w\ge 0, \alpha \ge 0\) 满足
\[A \bm w \le \alpha \bm b \quad A^{\mathsf T}\bm z \ge \alpha \bm c \quad \bm b^{\mathsf T}\bm z < \bm c^{\mathsf T} \bm w \]\(\alpha \neq 0\)。不然，设 \(\hat{\bm x},\hat{\bm y}\) 分别是 \(P, D\) 的可行解，有
\[0 \le \hat{\bm x}^{\mathsf T} A^{\mathsf T} \bm z = (A\hat{\bm z})^{\mathsf T} \bm z \le \bm b^{\mathsf T}\bm z < \bm c^{\mathsf T}\bm w \le (A^{\mathsf T} \hat{\bm y})^{\mathsf T} \bm w = \hat{\bm y}^{\mathsf T} A\bm w \le 0 \]这矛盾。
此时可以设 \(\bm x = \bm w / \alpha,\bm y = \bm z / \alpha\)。可以验证 \(\bm x, \bm y\) 分别是 \(P, D\) 的可行解。由弱对偶性引出
\[\bm c^{\mathsf T}\bm w = \alpha(\bm c^{\mathsf T}\bm x) = \alpha(\bm b^{\mathsf T}\bm y) = \bm b^{\mathsf T} \bm z \]这与 \(\bm b^{\mathsf T}\bm z < \bm c^{\mathsf T} \bm w\) 矛盾。
因此上系统必有解，即最优解的值相同。
假设 \(P\) 无可行解，\(D\) 有可行解。由推论 \(1\) 可得 \(A^{\mathsf T}\bm w \ge \bm 0, \bm w \ge \bm 0, \bm b^{\mathsf T} \bm w < 0\) 有解。设 \(\bm y\) 是 \(D\) 的可行解，能注意到对任意非负实数 \(\lambda\)，\(\bm y + \lambda \bm w\) 都是可行解。\(D\) 的目标函数可以写作 \(\bm b^{\mathsf T}(\bm y + \lambda \bm w) = \bm b^{\mathsf T}\bm y + \lambda(\bm b^{\mathsf T} \bm w)\)。由于 \(\bm b^{\mathsf T} \bm w < 0\)，因此取充分大的 \(\lambda\) 可以使目标函数取值充分小，\(D\) 无界。\(2.\) 同理。
剩余情况即为 \(4.\)。
证完。
强对偶性还能导出一个很重要的性质，即互补松弛性。
\(\textbf{推论 2 }\text{(互补松弛性) }\)
设线性规划的原问题和对偶如定义 \(1,3\) 形式，记为 \(P, D\)。设 \(\bm x,\bm y\) 分别为 \(P, D\) 的最优解，下面的叙述有且仅有一个成立：
- \(y_i > 0\) 推出 \(\sum_{j=1}^n a_{i,j} x_j = b_i (1\le i \le m)\)。
- \(x_j > 0\) 推出 \(\sum_{i=1}^m b_{i,j} y_i = c_j (1\le j \le n)\)。
具体地说，就是第 \(i\) 个分量非负的约束和对偶问题的第 \(i\) 个约束一定有一个取等。
由强对偶性，有
\[\sum_{j=1}^n c_j x_j = \sum_{i, j} y_i a_{i, j} x_j = \sum_{i=1}^m b_i y_i \]这得到
\[\sum_{i=1}^m \left(b_i - \sum_{j=1}^n a_{i, j}x_j \right) y_i = 0 \]由于求和的每一项都 \(\ge 0\)，因此每一项都必须 \(=0\)。因此第 \(i\) 个分量 \(\ge 0\) 的约束和对偶问题的第 \(i\) 个约束一定有一个取等。
因此必要性得证。
当 \(1.2.\) 都成立时有
\[\bm c^{\mathsf T} \bm x = \sum_{j=1}^n c_j x_j = \sum_{j=1}^n\left(\sum_{i=1}^m a_{i,j}y_j\right)x_j = \sum_{i=1}^m\left(\sum_{j=1}^n a_{i,j}x_j\right)y_j = \sum_{i=1}^m b_i y_i = \bm b^{\mathsf T} \bm y \]由强对偶性得均为最优解。
因此充分性得证。
证完。
例题
给定一个网络，每条边 \((u,v)\) 有代价 \(c_{u,v}\) 和费用 \(w_{u,v}\)。对于一条边，可以将它的费用减少，不能减到负数，代价为减少量。问要让网络的最大费用循环流费用不超过 \(x\) 的最少代价。
HihoCoder 是不是早炸了？
考虑设 \(w'_{i, j}\) 为更改后的费用。然后根据例 \(3\) 的对偶形式，直接写出线性规划问题
\[\begin{aligned} \min\quad &\sum_{(u, v)} w_{u, v} - w'_{(u,v)} \\ \text{s.t.} \quad & \forall(u,v), \ d_{u, v} + y_{u, v} \ge w'_{u, v} \\ & \forall(u,v), \ w'_{u,v} \le w_{u, v} \\ & \sum_{(u, v)}d_{u, v} \times c_{u, v} \le x \\ & \forall(u, v), \ d_{u, v}, w'_{u, v} \ge 0 \end{aligned}\]这里需要注意的是 \(d\) 需要让 \(\sum_{(u, v)}d_{u, v} \times c_{u, v}\) 取到最小值。采用单纯形法解即可。
你问咋做矩阵？考虑在关联矩阵上刻画这些性质即可。由于单纯形法能求解的是最大值，因此求解 \(\sum w'_{i, j}\) 的最大值后用 \(\sum w_{i, j}\) 减就行了。
在关联矩阵上做限制条件是挺常见的 trick。
给出一个 \(n\) 个点 \(m\) 条边的有向图，每条边有边权 \(w_i\) 。有 \(Q\) 次询问，每次询问给出一个 \(k\) 。你可以把一条边修改成 \(w_i+a_i\) （\(a_i\) 不一定是整数），不过需要保证 \(a_i \geq 0\) 且 \(\sum a_i \leq k\) 。
你要通过修改边权使得从 \(1\) 到 \(n\) 的最短路径尽可能长，每次询问之间独立。数据保证至少存在一条从 \(1\) 到 \(n\) 的路径，无重边自环。输出答案和标准答案的相对误差或绝对误差应不超过 \(10^{-6}\) 。
\(2\le n \le 50,\ 1\le m\le n(n - 1),\ 1\le q\le 10^5\)。
考虑令 \(d_u\) 为差分情况下的最短路，即满足 \(d_u - d_1\) 为 \(1 \to u\) 的最短路长度。设 \(w_{u, v}\) 为 \(u\to v\) 的边的边权，\(x_{u, v}\) 为 \(u\to v\) 增加的边权。然后可以写出线性规划：
\[\begin{aligned} \max \quad & d_n - d_1 \\ \text{s.t.} \quad & d_v \le d_u + w_{u, v} + x_{u, v} \\ & \sum_{u, v} x_{u, v} \le k \\ & x_{u,v} \ge 0 \end{aligned}\]自然地，我们考虑构造限制矩阵。我们令 \(M\) 为对应图的关联矩阵，满足 \((u,v)\) 有一条边 \(i\) 则 \(M_{i,u} - 1, M_{i, v} + 1\)。令 \(\bm d\) 为差分最短路的向量，\(\bm x\) 为增加边权的向量，\(\bm w\) 为原边权的向量，然后可以构造出如下的限制：
\[\begin{aligned} \max \quad & (-1, 0, \dots, 0, 1, 0, \dots, 0) \left[\begin{aligned} \bm d \\ \bm x \end{aligned}\right] \\ \text{s.t.} \quad & \left[\begin{aligned} &M \ &- &I_m \\ &\bm 0 \ & &\bm 1 \end{aligned}\right] \left[\begin{aligned} \bm d \\ \bm x \end{aligned}\right] \le \left[\begin{aligned} &\bm w \\ & k \end{aligned}\right],\ \left[\begin{aligned} \bm d \\ \bm x \end{aligned}\right] \ge \bm 0 \end{aligned} \]设 \(\bm l = (-1, 0, \dots, 0, 1, 0, \dots, 0) ^{\mathsf T}\)。直接转对偶：
\[\begin{aligned} \min_{\bm y} \quad & \left[\bm w\quad k\right] \bm y \\ \text{s.t.} \quad & \left[\begin{aligned} &M^{\mathsf T} \ &&\bm 0 \\ - &I_m \ & &\bm 1 \end{aligned}\right] \bm y \ge \bm l,\bm y \ge \bm 0 \end{aligned} \]注意这里 \(\bm y\) 是个 \(m + 1\) 维的向量。根据互补松弛性取等。自然展开，设 \(y = [\bm \alpha \ \ \beta]\)，其中 \(\alpha_{u, v}\) 表示 \(u\to v\) 的边对应的变量。得到如下的线性规划：
\[\begin{aligned} \min_{\bm y} \quad & \sum_{(u, v)} w_{u,v} \alpha_{u,v} + \beta k \\ \text{s.t.} \quad & \forall 1<u<n, \ \sum_{v} \alpha_{u, v} - \sum_{v} \alpha_{v, u} = 0 \\ & \sum_{v} \sum_{v} \alpha_{v, 1} - \alpha_{1, v} = -1 \\ & \sum_{v} \sum_{v} \alpha_{v, n} - \alpha_{n, v} = 1 \\ & \beta \ge \alpha _{u, v} \end{aligned}\]若将 \(\alpha_{u, v}\) 看作流量，则流量上界均是 \(\beta\)。不妨令 \(\alpha_{u,v} \in [0, 1]\)，令单位流为 \(f = 1 / \beta\)，改写为
\[\begin{aligned} \min_{\bm y} \quad & \frac{\sum_{(u, v)} w_{u,v} \alpha_{u,v} + \beta k}f \\ \text{s.t.} \quad & \forall 1<u<n, \ \sum_{v} \alpha_{u, v} - \sum_{v} \alpha_{v, u} = 0 \\ & \sum_{v} \sum_{v} \alpha_{v, 1} - \alpha_{1, v} = -f \\ & \sum_{v} \sum_{v} \alpha_{v, n} - \alpha_{n, v} = f \\ & \alpha _{u, v} \in[0, 1] \end{aligned}\]由于答案对 \(f\) 单调，因此当 \(f\in [s, s + 1](s \in \mathbb Z)\) 时目标函数的最值肯定出现在边界，这时 \(\alpha_{u,v}\) 的值也是整数。
于是我们只需要直接建图跑网络流，对答案枚举取值后取 \(\max\) 即可。
总时间复杂度 \(O(\text{Dinic}(n, m) + qn)\)。
总的来说是一道好题。用关联矩阵将网络流语言转换成线性代数语言后就能显见地取对偶了，这点的直观性是配凑等方法所不具有的。什么时候写完代码交一发题解（
放一下 UOJ 板子的代码：
code
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
const int inf = 1e9;
const double eps = 1e-9;
int n, m, t;
namespace Simp {
// c_i = - r[0][i]
// a[i][j] = - r[i][j]
// b_i = r[i][0]
// MAX_VALUE = - r[0][0]
const int N = 1000;
double r[N][N];
int row[N];
void pivot(int out, int in) {
swap(row[out + n], row[in]);
double roi = - r[out][in];
rep(i,0,n) r[out][i] /= roi;
r[out][in] = -1 / roi;
rep(i,0,m) if (i != out) {
double rin = r[i][in];
if (abs(rin) <= eps) continue;
rep(j,0,n) {
if (j != in) r[i][j] += rin * r[out][j];
r[i][in] = r[out][in] * rin;
}
}
}
bool init() {
rep(i,1,n+m) row[i] = i;
while (1) {
int q = 1; // 找到最小的 b 相同最小所在行
double b_min = r[1][0];
rep(i,2,m) if (r[i][0] < b_min)
b_min = r[i][0], q = i;
if (b_min + eps >= 0) return true; // 所有 b \ge 0
int p = 0;
rep(i,1,n) if (r[q][i] > eps and (p == 0 or row[i] > row[p]))
p = i;
if (p == 0) break;
pivot(q, p);
} return false;
}
bool simp() {
while (1) {
int t = 1, k = 0; // 最小 t
rep(j,2,n) if (r[0][j] < r[0][t]) t = j;
if (r[0][t] >= - eps) return 1; // 最优解
double rati_min = 1e18;
rep(i,1,m) if (r[i][t] < - eps) {
double rati = - r[i][0] / r[i][t];
if (k == 0 or (rati < rati_min) or
(abs(rati - rati_min) <= eps and row[i] > row[k]))
rati_min = rati, k = i;
}
if (k == 0) break;
pivot(k, t);
}
return 0;
}
void Simplex() {
if (!init()) puts("Infeasible"), exit(0);
if (!simp()) puts("Unbounded"), exit(0);
}
int col[N];
void print_xi() {
rep(i,n+1,n+m) col[row[i]] = i;
rep(i,1,n) cout << (col[i] ? r[col[i] - n][0] : 0) << ' ';
cout << endl;
}
} // namespace Simplex Method
using namespace Simp;
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m >> t; cout << setprecision(12) << fixed;
rep(i,1,n) cin >> r[0][i], r[0][i] = -r[0][i];
rep(i,1,m) {
rep(j,1,n) cin >> r[i][j], r[i][j] = -r[i][j];
cin >> r[i][0];
}
Simplex();
cout << - r[0][0] << '\n';
if (t) print_xi();
}