基于线性规划的Dantzig-Wolfe分解算法求解示例
字数 3077 2025-10-27 08:13:39

基于线性规划的Dantzig-Wolfe分解算法求解示例

题目描述
考虑一个生产计划问题：某公司有两个工厂（工厂1和工厂2）生产两种产品（产品A和产品B）。每个工厂有独立的生产能力约束（如工时、原料限制），但公司需满足整体市场需求（如产品A至少100单位，产品B至少150单位），并最小化总生产成本。该问题的约束可分为两类：工厂的局部生产能力约束（每个工厂独立）和公司的全局市场需求约束。这种结构适合使用Dantzig-Wolfe分解算法，将原问题分解为一个主问题（处理全局约束）和多个子问题（处理每个工厂的局部约束）。

原问题数学模型
设工厂1生产产品A和B的数量分别为 \(x_1\) 和 \(x_2\)，工厂2生产产品A和B的数量分别为 \(x_3\) 和 \(x_4\)。

  • 目标函数：最小化总成本

\[ \min \quad 2x_1 + 3x_2 + 4x_3 + 5x_4 \]

  • 全局约束（市场需求）：

\[ x_1 + x_3 \geq 100 \quad (\text{产品A需求}), \quad x_2 + x_4 \geq 150 \quad (\text{产品B需求}) \]

  • 局部约束（每个工厂的生产能力）：
    工厂1：\(x_1 + 2x_2 \leq 500\)，\(x_1 \geq 0, x_2 \geq 0\)
    工厂2：\(3x_3 + x_4 \leq 300\)，\(x_3 \geq 0, x_4 \geq 0\)

Dantzig-Wolfe分解原理

  1. 主问题（Master Problem）：管理全局约束，变量为各子问题极值点的凸组合权重。
  2. 子问题（Subproblems）：每个子问题对应一个工厂的局部约束，接受主问题传递的“价格”信号，求解局部最优生产方案。
  3. 迭代过程：主问题根据当前解计算全局约束的“价格”（对偶变量），子问题利用这些价格调整生产计划，并向主问题反馈新的极值点。

解题步骤
步骤1：定义子问题的极值点

  • 工厂1的约束集 \(X_1 = \{ (x_1, x_2) \mid x_1 + 2x_2 \leq 500, x_1, x_2 \geq 0 \}\) 是一个有界多面体，其极值点可通过枚举约束交点得到：
    • 点1: \((0, 0)\)，成本 \(2\cdot0 + 3\cdot0 = 0\)
    • 点2: \((500, 0)\)，成本 \(2\cdot500 + 3\cdot0 = 1000\)
    • 点3: \((0, 250)\)，成本 \(2\cdot0 + 3\cdot250 = 750\)
  • 工厂2的约束集 \(X_2 = \{ (x_3, x_4) \mid 3x_3 + x_4 \leq 300, x_3, x_4 \geq 0 \}\) 的极值点：
    • 点1: \((0, 0)\)，成本 \(4\cdot0 + 5\cdot0 = 0\)
    • 点2: \((100, 0)\)，成本 \(4\cdot100 + 5\cdot0 = 400\)
    • 点3: \((0, 300)\)，成本 \(4\cdot0 + 5\cdot300 = 1500\)

步骤2：初始化主问题
主问题用极值点的凸组合表示原变量：
设工厂1的极值点权重为 \(\lambda_1, \lambda_2, \lambda_3\)，工厂2的极值点权重为 \(\mu_1, \mu_2, \mu_3\)，且满足 \(\sum \lambda_i = 1\)，\(\sum \mu_i = 1\)。
初始主问题仅包含凸组合约束和全局约束：

\[\begin{aligned} \min \quad & 0\lambda_1 + 1000\lambda_2 + 750\lambda_3 + 0\mu_1 + 400\mu_2 + 1500\mu_3 \\ \text{s.t.} \quad & (0\lambda_1 + 500\lambda_2 + 0\lambda_3) + (0\mu_1 + 100\mu_2 + 0\mu_3) \geq 100 \quad (\text{产品A需求}) \\ & (0\lambda_1 + 0\lambda_2 + 250\lambda_3) + (0\mu_1 + 0\mu_2 + 300\mu_3) \geq 150 \quad (\text{产品B需求}) \\ & \lambda_1 + \lambda_2 + \lambda_3 = 1, \quad \mu_1 + \mu_2 + \mu_3 = 1 \\ & \lambda_i, \mu_i \geq 0 \end{aligned} \]

步骤3：求解主问题并获取对偶变量
求解上述线性规划（可用单纯形法），得到最优解和对偶变量。假设初始解不满足需求（如全选成本最低的极值点 \((0,0)\) 和 \((0,0)\)），则主问题不可行，需添加极值点。实际中，可先添加能满足需求的点（如工厂1的点2和工厂2的点3）初始化。
设第一次求解后，对偶变量为：

  • 产品A需求约束的价格 \(\pi_1 = 2\)
  • 产品B需求约束的价格 \(\pi_2 = 3\)
  • 凸组合约束的价格（工厂1）\(\sigma_1 = -100\)，工厂2 \(\sigma_2 = -200\)（这些值在迭代中更新）。

步骤4：子问题求解并生成新列
子问题利用主问题的价格信号调整生产计划：

  • 工厂1子问题：目标为最小化减少成本 \(\min (2 - \pi_1)x_1 + (3 - \pi_2)x_2 - \sigma_1\)，代入价格得 \(\min (2-2)x_1 + (3-3)x_2 - (-100) = 100\)。由于成本系数为0，任意可行点均满足，但需检查是否生成新极值点。
  • 工厂2子问题：类似计算 \(\min (4-2)x_3 + (5-3)x_4 - (-200) = 2x_3 + 2x_4 + 200\)，在约束 \(3x_3 + x_4 \leq 300\) 下求解，最优解为 \((x_3, x_4) = (100, 0)\)，成本 \(2\cdot100 + 2\cdot0 + 200 = 400\)。
    若子问题目标值小于0（本例中均大于0），说明当前主问题已最优；否则，将新极值点加入主问题。

步骤5：迭代至收敛
重复步骤3-4，直到所有子问题的减少成本非负（满足最优性条件）。最终主问题的解通过极值点权重组合给出原问题最优生产计划：

  • 工厂1生产 \((x_1, x_2) = (500, 0)\)，工厂2生产 \((x_3, x_4) = (0, 300)\)，总成本 \(1000 + 1500 = 2500\)，满足市场需求（产品A: \(500+0=500 \geq 100\)，产品B: \(0+300=300 \geq 150\)）。

关键点总结

  • Dantzig-Wolfe分解通过主问题-子问题协作，利用问题结构降低计算复杂度。
  • 主问题管理全局约束，子问题处理局部约束，通过价格信号引导优化方向。
  • 适用于大规模线性规划中约束可分解的场景（如资源分配、网络流问题）。
基于线性规划的Dantzig-Wolfe分解算法求解示例 题目描述 考虑一个生产计划问题：某公司有两个工厂（工厂1和工厂2）生产两种产品（产品A和产品B）。每个工厂有独立的生产能力约束（如工时、原料限制），但公司需满足整体市场需求（如产品A至少100单位，产品B至少150单位），并最小化总生产成本。该问题的约束可分为两类：工厂的局部生产能力约束（每个工厂独立）和公司的全局市场需求约束。这种结构适合使用Dantzig-Wolfe分解算法，将原问题分解为一个主问题（处理全局约束）和多个子问题（处理每个工厂的局部约束）。 原问题数学模型 设工厂1生产产品A和B的数量分别为 \(x_ 1\) 和 \(x_ 2\)，工厂2生产产品A和B的数量分别为 \(x_ 3\) 和 \(x_ 4\)。 目标函数 ：最小化总成本 \[ \min \quad 2x_ 1 + 3x_ 2 + 4x_ 3 + 5x_ 4 \] 全局约束 （市场需求）： \[ x_ 1 + x_ 3 \geq 100 \quad (\text{产品A需求}), \quad x_ 2 + x_ 4 \geq 150 \quad (\text{产品B需求}) \] 局部约束 （每个工厂的生产能力）： 工厂1：\(x_ 1 + 2x_ 2 \leq 500\)，\(x_ 1 \geq 0, x_ 2 \geq 0\) 工厂2：\(3x_ 3 + x_ 4 \leq 300\)，\(x_ 3 \geq 0, x_ 4 \geq 0\) Dantzig-Wolfe分解原理 主问题（Master Problem） ：管理全局约束，变量为各子问题极值点的凸组合权重。 子问题（Subproblems） ：每个子问题对应一个工厂的局部约束，接受主问题传递的“价格”信号，求解局部最优生产方案。 迭代过程 ：主问题根据当前解计算全局约束的“价格”（对偶变量），子问题利用这些价格调整生产计划，并向主问题反馈新的极值点。 解题步骤 步骤1：定义子问题的极值点 工厂1的约束集 \(X_ 1 = \{ (x_ 1, x_ 2) \mid x_ 1 + 2x_ 2 \leq 500, x_ 1, x_ 2 \geq 0 \}\) 是一个有界多面体，其极值点可通过枚举约束交点得到： 点1: \((0, 0)\)，成本 \(2\cdot0 + 3\cdot0 = 0\) 点2: \((500, 0)\)，成本 \(2\cdot500 + 3\cdot0 = 1000\) 点3: \((0, 250)\)，成本 \(2\cdot0 + 3\cdot250 = 750\) 工厂2的约束集 \(X_ 2 = \{ (x_ 3, x_ 4) \mid 3x_ 3 + x_ 4 \leq 300, x_ 3, x_ 4 \geq 0 \}\) 的极值点： 点1: \((0, 0)\)，成本 \(4\cdot0 + 5\cdot0 = 0\) 点2: \((100, 0)\)，成本 \(4\cdot100 + 5\cdot0 = 400\) 点3: \((0, 300)\)，成本 \(4\cdot0 + 5\cdot300 = 1500\) 步骤2：初始化主问题 主问题用极值点的凸组合表示原变量： 设工厂1的极值点权重为 \(\lambda_ 1, \lambda_ 2, \lambda_ 3\)，工厂2的极值点权重为 \(\mu_ 1, \mu_ 2, \mu_ 3\)，且满足 \(\sum \lambda_ i = 1\)，\(\sum \mu_ i = 1\)。 初始主问题仅包含凸组合约束和全局约束： \[ \begin{aligned} \min \quad & 0\lambda_ 1 + 1000\lambda_ 2 + 750\lambda_ 3 + 0\mu_ 1 + 400\mu_ 2 + 1500\mu_ 3 \\ \text{s.t.} \quad & (0\lambda_ 1 + 500\lambda_ 2 + 0\lambda_ 3) + (0\mu_ 1 + 100\mu_ 2 + 0\mu_ 3) \geq 100 \quad (\text{产品A需求}) \\ & (0\lambda_ 1 + 0\lambda_ 2 + 250\lambda_ 3) + (0\mu_ 1 + 0\mu_ 2 + 300\mu_ 3) \geq 150 \quad (\text{产品B需求}) \\ & \lambda_ 1 + \lambda_ 2 + \lambda_ 3 = 1, \quad \mu_ 1 + \mu_ 2 + \mu_ 3 = 1 \\ & \lambda_ i, \mu_ i \geq 0 \end{aligned} \] 步骤3：求解主问题并获取对偶变量 求解上述线性规划（可用单纯形法），得到最优解和对偶变量。假设初始解不满足需求（如全选成本最低的极值点 \((0,0)\) 和 \((0,0)\)），则主问题不可行，需添加极值点。实际中，可先添加能满足需求的点（如工厂1的点2和工厂2的点3）初始化。 设第一次求解后，对偶变量为： 产品A需求约束的价格 \(\pi_ 1 = 2\) 产品B需求约束的价格 \(\pi_ 2 = 3\) 凸组合约束的价格（工厂1）\(\sigma_ 1 = -100\)，工厂2 \(\sigma_ 2 = -200\)（这些值在迭代中更新）。 步骤4：子问题求解并生成新列 子问题利用主问题的价格信号调整生产计划： 工厂1子问题：目标为最小化减少成本 \(\min (2 - \pi_ 1)x_ 1 + (3 - \pi_ 2)x_ 2 - \sigma_ 1\)，代入价格得 \(\min (2-2)x_ 1 + (3-3)x_ 2 - (-100) = 100\)。由于成本系数为0，任意可行点均满足，但需检查是否生成新极值点。 工厂2子问题：类似计算 \(\min (4-2)x_ 3 + (5-3)x_ 4 - (-200) = 2x_ 3 + 2x_ 4 + 200\)，在约束 \(3x_ 3 + x_ 4 \leq 300\) 下求解，最优解为 \((x_ 3, x_ 4) = (100, 0)\)，成本 \(2\cdot100 + 2\cdot0 + 200 = 400\)。 若子问题目标值小于0（本例中均大于0），说明当前主问题已最优；否则，将新极值点加入主问题。 步骤5：迭代至收敛 重复步骤3-4，直到所有子问题的减少成本非负（满足最优性条件）。最终主问题的解通过极值点权重组合给出原问题最优生产计划： 工厂1生产 \((x_ 1, x_ 2) = (500, 0)\)，工厂2生产 \((x_ 3, x_ 4) = (0, 300)\)，总成本 \(1000 + 1500 = 2500\)，满足市场需求（产品A: \(500+0=500 \geq 100\)，产品B: \(0+300=300 \geq 150\)）。 关键点总结 Dantzig-Wolfe分解通过主问题-子问题协作，利用问题结构降低计算复杂度。 主问题管理全局约束，子问题处理局部约束，通过价格信号引导优化方向。 适用于大规模线性规划中约束可分解的场景（如资源分配、网络流问题）。