基于线性规划的图最小顶点覆盖问题的分支定界法求解示例 我将为您讲解如何使用分支定界法求解图的最小顶点覆盖问题。这是一个经典的组合优化问题，我们可以通过线性规划松弛和分支定界技术来高效求解。 问题描述 给定一个无向图G=(V,E)，其中V是顶点集合，E是边集合。最小顶点覆盖问题是寻找一个最小的顶点子集C⊆V，使得图中的每条边至少有一个端点在C中。 数学模型 设决策变量x_ i表示顶点i是否被选入覆盖集： x_ i = 1 表示顶点i在覆盖集中 x_ i = 0 表示顶点i不在覆盖集中 整数规划模型为： minimize ∑x_ i subject to: x_ i + x_ j ≥ 1, ∀(i,j)∈E x_ i ∈ {0,1}, ∀i∈V 解题过程 步骤1：线性规划松弛 首先，我们将整数约束松弛为连续约束： minimize ∑x_ i subject to: x_ i + x_ j ≥ 1, ∀(i,j)∈E 0 ≤ x_ i ≤ 1, ∀i∈V 这个松弛问题可以用单纯形法快速求解。 步骤2：分支定界框架 我们构建一个搜索树，每个节点代表一个子问题： 根节点：原始松弛问题 分支操作：选择一个分数变量x_ k，创建两个子节点： 左子节点：添加约束x_ k = 0 右子节点：添加约束x_ k = 1 步骤3：界限计算 对于每个节点： 上界：当前找到的最好整数解的目标值 下界：当前节点的松弛问题最优值 步骤4：剪枝规则 界限剪枝：如果下界 ≥ 上界，剪枝 整数解剪枝：如果解是整数且优于当前上界，更新上界 不可行剪枝：如果子问题不可行，剪枝 详细求解示例 考虑一个简单图：顶点{1,2,3,4}，边{(1,2),(2,3),(3,4),(4,1)} 根节点（节点0） 松弛问题： min x1+x2+x3+x4 s.t. x1+x2 ≥ 1 x2+x3 ≥ 1 x3+x4 ≥ 1 x4+x1 ≥ 1 0 ≤ xi ≤ 1 最优解：x=(0.5,0.5,0.5,0.5)，目标值=2.0 下界=2.0，上界=∞ 第一次分支：选择x1 选择分数变量x1进行分支： 节点1（x1=0） 添加约束x1=0： x2 ≥ 1 (由x1+x2≥1) x4 ≥ 1 (由x4+x1≥1) x3 ≥ 0 (由其他约束) 最优解：x=(0,1,0,1)，目标值=2.0 这是一个整数解！更新上界=2.0 节点2（x1=1） 添加约束x1=1： x2 ≥ 0 (由x1+x2≥1) x4 ≥ 0 (由x4+x1≥1) x3 ≥ 1 (由x2+x3≥1和x3+x4≥1) 最优解：x=(1,0,1,0)，目标值=2.0 这也是一个整数解！上界保持2.0 步骤5：终止检查 所有节点都已处理，最优解为： 覆盖集{2,4}或{1,3} 最小覆盖大小为2 算法特点 分支策略：选择分数值最接近0.5的变量 界限更新：及时更新上界加速剪枝 预处理：度数为1的顶点可以优先处理 这个方法能够有效求解中等规模的最小顶点覆盖问题，比暴力枚举效率显著提高。