基于线性规划的图最小控制集问题的对偶方法求解示例 我将通过一个具体示例来讲解如何使用线性规划的对偶方法求解图的最小控制集问题。 问题描述 给定无向图G=(V,E)，最小控制集问题是寻找最小的顶点子集D⊆V，使得图中每个顶点要么在D中，要么至少与D中的一个顶点相邻。 考虑图G有4个顶点：V={1,2,3,4}，边集E={(1,2),(2,3),(3,4),(4,1)}，即一个4个顶点的环。 线性规划建模 原始问题 对于每个顶点i，引入0-1变量x_ i，表示顶点i是否在控制集中。 目标函数：minimize ∑x_ i (i=1 to 4) 约束条件：对于每个顶点i，x_ i + ∑x_ j ≥ 1，其中j是i的邻居 具体约束： 顶点1：x₁ + x₂ + x₄ ≥ 1 顶点2：x₂ + x₁ + x₃ ≥ 1 顶点3：x₃ + x₂ + x₄ ≥ 1 顶点4：x₄ + x₃ + x₁ ≥ 1 0 ≤ x_ i ≤ 1 对偶问题推导 构造对偶问题 对每个约束引入对偶变量y_ i ≥ 0 对偶问题： maximize ∑y_ i (i=1 to 4) 约束条件： y₁ + y₂ + y₄ ≤ 1 y₂ + y₁ + y₃ ≤ 1 y₃ + y₂ + y₄ ≤ 1 y₄ + y₃ + y₁ ≤ 1 y_ i ≥ 0 求解过程 步骤1：分析对偶约束 观察对偶约束的结构，发现每个约束都是三个对偶变量之和不超过1。 由于图是对称的，可以假设最优解具有对称性：y₁=y₂=y₃=y₄=t 步骤2：代入对称假设 将对称假设代入约束： 3t ≤ 1 ⇒ t ≤ 1/3 目标函数：4t ≤ 4/3 步骤3：寻找最优解 当t=1/3时，目标函数值为4/3，达到上界。 因此对偶问题的最优值OPT_ dual = 4/3 步骤4：利用对偶性 根据线性规划强对偶定理，原始问题最优值等于对偶问题最优值：OPT_ primal = 4/3 由于原始问题是0-1整数规划，最优解必须是整数，因此最小控制集的大小至少为⌈4/3⌉=2 原始问题求解验证 步骤5：寻找原始可行解 考虑控制集D={1,3}： 顶点1∈D，满足条件 顶点2与顶点1相邻，满足条件 顶点3∈D，满足条件 顶点4与顶点3相邻，满足条件 目标函数值=2 步骤6：验证最优性 由于2 > 4/3，且2是最接近4/3的整数，因此D={1,3}是最优解。 实际上，对于4个顶点的环，任何两个不相邻的顶点都构成最小控制集。 方法推广 这种对偶方法的一般步骤： 将最小控制集问题建模为整数线性规划 松弛为线性规划并构造对偶问题 求解对偶问题获得原问题最优值的下界 利用对偶信息指导寻找原始可行解 通过原始-对偶间隙验证解的质量 该方法的关键优势在于对偶问题提供了原问题最优值的紧下界，为寻找高质量的解提供了理论保证。