基于线性规划的“最小成本网络流”问题的建模、网络单纯形法求解与对偶经济解释示例
我将为您讲解一个经典的线性规划应用——“最小成本网络流”问题，并演示如何用网络单纯形法高效求解，同时结合对偶理论给出经济解释。
1. 问题描述
最小成本网络流（Minimum Cost Network Flow, MCNF） 是图论与线性规划交叉的核心问题。给定一个有向图 \(G = (V, E)\)，其中每条边 \((i,j) \in E\) 具有：
- 单位流量成本 \(c_{ij} \in \mathbb{R}\)（运输单位流量的费用）
- 容量上界 \(u_{ij} \geq 0\)（最大允许流量）
- 容量下界 \(l_{ij} \geq 0\)（最小必须流量，通常为0）
每个顶点 \(i \in V\) 有一个净需求量（净产出）\(b_i\)：
- 若 \(b_i > 0\)，表示供应点（源点），可提供 \(b_i\) 单位流量
- 若 \(b_i < 0\)，表示需求点（汇点），需要接收 \(|b_i|\) 单位流量
- 若 \(b_i = 0\)，表示中转点
目标：找到满足所有顶点净需求和边容量限制的可行流，使总运输成本最小。
实例：考虑一个小型供应网络（如下图）：
- 顶点：1（工厂），2（仓库），3（客户A），4（客户B）
- 边与参数：
- (1,2)：成本2，容量10，下界0
- (1,3)：成本4，容量5，下界0
- (2,3)：成本1，容量8，下界0
- (2,4)：成本3，容量7，下界0
- (3,4)：成本2，容量4，下界0
- 净需求：\(b_1 = 8\)（供应8单位），\(b_3 = -3\)，\(b_4 = -5\)，\(b_2 = 0\)（中转）。
(2,10)
1 ------> 2
| \ | \
(4,5)| \ |(3,7)
| \ | \
v v v v
3<---- 4
(1,8) (2,4)
2. 线性规划建模
决策变量：\(x_{ij}\) 表示边 \((i,j)\) 上的流量。
目标函数：最小化总成本
\[\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 \]
（流出减流入等于净供应/需求）
2. 容量限制（对每条边 \((i,j)\)）：
\[ l_{ij} \leq x_{ij} \leq u_{ij} \]
代入实例数据：
\[\begin{aligned} \min \quad & 2x_{12} + 4x_{13} + 1x_{23} + 3x_{24} + 2x_{34} \\ \text{s.t.} \quad & x_{12} + x_{13} = 8 \quad &\text{(顶点1)} \\ & -x_{12} + x_{23} + x_{24} = 0 \quad &\text{(顶点2)} \\ & -x_{13} - x_{23} + x_{34} = -3 \quad &\text{(顶点3)} \\ & -x_{24} - x_{34} = -5 \quad &\text{(顶点4)} \\ & 0 \leq x_{12} \leq 10,\; 0 \leq x_{13} \leq 5,\; 0 \leq x_{23} \leq 8,\; 0 \leq x_{24} \leq 7,\; 0 \leq x_{34} \leq 4 \end{aligned} \]
注意：四个顶点方程线性相关（和为0），可去掉一个（如顶点4）以消除冗余。
3. 网络单纯形法求解步骤
网络单纯形法是单纯形法的特化，直接在图上操作，高效且直观。
步骤1：构造初始生成树结构
- 在图中添加人工边（零成本、大容量）或找一棵生成树支撑流。
- 实例中，我们取生成树 \(T = \{ (1,2), (1,3), (3,4) \}\)（虚线边为非树边）：
- 树边流量 \(x_{12}, x_{13}, x_{34}\) 为基变量
- 非树边 \(x_{23}, x_{24}\) 为非基变量（初始设为下界0）
步骤2：计算树边流量（满足流量守恒）
在生成树中，流量可由顶点需求唯一确定：
- 从叶子开始：顶点4需求-5，由 \(x_{34}\) 满足 ⇒ \(x_{34} = 5\)（但容量为4，超出！需调整树或初始解）
实际上，发现初始树不可行（需求无法满足）。改用另一种方法：从可行解开始，如设 \(x_{12}=5, x_{13}=3, x_{23}=0, x_{24}=5, x_{34}=0\) 是可行的（验证：顶点1流出8，顶点3流入3，顶点4流入5，顶点2平衡）。
对应生成树可取 \(T = \{ (1,2), (2,4), (1,3) \}\)，非树边 \((2,3), (3,4)\) 置为下界0。
步骤3：计算顶点势（对偶变量）
对每个顶点 \(i\) 引入势 \(\pi_i\)（对应流量守恒约束的对偶变量），满足树边 \((i,j)\) 的简约成本为零：
\[\bar{c}_{ij} = c_{ij} - \pi_i + \pi_j = 0 \quad \forall (i,j) \in T \]
任选一个顶点势为参考点（如设 \(\pi_1 = 0\)），然后解出其他：
- 对 \((1,2) \in T\)：\(2 - 0 + \pi_2 = 0\) ⇒ \(\pi_2 = -2\)
- 对 \((1,3) \in T\)：\(4 - 0 + \pi_3 = 0\) ⇒ \(\pi_3 = -4\)
- 对 \((2,4) \in T\)：\(3 - (-2) + \pi_4 = 0\) ⇒ \(\pi_4 = -5\)
步骤4：检查非树边的最优性条件
计算非树边 \((i,j)\) 的简约成本：
- \(\bar{c}_{23} = c_{23} - \pi_2 + \pi_3 = 1 - (-2) + (-4) = -1\)
- \(\bar{c}_{34} = c_{34} - \pi_3 + \pi_4 = 2 - (-4) + (-5) = 1\)
最优条件：对最小化问题，若所有非树边 \(\bar{c}_{ij} \geq 0\) 则最优。这里 \(\bar{c}_{23} = -1 < 0\)，故边 \((2,3)\) 可进基以降低成本。
步骤5：确定进基边与调整流量
- 进基边：\(e_{\text{in}} = (2,3)\)，其简约成本为负。
- 在生成树 \(T\) 中加入 \((2,3)\) 会形成一个圈：2 → 3 → 1 → 2（路径：2→3是新边，3→1是树边反向，1→2是树边）。
- 沿圈调整流量：在圈上，正向边（与进基边方向一致）增加流量 \(\theta\)，反向边减少 \(\theta\)，同时保持流量守恒。
圈边方向：\((2,3)^+\), \((3,1)^-\)（对应 \((1,3)\) 反向），\((1,2)^-\)。 - 确定 \(\theta\) 上限：
- 正向边不能超过上界：\(x_{23} + \theta \leq 8\)（上界8，当前0）⇒ \(\theta \leq 8\)
- 反向边不能低于下界：\(x_{13} - \theta \geq 0\)（当前3）⇒ \(\theta \leq 3\)；\(x_{12} - \theta \geq 0\)（当前5）⇒ \(\theta \leq 5\)
- 取最小值 \(\theta^* = 3\)（由 \(x_{13}\) 限制）。
- 更新圈上流量：
- \(x_{23} = 0 + 3 = 3\)
- \(x_{13} = 3 - 3 = 0\)
- \(x_{12} = 5 - 3 = 2\)
- 出基边：流量变为下界的边 \((1,3)\)（流量变为0）离开基。
步骤6：更新生成树与迭代
新生成树 \(T' = \{ (1,2), (2,4), (2,3) \}\)，非树边 \((1,3), (3,4)\)。
重新计算顶点势（仍设 \(\pi_1=0\)）：
- \((1,2)\)：\(2 - 0 + \pi_2 = 0\) ⇒ \(\pi_2 = -2\)
- \((2,4)\)：\(3 - (-2) + \pi_4 = 0\) ⇒ \(\pi_4 = -5\)
- \((2,3)\)：\(1 - (-2) + \pi_3 = 0\) ⇒ \(\pi_3 = -3\)
计算非树边简约成本： - \(\bar{c}_{13} = 4 - 0 + (-3) = 1 \geq 0\)
- \(\bar{c}_{34} = 2 - (-3) + (-5) = 0 \geq 0\)
所有非树边简约成本非负，达到最优。
最优解：
\[x_{12}^* = 2, \quad x_{13}^* = 0, \quad x_{23}^* = 3, \quad x_{24}^* = 5, \quad x_{34}^* = 0 \]
总成本：\(2 \times 2 + 4 \times 0 + 1 \times 3 + 3 \times 5 + 2 \times 0 = 4+0+3+15=22\)
4. 对偶问题与经济解释
原问题的对偶变量为顶点势 \(\pi_i\) 和边上的冗余变量。对偶问题：
\[\max \sum_{i \in V} b_i \pi_i - \sum_{(i,j) \in E} u_{ij} w_{ij} + \sum_{(i,j) \in E} l_{ij} v_{ij} \]
\[ \text{s.t.} \quad \pi_i - \pi_j - w_{ij} + v_{ij} \leq c_{ij}, \quad w_{ij}, v_{ij} \geq 0 \]
其中 \(w_{ij}, v_{ij}\) 对应容量上下界的对偶变量。
经济解释：
- \(\pi_i\) 可理解为顶点 \(i\) 的影子价格（即在该点增加一单位供应的边际成本减少量）。
- 实例中最优势：\(\pi_1=0, \pi_2=-2, \pi_3=-3, \pi_4=-5\)。
- 从工厂（顶点1）发货成本基准为0。
- 客户A（顶点3）的影子价格-3，意味着若其需求增加1单位，总成本将增加3（因为 \(\pi_3 - \pi_1 = -3\)，实际增加 \(|\pi_3| = 3\)）。
- 客户B（顶点4）更“贵”（-5），因其需求需经更贵路径满足。
- 简约成本 \(\bar{c}_{ij} = c_{ij} - \pi_i + \pi_j\) 表示通过边 \((i,j)\) 运输的净成本减去两端影子价格差。最优时，对非树边 \(\bar{c}_{ij} \geq 0\) 意味着使用该边不会更省（树边正好平衡）。
5. 核心要点总结
- 网络单纯形法优势：利用图结构，迭代在生成树上进行，避免普通单纯形法的大矩阵运算，复杂度更低。
- 最优性判定：所有非树边简约成本非负（最小化问题）。
- 经济意义：顶点势提供资源定价，指导网络资源配置。
此问题广泛用于物流、通信、电力调度等领域，是网络优化和线性规划结合的经典范例。