基于线性规划的图最大流问题的最小化最大边负载的公平分配模型求解示例
我将为您讲解一个基于线性规划的、在图最大流问题基础上考虑公平性约束的扩展模型。这个模型不仅要求从源点到汇点输送尽可能多的流（最大流），还希望流量在路径上分配时，尽量均衡地使用各条边，避免某些边负载过高而其他边空闲。这在实际网络（如交通、通信）中很有意义，可以防止拥塞、提高鲁棒性。
问题描述
给定一个有向图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集。每条边 \(e \in E\) 有一个非负容量 \(c_e\)。指定一个源点 \(s \in V\) 和一个汇点 \(t \in V\)。目标是在满足以下条件的前提下，找到从 \(s\) 到 \(t\) 的一个流：
- （容量约束）每条边 \(e\) 上的流量 \(f_e\) 不超过其容量 \(c_e\)。
- （流量守恒）对于除 \(s\) 和 \(t\) 外的每个顶点 \(v\)，流入 \(v\) 的总流量等于流出 \(v\) 的总流量。
- （最大流目标）从 \(s\) 流出的总流量（即流值）尽可能大。
- （公平性目标）在所有满足上述条件的最大流中，我们希望最小化 最大边负载率。边 \(e\) 的负载率定义为 \(f_e / c_e\)（当 \(c_e > 0\) 时）。最小化最大负载率意味着让流量尽可能均匀地分布在边上，避免出现某些边接近满容量而其他边利用率很低的情况。
这本质上是一个 两阶段优化问题：首先最大化流值 \(F\)，然后在所有能达到该最大流值 \(F\) 的流中，最小化最大的边负载率。我们可以将其建模为一个 单目标线性规划，其中最大流值 \(F\) 将作为一个变量出现，但最终目标是最小化最大负载率。
线性规划模型构建
1. 决策变量
- \(f_e \in \mathbb{R}^+\)：边 \(e\) 上的流量。
- \(F \in \mathbb{R}^+\)：从源点 \(s\) 流出的总流量（流值）。
- \(\lambda \in \mathbb{R}^+\)：我们需要最小化的最大边负载率。即，我们希望所有边的负载率 \(f_e / c_e\) 都不超过 \(\lambda\)，并且 \(\lambda\) 尽可能小。
2. 目标函数
最小化最大负载率：
\[\min \quad \lambda \]
3. 约束条件
(1) 容量约束：流量不能超过容量。
\[0 \leq f_e \leq c_e, \quad \forall e \in E \]
(2) 流量守恒：对于每个顶点 \(v \in V \setminus \{s, t\}\)，
\[\sum_{e \in \delta^-(v)} f_e = \sum_{e \in \delta^+(v)} f_e \]
其中 \(\delta^-(v)\) 表示指向顶点 \(v\) 的边集，\(\delta^+(v)\) 表示从顶点 \(v\) 出发的边集。
(3) 流值定义：
\[\sum_{e \in \delta^+(s)} f_e = F \]
\[ \sum_{e \in \delta^-(t)} f_e = F \]
（注意：根据守恒，这两个值相等。）
(4) 最大流约束：我们需要确保 \(F\) 是最大流值。这可以通过对 \(s-t\) 割的约束来实现。根据最大流最小割定理，最大流值等于最小割的容量。因此，对于所有 \(s-t\) 割 \((S, \bar{S})\)（其中 \(s \in S, t \in \bar{S}\)），有：
\[F \leq \sum_{e \in (S, \bar{S})} c_e \]
但直接列出所有割约束是指数级的，不可行。替代方案是：我们不显式列出所有割约束，而是将 \(F\) 也作为变量，并在目标中通过“最小化 \(\lambda\)”来间接推动 \(F\) 达到最大。但我们需要保证在最小化 \(\lambda\) 时，\(F\) 不会被无意义地降低。为此，我们引入一个关键的两阶段思想到线性规划中：
实际上，这是一个字典序多目标优化：第一优先目标是最大化 \(F\)，第二优先目标是在 \(F\) 最大的前提下最小化 \(\lambda\)。我们可以用以下技巧将其转化为单目标线性规划：
- 设 \(F^*\) 是传统的（不考虑公平性的）最大流值。我们可以先通过任何最大流算法（如Edmonds-Karp、Dinic）求出 \(F^*\)。
- 然后，在已知 \(F^*\) 的情况下，我们求解以下线性规划：
修正后的线性规划模型（已知最大流值 \(F^*\)）：
决策变量：
- \(f_e \in \mathbb{R}^+\)
- \(\lambda \in \mathbb{R}^+\)
目标：
\[\min \quad \lambda \]
约束：
- 容量约束：\(0 \leq f_e \leq c_e, \quad \forall e \in E\)
- 流量守恒：\(\sum_{e \in \delta^-(v)} f_e = \sum_{e \in \delta^+(v)} f_e, \quad \forall v \in V \setminus \{s, t\}\)
- 流值固定为最大：\(\sum_{e \in \delta^+(s)} f_e = F^*\)
- 负载率约束：\(f_e \leq \lambda \cdot c_e, \quad \forall e \in E\)（这等价于 \(f_e / c_e \leq \lambda\)）
解释：约束4确保了每条边的负载率不超过 \(\lambda\)，而目标是最小化这个上界 \(\lambda\)。由于流值固定为最大流值 \(F^*\)，我们是在所有最大流中寻找最均衡（最小化最大负载率）的那个。这个模型是一个标准的线性规划。
求解步骤（循序渐进）
假设我们有一个具体的图例。考虑如下有向图：
- 顶点：\(V = \{s, a, b, t\}\)
- 边及容量：\((s, a): 4, (s, b): 2, (a, b): 3, (a, t): 1, (b, t): 5\)
- 源点 \(s\)，汇点 \(t\)。
步骤1：求解传统最大流值 \(F^*\)
我们可以用最大流算法（如Ford-Fulkerson）快速求出。
- 寻找增广路：\(s \to a \to t\)，可增广流量 \(\min(4, 1) = 1\)。更新后，边 \((s,a)\) 剩余容量3，\((a,t)\) 满（剩余0）。
- 增广路：\(s \to a \to b \to t\)，可增广流量 \(\min(3, 3, 5) = 3\)。更新后，\((s,a)\) 满（剩余0），\((a,b)\) 满（剩余0），\((b,t)\) 剩余容量2。
- 增广路：\(s \to b \to t\)，可增广流量 \(\min(2, 2) = 2\)。更新后，\((s,b)\) 满（剩余0），\((b,t)\) 满（剩余0）。
无法再找到从 \(s\) 到 \(t\) 的增广路。总流值 \(F^* = 1 + 3 + 2 = 6\)。
步骤2：建立最小化最大负载率的线性规划模型
变量：\(f_{sa}, f_{sb}, f_{ab}, f_{at}, f_{bt}\)，以及 \(\lambda\)。
目标：\(\min \lambda\)
约束：
- 容量约束：
\[ 0 \leq f_{sa} \leq 4, \quad 0 \leq f_{sb} \leq 2, \quad 0 \leq f_{ab} \leq 3, \quad 0 \leq f_{at} \leq 1, \quad 0 \leq f_{bt} \leq 5 \]
- 流量守恒：
- 顶点 \(a\)：流入 = \(f_{sa}\)；流出 = \(f_{ab} + f_{at}\)。所以 \(f_{sa} = f_{ab} + f_{at}\)。
- 顶点 \(b\)：流入 = \(f_{sb} + f_{ab}\)；流出 = \(f_{bt}\)。所以 \(f_{sb} + f_{ab} = f_{bt}\)。
- 流值固定为 \(F^* = 6\)：
- 从 \(s\) 流出：\(f_{sa} + f_{sb} = 6\)。
- 流入 \(t\)：\(f_{at} + f_{bt} = 6\)（可由以上推导得出，作为验证）。
- 负载率约束（对每条边，流量 ≤ λ × 容量）：
\[ f_{sa} \leq 4\lambda, \quad f_{sb} \leq 2\lambda, \quad f_{ab} \leq 3\lambda, \quad f_{at} \leq 1\lambda, \quad f_{bt} \leq 5\lambda \]
步骤3：简化模型
代入守恒和流值约束，可以减少变量数量。由 \(f_{sa} + f_{sb} = 6\) 和 \(f_{sa} = f_{ab} + f_{at}\)，可得 \(f_{sb} = 6 - (f_{ab} + f_{at})\)。
由顶点 \(b\) 守恒：\(f_{sb} + f_{ab} = f_{bt}\) → \([6 - (f_{ab} + f_{at})] + f_{ab} = f_{bt}\) → \(6 - f_{at} = f_{bt}\)。
所以变量可化为：\(f_{at}, f_{ab}, f_{bt}\)（其中 \(f_{bt} = 6 - f_{at}\)），以及 \(\lambda\)。同时 \(f_{sa} = f_{ab} + f_{at}\)，\(f_{sb} = 6 - f_{ab} - f_{at}\)。
代入容量和负载率约束：
- \(0 \leq f_{at} \leq 1\)
- \(0 \leq f_{ab} \leq 3\)
- \(0 \leq 6 - f_{at} \leq 5\) → \(1 \leq f_{at} \leq 6\)（与1结合得 \(f_{at} = 1\)）
- 由 \(0 \leq f_{bt} = 6 - f_{at} \leq 5\) → \(1 \leq f_{at} \leq 6\)，结合 \(f_{at} \leq 1\)，所以 \(f_{at} = 1\) 是唯一可能。
- 由此，\(f_{bt} = 6 - 1 = 5\)。
- \(f_{sa} = f_{ab} + 1\)，且 \(0 \leq f_{sa} \leq 4\) → \(0 \leq f_{ab} + 1 \leq 4\) → \(-1 \leq f_{ab} \leq 3\)（下界自动满足）。
- \(f_{sb} = 6 - (f_{ab} + 1) = 5 - f_{ab}\)，且 \(0 \leq f_{sb} \leq 2\) → \(0 \leq 5 - f_{ab} \leq 2\) → \(3 \leq f_{ab} \leq 5\)。
- 结合5和6：\(3 \leq f_{ab} \leq 3\)（因为5要求 \(f_{ab} \leq 3\)，6要求 \(f_{ab} \geq 3\)）。所以 \(f_{ab} = 3\)。
- 于是，\(f_{sa} = 3+1=4\)，\(f_{sb} = 5-3=2\)。
至此，在满足容量、守恒和流值为6的条件下，流量分布已被唯一确定：\(f_{sa}=4, f_{sb}=2, f_{ab}=3, f_{at}=1, f_{bt}=5\)。
步骤4：计算最小可能的最大负载率 \(\lambda\)
负载率：
- \(f_{sa}/c_{sa} = 4/4 = 1\)
- \(f_{sb}/c_{sb} = 2/2 = 1\)
- \(f_{ab}/c_{ab} = 3/3 = 1\)
- \(f_{at}/c_{at} = 1/1 = 1\)
- \(f_{bt}/c_{bt} = 5/5 = 1\)
所有边的负载率均为1。因此，最大负载率 \(\lambda = 1\)，且无法更小（因为已经有边达到容量）。所以最优解就是上述唯一流量分配，\(\lambda^* = 1\)。
模型的一般求解方法
对于一般图，步骤为：
- 使用任何最大流算法（如Edmonds-Karp、Dinic或Push-Relabel）求出最大流值 \(F^*\)。
- 建立如上所述的线性规划模型，变量为各边流量 \(f_e\) 和 \(\lambda\)。
- 目标为最小化 \(\lambda\)，约束包括：容量约束、流量守恒、总流值等于 \(F^*\)、以及 \(f_e \leq \lambda c_e\) 对于所有边 \(e\)。
- 使用线性规划求解器（如单纯形法或内点法）求解该LP，得到最优流量分配 \(f_e^*\) 和最小最大负载率 \(\lambda^*\)。
总结
本问题在经典最大流问题上增加了一个公平性目标：在保证流最大的前提下，最小化任何一条边的相对负载（流量/容量）。这可以建模为一个两阶段优化，并通过先求最大流值、再解一个最小化最大比值的线性规划来实现。求解后得到的流不仅最大，而且负载最均衡，有助于提高网络资源的利用公平性和鲁棒性。在实际网络中，可以在此基础上进一步引入边权重、多商品流等扩展。