线性规划的Benders分解算法求解示例

我将通过一个生产计划问题来讲解Benders分解算法。假设某公司有两个工厂（F1、F2）和三个市场（M1、M2、M3），需要决定各工厂的生产量和向各市场的运输量。

问题描述
目标函数：最小化总成本 = 固定成本 + 可变成本

• 固定成本：工厂开工的固定费用（F1: 5000, F2: 8000）
• 可变成本：生产成本（F1: 3/单位, F2: 2/单位）+ 运输成本（如下表）
• 需求约束：M1需求≥100, M2需求≥200, M3需求≥150
• 供应约束：F1最大产量≤300, F2最大产量≤400

运输成本矩阵：

   M1 M2 M3
F1 2  4  5
F2 3  1  2

数学模型
主问题（MP）：
min 5000y₁ + 8000y₂ + z
s.t.
y₁, y₂ ∈ {0,1} （工厂开关决策）
z ≥ 下界估计

子问题（SP）：
min (3+2)x₁₁ + (3+4)x₁₂ + (3+5)x₁₃ + (2+3)x₂₁ + (2+1)x₂₂ + (2+2)x₂₃
s.t.
x₁₁ + x₁₂ + x₁₃ ≤ 300y₁ （F1供应约束）
x₂₁ + x₂₂ + x₂₃ ≤ 400y₂ （F2供应约束）
x₁₁ + x₂₁ ≥ 100 （M1需求）
x₁₂ + x₂₂ ≥ 200 （M2需求）
x₁₃ + x₂₃ ≥ 150 （M3需求）
xᵢⱼ ≥ 0

求解过程
步骤1：初始化

• 设置上界UB=+∞，下界LB=-∞
• 主问题初始解：y₁=0, y₂=0（都不开工）

步骤2：第一次迭代

1. 子问题求解：
   当前解不可行（无供应），添加可行性割：
   π₁(300y₁ - x₁₁ - x₁₂ - x₁₃) + π₂(400y₂ - x₂₁ - x₂₂ - x₂₃) + π₃(x₁₁ + x₂₁ - 100) + π₄(x₁₂ + x₂₂ - 200) + π₅(x₁₃ + x₂₃ - 150) ≤ 0
   得到割平面：300y₁ + 400y₂ ≥ 450

2. 主问题更新：
   min 5000y₁ + 8000y₂ + z
   s.t. 300y₁ + 400y₂ ≥ 450
   y₁,y₂∈{0,1}, z≥0
   求解得：y₁=1, y₂=0, z=0（仅F1开工）

步骤3：第二次迭代

1. 子问题求解（y₁=1, y₂=0）：
   目标值=3150，添加最优性割：
   z ≥ 3150 + σ₁(300-300) + σ₂(0-0) = 3150

2. 主问题更新：
   min 5000y₁ + 8000y₂ + z
   s.t.
   300y₁ + 400y₂ ≥ 450
   z ≥ 3150
   求解得：y₁=0, y₂=1, z=3150（仅F2开工）

步骤4：第三次迭代

1. 子问题求解（y₁=0, y₂=1）：
   目标值=2600，添加最优性割：
   z ≥ 2600

2. 主问题更新：
   min 5000y₁ + 8000y₂ + z
   s.t.
   300y₁ + 400y₂ ≥ 450
   z ≥ 3150
   z ≥ 2600
   求解得：y₁=0, y₂=1, z=3150（与上次相同）

步骤5：收敛检查
上界=2600（子问题最优值）
下界=3150（主问题最优值）
下界>上界，算法终止

最终结果
最优解：仅开启F2工厂
最小总成本=8000（固定）+2600（可变）=10600
运输方案：F2向M1运100单位，M2运200单位，M3运150单位

Benders分解通过主问题处理复杂整数变量，子问题处理连续变量，通过交替求解和添加割平面来逼近最优解。