基于线性规划的图最小顶点覆盖问题的对偶方法求解示例

我将为您详细讲解如何使用线性规划的对偶方法求解图的最小顶点覆盖问题。让我们从问题描述开始，逐步深入解题过程。

问题描述

考虑一个无向图 G = (V, E)，其中：

• V = {1, 2, 3, 4} 是顶点集合
• E = {(1,2), (1,3), (2,3), (2,4), (3,4)} 是边集合

每个顶点 i 有一个权重 w_i = 1（即所有顶点权重相等）。

最小顶点覆盖问题要求找到一个顶点子集 S ⊆ V，使得图中的每条边至少有一个端点在 S 中，并且 S 中顶点的总权重最小。

线性规划建模

原始问题建模

对于每个顶点 i，引入二进制变量 x_i：

• x_i = 1 表示顶点 i 被选入覆盖集
• x_i = 0 表示顶点 i 未被选入覆盖集

最小顶点覆盖问题的整数规划模型为：

最小化：x₁ + x₂ + x₃ + x₄
约束条件：
x₁ + x₂ ≥ 1  (边(1,2))
x₁ + x₃ ≥ 1  (边(1,3))
x₂ + x₃ ≥ 1  (边(2,3))
x₂ + x₄ ≥ 1  (边(2,4))
x₃ + x₄ ≥ 1  (边(3,4))
x₁, x₂, x₃, x₄ ∈ {0, 1}

线性规划松弛

将整数约束松弛为连续约束：

最小化：x₁ + x₂ + x₃ + x₄
约束条件：
x₁ + x₂ ≥ 1
x₁ + x₃ ≥ 1
x₂ + x₃ ≥ 1
x₂ + x₄ ≥ 1
x₃ + x₄ ≥ 1
x₁, x₂, x₃, x₄ ≥ 0

对偶问题推导

构造对偶问题

根据线性规划对偶理论，原始问题的对偶问题构造如下：

对于每个原始约束，引入对偶变量 y_e（对应每条边 e）：

• y₁₂, y₁₃, y₂₃, y₂₄, y₃₄

对偶问题为：

最大化：y₁₂ + y₁₃ + y₂₃ + y₂₄ + y₃₄
约束条件：
y₁₂ + y₁₃ ≤ 1  (顶点1的约束)
y₁₂ + y₂₃ + y₂₄ ≤ 1  (顶点2的约束)
y₁₃ + y₂₃ + y₃₄ ≤ 1  (顶点3的约束)
y₂₄ + y₃₄ ≤ 1  (顶点4的约束)
y₁₂, y₁₃, y₂₃, y₂₄, y₃₄ ≥ 0

对偶问题求解

问题分析

对偶问题实际上是求图的最大匹配问题。我们需要找到边集的一个子集 M ⊆ E，使得：

1. 没有两条边共享公共顶点
2. 子集的大小最大化

求解过程

观察图 G = (V, E)，其中 V = {1,2,3,4}，E = {(1,2), (1,3), (2,3), (2,4), (3,4)}

步骤1：寻找最大匹配

• 选择边 (1,2)，顶点1和2被覆盖
• 剩余未覆盖顶点：3,4
• 选择边 (3,4)，顶点3和4被覆盖
• 得到匹配 M = {(1,2), (3,4)}

步骤2：验证匹配的最大性

• 图中最多只能有2条不相交的边（因为图有4个顶点）
• 当前匹配包含2条边，因此是最大匹配

步骤3：构造对偶解
令 y_e = 1 当 e ∈ M，否则 y_e = 0
即：y₁₂ = 1, y₁₃ = 0, y₂₃ = 0, y₂₄ = 0, y₃₄ = 1

验证可行性：

• 顶点1：y₁₂ + y₁₃ = 1 + 0 = 1 ≤ 1 ✓
• 顶点2：y₁₂ + y₂₃ + y₂₄ = 1 + 0 + 0 = 1 ≤ 1 ✓
• 顶点3：y₁₃ + y₂₃ + y₃₄ = 0 + 0 + 1 = 1 ≤ 1 ✓
• 顶点4：y₂₄ + y₃₄ = 0 + 1 = 1 ≤ 1 ✓

目标函数值：y₁₂ + y₁₃ + y₂₃ + y₂₄ + y₃₄ = 1 + 0 + 0 + 0 + 1 = 2

原始问题求解

利用对偶解求原始解

根据互补松弛条件：

• 如果 y_e > 0，则对应的原始约束取等号
• 如果 x_i > 0，则对应的对偶约束取等号

在我们的解中：

• y₁₂ = 1 > 0 ⇒ x₁ + x₂ = 1
• y₃₄ = 1 > 0 ⇒ x₃ + x₄ = 1

同时，由于对偶约束都是紧的（都取等号），我们有：
x₁ + x₂ = 1, x₁ + x₃ = 1, x₂ + x₃ = 1, x₂ + x₄ = 1, x₃ + x₄ = 1

解这个方程组，得到多个可行解，如：

• x₁ = 0, x₂ = 1, x₃ = 1, x₄ = 0（顶点2和3被选中）
• x₁ = 1, x₂ = 0, x₃ = 1, x₄ = 0（顶点1和3被选中）
• x₁ = 0, x₂ = 1, x₃ = 0, x₄ = 1（顶点2和4被选中）

验证最优性

原始目标函数值：x₁ + x₂ + x₃ + x₄ = 2
对偶目标函数值：y₁₂ + y₁₃ + y₂₃ + y₂₄ + y₃₄ = 2

根据强对偶定理，原始问题和对偶问题的最优值相同，因此我们找到了最优解。

结果分析

最小顶点覆盖的大小为2，对应的覆盖集可以是：

• {2,3}：覆盖边(1,2),(1,3),(2,3),(2,4),(3,4)
• {1,3}：覆盖边(1,2),(1,3),(2,3),(3,4)
• {2,4}：覆盖边(1,2),(2,3),(2,4),(3,4)

这个结果验证了König定理：在二分图中，最小顶点覆盖的大小等于最大匹配的大小。虽然我们的图不是二分图，但在这种情况下结论仍然成立。

方法总结

这种对偶方法的核心思想是：

1. 将最小顶点覆盖问题建模为整数规划
2. 松弛为线性规划
3. 构造对偶问题（即最大匹配问题）
4. 求解对偶问题获得边界
5. 利用互补松弛条件恢复原始问题的最优解

这种方法在理论上有重要意义，揭示了组合优化问题之间的深刻联系。