线性规划的图最小平均生成树问题的分数规划Dinkelbach算法求解示例
题目描述
我们考虑一个边带权的连通无向图 \(G = (V, E)\)，每条边 \(e \in E\) 有一个正的成本 \(c(e) > 0\) 和一个正的效益 \(t(e) > 0\)。目标是选择一棵生成树 \(T \subseteq E\)，使得总成本与总效益的比值最小，即最小化：
\[\lambda(T) = \frac{\sum_{e \in T} c(e)}{\sum_{e \in T} t(e)}. \]
这个问题称为最小平均生成树问题（Minimum Ratio Spanning Tree Problem）。该问题属于分数规划（Fractional Programming）的一种，不能用直接的最小生成树算法（如Kruskal或Prim）求解，因为比值目标是非线性的。我们将介绍如何使用Dinkelbach算法结合线性规划（或最小生成树子程序）来求解。
解题过程
1. 问题形式化与分数规划转化
设变量 \(x_e \in \{0,1\}\) 表示边 \(e\) 是否被选入生成树 \(T\) 中。则问题可写为整数分数规划：
\[\min \frac{\sum_{e \in E} c(e) x_e}{\sum_{e \in E} t(e) x_e} \quad \text{s.t.} \quad x \in X, \]
其中 \(X\) 是所有生成树的指标向量集合（即满足 \(x\) 对应一棵生成树的约束集合，包括连通性、无环、恰好 \(|V|-1\) 条边等）。
设最优比值为 \(\lambda^* = \min_{x \in X} \frac{c^T x}{t^T x}\)。
2. Dinkelbach算法的核心思想
对于给定的参数 \(\lambda \in \mathbb{R}\)，定义辅助函数：
\[F(\lambda) = \min_{x \in X} \left( \sum_{e} c(e) x_e - \lambda \sum_{e} t(e) x_e \right) = \min_{x \in X} \sum_{e} \big( c(e) - \lambda \, t(e) \big) x_e. \]
关键性质：
- 如果 \(F(\lambda) > 0\)，则对于任意可行解 \(x\)，有 \(c^T x - \lambda t^T x > 0\)，即 \(\frac{c^T x}{t^T x} > \lambda\)，因此 \(\lambda^* > \lambda\)。
- 如果 \(F(\lambda) < 0\)，则存在某个解使得比值 \(< \lambda\)，因此 \(\lambda^* < \lambda\)。
- 如果 \(F(\lambda) = 0\)，则存在一个解 \(x\) 满足 \(\frac{c^T x}{t^T x} = \lambda\)，且这个比值是最优的，即 \(\lambda^* = \lambda\)。
因此，寻找 \(\lambda^*\) 等价于寻找方程 \(F(\lambda) = 0\) 的根。
3. Dinkelbach算法步骤
算法通过迭代更新 \(\lambda\) 来逼近最优比值，每一步都需要求解一个参数化的最小生成树问题。
输入：图 \(G=(V,E)\)，边权 \(c(e), t(e) > 0\)。
输出：最优生成树 \(T^*\) 和最优比值 \(\lambda^*\)。
-
初始化：设初始比值 \(\lambda_0 = 0\)（或任意值），迭代次数 \(k = 0\)。
-
迭代步骤：
- 对每条边 \(e \in E\)，定义新权重 \(w_\lambda(e) = c(e) - \lambda_k \cdot t(e)\)。
- 在新的权重 \(w_\lambda(e)\) 下，用任何最小生成树算法（如Kruskal或Prim）求一棵最小生成树 \(T_k\)。这等价于求解 \(F(\lambda_k)\) 的最小值点。
- 计算当前比值 \(r_k = \frac{\sum_{e \in T_k} c(e)}{\sum_{e \in T_k} t(e)}\)。
- 如果 \(F(\lambda_k) = \sum_{e \in T_k} (c(e) - \lambda_k t(e)) = 0\)（或小于某个很小的阈值 \(\epsilon\)），则停止，\(\lambda^* = r_k\)。
- 否则，更新 \(\lambda_{k+1} = r_k\)，\(k \leftarrow k+1\)，继续迭代。
-
终止条件：当 \(|F(\lambda_k)| < \epsilon\) 时，输出 \(T_k\) 和 \(\lambda_k\)。
注意：算法在有限步内收敛（通常超线性收敛），且每次迭代只需调用一次最小生成树算法。
4. 为何需要线性规划？
实际上，Dinkelbach算法中我们并未显式求解线性规划，而是利用了一个重要事实：
集合 \(X\)（生成树的凸包）的线性优化问题可以在多项式时间内求解（通过最小生成树算法）。这本质上是利用了生成树多面体的线性规划性质：
对于任意边权重 \(w(e)\)，最小生成树就是线性规划
\[\min \sum_{e} w(e) x_e \quad \text{s.t.} \quad x \in \text{SpanningTreePolyhedron} \]
的最优解。因此，Dinkelbach算法实际上是在求解一系列线性规划（或等价的最小生成树问题）。
5. 举例说明
考虑一个小型图 \(V = \{1,2,3\}\)，边集 \(E = \{a=(1,2), b=(1,3), c=(2,3)\}\)，数据如下：
| 边 | 成本 \(c\) | 效益 \(t\) |
|---|---|---|
| a | 4 | 2 |
| b | 5 | 4 |
| c | 3 | 3 |
迭代过程（取 \(\epsilon = 0.001\)）：
- 初始化：\(\lambda_0 = 0\)。
- 迭代1：权重 \(w = c - 0 \cdot t = [4,5,3]\)。最小生成树选边 \(\{a,c\}\)（总权重 4+3=7）。
当前比值 \(r_0 = \frac{4+3}{2+3} = \frac{7}{5} = 1.4\)。
计算 \(F(0) = (4+3) - 0 \cdot (2+3) = 7 > 0\)，未收敛。 - 迭代2：\(\lambda_1 = 1.4\)。新权重：
\(w(a)=4-1.4\times2=1.2\)
\(w(b)=5-1.4\times4=-0.6\)
\(w(c)=3-1.4\times3=-1.2\)
最小生成树选边 \(\{b,c\}\)（总权重 -0.6-1.2=-1.8）。
当前比值 \(r_1 = \frac{5+3}{4+3} = \frac{8}{7} \approx 1.142857\)。
\(F(1.4) = -1.8 < 0\)，未收敛。 - 迭代3：\(\lambda_2 = 1.142857\)。新权重：
\(w(a)=4-1.142857\times2=1.714286\)
\(w(b)=5-1.142857\times4=0.428572\)
\(w(c)=3-1.142857\times3=-0.428571\)
最小生成树选边 \(\{a,b\}\)（总权重 1.714286+0.428572=2.142858）。
当前比值 \(r_2 = \frac{4+5}{2+4} = \frac{9}{6} = 1.5\)。
\(F(1.142857) = 2.142858 > 0\)，未收敛。 - 迭代4：\(\lambda_3 = 1.5\)。新权重：
\(w(a)=4-1.5\times2=1\)
\(w(b)=5-1.5\times4=-1\)
\(w(c)=3-1.5\times3=-1.5\)
最小生成树选边 \(\{b,c\}\)（总权重 -1-1.5=-2.5）。
当前比值 \(r_3 = \frac{5+3}{4+3} = \frac{8}{7} \approx 1.142857\)。
\(F(1.5) = -2.5 < 0\)，未收敛。
我们观察到比值在 \(1.142857\) 和 \(1.5\) 之间振荡？实际上我们需要检查精确解。
直接枚举三棵生成树：
- \(T_1 = \{a,b\}\): 比值 \(= 9/6 = 1.5\)。
- \(T_2 = \{a,c\}\): 比值 \(= 7/5 = 1.4\)。
- \(T_3 = \{b,c\}\): 比值 \(= 8/7 \approx 1.142857\)。
最优解为 \(T_3\)，比值 \(\lambda^* = 8/7\)。
算法应在迭代中收敛到此值。实际上，如果取 \(\lambda = 8/7\)，则权重为：
\(w(a)=4 - (8/7)\times2 = 12/7 \approx 1.714\),
\(w(b)=5 - (8/7)\times4 = 3/7 \approx 0.4286\),
\(w(c)=3 - (8/7)\times3 = -3/7 \approx -0.4286\)。
此时最小生成树可以是 \(T_3\) 或 \(T_2\)？需要比较：
\(T_3\) 总权重 \(= 3/7 - 3/7 = 0\)，
\(T_2\) 总权重 \(= 12/7 - 3/7 = 9/7 > 0\)，
\(T_1\) 总权重 \(= 12/7 + 3/7 = 15/7 > 0\)。
所以最小值为 \(T_3\)，且 \(F(8/7)=0\)。因此算法会收敛到 \(\lambda^*=8/7\)。
6. 算法收敛性说明
Dinkelbach算法本质上是一种牛顿法在分数规划上的应用。每次迭代更新 \(\lambda_{k+1} = \frac{c(T_k)}{t(T_k)}\) 相当于用当前解的实际比值作为新的猜测值。由于 \(F(\lambda)\) 是凹函数（在离散集合上），该算法通常会在很少的迭代次数内收敛（本例中若初始值合适，2-3次迭代即可）。
7. 总结
- 最小平均生成树是一个分数规划问题。
- Dinkelbach算法通过转化为一系列参数化的最小生成树问题来求解。
- 每一步参数化的最小生成树求解，相当于求解一个生成树多面体上的线性规划，但利用组合算法（Kruskal/Prim）更高效。
- 算法收敛快，且不涉及直接处理分数目标的非线性。
这种方法可推广到其他比值最小化问题，只要分母为正且子问题可在多项式时间内求解。