基于线性规划的图多目标最小生成树问题的epsilon-约束法求解示例

字数 7120 2025-12-13 08:56:51

基于线性规划的图多目标最小生成树问题的epsilon-约束法求解示例

我将为您讲解线性规划在多目标优化中的一个应用：使用epsilon-约束法求解图上的多目标最小生成树问题。这是一个将多目标优化问题转化为一系列单目标线性规划问题的经典方法。

问题描述

考虑一个无向连通图 \(G=(V,E)\)，其中 \(V\) 是顶点集合（\(|V|=n\)），\(E\) 是边集合（\(|E|=m\)）。每条边 \(e \in E\) 有两个不同的费用（或权重）：

\(c_e^{(1)}\): 第一个费用（如建设成本）
\(c_e^{(2)}\): 第二个费用（如维护成本）

我们的目标是找到一个生成树 \(T \subseteq E\)，它同时最小化两个总费用：

总成本1: \(C^{(1)}(T) = \sum_{e \in T} c_e^{(1)}\)
总成本2: \(C^{(2)}(T) = \sum_{e \in T} c_e^{(2)}\)

这是一个双目标优化问题。通常没有单个生成树能同时最小化两个目标，因为两个目标往往冲突。因此，我们寻找帕累托最优解集（也称为非支配解集）。

单目标最小生成树的线性规划模型

首先回顾单目标最小生成树（MST）的线性规划模型。对于费用 \(c_e\)，MST问题可以建模为：

最小化: \(\sum_{e \in E} c_e x_e\)

约束条件:

\(\sum_{e \in E} x_e = n-1\)（生成树有 \(n-1\) 条边）
\(\sum_{e \in E(S)} x_e \leq |S| - 1\)，对于所有非空子集 \(S \subset V\)，其中 \(E(S)\) 是 \(S\) 中顶点之间的边集合（ Subtour Elimination Constraints, SECs，防止形成环路）
\(x_e \in \{0,1\}\)，对于所有 \(e \in E\)

这是一个整数线性规划（ILP）。其线性规划松弛（LP relaxation）是允许 \(0 \leq x_e \leq 1\)。有趣的是，对于无向图的最小生成树问题，该LP松弛的最优顶点解（extreme point solution）总是整数的（0或1），因此直接求解这个LP松弛即可得到精确的最小生成树。

epsilon-约束法的基本思想

对于双目标问题，epsilon-约束法的核心策略是：

选择一个目标作为主优化目标，这里我们选择最小化第一个成本 \(C^{(1)}\)。
将另一个目标转化为约束，即要求第二个成本 \(C^{(2)}\) 不大于某个给定的上限值 \(\epsilon\)。
通过系统地改变 \(\epsilon\) 的值，求解一系列单目标线性规划问题，从而获得帕累托前沿上的各个解。

epsilon-约束法的具体步骤

步骤1：确定epsilon的取值范围
我们需要找到第二个目标 \(C^{(2)}\) 的可能最小值 \(L\) 和最大值 \(U\)。

\(L\): 单独最小化 \(C^{(2)}\) 得到的最小生成树 \(T_2^*\) 的总成本，即 \(L = C^{(2)}(T_2^*)\)。这是第二个成本能达到的下界。
\(U\): 在最小化 \(C^{(1)}\) 时，我们也会得到一个生成树 \(T_1^*\)，其第二个成本 \(C^{(2)}(T_1^*)\) 可能较大。我们可以将其作为初始上界。实际上，任何可行生成树的第二个成本都可以作为 \(U\) 的参考。一个保守的上界可以是所有边第二个成本之和。

步骤2：建立epsilon-约束模型
对于给定的 \(\epsilon\) 值（满足 \(L \leq \epsilon \leq U\)），我们构建并求解以下单目标线性规划：

(P_\epsilon):
最小化: \(\sum_{e \in E} c_e^{(1)} x_e\)
约束条件:

\(\sum_{e \in E} c_e^{(2)} x_e \leq \epsilon\) （epsilon约束）
\(\sum_{e \in E} x_e = n-1\)
\(\sum_{e \in E(S)} x_e \leq |S| - 1\)，对于所有非空子集 \(S \subset V\)
\(0 \leq x_e \leq 1\)，对于所有 \(e \in E\)

步骤3：求解并记录非支配解
对于每个 \(\epsilon\) 值，求解线性规划 \(P_\epsilon\)。

如果 \(P_\epsilon\) 可行，其最优解 \(x^*\) 对应一个生成树（LP松弛的整数性保证），其总成本为 \((C^{(1)*}, C^{(2)*})\)，且 \(C^{(2)*} \leq \epsilon\)。
这个解是帕累托最优的吗？对于给定的 \(\epsilon\)，我们是在最小化 \(C^{(1)}\) 的前提下，确保 \(C^{(2)} \leq \epsilon\)。因此，得到的解是弱帕累托最优的（即在所有满足 \(C^{(2)} \leq C^{(2)*}\) 的解中，它的 \(C^{(1)}\) 最小）。通过精细选择 \(\epsilon\)，我们可以得到严格帕累托最优解。
我们将这个解及其目标值对 \((C^{(1)*}, C^{(2)*})\) 记录下来。

步骤4：迭代更新epsilon以探索前沿
关键是如何选择 \(\epsilon\) 的值以覆盖整个帕累托前沿。

从 \(\epsilon = L\) 开始（第二个成本的下界），求解 \(P_\epsilon\)，得到一个帕累托最优解 \(S_1\)。
我们需要找到下一个“有意义的” \(\epsilon\) 值。假设我们刚刚得到的解 \(S_1\) 的第二个成本为 \(C^{(2)}(S_1)\)。
为了找到在帕累托前沿上“相邻”的下一个解（即第二个成本稍大，但第一个成本更小的解），我们将 \(\epsilon\) 稍微增加一点点，例如设为 \(C^{(2)}(S_1) + \delta\)，其中 \(\delta\) 是一个很小的正数（理论上，对于线性目标，\(\delta\) 可以是任意小的正数，但实际计算中需考虑数值精度）。
更系统的方法是：在得到解 \(S_1\) 后，我们添加一个切割约束（cut constraint）以排除这个解，并寻找下一个最优解。我们可以修改问题为：在保持第二个成本 \(C^{(2)}\) 严格大于 \(C^{(2)}(S_1)\) 的前提下，最小化第一个成本 \(C^{(1)}\)。这可以通过在模型中加入约束 \(\sum_{e \in E} c_e^{(2)} x_e \geq C^{(2)}(S_1) + \delta\) 来实现，其中 \(\delta\) 是成本度量的最小单位（如果成本是整数，则 \(\delta=1\)）。
然后，我们在这个新的约束下求解最小化 \(C^{(1)}\) 的问题，得到下一个帕累托最优解 \(S_2\)，其第二个成本为 \(C^{(2)}(S_2)\)。
重复这个过程，直到问题变得不可行（即不存在第二个成本大于当前解，但仍满足其他约束的生成树），或者第二个成本达到上界 \(U\)。

算法流程总结

初始化: 找到第二个目标的下界 \(L\)（通过求解单目标MST问题，最小化 \(C^{(2)}\) ）。
设置初始约束: 令当前约束为 \(\sum_{e \in E} c_e^{(2)} x_e \geq L\)。（实际上，第一个求解时我们可以直接用等号或稍宽松的约束）。
循环求解:
a. 求解线性规划：最小化 \(C^{(1)}\)，满足 生成树约束 和 当前对 \(C^{(2)}\) 的约束。
b. 如果问题可行，记录最优解（生成树 \(T_k\)）及其目标值对 \((C^{(1)}_k, C^{(2)}_k)\)。这个解是帕累托最优的。
c. 如果问题不可行，终止循环。
d. 更新约束：添加一个新的约束 \(\sum_{e \in E} c_e^{(2)} x_e \geq C^{(2)}_k + \delta\)（\(\delta\) 是一个小的正数，如1，用于确保找到不同的解），将其加入约束集，替代或与原约束合并。返回步骤a。
输出: 所有记录的解构成了双目标最小生成树问题的帕累托最优解集（或一个近似集）。

简单算例演示

考虑一个4个顶点的完全图 \(K_4\)，顶点集 \(V = \{1,2,3,4\}\)。边和两种成本如下：

边 (u,v)	\(c^{(1)}\)	\(c^{(2)}\)
(1,2)	3	10
(1,3)	5	2
(1,4)	1	8
(2,3)	7	4
(2,4)	6	3
(3,4)	2	9

步骤A：求下界 \(L\)
最小化 \(C^{(2)}\): 最小生成树应选取 \(c^{(2)}\) 最小的 \(n-1=3\) 条边。
排序 \(c^{(2)}\): (1,3):2, (2,4):3, (2,3):4, (1,2):10, (1,4):8, (3,4):9。
选择 (1,3), (2,4), (2,3) 构成生成树（检查无环）。总成本 \(C^{(2)} = 2+3+4 = 9\)。所以 \(L = 9\)。

步骤B：应用epsilon-约束法迭代

迭代1：
求解：最小化 \(C^{(1)}\)，约束 \(C^{(2)} \leq 9\) 且为生成树。
我们需要找到所有生成树中，\(C^{(2)} \leq 9\) 且 \(C^{(1)}\) 最小的。
可能满足 \(C^{(2)} \leq 9\) 的生成树需要由低成本 \(c^{(2)}\) 的边构成。边(1,3),(2,4),(2,3)组成的树 \(T_1\)，其 \(C^{(2)} = 9\)，\(C^{(1)} = 5+6+7=18\)。
检查其他组合：例如边(1,3),(2,4),(1,4)：\(C^{(2)} = 2+3+8=13 > 9\)，不满足。
边(1,3),(2,3),(3,4)：\(C^{(2)} = 2+4+9=15 > 9\)。
看起来 \(T_1\) 是唯一 \(C^{(2)} \leq 9\) 的生成树。所以解 \(S_1 = T_1\)，目标值 \((18, 9)\)。

迭代2：
更新约束：要求 \(C^{(2)} \geq 9 + 1 = 10\)（设 \(\delta = 1\)）。
求解：最小化 \(C^{(1)}\)，约束 \(C^{(2)} \geq 10\) 且为生成树。
我们寻找 \(C^{(2)}\) 至少为10的生成树中，\(C^{(1)}\) 最小的。
候选：考虑边(1,3),(2,4),(1,2)：\(C^{(2)} = 2+3+10 = 15\)，\(C^{(1)} = 5+6+3 = 14\)。
另一个：边(1,3),(2,4),(3,4)：\(C^{(2)} = 2+3+9 = 14\)，\(C^{(1)} = 5+6+2 = 13\)（更优）。
再检查：边(1,4),(2,3),(2,4)：\(C^{(2)} = 8+4+3 = 15\)，\(C^{(1)} = 1+7+6 = 14\)。
边(1,3),(1,4),(2,4)：\(C^{(2)} = 2+8+3 = 13\)，\(C^{(1)} = 5+1+6 = 12\)（这是目前找到的 \(C^{(1)}\) 最小的，且 \(C^{(2)} \geq 10\)）。
这是否是最小？我们可以通过枚举或求解LP来验证。假设我们求解LP得到解 \(S_2\)，对应生成树为 \(\{(1,3), (1,4), (2,4)\}\)，目标值 \((12, 13)\)。

迭代3：
更新约束：要求 \(C^{(2)} \geq 13 + 1 = 14\)。
求解：最小化 \(C^{(1)}\)，约束 \(C^{(2)} \geq 14\)。
候选：边(1,3),(2,3),(3,4)：\(C^{(2)} = 2+4+9=15\)，\(C^{(1)} = 5+7+2=14\)。
另一个：边(1,2),(1,4),(3,4)：\(C^{(2)} = 10+8+9=27\)，\(C^{(1)} = 3+1+2=6\)（这个 \(C^{(1)}\) 更小！）。
检查这是否为生成树：是的。其 \(C^{(2)}=27\) 满足 \(\geq 14\)。
是否存在 \(C^{(1)}\) 更小的树？树 \(\{(1,2), (1,4), (2,3)\}\)：\(C^{(1)} = 3+1+7=11\)，\(C^{(2)} = 10+8+4=22\)。
树 \(\{(1,2), (1,4), (1,3)\}\)：有环，不是生成树（实际上边数=3但顶点数覆盖不全？检查：顶点集{1,2,3,4}，边集{(1,2),(1,4),(1,3)}连通所有顶点且无环，是生成树）。其 \(C^{(1)} = 3+1+5=9\)，\(C^{(2)} = 10+8+2=20\)。
这比6大。树 \(\{(1,2), (1,4), (3,4)\}\) 的 \(C^{(1)}=6\) 似乎是最小的。我们可以通过观察得到：为了最小化 \(C^{(1)}\)，我们会选成本最低的三条边：\(c^{(1)}\) 排序：(1,4):1, (3,4):2, (1,2):3, (1,3):5, (2,4):6, (2,3):7。选择(1,4),(3,4),(1,2)正好构成生成树。其 \(C^{(2)} = 8+9+10=27\)。这就是全局最小化 \(C^{(1)}\) 的生成树 \(T_1^*\)。所以解 \(S_3 = T_1^*\)，目标值 \((6, 27)\)。

迭代4：
更新约束：要求 \(C^{(2)} \geq 27 + 1 = 28\)。
不存在 \(C^{(2)} \geq 28\) 的生成树，因为所有边的 \(c^{(2)}\) 最大为10，三条边之和最大为 \(10+9+8=27\)。所以问题不可行，终止。

步骤C：输出帕累托最优解集
我们得到三个帕累托最优解：

\(S_1\): 树 \(\{(1,3), (2,3), (2,4)\}\)，目标值 \((18, 9)\)
\(S_2\): 树 \(\{(1,3), (1,4), (2,4)\}\)，目标值 \((12, 13)\)
\(S_3\): 树 \(\{(1,2), (1,4), (3,4)\}\)，目标值 \((6, 27)\)

可以验证，没有其他生成树能在一个目标上优于这些解而不在另一个目标上变差。这三个解构成了该双目标最小生成树问题的帕累托前沿。

总结与扩展

epsilon-约束法的优点：它将复杂的多目标优化问题转化为一系列标准的线性规划问题，可以利用成熟的LP求解器。
处理更多目标：对于超过两个目标的问题，可以将除一个目标外的所有其他目标都转化为约束，原理相同，但需要处理多维的epsilon向量和更复杂的迭代。
实现细节：在实际编程实现中，需要高效处理生成树约束（SECs）。由于约束数量是指数级的（所有顶点子集），通常采用延迟约束生成（Cutting Plane Method）或分支切割法，即开始时只包含少部分约束（如连通性约束），求解LP，检查解是否违反任何SECs（即是否存在子图环），如果违反，则添加相应的约束，重新求解，直到得到可行生成树解。
帕累托前沿的表示：epsilon-约束法可以生成帕累托前沿的离散近似。通过精细选择epsilon的间隔，可以获得前沿的完整描绘。

这个方法的核心在于利用线性规划处理一个目标，同时将其他目标作为资源约束，并通过系统地调整这些约束的界限来探索所有有意义的折衷解。

基于线性规划的图多目标最小生成树问题的epsilon-约束法求解示例我将为您讲解线性规划在多目标优化中的一个应用：使用epsilon-约束法求解图上的多目标最小生成树问题。这是一个将多目标优化问题转化为一系列单目标线性规划问题的经典方法。问题描述考虑一个无向连通图 \( G=(V,E) \)，其中 \( V \) 是顶点集合（\( |V|=n \)），\( E \) 是边集合（\( |E|=m \)）。每条边 \( e \in E \) 有两个不同的费用（或权重）： \( c_ e^{(1)} \): 第一个费用（如建设成本） \( c_ e^{(2)} \): 第二个费用（如维护成本）我们的目标是找到一个生成树 \( T \subseteq E \)，它同时最小化两个总费用：总成本1: \( C^{(1)}(T) = \sum_ {e \in T} c_ e^{(1)} \) 总成本2: \( C^{(2)}(T) = \sum_ {e \in T} c_ e^{(2)} \) 这是一个双目标优化问题。通常没有单个生成树能同时最小化两个目标，因为两个目标往往冲突。因此，我们寻找帕累托最优解集（也称为非支配解集）。单目标最小生成树的线性规划模型首先回顾单目标最小生成树（MST）的线性规划模型。对于费用 \( c_ e \)，MST问题可以建模为：最小化: \( \sum_ {e \in E} c_ e x_ e \) 约束条件: \( \sum_ {e \in E} x_ e = n-1 \)（生成树有 \( n-1 \) 条边） \( \sum_ {e \in E(S)} x_ e \leq |S| - 1 \)，对于所有非空子集 \( S \subset V \)，其中 \( E(S) \) 是 \( S \) 中顶点之间的边集合（ Subtour Elimination Constraints, SECs，防止形成环路） \( x_ e \in \{0,1\} \)，对于所有 \( e \in E \) 这是一个整数线性规划（ILP）。其线性规划松弛（LP relaxation）是允许 \( 0 \leq x_ e \leq 1 \)。有趣的是，对于无向图的最小生成树问题，该LP松弛的最优顶点解（extreme point solution）总是整数的（0或1），因此直接求解这个LP松弛即可得到精确的最小生成树。 epsilon-约束法的基本思想对于双目标问题，epsilon-约束法的核心策略是：选择一个目标作为主优化目标，这里我们选择最小化第一个成本 \( C^{(1)} \)。将另一个目标转化为约束，即要求第二个成本 \( C^{(2)} \) 不大于某个给定的上限值 \( \epsilon \)。通过系统地改变 \( \epsilon \) 的值，求解一系列单目标线性规划问题，从而获得帕累托前沿上的各个解。 epsilon-约束法的具体步骤步骤1：确定epsilon的取值范围我们需要找到第二个目标 \( C^{(2)} \) 的可能最小值 \( L \) 和最大值 \( U \)。 \( L \): 单独最小化 \( C^{(2)} \) 得到的最小生成树 \( T_ 2^* \) 的总成本，即 \( L = C^{(2)}(T_ 2^* ) \)。这是第二个成本能达到的下界。 \( U \): 在最小化 \( C^{(1)} \) 时，我们也会得到一个生成树 \( T_ 1^* \)，其第二个成本 \( C^{(2)}(T_ 1^* ) \) 可能较大。我们可以将其作为初始上界。实际上，任何可行生成树的第二个成本都可以作为 \( U \) 的参考。一个保守的上界可以是所有边第二个成本之和。步骤2：建立epsilon-约束模型对于给定的 \( \epsilon \) 值（满足 \( L \leq \epsilon \leq U \)），我们构建并求解以下单目标线性规划： (P_ \epsilon): 最小化: \( \sum_ {e \in E} c_ e^{(1)} x_ e \) 约束条件: \( \sum_ {e \in E} c_ e^{(2)} x_ e \leq \epsilon \) （epsilon约束） \( \sum_ {e \in E} x_ e = n-1 \) \( \sum_ {e \in E(S)} x_ e \leq |S| - 1 \)，对于所有非空子集 \( S \subset V \) \( 0 \leq x_ e \leq 1 \)，对于所有 \( e \in E \) 步骤3：求解并记录非支配解对于每个 \( \epsilon \) 值，求解线性规划 \( P_ \epsilon \)。如果 \( P_ \epsilon \) 可行，其最优解 \( x^* \) 对应一个生成树（LP松弛的整数性保证），其总成本为 \( (C^{(1) }, C^{(2) }) \)，且 \( C^{(2)* } \leq \epsilon \)。这个解是帕累托最优的吗？对于给定的 \( \epsilon \)，我们是在最小化 \( C^{(1)} \) 的前提下，确保 \( C^{(2)} \leq \epsilon \)。因此，得到的解是弱帕累托最优的（即在所有满足 \( C^{(2)} \leq C^{(2)* } \) 的解中，它的 \( C^{(1)} \) 最小）。通过精细选择 \( \epsilon \)，我们可以得到严格帕累托最优解。我们将这个解及其目标值对 \( (C^{(1) }, C^{(2) }) \) 记录下来。步骤4：迭代更新epsilon以探索前沿关键是如何选择 \( \epsilon \) 的值以覆盖整个帕累托前沿。从 \( \epsilon = L \) 开始（第二个成本的下界），求解 \( P_ \epsilon \)，得到一个帕累托最优解 \( S_ 1 \)。我们需要找到下一个“有意义的” \( \epsilon \) 值。假设我们刚刚得到的解 \( S_ 1 \) 的第二个成本为 \( C^{(2)}(S_ 1) \)。为了找到在帕累托前沿上“相邻”的下一个解（即第二个成本稍大，但第一个成本更小的解），我们将 \( \epsilon \) 稍微增加一点点，例如设为 \( C^{(2)}(S_ 1) + \delta \)，其中 \( \delta \) 是一个很小的正数（理论上，对于线性目标，\(\delta\) 可以是任意小的正数，但实际计算中需考虑数值精度）。更系统的方法是：在得到解 \( S_ 1 \) 后，我们添加一个切割约束（cut constraint）以排除这个解，并寻找下一个最优解。我们可以修改问题为：在保持第二个成本 \( C^{(2)} \) 严格大于 \( C^{(2)}(S_ 1) \) 的前提下，最小化第一个成本 \( C^{(1)} \)。这可以通过在模型中加入约束 \( \sum_ {e \in E} c_ e^{(2)} x_ e \geq C^{(2)}(S_ 1) + \delta \) 来实现，其中 \(\delta\) 是成本度量的最小单位（如果成本是整数，则 \(\delta=1\)）。然后，我们在这个新的约束下求解最小化 \( C^{(1)} \) 的问题，得到下一个帕累托最优解 \( S_ 2 \)，其第二个成本为 \( C^{(2)}(S_ 2) \)。重复这个过程，直到问题变得不可行（即不存在第二个成本大于当前解，但仍满足其他约束的生成树），或者第二个成本达到上界 \( U \)。算法流程总结初始化 : 找到第二个目标的下界 \( L \)（通过求解单目标MST问题，最小化 \( C^{(2)} \) ）。设置初始约束 : 令当前约束为 \( \sum_ {e \in E} c_ e^{(2)} x_ e \geq L \)。（实际上，第一个求解时我们可以直接用等号或稍宽松的约束）。循环求解 : a. 求解线性规划：最小化 \( C^{(1)} \)，满足生成树约束和当前对 \( C^{(2)} \) 的约束。 b. 如果问题可行，记录最优解（生成树 \( T_ k \)）及其目标值对 \( (C^{(1)}_ k, C^{(2)} k) \)。这个解是帕累托最优的。 c. 如果问题不可行，终止循环。 d. 更新约束：添加一个新的约束 \( \sum {e \in E} c_ e^{(2)} x_ e \geq C^{(2)}_ k + \delta \)（\(\delta\) 是一个小的正数，如1，用于确保找到不同的解），将其加入约束集，替代或与原约束合并。返回步骤a。输出 : 所有记录的解构成了双目标最小生成树问题的帕累托最优解集（或一个近似集）。简单算例演示考虑一个4个顶点的完全图 \( K_ 4 \)，顶点集 \( V = \{1,2,3,4\} \)。边和两种成本如下： | 边 (u,v) | \( c^{(1)} \) | \( c^{(2)} \) | |:---:|:---:|:---:| | (1,2) | 3 | 10 | | (1,3) | 5 | 2 | | (1,4) | 1 | 8 | | (2,3) | 7 | 4 | | (2,4) | 6 | 3 | | (3,4) | 2 | 9 | 步骤A：求下界 \( L \) 最小化 \( C^{(2)} \): 最小生成树应选取 \( c^{(2)} \) 最小的 \( n-1=3 \) 条边。排序 \( c^{(2)} \): (1,3):2, (2,4):3, (2,3):4, (1,2):10, (1,4):8, (3,4):9。选择 (1,3), (2,4), (2,3) 构成生成树（检查无环）。总成本 \( C^{(2)} = 2+3+4 = 9 \)。所以 \( L = 9 \)。步骤B：应用epsilon-约束法迭代迭代1：求解：最小化 \( C^{(1)} \)，约束 \( C^{(2)} \leq 9 \) 且为生成树。我们需要找到所有生成树中，\( C^{(2)} \leq 9 \) 且 \( C^{(1)} \) 最小的。可能满足 \( C^{(2)} \leq 9 \) 的生成树需要由低成本 \( c^{(2)} \) 的边构成。边(1,3),(2,4),(2,3)组成的树 \( T_ 1 \)，其 \( C^{(2)} = 9 \)，\( C^{(1)} = 5+6+7=18 \)。检查其他组合：例如边(1,3),(2,4),(1,4)：\( C^{(2)} = 2+3+8=13 > 9 \)，不满足。边(1,3),(2,3),(3,4)：\( C^{(2)} = 2+4+9=15 > 9 \)。看起来 \( T_ 1 \) 是唯一 \( C^{(2)} \leq 9 \) 的生成树。所以解 \( S_ 1 = T_ 1 \)，目标值 \( (18, 9) \)。迭代2：更新约束：要求 \( C^{(2)} \geq 9 + 1 = 10 \)（设 \( \delta = 1 \)）。求解：最小化 \( C^{(1)} \)，约束 \( C^{(2)} \geq 10 \) 且为生成树。我们寻找 \( C^{(2)} \) 至少为10的生成树中，\( C^{(1)} \) 最小的。候选：考虑边(1,3),(2,4),(1,2)：\( C^{(2)} = 2+3+10 = 15 \)，\( C^{(1)} = 5+6+3 = 14 \)。另一个：边(1,3),(2,4),(3,4)：\( C^{(2)} = 2+3+9 = 14 \)，\( C^{(1)} = 5+6+2 = 13 \)（更优）。再检查：边(1,4),(2,3),(2,4)：\( C^{(2)} = 8+4+3 = 15 \)，\( C^{(1)} = 1+7+6 = 14 \)。边(1,3),(1,4),(2,4)：\( C^{(2)} = 2+8+3 = 13 \)，\( C^{(1)} = 5+1+6 = 12 \)（这是目前找到的 \( C^{(1)} \) 最小的，且 \( C^{(2)} \geq 10 \)）。这是否是最小？我们可以通过枚举或求解LP来验证。假设我们求解LP得到解 \( S_ 2 \)，对应生成树为 \( \{(1,3), (1,4), (2,4)\} \)，目标值 \( (12, 13) \)。迭代3：更新约束：要求 \( C^{(2)} \geq 13 + 1 = 14 \)。求解：最小化 \( C^{(1)} \)，约束 \( C^{(2)} \geq 14 \)。候选：边(1,3),(2,3),(3,4)：\( C^{(2)} = 2+4+9=15 \)，\( C^{(1)} = 5+7+2=14 \)。另一个：边(1,2),(1,4),(3,4)：\( C^{(2)} = 10+8+9=27 \)，\( C^{(1)} = 3+1+2=6 \)（这个 \( C^{(1)} \) 更小！）。检查这是否为生成树：是的。其 \( C^{(2)}=27 \) 满足 \( \geq 14 \)。是否存在 \( C^{(1)} \) 更小的树？树 \( \{(1,2), (1,4), (2,3)\} \)：\( C^{(1)} = 3+1+7=11 \)，\( C^{(2)} = 10+8+4=22 \)。树 \( \{(1,2), (1,4), (1,3)\} \)：有环，不是生成树（实际上边数=3但顶点数覆盖不全？检查：顶点集{1,2,3,4}，边集{(1,2),(1,4),(1,3)}连通所有顶点且无环，是生成树）。其 \( C^{(1)} = 3+1+5=9 \)，\( C^{(2)} = 10+8+2=20 \)。这比6大。树 \( \{(1,2), (1,4), (3,4)\} \) 的 \( C^{(1)}=6 \) 似乎是最小的。我们可以通过观察得到：为了最小化 \( C^{(1)} \)，我们会选成本最低的三条边：\( c^{(1)} \) 排序：(1,4):1, (3,4):2, (1,2):3, (1,3):5, (2,4):6, (2,3):7。选择(1,4),(3,4),(1,2)正好构成生成树。其 \( C^{(2)} = 8+9+10=27 \)。这就是全局最小化 \( C^{(1)} \) 的生成树 \( T_ 1^* \)。所以解 \( S_ 3 = T_ 1^* \)，目标值 \( (6, 27) \)。迭代4：更新约束：要求 \( C^{(2)} \geq 27 + 1 = 28 \)。不存在 \( C^{(2)} \geq 28 \) 的生成树，因为所有边的 \( c^{(2)} \) 最大为10，三条边之和最大为 \( 10+9+8=27 \)。所以问题不可行，终止。步骤C：输出帕累托最优解集我们得到三个帕累托最优解： \( S_ 1 \): 树 \( \{(1,3), (2,3), (2,4)\} \)，目标值 \( (18, 9) \) \( S_ 2 \): 树 \( \{(1,3), (1,4), (2,4)\} \)，目标值 \( (12, 13) \) \( S_ 3 \): 树 \( \{(1,2), (1,4), (3,4)\} \)，目标值 \( (6, 27) \) 可以验证，没有其他生成树能在一个目标上优于这些解而不在另一个目标上变差。这三个解构成了该双目标最小生成树问题的帕累托前沿。总结与扩展 epsilon-约束法的优点：它将复杂的多目标优化问题转化为一系列标准的线性规划问题，可以利用成熟的LP求解器。处理更多目标：对于超过两个目标的问题，可以将除一个目标外的所有其他目标都转化为约束，原理相同，但需要处理多维的epsilon向量和更复杂的迭代。实现细节：在实际编程实现中，需要高效处理生成树约束（SECs）。由于约束数量是指数级的（所有顶点子集），通常采用延迟约束生成（Cutting Plane Method）或分支切割法，即开始时只包含少部分约束（如连通性约束），求解LP，检查解是否违反任何SECs（即是否存在子图环），如果违反，则添加相应的约束，重新求解，直到得到可行生成树解。帕累托前沿的表示：epsilon-约束法可以生成帕累托前沿的离散近似。通过精细选择epsilon的间隔，可以获得前沿的完整描绘。这个方法的核心在于利用线性规划处理一个目标，同时将其他目标作为资源约束，并通过系统地调整这些约束的界限来探索所有有意义的折衷解。