基于线性规划的“多商品流问题”建模与列生成算法求解示例
字数 4810 2025-12-15 18:35:51

基于线性规划的“多商品流问题”建模与列生成算法求解示例

题目描述

考虑一个由节点集合 \(V\) 和边集合 \(E\) 构成的有向图 \(G=(V,E)\)。图中每条边 \(e \in E\) 有容量 \(u_e \ge 0\)。现在有 \(K\) 种不同的商品（commodities），商品 \(k\) 的源点为 \(s_k\)，汇点为 \(t_k\)，需求量为 \(d_k > 0\)，即需要从 \(s_k\) 运送 \(d_k\) 单位的商品 \(k\) 到 \(t_k\)。所有商品共享图中的边容量，即每条边 \(e\) 上所有商品的流量总和不能超过 \(u_e\)。目标是寻找一个可行流，满足所有商品的需求，同时不违反边容量约束。该问题被称为多商品流问题（Multi-commodity Flow Problem, MCFP）。本题将展示如何用线性规划建模，并利用列生成算法求解其线性规划松弛。

解题步骤

1. 问题建模

  • 决策变量：设 \(f_e^k \ge 0\) 表示商品 \(k\) 在边 \(e\) 上的流量。
  • 目标：本题仅要求可行性，因此可设目标函数为常数（例如 0），但为列生成框架，可设最小化总流量或检查可行性。
  • 约束：
    1. 流量守恒：对每个商品 \(k\) 和每个节点 \(v \in V\)，有：

\[ \sum_{e \in \delta^+(v)} f_e^k - \sum_{e \in \delta^-(v)} f_e^k = \begin{cases} d_k, & \text{if } v = s_k, \\ -d_k, & \text{if } v = t_k, \\ 0, & \text{otherwise}. \end{cases} \]

 其中 $\delta^+(v)$ 和 $\delta^-(v)$ 分别表示从 $v$ 出发的边和进入 $v$ 的边。
  1. 容量约束：对每条边 \(e \in E\)，有：

\[ \sum_{k=1}^K f_e^k \le u_e. \]

  1. 非负约束：\(f_e^k \ge 0\)。

这个线性规划的规模是 \(O(K|E|)\) 个变量和 \(O(K|V| + |E|)\) 个约束。当图很大或商品数很多时，直接求解可能效率低。列生成可以通过隐式处理所有路径来降低问题规模。

2. 列生成建模思路

  • 对每个商品 \(k\)，考虑其所有从 \(s_k\) 到 \(t_k\) 的路径集合 \(\mathcal{P}_k\)。
  • 设变量 \(x_p \ge 0\) 表示商品 \(k\) 在路径 \(p \in \mathcal{P}_k\) 上发送的流量。
  • 则对商品 \(k\)，有需求约束：

\[ \sum_{p \in \mathcal{P}_k} x_p = d_k. \]

  • 容量约束：对每条边 \(e\)，有：

\[ \sum_{k=1}^K \sum_{p \in \mathcal{P}_k: e \in p} x_p \le u_e. \]

  • 主问题（Master Problem, MP）为：

\[ \begin{aligned} \min \quad & 0 \\ \text{s.t.} \quad & \sum_{p \in \mathcal{P}_k} x_p = d_k, \quad \forall k=1,\dots,K, \\ & \sum_{k=1}^K \sum_{p \in \mathcal{P}_k: e \in p} x_p \le u_e, \quad \forall e \in E, \\ & x_p \ge 0, \quad \forall p \in \mathcal{P}_k, k=1,\dots,K. \end{aligned} \]

由于路径数量巨大，不能显式列出所有变量。列生成从一部分路径（初始可行解）开始，通过求解子问题生成具有负检验数（即能改进目标）的新列（路径变量）。

3. 列生成步骤

  • 第一步：构建限制主问题（Restricted Master Problem, RMP）
    • 对每个商品 \(k\)，初始选取一组从 \(s_k\) 到 \(t_k\) 的路径（例如最短路径）构成集合 \(\mathcal{P}'_k \subset \mathcal{P}_k\)，确保 RMP 可行（例如，每条边容量足够大时，单用最短路径可满足需求）。
    • 用单纯形法求解 RMP，得到最优解和对偶变量值：
      • 对每个商品 \(k\)，需求约束的对偶变量记为 \(\pi_k\)。
      • 对每条边 \(e\)，容量约束的对偶变量记为 \(\lambda_e \le 0\)（因为是不等式约束 ≤）。
  • 第二步：子问题（定价问题）
    • 检验是否有不在 RMP 中的路径变量能降低目标（本题目标为常数 0，但单纯形法要求检验数非负才能最优）。变量 \(x_p\) 对应的检验数为：

\[ \bar{c}_p = 0 - \left( \pi_k + \sum_{e \in p} \lambda_e \right) = -\left( \pi_k + \sum_{e \in p} \lambda_e \right). \]

  • 由于变量 \(x_p\) 在单纯形法中要求检验数 ≥ 0 才最优，因此若存在路径 \(p\) 使 \(\bar{c}_p < 0\)，则可将该列加入 RMP。子问题为：对每个商品 \(k\)，找一条从 \(s_k\) 到 \(t_k\) 的路径 \(p\) 最小化 \(\pi_k + \sum_{e \in p} \lambda_e\)。
  • 因为 \(\pi_k\) 是常数，子问题等价于在边权为 \(w_e = \lambda_e\) 的图上求 \(s_k\) 到 \(t_k\) 的最短路（注意 \(\lambda_e \le 0\)，但最短路算法可处理负权重，只要无负环）。
  • 对每个商品 \(k\)，用最短路算法（如 Bellman-Ford，若所有权重非负则用 Dijkstra）找到最短路径 \(p_k^*\)，计算路径长度 \(L_k = \pi_k + \sum_{e \in p_k^*} w_e\)。若 \(L_k < 0\)，则对应检验数 \(\bar{c}_{p_k^*} = -L_k > 0\)? 等等，需要仔细检查符号。
    实际上，检验数 = 原始成本系数 - 对偶约束乘积和。原始成本系数为 0，对偶约束乘积和为 \(\pi_k + \sum_{e \in p} \lambda_e\)，所以检验数 = \(0 - (\pi_k + \sum_{e \in p} \lambda_e) = -(\pi_k + \sum_{e \in p} \lambda_e)\)。要使检验数 < 0，需 \(\pi_k + \sum_{e \in p} \lambda_e > 0\)。因为 \(\lambda_e \le 0\)，所以可转化为：若存在路径 \(p\) 使 \(\sum_{e \in p} (-\lambda_e) < -\pi_k\)，则检验数为负。等价地，定义边权 \(w_e' = -\lambda_e \ge 0\)，在图上找最短路，若最短路长度 \(< -\pi_k\)，则对应新列检验数为负，可加入 RMP。
  • 第三步：迭代
    • 将检验数为负的路径变量（可能多个商品）加入 RMP，重新求解 RMP，更新对偶变量，重复第二步。
    • 当所有商品的子问题中最短路径长度均 \(\ge -\pi_k\) 时，即无检验数为负的列，达到线性规划松弛的最优解。

4. 具体示例

考虑简单图：\(V=\{1,2,3,4\}, E=\{(1,2),(1,3),(2,4),(3,4),(2,3)\}\)，边容量均为 \(u_e=5\)。两种商品：商品1：\(s_1=1, t_1=4, d_1=3\)；商品2：\(s_2=2, t_2=4, d_2=4\)。

  • 初始化 RMP：为商品1选路径 \(p_1: 1 \rightarrow 2 \rightarrow 4\)，商品2选路径 \(p_2: 2 \rightarrow 4\)。初始 RMP 变量 \(x_{p_1}, x_{p_2}\)。
  • 需求约束：

\[ x_{p_1} = 3, \quad x_{p_2} = 4. \]

  • 容量约束：边(2,4)流量 \(x_{p_1}+x_{p_2}=7 > 5\)，不可行。说明需增加其他路径分散流量。因此初始 RMP 需更多列以保证可行性。可添加路径：商品1的 \(1 \rightarrow 3 \rightarrow 4\)，商品2的 \(2 \rightarrow 3 \rightarrow 4\)。这样 RMP 有 4 个变量，求解 RMP 得到初始可行解和对偶值。
  • 求解 RMP 后，得到对偶变量 \(\pi_1, \pi_2\) 和 \(\lambda_e \le 0\) 对于边 \(e \in E\)。为简便，假设当前对偶值：\(\pi_1 = -2, \pi_2 = -1, \lambda_{(2,4)}=-0.5, \lambda_{(1,2)}=0, \lambda_{(1,3)}=0, \lambda_{(3,4)}=0, \lambda_{(2,3)}=0\)。
  • 子问题：对商品1，边权 \(w_e' = -\lambda_e \ge 0\)，计算最短路。从1到4：路径 \(1\rightarrow2\rightarrow4\) 长度 = \(0+0.5=0.5\)，路径 \(1\rightarrow3\rightarrow4\) 长度 = 0，路径 \(1\rightarrow2\rightarrow3\rightarrow4\) 长度 = 0+0+0=0。最短路长为 0，与 \(-\pi_1=2\) 比较，0 < 2，所以检验数 = 0 - ( (-2) + 路径的λ和 )？用公式：检验数 = \(-(\pi_k + \sum_{e \in p} \lambda_e)\)。对路径 \(1\rightarrow3\rightarrow4\)，\(\sum \lambda_e = 0\)，检验数 = \(-(-2+0)=2>0\)，但这是正的，说明该列已基本最优方向？等等，我们需要检验数为负的列。计算其他路径：对商品1，路径 \(1\rightarrow2\rightarrow3\rightarrow4\)，\(\sum \lambda_e = 0+0+0=0\)，检验数 = 2，同样非负。商品2的最短路检查类似。若无负检验数列，则当前解最优。

5. 最终结果

通过列生成迭代，最终得到线性规划松弛的最优解，各路径流量分配满足需求和容量约束。此方法可高效处理大规模多商品流问题，因为每次只需解决小规模 RMP 和多个最短路子问题。若需要整数解，可在列生成框架内结合分支定价（branch-and-price）进行整数规划求解。

关键点总结

  • 多商品流问题的线性规划模型变量多，列生成利用路径变量建模，主问题规模小。
  • 子问题转化为最短路问题，高效生成改进列。
  • 算法迭代直到无负检验数列，得到线性规划松弛最优解。
基于线性规划的“多商品流问题”建模与列生成算法求解示例 题目描述 考虑一个由节点集合 \(V\) 和边集合 \(E\) 构成的有向图 \(G=(V,E)\)。图中每条边 \(e \in E\) 有容量 \(u_ e \ge 0\)。现在有 \(K\) 种不同的商品（commodities），商品 \(k\) 的源点为 \(s_ k\)，汇点为 \(t_ k\)，需求量为 \(d_ k > 0\)，即需要从 \(s_ k\) 运送 \(d_ k\) 单位的商品 \(k\) 到 \(t_ k\)。所有商品共享图中的边容量，即每条边 \(e\) 上所有商品的流量总和不能超过 \(u_ e\)。目标是寻找一个可行流，满足所有商品的需求，同时不违反边容量约束。该问题被称为 多商品流问题（Multi-commodity Flow Problem, MCFP） 。本题将展示如何用线性规划建模，并利用 列生成算法 求解其线性规划松弛。 解题步骤 1. 问题建模 决策变量：设 \(f_ e^k \ge 0\) 表示商品 \(k\) 在边 \(e\) 上的流量。 目标：本题仅要求可行性，因此可设目标函数为常数（例如 0），但为列生成框架，可设最小化总流量或检查可行性。 约束： 流量守恒 ：对每个商品 \(k\) 和每个节点 \(v \in V\)，有： \[ \sum_ {e \in \delta^+(v)} f_ e^k - \sum_ {e \in \delta^-(v)} f_ e^k = \begin{cases} d_ k, & \text{if } v = s_ k, \\ -d_ k, & \text{if } v = t_ k, \\ 0, & \text{otherwise}. \end{cases} \] 其中 \(\delta^+(v)\) 和 \(\delta^-(v)\) 分别表示从 \(v\) 出发的边和进入 \(v\) 的边。 容量约束 ：对每条边 \(e \in E\)，有： \[ \sum_ {k=1}^K f_ e^k \le u_ e. \] 非负约束 ：\(f_ e^k \ge 0\)。 这个线性规划的规模是 \(O(K|E|)\) 个变量和 \(O(K|V| + |E|)\) 个约束。当图很大或商品数很多时，直接求解可能效率低。列生成可以通过隐式处理所有路径来降低问题规模。 2. 列生成建模思路 对每个商品 \(k\)，考虑其所有从 \(s_ k\) 到 \(t_ k\) 的路径集合 \(\mathcal{P}_ k\)。 设变量 \(x_ p \ge 0\) 表示商品 \(k\) 在路径 \(p \in \mathcal{P}_ k\) 上发送的流量。 则对商品 \(k\)，有需求约束： \[ \sum_ {p \in \mathcal{P}_ k} x_ p = d_ k. \] 容量约束：对每条边 \(e\)，有： \[ \sum_ {k=1}^K \sum_ {p \in \mathcal{P}_ k: e \in p} x_ p \le u_ e. \] 主问题（Master Problem, MP）为： \[ \begin{aligned} \min \quad & 0 \\ \text{s.t.} \quad & \sum_ {p \in \mathcal{P} k} x_ p = d_ k, \quad \forall k=1,\dots,K, \\ & \sum {k=1}^K \sum_ {p \in \mathcal{P}_ k: e \in p} x_ p \le u_ e, \quad \forall e \in E, \\ & x_ p \ge 0, \quad \forall p \in \mathcal{P}_ k, k=1,\dots,K. \end{aligned} \] 由于路径数量巨大，不能显式列出所有变量。列生成从一部分路径（初始可行解）开始，通过求解子问题生成具有负检验数（即能改进目标）的新列（路径变量）。 3. 列生成步骤 第一步：构建限制主问题（Restricted Master Problem, RMP） 对每个商品 \(k\)，初始选取一组从 \(s_ k\) 到 \(t_ k\) 的路径（例如最短路径）构成集合 \(\mathcal{P}'_ k \subset \mathcal{P}_ k\)，确保 RMP 可行（例如，每条边容量足够大时，单用最短路径可满足需求）。 用单纯形法求解 RMP，得到最优解和对偶变量值： 对每个商品 \(k\)，需求约束的对偶变量记为 \(\pi_ k\)。 对每条边 \(e\)，容量约束的对偶变量记为 \(\lambda_ e \le 0\)（因为是不等式约束 ≤）。 第二步：子问题（定价问题） 检验是否有不在 RMP 中的路径变量能降低目标（本题目标为常数 0，但单纯形法要求检验数非负才能最优）。变量 \(x_ p\) 对应的检验数为： \[ \bar{c} p = 0 - \left( \pi_ k + \sum {e \in p} \lambda_ e \right) = -\left( \pi_ k + \sum_ {e \in p} \lambda_ e \right). \] 由于变量 \(x_ p\) 在单纯形法中要求检验数 ≥ 0 才最优，因此若存在路径 \(p\) 使 \(\bar{c} p < 0\)，则可将该列加入 RMP。子问题为：对每个商品 \(k\)，找一条从 \(s_ k\) 到 \(t_ k\) 的路径 \(p\) 最小化 \( \pi_ k + \sum {e \in p} \lambda_ e \)。 因为 \(\pi_ k\) 是常数，子问题等价于在边权为 \(w_ e = \lambda_ e\) 的图上求 \(s_ k\) 到 \(t_ k\) 的最短路（注意 \(\lambda_ e \le 0\)，但最短路算法可处理负权重，只要无负环）。 对每个商品 \(k\)，用最短路算法（如 Bellman-Ford，若所有权重非负则用 Dijkstra）找到最短路径 \(p_ k^ \)，计算路径长度 \(L_ k = \pi_ k + \sum_ {e \in p_ k^ } w_ e\)。若 \(L_ k < 0\)，则对应检验数 \(\bar{c} {p_ k^* } = -L_ k > 0\)? 等等，需要仔细检查符号。 实际上，检验数 = 原始成本系数 - 对偶约束乘积和。原始成本系数为 0，对偶约束乘积和为 \(\pi_ k + \sum {e \in p} \lambda_ e\)，所以检验数 = \(0 - (\pi_ k + \sum_ {e \in p} \lambda_ e) = -(\pi_ k + \sum_ {e \in p} \lambda_ e)\)。要使检验数 < 0，需 \(\pi_ k + \sum_ {e \in p} \lambda_ e > 0\)。因为 \(\lambda_ e \le 0\)，所以可转化为：若存在路径 \(p\) 使 \(\sum_ {e \in p} (-\lambda_ e) < -\pi_ k\)，则检验数为负。等价地，定义边权 \(w_ e' = -\lambda_ e \ge 0\)，在图上找最短路，若最短路长度 \(< -\pi_ k\)，则对应新列检验数为负，可加入 RMP。 第三步：迭代 将检验数为负的路径变量（可能多个商品）加入 RMP，重新求解 RMP，更新对偶变量，重复第二步。 当所有商品的子问题中最短路径长度均 \(\ge -\pi_ k\) 时，即无检验数为负的列，达到线性规划松弛的最优解。 4. 具体示例 考虑简单图：\(V=\{1,2,3,4\}, E=\{(1,2),(1,3),(2,4),(3,4),(2,3)\}\)，边容量均为 \(u_ e=5\)。两种商品：商品1：\(s_ 1=1, t_ 1=4, d_ 1=3\)；商品2：\(s_ 2=2, t_ 2=4, d_ 2=4\)。 初始化 RMP：为商品1选路径 \(p_ 1: 1 \rightarrow 2 \rightarrow 4\)，商品2选路径 \(p_ 2: 2 \rightarrow 4\)。初始 RMP 变量 \(x_ {p_ 1}, x_ {p_ 2}\)。 需求约束： \[ x_ {p_ 1} = 3, \quad x_ {p_ 2} = 4. \] 容量约束：边(2,4)流量 \(x_ {p_ 1}+x_ {p_ 2}=7 > 5\)，不可行。说明需增加其他路径分散流量。因此初始 RMP 需更多列以保证可行性。可添加路径：商品1的 \(1 \rightarrow 3 \rightarrow 4\)，商品2的 \(2 \rightarrow 3 \rightarrow 4\)。这样 RMP 有 4 个变量，求解 RMP 得到初始可行解和对偶值。 求解 RMP 后，得到对偶变量 \(\pi_ 1, \pi_ 2\) 和 \(\lambda_ e \le 0\) 对于边 \(e \in E\)。为简便，假设当前对偶值：\(\pi_ 1 = -2, \pi_ 2 = -1, \lambda_ {(2,4)}=-0.5, \lambda_ {(1,2)}=0, \lambda_ {(1,3)}=0, \lambda_ {(3,4)}=0, \lambda_ {(2,3)}=0\)。 子问题：对商品1，边权 \(w_ e' = -\lambda_ e \ge 0\)，计算最短路。从1到4：路径 \(1\rightarrow2\rightarrow4\) 长度 = \(0+0.5=0.5\)，路径 \(1\rightarrow3\rightarrow4\) 长度 = 0，路径 \(1\rightarrow2\rightarrow3\rightarrow4\) 长度 = 0+0+0=0。最短路长为 0，与 \(-\pi_ 1=2\) 比较，0 < 2，所以检验数 = 0 - ( (-2) + 路径的λ和 )？用公式：检验数 = \(-(\pi_ k + \sum_ {e \in p} \lambda_ e)\)。对路径 \(1\rightarrow3\rightarrow4\)，\(\sum \lambda_ e = 0\)，检验数 = \(-(-2+0)=2>0\)，但这是正的，说明该列已基本最优方向？等等，我们需要检验数为负的列。计算其他路径：对商品1，路径 \(1\rightarrow2\rightarrow3\rightarrow4\)，\(\sum \lambda_ e = 0+0+0=0\)，检验数 = 2，同样非负。商品2的最短路检查类似。若无负检验数列，则当前解最优。 5. 最终结果 通过列生成迭代，最终得到线性规划松弛的最优解，各路径流量分配满足需求和容量约束。此方法可高效处理大规模多商品流问题，因为每次只需解决小规模 RMP 和多个最短路子问题。若需要整数解，可在列生成框架内结合分支定价（branch-and-price）进行整数规划求解。 关键点总结 多商品流问题的线性规划模型变量多，列生成利用路径变量建模，主问题规模小。 子问题转化为最短路问题，高效生成改进列。 算法迭代直到无负检验数列，得到线性规划松弛最优解。