基于线性规划的图最大二分匹配问题的原始-对偶近似算法求解示例
我将为您讲解线性规划在图论中的一个经典应用——最大二分匹配问题，并介绍如何设计一个原始-对偶近似算法来求解它。我会从问题描述开始，逐步展开建模、算法设计、分析，确保每一步都清晰易懂。
第一步：问题描述与定义
问题背景
- 我们有一个二分图 \(G = (U, V, E)\)，其中 \(U\) 和 \(V\) 是互不相交的顶点集，\(E\) 是连接 \(U\) 和 \(V\) 的边集。
- 一个匹配是边集的一个子集，其中任意两条边不共享公共顶点。
- 目标：找到包含最多边的匹配，即最大基数匹配（最大匹配）。
例如：
- \(U\) 表示任务集合，\(V\) 表示工人集合，边表示工人能执行的任务。
- 最大匹配表示能同时进行的最大任务数。
第二步：整数规划建模
我们将最大二分匹配问题建模为一个整数线性规划（ILP）：
- 为每条边 \(e \in E\) 引入变量 \(x_e\)：
- \(x_e = 1\) 表示边 \(e\) 在匹配中，
- \(x_e = 0\) 表示不在匹配中。
约束条件：每个顶点最多与一条匹配边相连：
\[\sum_{e \in \delta(u)} x_e \leq 1, \quad \forall u \in U \]
\[ \sum_{e \in \delta(v)} x_e \leq 1, \quad \forall v \in V \]
其中 \(\delta(u)\) 表示与顶点 \(u\) 关联的边集。
目标：最大化匹配边数：
\[\text{最大化} \quad \sum_{e \in E} x_e \]
\[ \text{约束：} \quad x_e \in \{0,1\}, \quad \forall e \in E \]
第三步：线性规划松弛与对偶
线性规划松弛（LP松弛）：
将整数约束 \(x_e \in \{0,1\}\) 放宽为 \(0 \leq x_e \leq 1\)：
\[\text{(P)} \quad \max \sum_{e \in E} x_e \]
\[ \sum_{e \in \delta(u)} x_e \leq 1, \quad \forall u \in U \]
\[ \sum_{e \in \delta(v)} x_e \leq 1, \quad \forall v \in V \]
\[ x_e \geq 0, \quad \forall e \in E \]
（注意：上界 \(x_e \leq 1\) 已隐含在顶点约束中，可不显式写出。）
对偶线性规划（Dual）：
为每个顶点约束引入对偶变量 \(y_u\)（\(u \in U\)）和 \(y_v\)（\(v \in V\)）：
\[\text{(D)} \quad \min \sum_{u \in U} y_u + \sum_{v \in V} y_v \]
\[ y_u + y_v \geq 1, \quad \forall e = (u,v) \in E \]
\[ y_u, y_v \geq 0, \quad \forall u \in U, v \in V \]
对偶的直观意义：
- \(y_u\) 和 \(y_v\) 可视为顶点“价格”或“权重”。
- 每条边的两端点权重之和至少为1。
- 目标是使总权重最小。
第四步：原始-对偶算法设计思路
原始-对偶方法的核心思想：
- 同时维护原始可行解（匹配边集合）和对偶可行解（顶点权重）。
- 通过互补松弛条件指导算法的迭代过程。
互补松弛条件（针对松弛后的LP）：
- 原始条件：若边 \(e = (u,v)\) 被选入匹配（\(x_e > 0\)），则必须有 \(y_u + y_v = 1\)。
- 对偶条件：若顶点 \(u\) 的对偶变量 \(y_u > 0\)，则与 \(u\) 关联的匹配边数必须达到上限（即 \(\sum_{e \in \delta(u)} x_e = 1\)）。
算法将尝试构造满足这些条件的解。
第五步：原始-对偶近似算法步骤
该算法实际上是精确算法（因为最大二分匹配的LP松弛具有整数最优解），但其设计框架体现了原始-对偶思想。步骤如下：
-
初始化：
- 匹配 \(M = \emptyset\)。
- 对偶变量 \(y_u = y_v = 0\)（未满足对偶约束）。
-
迭代过程：
-
阶段1：增加对偶变量（“涨价”）：
- 找到所有未匹配顶点（在 \(U\) 中）组成的集合 \(U'\)。
- 同时增加所有 \(u \in U'\) 的 \(y_u\) 和所有 \(v \in V\)（与 \(U'\) 中顶点相邻）的 \(y_v\)，直到对某些边 \(e = (u,v)\) 有 \(y_u + y_v = 1\)。
- 这些边变为紧边（即满足对偶约束为等式）。
-
阶段2：增广匹配：
- 在紧边构成的子图中寻找增广路径（交替经过匹配边和非匹配边，起点和终点均为未匹配顶点）。
- 若找到增广路径，则沿路径反转匹配状态，从而增加匹配大小。
- 更新未匹配顶点集合。
-
重复直到 \(U\) 中无未匹配顶点，或无法再增广。
-
-
终止：
- 输出匹配 \(M\)。
- 同时得到对偶解 \(y\)。
第六步：算法演示（小例子）
考虑二分图：
- \(U = \{u1, u2\}\), \(V = \{v1, v2\}\)
- 边：\((u1,v1), (u1,v2), (u2,v1)\)
执行过程：
- 初始：\(M = \emptyset\), \(y = 0\)。
- 第一次迭代：
- 未匹配顶点：\(U' = \{u1, u2\}\)。
- 增加 \(y_{u1}, y_{u2}\) 和相邻的 \(y_{v1}, y_{v2}\) 直到 \(y_{u1} + y_{v1} = 1\)（假设边 \((u1,v1)\) 首先变紧）。
- 此时 \(y_{u1}=y_{v1}=0.5, y_{u2}=y_{v2}=0.5\)。
- 紧边：\((u1,v1), (u1,v2), (u2,v1)\)。
- 找到增广路径 \(u1-v1\)，将 \((u1,v1)\) 加入 \(M\)。
- 第二次迭代：
- 未匹配顶点：\(U' = \{u2\}\)。
- 增加 \(y_{u2}\) 和相邻的 \(y_{v1}\)（注意 \(v1\) 已匹配，但仍可参与对偶变量更新）。
- 当 \(y_{u2} + y_{v1} = 1\) 时（从0.5+0.5开始增加，实际已满足），边 \((u2,v1)\) 为紧边。
- 但 \(v1\) 已匹配给 \(u1\)，因此尝试交替路径 \(u2-v1-u1-v2\)：
- 发现 \(v2\) 未匹配，路径 \(u2-v1-u1-v2\) 是增广路径。
- 反转匹配：移除 \((u1,v1)\)，加入 \((u2,v1)\) 和 \((u1,v2)\)。
- 最终匹配 \(M = \{(u1,v2), (u2,v1)\}\)，大小2（最大匹配）。
对偶解：\(y_{u1}=0.5, y_{u2}=0.5, y_{v1}=0.5, y_{v2}=0.5\)，目标和 \(= 2\)，等于原始目标值。
第七步：算法分析与结论
- 正确性：该算法本质上是匈牙利算法的原始-对偶解释，总能找到最大匹配。
- 最优性保证：根据线性规划的强对偶定理，原始最优解（最大匹配）等于对偶最优解（最小顶点权重和）。算法构造的原始解 \(M\) 和对偶解 \(y\) 满足互补松弛条件，因此均为最优。
- 时间复杂度：与匈牙利算法相同，为 \(O(|V| \cdot |E|)\)。
关键启示：
- 原始-对偶方法将组合优化问题转化为通过对偶变量调整来逐步改进原始解。
- 对于最大二分匹配，LP松弛具有整数最优解，因此原始-对偶算法能得到精确最优解。
- 该方法可扩展至更一般问题（如加权匹配、覆盖问题），但可能变为近似算法。
总结
通过以上步骤，我们：
- 将最大二分匹配建模为整数线性规划。
- 构造其LP松弛及对偶。
- 设计了基于互补松弛条件的原始-对偶算法。
- 通过实例演示了算法过程。
- 分析了算法的最优性和复杂度。
该示例展示了线性规划对偶理论如何指导设计高效组合优化算法，是原始-对偶方法的经典案例。