列生成算法在供应链网络设计问题中的应用示例

字数 4111 2025-10-27 17:41:11

列生成算法在供应链网络设计问题中的应用示例

题目描述
考虑一个供应链网络设计问题：某公司需要为其新产品建立分销网络。有多个潜在工厂选址（供应点）和多个分销中心选址（需求点）。每个潜在工厂有一个固定的开设成本，以及一个最大生产能力限制。每个分销中心有一个已知的产品需求量。从任一工厂到任一分销中心都存在一个单位运输成本。公司的目标是：决定开设哪些工厂，以及如何安排从开设的工厂到分销中心的运输流，才能在满足所有分销中心需求的前提下，使总成本（固定开设成本 + 运输成本）最小。

解题过程

问题建模（主问题 - Master Problem）
这是一个典型的带固定费用的网络流问题，可以建模成一个大规模的混合整数线性规划（MILP）。其紧凑模型（Compact Formulation）如下：
- 集合：
  - \(I\)：潜在工厂的集合。
  - \(J\)：分销中心的集合。
- 参数：
  - \(f_i\)：开设工厂 \(i\) 的固定成本。
  - \(s_i\)：工厂 \(i\) 的最大生产能力。
  - \(d_j\)：分销中心 \(j\) 的需求量。
  - \(c_{ij}\)：从工厂 \(i\) 到分销中心 \(j\) 的单位运输成本。
- 决策变量：
  - \(y_i \in \{0, 1\}\)：如果工厂 \(i\) 被开设，则为 1；否则为 0。
  - \(x_{ij} \ge 0\)：从工厂 \(i\) 运往分销中心 \(j\) 的产品数量。
- 目标函数：最小化总成本。

\[ \min \sum_{i \in I} f_i y_i + \sum_{i \in I} \sum_{j \in J} c_{ij} x_{ij} \]

*   **约束条件**：
    1.  **需求约束**：每个分销中心的需求必须被满足。

\[ \sum_{i \in I} x_{ij} = d_j, \quad \forall j \in J \]

    2.  **供应/产能约束**：从任何工厂运出的总量不能超过其产能，且只有开设的工厂才能供货。

\[ \sum_{j \in J} x_{ij} \le s_i y_i, \quad \forall i \in I \]

    3.  **逻辑约束**：

\[ x_{ij} \ge 0, \quad y_i \in \{0,1\} \]

当工厂和分销中心数量很大时，这个模型中的变量 $ x_{ij} $ 会非常多（|I| x |J|），直接求解可能非常困难。列生成算法通过分解问题来应对这种规模。

分解与重构（Dantzig-Wolfe 分解）
列生成算法的核心思想是将原问题分解为一个主问题（Master Problem, MP） 和一个或多个子问题（Subproblem, SP）。
- 分解视角：我们可以将原问题看作是为每个工厂 \(i\) 选择一个“运营模式”或“配送方案”。一个针对工厂 \(i\) 的配送方案 \(p\) 定义了它如何满足各个分销中心的需求，即一个非负的运输向量 \((x_{ij}^p)_{j \in J}\)，并且满足 \(\sum_{j} x_{ij}^p \le s_i\)（即方案本身是可行的）。
- 重构主问题（RMP）：我们用这些“配送方案”来重新表述原问题。令 \(P_i\) 为工厂 \(i\) 所有可能的可行配送方案的集合。
  - 新决策变量：\(\lambda_{ip} \in \{0, 1\}\)，如果为工厂 \(i\) 选择方案 \(p\)，则其为 1。
  - 方案的成本：一个方案的成本包括固定成本（如果该方案被选中，即工厂被开设）和运输成本。方案 \(p\) 对于工厂 \(i\) 的总成本为 \(f_i + \sum_{j \in J} c_{ij} x_{ij}^p\)。
  - 重构后的主问题（RMP）：

\[ \min \sum_{i \in I} \sum_{p \in P_i} (f_i + \sum_{j \in J} c_{ij} x_{ij}^p) \lambda_{ip} \]

\[ \text{s.t.} \quad \sum_{i \in I} \sum_{p \in P_i} x_{ij}^p \lambda_{ip} = d_j, \quad \forall j \in J \quad \text{(需求约束)} \]

\[ \sum_{p \in P_i} \lambda_{ip} \le 1, \quad \forall i \in I \quad \text{(每个工厂至多选择一个方案)} \]

\[ \lambda_{ip} \in \{0,1\}, \quad \forall i \in I, \forall p \in P_i \]

    这个RMP的变量数量是天文数字（因为 $ P_i $ 是巨大的集合），我们无法显式地列出所有变量（列）。

列生成算法流程
算法从一个简化的、只包含少量初始方案的限制性主问题（Restricted Master Problem, RMP） 开始，通过解决子问题来寻找可以改进当前解的新列（方案），并将其加入RMP，迭代求解。
- 步骤 1：初始化
  为每个工厂 \(i\) 生成一个或多个简单的初始可行方案，构成初始的列集合 \(\overline{P_i}\)（例如，一个“什么都不做”的方案，或者一个只服务最近分销中心的简单方案）。用这些有限的列构建最初的RMP。通常，我们会先求解RMP的线性规划松弛（LP Relaxation），即把 \(\lambda_{ip} \in \{0,1\}\) 松弛为 \(\lambda_{ip} \ge 0\)。
- 步骤 2：求解限制性主问题（RMP）
  求解当前RMP的LP松弛。设求解后得到：
  - 最优解 \(\lambda^*\)。
  - 与需求约束（对偶变量） \(\pi_j\)：这是满足分销中心 \(j\) 一个单位需求所带来的“价值”或“节省”。
- 步骤 3：定价子问题（Pricing Subproblem）
  我们需要检查是否存在不在当前RMP中的列（即方案），如果将其加入RMP，可以降低总成本。这通过计算列的检验数（Reduced Cost） 来判断。
  - 对于工厂 \(i\)，一个新方案 \(p\) 的检验数 \(\overline{c}_{ip}\) 为：

\[ \overline{c}_{ip} = (f_i + \sum_{j \in J} c_{ij} x_{ij}^p) - \sum_{j \in J} \pi_j x_{ij}^p \]

        这个公式可以重新组织为：

\[ \overline{c}_{ip} = f_i + \sum_{j \in J} (c_{ij} - \pi_j) x_{ij}^p \]

    *   **定价子问题**：对于**每个工厂 $ i $**，我们需要解决以下优化问题，寻找检验数最小的新方案：

\[ \min \quad f_i + \sum_{j \in J} (c_{ij} - \pi_j) x_{ij} \]

\[ \text{s.t.} \quad \sum_{j \in J} x_{ij} \le s_i \quad \text{(产能约束)} \]

\[ x_{ij} \ge 0, \quad \forall j \in J \]

    注意，$ f_i $ 是常数。这个子问题本质上是一个**连续背包问题**。其最优解很容易求得：因为变量 $ x_{ij} $ 是连续的，我们只需将所有“净收益” $ (\pi_j - c_{ij}) $ 为正的分销中心按照该比值从高到低排序，并尽可能多地用产能 $ s_i $ 去满足这些需求，直到产能用尽或没有正收益的需求为止。这个最优解就对应了一个新的潜在配送方案。

*   **步骤 4：判断最优性 & 添加新列**
    *   对于某个工厂 $ i $，如果其子问题的最优值（即 $ \min \overline{c}_{ip} $ ）**小于 0**（在最小化问题中，检验数为负的列是有吸引力的），那么我们就找到了一个能改进当前解的新列（方案）。
    *   我们将这个新方案 $ p^* $（即子问题的最优解 $ x_{ij}^* $）作为一个新列加入到RMP中（变量 $ \lambda_{ip^*} $）。
    *   如果**所有工厂 $ i $ 对应的子问题的最优值都大于等于 0**，则说明当前RMP的LP松弛解已经是最优的，没有能改进目标函数的新列了。列生成过程结束。

*   **步骤 5：迭代**
    回到步骤 2，用更新后的列集合求解新的RMP，然后再次进行定价、判断和添加新列的过程。

*   **步骤 6：获得整数解**
    上述过程求解的是主问题的LP松弛。当列生成过程收敛后，我们得到了一个包含相对较少列但能代表原问题LP松弛最优解的RMP。最后，我们需要**恢复整数约束**，即在这个最终的RMP上，将变量 $ \lambda_{ip} $ 的约束改回 $ \lambda_{ip} \in \{0,1\} $，然后使用分支定界法等MILP求解器来求解这个规模已经大大减小的整数规划问题，从而得到原供应链网络设计问题的整数最优解（或高质量可行解）。

总结
列生成算法通过分解思想，将庞大的原问题转化为一个不断扩展的“主问题”和一系列简单的“子问题”。主问题负责协调全局资源分配，子问题负责生成局部改进方案。通过迭代求解，算法可以避免同时处理所有变量，从而高效地求解大规模整数规划问题，特别适用于像供应链网络设计这种具有可分解结构的组合优化问题。

列生成算法在供应链网络设计问题中的应用示例题目描述考虑一个供应链网络设计问题：某公司需要为其新产品建立分销网络。有多个潜在工厂选址（供应点）和多个分销中心选址（需求点）。每个潜在工厂有一个固定的开设成本，以及一个最大生产能力限制。每个分销中心有一个已知的产品需求量。从任一工厂到任一分销中心都存在一个单位运输成本。公司的目标是：决定开设哪些工厂，以及如何安排从开设的工厂到分销中心的运输流，才能在满足所有分销中心需求的前提下，使总成本（固定开设成本 + 运输成本）最小。解题过程问题建模（主问题 - Master Problem）这是一个典型的带固定费用的网络流问题，可以建模成一个大规模的混合整数线性规划（MILP）。其紧凑模型（Compact Formulation）如下：集合： \( I \)：潜在工厂的集合。 \( J \)：分销中心的集合。参数： \( f_ i \)：开设工厂 \( i \) 的固定成本。 \( s_ i \)：工厂 \( i \) 的最大生产能力。 \( d_ j \)：分销中心 \( j \) 的需求量。 \( c_ {ij} \)：从工厂 \( i \) 到分销中心 \( j \) 的单位运输成本。决策变量： \( y_ i \in \{0, 1\} \)：如果工厂 \( i \) 被开设，则为 1；否则为 0。 \( x_ {ij} \ge 0 \)：从工厂 \( i \) 运往分销中心 \( j \) 的产品数量。目标函数：最小化总成本。 \[ \min \sum_ {i \in I} f_ i y_ i + \sum_ {i \in I} \sum_ {j \in J} c_ {ij} x_ {ij} \] 约束条件：需求约束：每个分销中心的需求必须被满足。 \[ \sum_ {i \in I} x_ {ij} = d_ j, \quad \forall j \in J \] 供应/产能约束：从任何工厂运出的总量不能超过其产能，且只有开设的工厂才能供货。 \[ \sum_ {j \in J} x_ {ij} \le s_ i y_ i, \quad \forall i \in I \] 逻辑约束： \[ x_ {ij} \ge 0, \quad y_ i \in \{0,1\} \] 当工厂和分销中心数量很大时，这个模型中的变量 \( x_ {ij} \) 会非常多（|I| x |J|），直接求解可能非常困难。列生成算法通过分解问题来应对这种规模。分解与重构（Dantzig-Wolfe 分解）列生成算法的核心思想是将原问题分解为一个主问题（Master Problem, MP）和一个或多个子问题（Subproblem, SP）。分解视角：我们可以将原问题看作是为每个工厂 \( i \) 选择一个“运营模式”或“配送方案”。一个针对工厂 \( i \) 的配送方案 \( p \) 定义了它如何满足各个分销中心的需求，即一个非负的运输向量 \( (x_ {ij}^p) {j \in J} \)，并且满足 \( \sum {j} x_ {ij}^p \le s_ i \)（即方案本身是可行的）。重构主问题（RMP）：我们用这些“配送方案”来重新表述原问题。令 \( P_ i \) 为工厂 \( i \) 所有可能的可行配送方案的集合。新决策变量：\( \lambda_ {ip} \in \{0, 1\} \)，如果为工厂 \( i \) 选择方案 \( p \)，则其为 1。方案的成本：一个方案的成本包括固定成本（如果该方案被选中，即工厂被开设）和运输成本。方案 \( p \) 对于工厂 \( i \) 的总成本为 \( f_ i + \sum_ {j \in J} c_ {ij} x_ {ij}^p \)。重构后的主问题（RMP）： \[ \min \sum_ {i \in I} \sum_ {p \in P_ i} (f_ i + \sum_ {j \in J} c_ {ij} x_ {ij}^p) \lambda_ {ip} \] \[ \text{s.t.} \quad \sum_ {i \in I} \sum_ {p \in P_ i} x_ {ij}^p \lambda_ {ip} = d_ j, \quad \forall j \in J \quad \text{(需求约束)} \] \[ \sum_ {p \in P_ i} \lambda_ {ip} \le 1, \quad \forall i \in I \quad \text{(每个工厂至多选择一个方案)} \] \[ \lambda_ {ip} \in \{0,1\}, \quad \forall i \in I, \forall p \in P_ i \] 这个RMP的变量数量是天文数字（因为 \( P_ i \) 是巨大的集合），我们无法显式地列出所有变量（列）。列生成算法流程算法从一个简化的、只包含少量初始方案的限制性主问题（Restricted Master Problem, RMP）开始，通过解决子问题来寻找可以改进当前解的新列（方案），并将其加入RMP，迭代求解。步骤 1：初始化为每个工厂 \( i \) 生成一个或多个简单的初始可行方案，构成初始的列集合 \( \overline{P_ i} \)（例如，一个“什么都不做”的方案，或者一个只服务最近分销中心的简单方案）。用这些有限的列构建最初的RMP。通常，我们会先求解RMP的线性规划松弛（LP Relaxation），即把 \( \lambda_ {ip} \in \{0,1\} \) 松弛为 \( \lambda_ {ip} \ge 0 \)。步骤 2：求解限制性主问题（RMP）求解当前RMP的LP松弛。设求解后得到：最优解 \( \lambda^* \)。与需求约束（对偶变量） \( \pi_ j \)：这是满足分销中心 \( j \) 一个单位需求所带来的“价值”或“节省”。步骤 3：定价子问题（Pricing Subproblem）我们需要检查是否存在不在当前RMP中的列（即方案），如果将其加入RMP，可以降低总成本。这通过计算列的检验数（Reduced Cost）来判断。对于工厂 \( i \)，一个新方案 \( p \) 的检验数 \( \overline{c} {ip} \) 为： \[ \overline{c} {ip} = (f_ i + \sum_ {j \in J} c_ {ij} x_ {ij}^p) - \sum_ {j \in J} \pi_ j x_ {ij}^p \] 这个公式可以重新组织为： \[ \overline{c} {ip} = f_ i + \sum {j \in J} (c_ {ij} - \pi_ j) x_ {ij}^p \] 定价子问题：对于每个工厂 \( i \) ，我们需要解决以下优化问题，寻找检验数最小的新方案： \[ \min \quad f_ i + \sum_ {j \in J} (c_ {ij} - \pi_ j) x_ {ij} \] \[ \text{s.t.} \quad \sum_ {j \in J} x_ {ij} \le s_ i \quad \text{(产能约束)} \] \[ x_ {ij} \ge 0, \quad \forall j \in J \] 注意，\( f_ i \) 是常数。这个子问题本质上是一个连续背包问题。其最优解很容易求得：因为变量 \( x_ {ij} \) 是连续的，我们只需将所有“净收益” \( (\pi_ j - c_ {ij}) \) 为正的分销中心按照该比值从高到低排序，并尽可能多地用产能 \( s_ i \) 去满足这些需求，直到产能用尽或没有正收益的需求为止。这个最优解就对应了一个新的潜在配送方案。步骤 4：判断最优性 & 添加新列对于某个工厂 \( i \)，如果其子问题的最优值（即 \( \min \overline{c}_ {ip} \) ）小于 0 （在最小化问题中，检验数为负的列是有吸引力的），那么我们就找到了一个能改进当前解的新列（方案）。我们将这个新方案 \( p^* \)（即子问题的最优解 \( x_ {ij}^* \)）作为一个新列加入到RMP中（变量 \( \lambda_ {ip^* } \)）。如果所有工厂 \( i \) 对应的子问题的最优值都大于等于 0 ，则说明当前RMP的LP松弛解已经是最优的，没有能改进目标函数的新列了。列生成过程结束。步骤 5：迭代回到步骤 2，用更新后的列集合求解新的RMP，然后再次进行定价、判断和添加新列的过程。步骤 6：获得整数解上述过程求解的是主问题的LP松弛。当列生成过程收敛后，我们得到了一个包含相对较少列但能代表原问题LP松弛最优解的RMP。最后，我们需要恢复整数约束，即在这个最终的RMP上，将变量 \( \lambda_ {ip} \) 的约束改回 \( \lambda_ {ip} \in \{0,1\} \)，然后使用分支定界法等MILP求解器来求解这个规模已经大大减小的整数规划问题，从而得到原供应链网络设计问题的整数最优解（或高质量可行解）。总结列生成算法通过分解思想，将庞大的原问题转化为一个不断扩展的“主问题”和一系列简单的“子问题”。主问题负责协调全局资源分配，子问题负责生成局部改进方案。通过迭代求解，算法可以避免同时处理所有变量，从而高效地求解大规模整数规划问题，特别适用于像供应链网络设计这种具有可分解结构的组合优化问题。