基于线性规划的图最小费用流问题求解示例 题目描述 假设有一个有向图 \( G = (V, E) \)，每条边 \( (i, j) \in E \) 有容量 \( u_ {ij} \)（最大允许流量）和单位流量费用 \( c_ {ij} \)。每个节点 \( i \in V \) 有净需求 \( b_ i \)（若 \( b_ i > 0 \) 表示供应量，\( b_ i < 0 \) 表示需求量，且需满足 \( \sum_ i b_ i = 0 \)）。目标是找到一组边流量 \( x_ {ij} \)，在满足容量约束和流量平衡的前提下，最小化总费用。 问题建模 线性规划形式如下： \[ \min \sum_ {(i,j) \in E} c_ {ij} x_ {ij} \] 约束条件： 流量平衡 ：对每个节点 \( i \in V \)， \[ \sum_ {j: (i,j) \in E} x_ {ij} - \sum_ {j: (j,i) \in E} x_ {ji} = b_ i \] 容量约束 ：对每条边 \( (i,j) \in E \)， \[ 0 \leq x_ {ij} \leq u_ {ij} \] 解题步骤 构造初始可行解 若图包含供应节点（\( b_ i > 0 \)）和需求节点（\( b_ i < 0 \)），可通过添加虚拟源点 \( s \) 和汇点 \( t \) 转化为最大流问题，但本例直接使用单纯形法求解。 初始基可行解可通过“虚拟流”或“人工变量法”生成，但更高效的方法是设计一个初始可行流（如零流，若满足平衡约束）。 单纯形法迭代 对每条非基边，计算检验数 \( \bar{c} {ij} = c {ij} - \pi_ i + \pi_ j \)，其中 \( \pi \) 是对偶变量（节点势），通过解基变量的对偶方程得到。 若存在 \( \bar{c}_ {ij} < 0 \)，则沿边 \( (i,j) \) 增加流量可降低总费用。 确定进基边后，通过 圈算法 调整流量： 在残余图中找到包含进基边的增广圈，沿圈增加流量直至某边达容量上限或降为零流量。 更新基变量集合，调整节点势。 最优性检验 当所有非基边的检验数 \( \bar{c}_ {ij} \geq 0 \) 时，当前流为最优解。 实例演示 考虑简单网络： 节点：\( V = \{1, 2, 3\} \)，净需求 \( b = [ 2, -1, -1 ] \) 边： \( (1,2): c=2, u=3 \) \( (1,3): c=3, u=2 \) \( (2,3): c=1, u=2 \) 步骤1 ：初始基可行解选为 \( x_ {12} = 1, x_ {13} = 1, x_ {23} = 0 \)（满足流量平衡）。 步骤2 ：计算对偶变量 \( \pi \)： 令 \( \pi_ 1 = 0 \)，由基边 \( (1,2) \) 得 \( \pi_ 2 = \pi_ 1 - c_ {12} = -2 \)； 由基边 \( (1,3) \) 得 \( \pi_ 3 = \pi_ 1 - c_ {13} = -3 \)。 步骤3 ：检验非基边 \( (2,3) \) 的检验数： \[ \bar{c} {23} = c {23} - \pi_ 2 + \pi_ 3 = 1 - (-2) + (-3) = 0 \] 无负检验数，当前解已最优。 最优流量：\( x_ {12} = 1, x_ {13} = 1, x_ {23} = 0 \)，总费用 \( 1 \times 2 + 1 \times 3 = 5 \)。 关键点 节点势 \( \pi \) 通过基边关联的方程求解，类似最短路径中的距离更新。 圈算法确保流量调整后仍满足平衡约束，避免显式处理网络单纯形法的树结构。