基于线性规划的图多目标最大流问题的ε-约束法求解示例
题目描述
考虑一个有向图 \(G=(V, E)\)，每条边 \(e \in E\) 有容量 \(u_e\) 和流成本 \(c_e\)。现有两个目标需要同时最大化：
- 从源点 \(s\) 到汇点 \(t\) 的总流量 \(f_{total}\)。
- 从源点 \(s\) 到汇点 \(t\) 的净收益 \(P_{total}\)，定义为总流量收入减去流动成本。假设单位流量收入为 \(p\)（常数）。
给定源点 \(s\) 和汇点 \(t\)，我们需要在满足容量和流量平衡约束的前提下，找到能同时优化这两个目标的流方案。由于两个目标可能冲突（例如，增加流量可能增加成本，降低净收益），这是一个多目标优化问题。我们将使用ε-约束法将其转化为一系列单目标线性规划问题来求解近似帕累托前沿。
解题步骤
步骤1：定义变量与数学模型
设决策变量 \(x_e \geq 0\) 表示边 \(e\) 上的流量。
经典最大流约束为：
- 容量约束：\(0 \leq x_e \leq u_e\)，对所有 \(e \in E\)。
- 流量平衡：除源点 \(s\) 和汇点 \(t\) 外，每个节点 \(v \in V \setminus \{s, t\}\) 满足
\[ \sum_{e \in \delta^+(v)} x_e - \sum_{e \in \delta^-(v)} x_e = 0, \]
其中 \(\delta^+(v)\) 表示流出 \(v\) 的边集，\(\delta^-(v)\) 表示流入 \(v\) 的边集。
3. 源点净流出：设从 \(s\) 流出的总流量为 \(f_{total}\)，即
\[ \sum_{e \in \delta^+(s)} x_e - \sum_{e \in \delta^-(s)} x_e = f_{total}. \]
两个目标函数：
- 总流量：\(F_1 = f_{total}\)（直接由源点净流出定义）。
- 净收益：\(F_2 = p \cdot f_{total} - \sum_{e \in E} c_e x_e\)，其中 \(p\) 是单位流量收入。
步骤2：多目标问题形式化
多目标问题可写为：
\[\max \left\{ F_1(x), F_2(x) \right\} \]
满足上述线性约束。
由于目标可能冲突，通常不存在单个解同时最大化二者，而是寻找帕累托最优解：即不存在其他可行解在至少一个目标上更优且不损害另一目标。
步骤3：ε-约束法的转化
ε-约束法的思想是：选择一个目标作为主优化目标，将另一个目标转化为约束，限制其不小于某个阈值 ε。通过系统调整 ε，生成一系列帕累托最优解。
这里我们选择 最大化净收益 \(F_2\) 作为主目标，将总流量 \(F_1\) 约束为不小于 ε。
对每个 ε，求解如下线性规划：
\[\begin{aligned} \max \quad & F_2 = p \cdot f_{total} - \sum_{e \in E} c_e x_e \\ \text{s.t.} \quad & f_{total} \geq \varepsilon, \\ & \text{容量与流量平衡约束如上}. \end{aligned} \]
注意：ε 的取值范围应在最小可能总流量 \(f_{min}\) 和最大可能总流量 \(f_{max}\) 之间。
- \(f_{max}\) 可通过求解经典最大流问题（仅最大化 \(F_1\)）得到。
- \(f_{min}\) 可取 0，或通过最小化 \(F_1\)（在流量平衡下）得到可能的最小正值。
步骤4：确定 ε 的取值区间与采样
- 先求 \(f_{max}\)：解线性规划
\[ \max f_{total} \quad \text{满足容量与流量平衡约束}. \]
得 \(f_{max}\)。
2. 可选求 \(f_{min}\)：若允许零流，则 \(f_{min} = 0\)；若要求正流，可解
\[ \min f_{total} \quad \text{满足容量与流量平衡约束}. \]
这里假设 \(f_{min} = 0\)。
3. 在区间 \([0, f_{max}]\) 内选择一组 ε 值，例如等间距采样：\(\varepsilon_k = \frac{k}{K} f_{max}\)，\(k = 0,1,\dots,K\)，K 为采样点数（如 K=10）。
步骤5：对每个 ε 求解线性规划
对每个 \(\varepsilon_k\)，求解步骤3中的线性规划。若问题可行，则得到最优解 \(x^{(k)}\) 及其对应的 \(F_1^{(k)}\)、\(F_2^{(k)}\)。
可能出现的情况：
- 若 \(\varepsilon_k\) 过大，约束 \(f_{total} \geq \varepsilon_k\) 可能使问题不可行（当 \(\varepsilon_k > f_{max}\) 时必然不可行）。
- 若 \(\varepsilon_k\) 很小，主目标 \(F_2\) 可能优先选择高收益的低流量方案，此时 \(f_{total}\) 可能刚好等于 \(\varepsilon_k\)（约束紧）或大于 \(\varepsilon_k\)（约束松）。
步骤6：提取帕累托前沿
收集所有可行的 \((F_1^{(k)}, F_2^{(k)})\) 点，去除被支配的点（即存在另一点在两个目标上均不差且至少一个更优），剩余的即为近似帕累托最优解集。
这些点展示了流量与净收益之间的权衡关系。
步骤7：实例演示
考虑简单网络：
- 节点：\(V = \{s, a, t\}\)。
- 边：\((s,a)\)：容量 5，成本 1；\((a,t)\)：容量 4，成本 2；\((s,t)\)：容量 3，成本 4。
- 单位流量收入 \(p = 10\)。
计算 \(f_{max}\)：最大流为 \(\min(5+3, 4+3) = 7\)（通过 \(s \to a \to t\) 流 4，\(s \to t\) 流 3）。
设置 ε 采样：取 \(\varepsilon = 0,1,2,\dots,7\)。
以 \(\varepsilon = 4\) 为例，模型为：
\[\begin{aligned} \max \quad & 10 f_{total} - (1 x_{sa} + 2 x_{at} + 4 x_{st}) \\ \text{s.t.} \quad & x_{sa} \leq 5,\ x_{at} \leq 4,\ x_{st} \leq 3, \\ & f_{total} = x_{sa} + x_{st}, \\ & x_{sa} = x_{at}, \quad \text{(节点a平衡)} \\ & f_{total} \geq 4, \\ & x_{sa}, x_{at}, x_{st} \geq 0. \end{aligned} \]
解得：\(x_{sa}=x_{at}=4\)，\(x_{st}=0\)，\(f_{total}=4\)，净收益 \(F_2 = 10*4 - (1*4+2*4+4*0)=40-12=28\)。
类似求解所有 ε，得到帕累托点，例如：
- ε=0：选择成本最低的流（可能为零流，若允许），得 \(F_1=0, F_2=0\)。
- ε=7：必须满流，但成本高，净收益可能较低。
权衡曲线将显示：随着流量增加，净收益先增后减（因成本增长可能超收入增长）。
总结
本问题展示了用 ε-约束法处理线性规划中的多目标优化：通过将次要目标转化为约束，生成一系列单目标线性规划，从而近似获得帕累托前沿。该方法适用于任意多个线性目标，但需注意 ε 采样的密度会影响前沿的精确度。