基于线性规划的图最小环覆盖问题求解示例 题目描述 考虑一个带权有向图 \( G = (V, E) \)，其中每条边 \( (i, j) \in E \) 有一个非负权重 \( w_ {ij} \)，表示从顶点 \( i \) 到顶点 \( j \) 的成本。最小环覆盖问题的目标是选择一组边，使得每个顶点被恰好一个环覆盖（即每个顶点的入度和出度均为1），且所有边的总权重最小。该问题可转化为指派问题，用线性规划建模求解。 解题过程 1. 问题建模 定义决策变量 \( x_ {ij} \in \{0, 1\} \)：当边 \( (i, j) \) 被选中时取1，否则取0。 目标函数：最小化总成本 \( \min \sum_ {(i,j) \in E} w_ {ij} x_ {ij} \)。 约束条件： 每个顶点的出度为1：\( \sum_ {j: (i,j) \in E} x_ {ij} = 1, \quad \forall i \in V \)。 每个顶点的入度为1：\( \sum_ {i: (i,j) \in E} x_ {ij} = 1, \quad \forall j \in V \)。 整数约束：\( x_ {ij} \in \{0, 1\} \)。 该模型是一个整数线性规划（ILP），但若忽略整数约束，其线性规划松弛的最优解恰好是整数解（因为约束矩阵是全单模矩阵），因此可直接用线性规划求解。 2. 线性规划松弛 将整数约束松弛为连续约束： \[ \min \sum_ {(i,j) \in E} w_ {ij} x_ {ij} \] \[ \text{s.t.} \quad \sum_ {j} x_ {ij} = 1, \ \forall i; \quad \sum_ {i} x_ {ij} = 1, \ \forall j; \quad x_ {ij} \geq 0. \] 由于约束矩阵是全单模的，线性规划的最优解自动满足 \( x_ {ij} \in \{0,1\} \)。 3. 实例演示 假设有4个顶点的完全有向图，权重矩阵如下（无穷大表示边不存在，但此处为完全图，权重为实际值）： \[ W = \begin{bmatrix} 0 & 2 & 3 & 1 \\ 4 & 0 & 1 & 2 \\ 3 & 5 & 0 & 4 \\ 2 & 1 & 3 & 0 \end{bmatrix} \] 变量 \( x_ {ij} \) 对应权重 \( w_ {ij} \)。 目标函数： \[ \min 0x_ {11} + 2x_ {12} + 3x_ {13} + 1x_ {14} + 4x_ {21} + 0x_ {22} + 1x_ {23} + 2x_ {24} + 3x_ {31} + 5x_ {32} + 0x_ {33} + 4x_ {34} + 2x_ {41} + 1x_ {42} + 3x_ {43} + 0x_ {44} \] 约束条件（以顶点1为例）： 出度：\( x_ {11} + x_ {12} + x_ {13} + x_ {14} = 1 \)。 入度：\( x_ {11} + x_ {21} + x_ {31} + x_ {41} = 1 \)。 （其他顶点类似。） 4. 求解与结果分析 使用单纯形法求解线性规划，得到最优解： \[ x_ {14} = 1, \ x_ {23} = 1, \ x_ {31} = 1, \ x_ {42} = 1, \ \text{其他为} 0。 \] 总成本：\( 1 + 1 + 3 + 1 = 6 \)。 环覆盖： 顶点1 → 顶点4 → 顶点2 → 顶点3 → 顶点1（实际为两个环：1→4→2→3→1？需验证）。 检查： 1→4, 4→2, 2→3, 3→1 形成一个环：1→4→2→3→1。 因此是单个环覆盖所有顶点。 5. 验证与讨论 全单模性保证了解的最优性。 若图非完全图，缺失的边对应权重设为无穷大（实际建模中用大数M代替），线性规划仍适用。 该方法的时间复杂度依赖于线性规划求解器（如单纯形法），在实际图中效率较高。