基于线性规划的图多目标最小费用流问题的帕累托前沿生成示例
题目描述
考虑一个有向图 \(G = (V, E)\)：
- 顶点集合 \(V\)，边集合 \(E\)。
- 每个边 \(e \in E\) 有容量上限 \(u_e \geq 0\)。
- 每个边 \(e\) 上有两个费用系数 \(c_e^1\) 和 \(c_e^2\)，分别对应两个目标。
- 存在单一源点 \(s \in V\) 和单一汇点 \(t \in V\)，需要从 \(s\) 向 \(t\) 输送流量 \(F\)。
问题：
我们需要找到从 \(s\) 到 \(t\) 的流量分配 \(f_e\)（对每条边 \(e\)），在满足流量守恒、容量约束、总流量恰好为 \(F\) 的前提下，使得两个目标函数：
\[\text{Cost}_1(f) = \sum_{e \in E} c_e^1 f_e, \quad \text{Cost}_2(f) = \sum_{e \in E} c_e^2 f_e \]
同时最小化。
由于两个目标通常无法同时达到最优，我们要求找出所有帕累托最优解（即不存在另一个可行流的两个目标值都严格优于它），并描绘出目标空间中的帕累托前沿。
解题过程
1. 建立多目标线性规划模型
设决策变量 \(f_e \geq 0\) 为边 \(e\) 上的流量。
约束：
(1) 容量约束：
\[0 \le f_e \le u_e, \quad \forall e \in E \]
(2) 流量守恒（对所有 \(v \in V\)）：
\[\sum_{e \in \delta^+(v)} f_e - \sum_{e \in \delta^-(v)} f_e = \begin{cases} F, & v = s \\ -F, & v = t \\ 0, & \text{其他} \end{cases} \]
其中 \(\delta^+(v)\) 是以 \(v\) 为起点的边，\(\delta^-(v)\) 是以 \(v\) 为终点的边。
(3) 总流量固定为 \(F\)。
目标：
同时最小化 \(\text{Cost}_1(f)\) 和 \(\text{Cost}_2(f)\)。
2. 多目标优化转为标量化子问题
由于是线性目标，帕累托前沿可以通过加权和法来生成：
对给定的权重 \(\alpha \in [0, 1]\)，求解单目标线性规划：
\[\min \, \alpha \cdot \text{Cost}_1(f) + (1-\alpha) \cdot \text{Cost}_2(f) \]
\[ = \sum_{e \in E} \big[ \alpha c_e^1 + (1-\alpha) c_e^2 \big] f_e \]
受上述相同约束。
3. 算法步骤（帕累托前沿生成）
输入：图 \(G\)，边容量 \(u_e\)，费用 \(c_e^1, c_e^2\)，源点 \(s\)，汇点 \(t\)，总流量 \(F\)。
输出：帕累托前沿上的一系列点 \((\text{Cost}_1, \text{Cost}_2)\)。
步骤：
- 初始化帕累托点集 \(P = \emptyset\)。
- 对每个 \(\alpha \in \{0, 0.05, 0.1, \dots, 1.0\}\)（或其他更密集网格）执行：
- 计算每条边的组合费用：
\[ \bar{c}_e = \alpha c_e^1 + (1-\alpha) c_e^2 \]
- 求解单目标最小费用流问题（可用网络单纯形法、容量缩放算法等）得到最优流 \(f^{(\alpha)}\) 和对应的目标值 \(C_1^{(\alpha)}, C_2^{(\alpha)}\)。
- 将点 \((C_1^{(\alpha)}, C_2^{(\alpha)})\) 加入候选集。
- 去除非帕累托点：
在候选集中，如果存在两点 \((a_1, a_2)\) 和 \((b_1, b_2)\) 满足 \(a_1 \leq b_1\) 且 \(a_2 \leq b_2\) 且至少一个严格不等，则删除 \((b_1, b_2)\)。 - 按 \(C_1\) 排序剩余点，得到近似的帕累托前沿。
4. 实例演示
假设一个简单有向图：
- 顶点 \(V = \{s, a, t\}\)。
- 边 \(E = \{e_1: s \to a, e_2: s \to t, e_3: a \to t\}\)。
- 容量均为 \(u_e = 5\)。
- 费用：
\[ c_{e_1}^1=2, c_{e_1}^2=5; \quad c_{e_2}^1=4, c_{e_2}^2=3; \quad c_{e_3}^1=1, c_{e_3}^2=6. \]
- 总流量 \(F = 5\)。
约束方程（流量守恒）：
\[\begin{aligned} f_1 + f_2 &= 5 \quad (\text{出 } s) \\ -f_1 + f_3 &= 0 \quad (\text{顶点 } a) \\ -f_2 - f_3 &= -5 \quad (\text{入 } t) \end{aligned} \]
容量约束： \(0 \le f_1, f_2, f_3 \le 5\)。
目标：
\[\text{Cost}_1 = 2f_1 + 4f_2 + 1f_3, \quad \text{Cost}_2 = 5f_1 + 3f_2 + 6f_3. \]
标量化：对 \(\alpha = 0.3\)，组合费用：
\[\bar{c}_1 = 0.3\times 2 + 0.7\times 5 = 4.1 \]
\[ \bar{c}_2 = 0.3\times 4 + 0.7\times 3 = 3.3 \]
\[ \bar{c}_3 = 0.3\times 1 + 0.7\times 6 = 4.5 \]
最小化 \(4.1 f_1 + 3.3 f_2 + 4.5 f_3\)。
从费用看，应多用 \(e_2\)（费用 3.3 最小），但必须满足流量守恒。
将 \(f_3 = f_1\) 代入，且 \(f_2 = 5 - f_1\)：
目标 = \(4.1 f_1 + 3.3(5-f_1) + 4.5 f_1 = (4.1 - 3.3 + 4.5) f_1 + 16.5 = 5.3 f_1 + 16.5\)。
因 \(f_1 \ge 0\)，最小在 \(f_1 = 0\) 时得到，则 \(f_2 = 5, f_3 = 0\)。
此时 \(C_1 = 2\times 0 + 4\times 5 + 1\times 0 = 20\)， \(C_2 = 5\times 0 + 3\times 5 + 6\times 0 = 15\)。
类似地对不同 \(\alpha\) 求解，得到几个极点的帕累托点：
- \(\alpha = 0\)：最小化 \(C_2\) → 多用 \(e_2\)（C2 最小 3），得 \(f_2=5, f_1=f_3=0\) → \((C_1,C_2)=(20,15)\)。
- \(\alpha = 1\)：最小化 \(C_1\) → 检查：\(c_1^1\) 最小是 \(e_3\) 的 1，但 \(e_3\) 需从 \(e_1\) 来，路径 \(s\to a\to t\) 总 \(c^1=3\)，比 \(e_2\) 的 4 小，所以全用路径 \(s-a-t\)：设 \(f_1=5, f_3=5, f_2=0\)（注意容量允许），则 \(C_1=2\times 5+4\times 0+1\times 5=15\)， \(C_2=5\times 5+3\times 0+6\times 5=55\)。
- 中间权重可能产生混合流，例如 \(f_1=2, f_3=2, f_2=3\) 等，需求解线性规划。
5. 前沿图示与理解
将各 \(\alpha\) 对应解画在 \((C_1, C_2)\) 平面，并筛选帕累托点。
帕累托前沿是这些点中在“左下”凸包边界上的点。
在该例子中，可能的帕累托前沿由两个极端点 (15,55) 和 (20,15) 及可能的凸组合对应流构成，取决于费用结构。
重要性质：
对于线性多目标问题，帕累托前沿是凸的，且可以通过加权和法生成所有极点（支撑点），但前沿上的点可能是多个极点的凸组合对应的目标值。
6. 算法扩展
-
自适应权重选择：
用帕累托边界面追踪方法，自动找到使目标空间凸包边界变化的 \(\alpha\) 值，而非均匀取权重。 -
两阶段法：
先求单目标最小值：- 解最小化 \(C_1\) 得点 \(A\)。
- 解最小化 \(C_2\) 得点 \(B\)。
然后在 \(A\) 与 \(B\) 之间的凸组合约束下，枚举可能的支撑点。
-
用对偶变量解释：
加权问题可对偶化，对偶变量反映了边际成本交换率，帕累托前沿的斜率与对偶解相关。
总结
这个示例展示了如何用线性规划和标量化方法求解多目标最小费用流的帕累托前沿。
核心步骤：
- 建立多目标线性规划模型。
- 用加权和法转为单目标最小费用流子问题。
- 用网格法或自适应权重法求解一系列子问题。
- 去除非支配点得到帕累托前沿。
该方法适用于任意多目标线性规划，是生成帕累托前沿的经典标量化技术。