基于线性规划的图带宽分配问题的最大最小公平性优化求解示例
我将为你详细讲解一个涉及图论和优化的线性规划问题：如何在网络图中分配带宽，以实现最大最小公平性（Max-Min Fairness）。我将从问题描述开始，逐步深入到建模、求解思路和算法步骤。
1. 问题描述
我们考虑一个通信网络，可以抽象成一个有向图 G = (V, E)。
- V 是网络中的节点集合（例如路由器、服务器）。
- E 是边的集合，每条有向边 e ∈ E 有一个容量 c_e > 0，表示该链路每秒能传输的最大数据量（如 Mbps）。
网络中有一组数据流（Flows），记为集合 F。每个流 f ∈ F 具有以下属性：
- 源节点 s_f 和目标节点 t_f。
- 需求 d_f：表示该流期望获得的带宽（传输速率）。在某些模型中，需求可能是无限大（即尽可能多获取带宽）。
- 固定路径 P_f：这是一个已知的、从 s_f 到 t_f 的、由若干条边构成的序列。我们假设路由是预先给定的。
核心问题：如何为每个流 f 分配一个实际的传输速率 x_f（0 ≤ x_f ≤ d_f），使得分配方案满足以下两个条件？
- 容量约束：对于任何一条边 e，所有经过该边的流的速率之和不能超过该边的容量 c_e。
- 最大最小公平性原则：在满足容量约束的前提下，我们追求一种“公平”的分配。最大最小公平性的定义是：无法在不减少其他更小（或相等）速率流的前提下，增加任何一个流的速率。 直观上，它倾向于“提升最慢者的速度”，实现一种“木桶效应”式的公平。
目标：找到一个满足上述约束的速率分配向量 x = (x_f)_{f∈F}，使得其是最大最小公平的。
2. 从直觉到线性规划建模
最大最小公平性本身不是一个单一目标函数，而是一种分配性质。我们可以通过一个迭代的线性规划（LP）过程来找到这种分配。
基本思路（“灌水”原理）：
- 首先，所有流从速率为0开始。
- 我们尝试同时、同速率地增加所有流的速率，就像向一个水桶系统里均匀灌水。
- 当某些边达到容量极限时，经过这些边的“瓶颈流”的速率就不能再增加了。我们“固定”这些流的速率。
- 在剩下的、尚未达到速率的流中，我们继续忽略那些被固定的流，只增加剩余流的速率。这个过程反复进行，直到所有流都无法再增加速率为止。
线性规划建模（单次迭代）：
假设我们处于第 k 轮迭代。设 S_k 是在前 k-1 轮中已经被固定速率的流集合，其速率已确定为 x_f^*。设 R_k = F \ S_k 是剩余的可增加速率的流集合。
在第 k 轮，我们想为所有剩余流 R_k 找一个共同的增量 Δ。目标是在不违反容量约束的前提下，最大化这个 Δ。
我们可以为第 k 轮建立如下线性规划：
决策变量:
- Δ: 本轮可以为所有剩余流增加的公共速率。
目标函数:
- 最大化 Δ
约束条件:
- 边容量约束：对于每条边 e ∈ E，所有经过它的流的总速率不能超过其容量。
\[ \sum_{f \in S_k, \, e \in P_f} x_f^* \ + \ \sum_{f \in R_k, \, e \in P_f} \Delta \ \leq \ c_e, \quad \forall e \in E \]
*解释*：不等式左边第一部分是已固定流的速率贡献（常数），第二部分是剩余流以相同增量 Δ 增加后的贡献。
- 需求上限约束：任何流的速率不能超过其需求。
\[ x_f^* + \Delta \leq d_f, \quad \forall f \in R_k \]
*解释*：对于剩余流，本轮增加 Δ 后，其总速率 (x_f^*+Δ) 不能超过其需求 d_f。对于已固定流，此约束已满足。
- 非负约束:
\[ \Delta \geq 0 \]
求解这个LP，我们得到一个最优解 Δ_k^。这一轮的结果是：**所有剩余流 R_k 的速率被设定为 x_f^ + Δ_k^**。
如何确定哪些流被“固定”？
在得到 Δ_k^* 后，检查约束。对于某些边 e 或某些流 f，对应的约束（1）或（2）可能在最优解下取等号（即成为“紧约束”）。那么：
- 如果某条边 e 的容量约束（1）变紧，则所有经过该边且仍在 R_k 中的流，在下一轮都无法再增加速率（因为再增加 Δ 就会违反该边约束）。这些流应被加入 S_k，形成 S_{k+1}。
- 如果某个流 f 的需求约束（2）变紧，则该流 f 已达到其最大需求，也应被加入 S_{k+1}。
算法终止：当没有剩余流（即 R_k 为空）时，算法终止。最终得到的 x_f^* 分配就是最大最小公平的。
3. 完整算法步骤与示例
让我们通过一个具体的小例子，手算一遍这个迭代过程。
示例网络：
- 边：E = {e1, e2, e3}，容量分别为 c1=10, c2=5, c3=8。
- 流：F = {f1, f2, f3}。
- f1: 路径 P1 = [e1, e2]，需求 d1 = ∞。
- f2: 路径 P2 = [e2, e3]，需求 d2 = 6。
- f3: 路径 P3 = [e1, e3]，需求 d3 = ∞。
初始化：S0 = ∅, R0 = {f1, f2, f3}。所有流的当前速率 x_f^0 = 0。
第1轮迭代:
-
构建LP：
- 目标：max Δ
- 约束：
- 边 e1: 经过的流是 f1, f3。∑(固定流速率0) + (Δ + Δ) ≤ 10 → 2Δ ≤ 10
- 边 e2: 经过的流是 f1, f2。 Δ + Δ ≤ 5 → 2Δ ≤ 5
- 边 e3: 经过的流是 f2, f3。 Δ + Δ ≤ 8 → 2Δ ≤ 8
- 需求约束：对 f2: 0 + Δ ≤ 6 → Δ ≤ 6 (f1, f3 需求无限，无约束)
- 非负：Δ ≥ 0
-
求解：约束最紧的是 e2 的 2Δ ≤ 5，所以 Δ_1^* = 2.5。
-
更新速率：x_f1^1 = 0 + 2.5 = 2.5, x_f2^1 = 2.5, x_f3^1 = 2.5。
-
识别瓶颈：边 e2 的约束（2Δ ≤ 5）在 Δ=2.5 时取等号。经过 e2 的剩余流是 f1 和 f2。所以 f1 和 f2 被固定。另外，检查 f2 的需求约束（Δ ≤ 6）是松的（2.5 < 6），所以需求不是瓶颈。
-
更新集合：S1 = {f1, f2}, R1 = {f3}。
第2轮迭代:
- 当前状态：x_f1^* = 2.5, x_f2^* = 2.5, x_f3^* = 2.5。本轮只增加 f3 的速率，增量为 Δ。
- 构建LP：
- 目标：max Δ
- 约束：
- 边 e1: 固定流 f1 贡献 2.5，增加流 f3 贡献 Δ。2.5 + Δ ≤ 10 → Δ ≤ 7.5
- 边 e2: 只有固定流 f1, f2，总贡献 5，已达到容量。2.5+2.5+0 ≤ 5 (自动满足，不影响 Δ)。
- 边 e3: 固定流 f2 贡献 2.5，增加流 f3 贡献 Δ。2.5 + Δ ≤ 8 → Δ ≤ 5.5
- 需求约束：f3 需求无限，无约束。
- 非负：Δ ≥ 0
- 求解：最紧约束是 e3: Δ ≤ 5.5，所以 Δ_2^* = 5.5。
- 更新速率：只有 f3 增加，x_f3^2 = 2.5 + 5.5 = 8.0。
- 识别瓶颈：边 e3 的约束（2.5+Δ ≤ 8）在 Δ=5.5 时取等号。经过 e3 的剩余流只有 f3，所以 f3 被固定。
- 更新集合：S2 = {f1, f2, f3}, R2 = ∅。
算法终止。
最终分配：x_f1^* = 2.5, x_f2^* = 2.5, x_f3^* = 8.0。
验证最大最小公平性：
- 能否单独增加 f1？不能，因为它和 f2 共享瓶颈边 e2（容量5），两者速率已均为2.5。增加 f1 就必须减少 f2，而 f2 的速率并不大于 f1，违反原则。
- 能否单独增加 f2？同理，不能。
- 能否单独增加 f3？不能，边 e3 容量8已被 f2(2.5)和 f3(8)占满。
因此，此分配是最大最小公平的。
4. 算法总结与扩展
上述迭代线性规划方法被称为逐步填充算法（Progressive Filling Algorithm） 或 水填充算法（Water-Filling Algorithm），是计算最大最小公平分配的经典方法。
关键特性：
- 最优性：该算法产生的结果严格满足最大最小公平性的定义。
- 计算复杂度：最坏情况下需要运行 |F| 轮（每轮固定至少一个流）。每轮需要求解一个简单的线性规划（实际上只有一个变量 Δ，可以直接通过计算所有约束的“松弛量”来找到最小的 Δ，无需调用完整LP求解器）。
- 建模灵活性：可以轻松纳入流的优先级（通过设置不同的初始“水位”或权重）和最小速率要求。
与其他方法的联系：
- 最大最小公平分配也可以表述为一个分层优化问题：先最大化最小速率，然后在保持最小速率最大的前提下最大化第二小速率，依此类推。这与我们的迭代过程等价。
- 在网络效用最大化框架下，当效用函数是 α→∞ 的 α-公平效用函数时，其解趋近于最大最小公平分配。
这个例子展示了如何将一种定性的“公平”概念，通过巧妙的迭代建模，转化为一系列可求解的线性规划问题，是线性规划在图论和网络优化中一个非常经典和实用的应用。