基于线性规划的图最大权匹配问题求解示例
题目描述
考虑一个无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集合，\(E\) 是边集合。每条边 \(e \in E\) 有一个权重 \(w_e\)。图的一个匹配是指一组边，其中任意两条边没有公共顶点。最大权匹配问题是寻找一个匹配，使得匹配中所有边的权重之和最大。该问题可以建模为线性规划问题，并通过单纯形法求解。
解题过程
- 问题建模
定义决策变量 \(x_e\) 表示边 \(e\) 是否被选入匹配（1 表示选中，0 表示未选中）。目标函数是最大化匹配的总权重：
\[ \max \sum_{e \in E} w_e x_e \]
约束条件确保每个顶点最多被一条边覆盖（即匹配的定义）：
\[ \sum_{e \in \delta(v)} x_e \leq 1, \quad \forall v \in V \]
其中 \(\delta(v)\) 表示与顶点 \(v\) 相连的边集合。此外，\(x_e \geq 0\)。由于约束矩阵是全单模的，线性规划的最优解自动为整数解（0 或 1），因此无需显式添加整数约束。
-
实例构造
假设图有 4 个顶点 \(V = \{1, 2, 3, 4\}\)，边集 \(E = \{(1,2), (1,3), (2,4), (3,4)\}\)，权重分别为 \(w_{12} = 3, w_{13} = 2, w_{24} = 1, w_{34} = 4\)。 -
线性规划标准化
将模型转化为标准形式（最大化目标，约束为等式）：- 引入松弛变量 \(s_v \geq 0\) 将每个顶点约束转为等式：
\[ \sum_{e \in \delta(v)} x_e + s_v = 1, \quad \forall v \in V \]
- 目标函数和变量非负性不变。
- 单纯形法求解
- 初始基可行解：选择松弛变量 \(s_1, s_2, s_3, s_4\) 为基变量，此时 \(x_e = 0\)，匹配为空，目标值为 0。
- 迭代 1：计算检验数 \(\sigma_e = w_e - \sum_{v \in e} \pi_v\)，其中 \(\pi_v\) 是顶点约束的对偶变量（初始为 0）。所有 \(\sigma_e = w_e > 0\)，选择最大检验数的边 \(e = (3,4)\)（\(\sigma_{34} = 4\)）入基。
最小比值测试：约束中顶点 3 和 4 的当前基变量值为 1，比值均为 1，任选顶点 3 的松弛变量 \(s_3\) 出基。更新基后，\(x_{34} = 1\)，顶点 3 和 4 被覆盖，其松弛变量为 0。 - 迭代 2：更新对偶变量 \(\pi_3 = \pi_4 = 4\)，重新计算剩余边的检验数：
\[ \sigma_{12} = 3 - (\pi_1 + \pi_2) = 3 - (0 + 0) = 3, \quad \sigma_{13} = 2 - (0 + 4) = -2, \quad \sigma_{24} = 1 - (0 + 4) = -3 \]
只有 $ \sigma_{12} > 0 $，边 $ (1,2) $ 入基。最小比值测试：顶点 1 和 2 的松弛变量值为 1，比值均为 1，任选 $ s_1 $ 出基。更新后 $ x_{12} = 1 $，匹配为 $ \{(1,2), (3,4)\} $。
- 迭代 3：更新对偶变量后，所有非基变量检验数非正（例如 \(\sigma_{13} = 2 - (3 + 4) = -5\)），达到最优解。
- 结果分析
最优匹配为边集 \(\{(1,2), (3,4)\}\)，总权重 \(3 + 4 = 7\)。验证可知不存在权重更大的匹配（如选 \((1,3)\) 和 \((2,4)\) 权重为 3，小于 7）。
关键点
- 全单模性保证线性规划解为整数，避免了整数规划复杂度。
- 单纯形法通过检验数选择入基边，逐步优化匹配权重。