列生成算法在炼油厂生产计划优化问题中的应用示例
字数 1416 2025-11-02 00:38:37

列生成算法在炼油厂生产计划优化问题中的应用示例

题目描述
炼油厂需要制定一个月的生产计划，将不同品质的原油（如轻质、中质、重质原油）通过蒸馏、裂解、混合等加工过程，转化为汽油、柴油、航空燃油等成品油。每种原油的采购成本、加工能力、成品油市场需求和价格均已知。目标是在满足设备产能和市场需求约束下，最大化总利润（销售收入减成本）。由于可能的加工方案组合极多（例如不同原油配比、加工路径），直接枚举所有变量会导致问题规模过大，需用列生成算法动态生成有价值的加工方案（即列）。

解题过程

  1. 问题建模为线性规划
    • 设炼油厂有 \(K\) 种加工装置（如蒸馏塔、裂解器），每种装置有最大处理能力 \(C_k\)。
    • 成品油有 \(M\) 种，每种有市场需求上限 \(D_m\) 和价格 \(p_m\)。
    • 可能的加工方案称为"列"，每个列 \(j\) 代表一种具体的生产模式：
      • 消耗的原油类型和量 \(a_{ij}\)（\(i\) 为原油种类）
      • 各装置占用时长 \(b_{kj}\)
      • 产出的成品油量 \(q_{mj}\)
    • 变量 \(x_j\) 表示采用方案 \(j\) 的频次（如加工批次），目标函数为：

\[ \max \sum_j \left( \sum_m p_m q_{mj} - \sum_i \text{原油成本} \cdot a_{ij} \right) x_j \]

 约束包括装置能力 $ \sum_j b_{kj} x_j \leq C_k $、市场需求 $ \sum_j q_{mj} x_j \leq D_m $、非负性 $ x_j \geq 0 $。
  1. 构造限制主问题（RMP）
    • 初始时仅包含少数可行列（如简单蒸馏方案），RMP 形式为：

\[ \max \{ c^T x : Ax \leq b, x \geq 0 \} \]

 其中 $ A $ 包含 $ b_{kj} $、$ q_{mj} $ 等系数，$ b $ 为设备能力和需求约束。
  1. 定价子问题（生成新列）
    • 求解 RMP 得到对偶变量 \(\pi_k\)（装置能力影子价格）和 \(\mu_m\)（市场需求影子价格）。
    • 子问题目标是找到减少成本（即检验数 \(c_j - \pi^T A_j\)）最小的新列 \(j\)：

\[ \min \left\{ \text{原油成本} - \sum_m p_m q_m + \sum_k \pi_k b_k - \sum_m \mu_m q_m \right\} \]

  • 子问题实为寻找最优加工路径：在原油选择、装置分配、产出比例等约束下优化上述目标，可建模为网络流或混合整数规划问题。

  1. 迭代求解

    • 若子问题找到检验数为负的列（可提升目标），将其加入 RMP 重新求解。
    • 若无负检验数列，当前 RMP 解即原问题最优解。

  2. 实际应用细节

    • 炼油加工常涉及非线性收率（如产出随原油品质变化），需用分段线性化近似。
    • 列生成可能陷入“尾效应”（后期改进缓慢），可设置收敛阈值提前终止。

关键点总结

  • 列生成通过分解问题，避免枚举所有可能方案。
  • 子问题设计需结合炼油工艺约束（如装置串联关系、收率模型）。
  • 该方法是 Exxon、Shell 等公司生产计划系统的核心算法之一。
列生成算法在炼油厂生产计划优化问题中的应用示例 题目描述 炼油厂需要制定一个月的生产计划，将不同品质的原油（如轻质、中质、重质原油）通过蒸馏、裂解、混合等加工过程，转化为汽油、柴油、航空燃油等成品油。每种原油的采购成本、加工能力、成品油市场需求和价格均已知。目标是在满足设备产能和市场需求约束下，最大化总利润（销售收入减成本）。由于可能的加工方案组合极多（例如不同原油配比、加工路径），直接枚举所有变量会导致问题规模过大，需用列生成算法动态生成有价值的加工方案（即列）。 解题过程 问题建模为线性规划 设炼油厂有 \( K \) 种加工装置（如蒸馏塔、裂解器），每种装置有最大处理能力 \( C_ k \)。 成品油有 \( M \) 种，每种有市场需求上限 \( D_ m \) 和价格 \( p_ m \)。 可能的加工方案称为"列"，每个列 \( j \) 代表一种具体的生产模式： 消耗的原油类型和量 \( a_ {ij} \)（\( i \) 为原油种类） 各装置占用时长 \( b_ {kj} \) 产出的成品油量 \( q_ {mj} \) 变量 \( x_ j \) 表示采用方案 \( j \) 的频次（如加工批次），目标函数为： \[ \max \sum_ j \left( \sum_ m p_ m q_ {mj} - \sum_ i \text{原油成本} \cdot a_ {ij} \right) x_ j \] 约束包括装置能力 \( \sum_ j b_ {kj} x_ j \leq C_ k \)、市场需求 \( \sum_ j q_ {mj} x_ j \leq D_ m \)、非负性 \( x_ j \geq 0 \)。 构造限制主问题（RMP） 初始时仅包含少数可行列（如简单蒸馏方案），RMP 形式为： \[ \max \{ c^T x : Ax \leq b, x \geq 0 \} \] 其中 \( A \) 包含 \( b_ {kj} \)、\( q_ {mj} \) 等系数，\( b \) 为设备能力和需求约束。 定价子问题（生成新列） 求解 RMP 得到对偶变量 \( \pi_ k \)（装置能力影子价格）和 \( \mu_ m \)（市场需求影子价格）。 子问题目标是找到减少成本（即检验数 \( c_ j - \pi^T A_ j \)）最小的新列 \( j \)： \[ \min \left\{ \text{原油成本} - \sum_ m p_ m q_ m + \sum_ k \pi_ k b_ k - \sum_ m \mu_ m q_ m \right\} \] 子问题实为寻找最优加工路径：在原油选择、装置分配、产出比例等约束下优化上述目标，可建模为网络流或混合整数规划问题。 迭代求解 若子问题找到检验数为负的列（可提升目标），将其加入 RMP 重新求解。 若无负检验数列，当前 RMP 解即原问题最优解。 实际应用细节 炼油加工常涉及非线性收率（如产出随原油品质变化），需用分段线性化近似。 列生成可能陷入“尾效应”（后期改进缓慢），可设置收敛阈值提前终止。 关键点总结 列生成通过分解问题，避免枚举所有可能方案。 子问题设计需结合炼油工艺约束（如装置串联关系、收率模型）。 该方法是 Exxon、Shell 等公司生产计划系统的核心算法之一。