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

字数 10880 2025-12-07 11:42:45

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

题目描述：
考虑一个两阶段生产-运输问题。一个公司需要生产并运输一种产品，以满足两个不同市场的需求。第一阶段决策是在两个工厂（工厂1和工厂2）的生产量，这两个工厂的生产成本不同且有产能限制。第二阶段决策是将产品从工厂运输到市场（市场A和市场B），产生运输成本，且必须满足每个市场的需求。目标是确定生产和运输计划，使总成本（生产成本 + 运输成本）最小。这是一个典型的具有“主问题”（生产决策）和“子问题”（运输决策）的两阶段优化问题，适合用Benders分解算法求解。
具体数据如下：

工厂产能：工厂1为40单位，工厂2为60单位。
市场需求：市场A需求30单位，市场B需求50单位。
生产成本：工厂1为2元/单位，工厂2为3元/单位。
运输成本（元/单位）：从工厂1到市场A为4元，到市场B为5元；从工厂2到市场A为6元，到市场B为3元。

解题过程：
Benders分解算法用于求解具有复杂结构的线性规划问题，特别是当变量可分解为“复杂”变量和“简单”变量时。在本问题中，生产决策是“第一阶段的复杂变量”，运输决策是“第二阶段的简单变量”，但运输问题依赖于生产量。算法将原问题分解为主问题（处理生产变量）和子问题（处理运输变量），通过迭代求解主问题和子问题，逐步添加“Benders割”来逼近原问题的最优解。

步骤1：建立原问题的线性规划模型
设生产变量：\(x_1\) = 工厂1的生产量，\(x_2\) = 工厂2的生产量。
设运输变量：\(y_{ij}\) 表示从工厂i到市场j的运输量（i=1,2；j=A,B）。
原问题（P）如下：

\[\text{最小化} \quad 2x_1 + 3x_2 + 4y_{1A} + 5y_{1B} + 6y_{2A} + 3y_{2B} \]

约束条件：

产能约束：\(x_1 \leq 40, \quad x_2 \leq 60\)
需求约束：\(y_{1A} + y_{2A} = 30, \quad y_{1B} + y_{2B} = 50\)
供应约束：\(y_{1A} + y_{1B} \leq x_1, \quad y_{2A} + y_{2B} \leq x_2\)
非负约束：\(x_1, x_2, y_{ij} \geq 0\)

步骤2：分解为Benders主问题和子问题

主问题（MP）：只包含生产变量 \(x_1, x_2\) 和一个辅助变量 \(\eta\)，其中 \(\eta\) 表示对第二阶段运输成本的下界估计。初始主问题没有Benders割，因此是一个松弛。
子问题（SP）：给定固定的生产量 \(\bar{x}_1, \bar{x}_2\)，求解运输问题。子问题是一个线性规划，其最优值用来生成Benders割添加到主问题。

步骤3：求解初始主问题
初始主问题（MP₀）为：

\[\text{最小化} \quad 2x_1 + 3x_2 + \eta \]

约束：

\[x_1 \leq 40, \quad x_2 \leq 60, \quad x_1, x_2 \geq 0, \quad \eta \text{ 无约束（但在迭代中会逐步约束）}. \]

由于 \(\eta\) 初始无约束，目标函数最小化会驱动 \(\eta \to -\infty\)，但算法中我们通常初始化 \(\eta\) 为一个足够小的数（例如 -∞）或通过第一次迭代生成割来约束。实际上，Benders分解从主问题的任意可行解开始。这里，为启动迭代，我们可任意选择一组生产量，例如令 \(x_1 = 0, x_2 = 0\)。但更有效的方法是先求解主问题忽略 \(\eta\)，即最小化 \(2x_1 + 3x_2\)，得到 \(x_1 = 0, x_2 = 0\)，然后进入子问题。

步骤4：第一次迭代

给定主问题解：\(\bar{x}_1 = 0, \bar{x}_2 = 0\)。
求解子问题（SP）：运输问题，但供应约束为 \(y_{1A} + y_{1B} \leq 0, y_{2A} + y_{2B} \leq 0\)，因此所有运输变量必须为0。但需求约束 \(y_{1A} + y_{2A} = 30, y_{1B} + y_{2B} = 50\) 无法满足，因此子问题不可行。这表明生产量不足，需要添加“可行割”到主问题。

步骤5：处理子问题不可行并生成可行割
当子问题不可行时，我们需要求解子问题的可行性问题（Phase I问题）。引入人工变量 \(s_1, s_2 \geq 0\) 到需求约束，并最小化人工变量之和。可行性问题（FSP）为：

\[\text{最小化} \quad s_1 + s_2 \]

约束：

\[y_{1A} + y_{2A} + s_1 = 30, \quad y_{1B} + y_{2B} + s_2 = 50, \]

\[y_{1A} + y_{1B} \leq \bar{x}_1, \quad y_{2A} + y_{2B} \leq \bar{x}_2, \quad y_{ij}, s_1, s_2 \geq 0. \]

代入 \(\bar{x}_1 = 0, \bar{x}_2 = 0\)，则 \(y_{ij} = 0\)，因此最优解为 \(s_1 = 30, s_2 = 50\)，最优值 = 80。对偶变量：设需求约束的对偶变量为 \(\alpha_1, \alpha_2\)（符号取决于问题形式，但Benders割的生成标准形式为：若原问题是最小化，子问题为最小化，则可行割为 \(0 \geq b^T \alpha + (x - \bar{x})^T \rho\)，其中 \(\alpha\) 是可行性问题的对偶解）。具体地，可行性问题的对偶为：
最大化 \(30\alpha_1 + 50\alpha_2 + \bar{x}_1 \rho_1 + \bar{x}_2 \rho_2\)
约束：\(\alpha_1 \leq 0, \alpha_2 \leq 0, \alpha_1 + \rho_1 \leq 0, \alpha_2 + \rho_1 \leq 0, \alpha_1 + \rho_2 \leq 0, \alpha_2 + \rho_2 \leq 0\)（这里 \(\rho_1, \rho_2\) 是供应约束的对偶变量）。求解得对偶最优解为 \(\alpha_1 = -1, \alpha_2 = -1, \rho_1 = 1, \rho_2 = 1\)（注意符号，需满足对偶约束）。则可行割为：

\[0 \geq (30\alpha_1 + 50\alpha_2) + (x_1 - \bar{x}_1)\rho_1 + (x_2 - \bar{x}_2)\rho_2 \]

代入值：\(0 \geq (30*(-1) + 50*(-1)) + (x_1 - 0)*1 + (x_2 - 0)*1\)，即：

\[0 \geq -80 + x_1 + x_2 \quad \Rightarrow \quad x_1 + x_2 \geq 80. \]

将此割加入主问题。

步骤6：更新主问题并第二次迭代
主问题（MP₁）变为：

\[\text{最小化} \quad 2x_1 + 3x_2 + \eta \]

约束：

\[x_1 \leq 40, \quad x_2 \leq 60, \quad x_1 + x_2 \geq 80, \quad x_1, x_2 \geq 0. \]

求解得最优解：最小化目标，由于 \(x_1\) 更便宜，优先使用 \(x_1\)。但 \(x_1 \leq 40\)，所以 \(x_2\) 必须至少为 40 以满足 \(x_1 + x_2 \geq 80\)。因此最优解为 \(x_1 = 40, x_2 = 40\)，此时生产成本 = \(2*40 + 3*40 = 200\)，但 \(\eta\) 仍无下界约束，所以主问题目标会趋向 -∞？实际上，在Benders分解中，主问题每次迭代会添加割来约束 \(\eta\)。第一次迭代只添加了可行割，还没有最优割，所以 \(\eta\) 可以任意小。但算法中，我们求解主问题时，如果没有最优割，可暂时忽略 \(\eta\) 或设 \(\eta = -\infty\)，然后得到生产解 \((40, 40)\)。现在进入第二次迭代。

步骤7：第二次迭代

给定主问题解：\(\bar{x}_1 = 40, \bar{x}_2 = 40\)。
求解子问题（SP）：运输问题，目标最小化运输成本 \(4y_{1A} + 5y_{1B} + 6y_{2A} + 3y_{2B}\)，约束：
需求：\(y_{1A} + y_{2A} = 30, \quad y_{1B} + y_{2B} = 50\)
供应：\(y_{1A} + y_{1B} \leq 40, \quad y_{2A} + y_{2B} \leq 40\)
非负。
这是一个运输问题，可用简单规则求解：从工厂1到市场B成本高（5），从工厂2到市场A成本高（6），所以优先分配低成本路线。
最优解：
市场A需求30：从工厂1运30（成本4），因为工厂1到A成本4 < 工厂2到A成本6。
市场B需求50：工厂1剩余产能 = 40 - 30 = 10，运10到市场B（成本5）；工厂2运40到市场B（成本3），但工厂2产能只有40，所以市场B还需0单位，但需求50已满足（10+40=50）。
计算：运输成本 = \(30*4 + 10*5 + 0*6 + 40*3 = 120 + 50 + 0 + 120 = 290\)。
子问题最优值 = 290。
由于子问题可行且达到最优，我们生成“最优割”。子问题的对偶变量：设需求约束对偶变量为 \(\lambda_A, \lambda_B\)，供应约束对偶变量为 \(\mu_1, \mu_2 \leq 0\)（因为约束是 ≤）。对偶问题为：
最大化 \(30\lambda_A + 50\lambda_B + 40\mu_1 + 40\mu_2\)
约束：\(\lambda_A + \mu_1 \leq 4, \lambda_B + \mu_1 \leq 5, \lambda_A + \mu_2 \leq 6, \lambda_B + \mu_2 \leq 3\)。
代入解：在原始最优解中，非基变量为 \(y_{2A} = 0\)，其约化成本 = \(6 - \lambda_A - \mu_2 \geq 0\)。可求解对偶最优解，例如由互补松弛性，当 \(y_{1A} = 30 > 0\)，有 \(\lambda_A + \mu_1 = 4\)；\(y_{1B} = 10 > 0\)，有 \(\lambda_B + \mu_1 = 5\)；\(y_{2B} = 40 > 0\)，有 \(\lambda_B + \mu_2 = 3\)。解方程组：
(1) \(\lambda_A + \mu_1 = 4\)
(2) \(\lambda_B + \mu_1 = 5\)
(3) \(\lambda_B + \mu_2 = 3\)
另由 \(y_{2A} = 0\) 的约化成本非负：\(6 - \lambda_A - \mu_2 \geq 0\)。
可令 \(\mu_1 = 0\)（因为供应约束不一定紧？实际上工厂1供应约束：\(y_{1A}+y_{1B}=40\)，是紧的，所以 \(\mu_1\) 可非零）。但为简单，求解：从(1)(2)得 \(\lambda_A = 4 - \mu_1, \lambda_B = 5 - \mu_1\)。代入(3)：\(5 - \mu_1 + \mu_2 = 3 \Rightarrow \mu_2 = \mu_1 - 2\)。由 \(\mu_1, \mu_2 \leq 0\)，可取 \(\mu_1 = 0\)，则 \(\lambda_A=4, \lambda_B=5, \mu_2=-2\)。检验：\(6 - \lambda_A - \mu_2 = 6-4-(-2)=4 \geq 0\)，可行。
则对偶最优解：\(\lambda_A=4, \lambda_B=5, \mu_1=0, \mu_2=-2\)，对偶目标值 = \(30*4 + 50*5 + 40*0 + 40*(-2) = 120 + 250 - 80 = 290\)，等于原始最优值。
最优割形式：\(\eta \geq (\lambda_A d_A + \lambda_B d_B) + \mu_1 x_1 + \mu_2 x_2\)，其中 \(d_A=30, d_B=50\) 是需求常数。代入：

\[\eta \geq (4*30 + 5*50) + 0*x_1 + (-2)*x_2 = 120 + 250 - 2x_2 = 370 - 2x_2. \]

将此割加入主问题。

步骤8：更新主问题并第三次迭代
主问题（MP₂）变为：

\[\text{最小化} \quad 2x_1 + 3x_2 + \eta \]

约束：

\[x_1 \leq 40, \quad x_2 \leq 60, \quad x_1 + x_2 \geq 80, \quad \eta \geq 370 - 2x_2, \quad x_1, x_2 \geq 0. \]

求解：目标 = \(2x_1 + 3x_2 + \eta \geq 2x_1 + 3x_2 + 370 - 2x_2 = 2x_1 + x_2 + 370\)。在约束下最小化 \(2x_1 + x_2\)，满足 \(x_1 \leq 40, x_2 \leq 60, x_1+x_2 \geq 80\)。显然，最小化时让 \(x_1\) 尽可能大（因为系数2 > 1？实际上系数2 > 1，所以应最小化 \(x_1\)？不，目标是最小化 \(2x_1 + x_2\)，所以应优先减小 \(x_1\)，因为其系数更大）。但约束 \(x_1+x_2 \geq 80\)，所以取 \(x_1=0, x_2=80\) 违反 \(x_2 \leq 60\)，所以 \(x_2\) 最大为60，则 \(x_1 \geq 20\)。因此最优解为 \(x_1=20, x_2=60\)，此时 \(2x_1+x_2 = 40+60=100\)，总目标下界 = 100+370=470。但还要考虑 \(\eta\) 可能更大？实际上，主问题会精确求解线性规划。我们直接求解MP₂：
目标：最小化 \(2x_1+3x_2+\eta\)
约束：\(\eta \geq 370-2x_2\)，所以最优时取 \(\eta = 370-2x_2\)（因为增大 \(\eta\) 会增加目标）。代入目标：\(2x_1+3x_2+370-2x_2 = 2x_1 + x_2 + 370\)。
在约束 \(x_1 \leq 40, x_2 \leq 60, x_1+x_2 \geq 80, x_1, x_2 \geq 0\) 下最小化 \(2x_1+x_2\)。作图或单纯形法：顶点有 (20,60), (40,40), (40,60) 等。计算：
(20,60)：\(2*20+60=100\)
(40,40)：\(2*40+40=120\)
(40,60)：\(2*40+60=140\)
所以最优解为 \(x_1=20, x_2=60\)，目标值 = 100+370=470。
主问题最优解：\(\bar{x}_1=20, \bar{x}_2=60, \eta=370-2*60=250\)。

步骤9：第三次迭代

给定主问题解：\(\bar{x}_1=20, \bar{x}_2=60\)。
求解子问题：运输问题，供应约束：\(y_{1A}+y_{1B} \leq 20, y_{2A}+y_{2B} \leq 60\)，需求同上。
求解最优运输：
市场A需求30：从工厂1运20（成本4），从工厂2运10（成本6）。
市场B需求50：工厂1无剩余，全部从工厂2运50（成本3）。
运输成本 = \(20*4 + 10*6 + 50*3 = 80 + 60 + 150 = 290\)。
对偶变量：设对偶变量同上形式，解对偶问题。由互补松弛性：
\(y_{1A}=20>0 \Rightarrow \lambda_A+\mu_1=4\)
\(y_{2A}=10>0 \Rightarrow \lambda_A+\mu_2=6\)
\(y_{2B}=50>0 \Rightarrow \lambda_B+\mu_2=3\)
供应约束：工厂1紧（20=20）⇒ \(\mu_1\) 可非零；工厂2紧（10+50=60）⇒ \(\mu_2\) 可非零。
解方程组：从 \(\lambda_A+\mu_2=6\) 和 \(\lambda_B+\mu_2=3\) 得 \(\lambda_A - \lambda_B = 3\)。从 \(\lambda_A+\mu_1=4\) 和 \(\lambda_B+\mu_1=5\)（？第二个方程应为 \(\lambda_B+\mu_1=5\) 来自 \(y_{1B}=0\) 的约化成本？实际上 \(y_{1B}=0\)，所以其约束 \(\lambda_B+\mu_1 \leq 5\) 不一定紧）。更严谨地，我们直接求解对偶最优值等于290，可设 \(\mu_1=0, \mu_2=-2, \lambda_A=4, \lambda_B=5\) 也满足？检验：\(\lambda_A+\mu_2=4-2=2 \neq 6\)，不满足。所以需要新解。
解方程：
(1) \(\lambda_A+\mu_1=4\)
(2) \(\lambda_A+\mu_2=6\)
(3) \(\lambda_B+\mu_2=3\)
由(1)(2)得 \(\mu_2-\mu_1=2\)。由(3)得 \(\lambda_B=3-\mu_2\)。
对偶目标：\(30\lambda_A+50\lambda_B+20\mu_1+60\mu_2 = 290\)。
代入 \(\lambda_A=4-\mu_1\) 和 \(\lambda_B=3-\mu_2\)：
\(30(4-\mu_1)+50(3-\mu_2)+20\mu_1+60\mu_2 = 120-30\mu_1+150-50\mu_2+20\mu_1+60\mu_2 = 270 -10\mu_1+10\mu_2 = 290 \Rightarrow -10\mu_1+10\mu_2=20 \Rightarrow \mu_2-\mu_1=2\)，与上面一致。所以有无穷多解，取一组简单解：令 \(\mu_1=0\)，则 \(\mu_2=2\)，但 \(\mu_2 \leq 0\) 是约束吗？在子问题中，供应约束是 ≤，对偶变量 \(\mu_1, \mu_2 \leq 0\)。所以 \(\mu_2=2\) 无效。需满足 \(\mu_1, \mu_2 \leq 0\)。取 \(\mu_2=0\)，则 \(\mu_1=-2\)，代入得 \(\lambda_A=6, \lambda_B=3\)，检验：\(\lambda_A+\mu_1=6-2=4\) 满足(1)，\(\lambda_A+\mu_2=6+0=6\) 满足(2)，\(\lambda_B+\mu_2=3+0=3\) 满足(3)。且对偶目标 = \(30*6+50*3+20*(-2)+60*0=180+150-40=290\)，正确。
所以对偶最优解：\(\lambda_A=6, \lambda_B=3, \mu_1=-2, \mu_2=0\)。
生成最优割：\(\eta \geq 30*6+50*3 + (-2)x_1 + 0*x_2 = 180+150 -2x_1 = 330 - 2x_1\)。
将此割加入主问题。

步骤10：更新主问题并继续迭代
主问题（MP₃）加入新割 \(\eta \geq 330-2x_1\) 和之前的割 \(\eta \geq 370-2x_2\)。
求解主问题：最小化 \(2x_1+3x_2+\eta\)
约束：
\(x_1 \leq 40, x_2 \leq 60, x_1+x_2 \geq 80\)
\(\eta \geq 370-2x_2\)
\(\eta \geq 330-2x_1\)
非负。
最优解应使 \(\eta = \max(370-2x_2, 330-2x_1)\)。为最小化目标，我们需平衡 \(x_1\) 和 \(x_2\)。枚举顶点：
交点1：\(370-2x_2 = 330-2x_1 \Rightarrow 2x_1 - 2x_2 = -40 \Rightarrow x_1 = x_2 - 20\)。结合 \(x_1+x_2 \geq 80\) 和边界。
在可行域内，计算目标值。可求解线性规划：
设目标为 \(2x_1+3x_2+\eta\)，且 \(\eta \geq 370-2x_2, \eta \geq 330-2x_1\)。
在最优解处，至少一个割是紧的。尝试同时紧：\(370-2x_2 = 330-2x_1 \Rightarrow x_1 = x_2 - 20\)。代入 \(x_1+x_2 \geq 80\) 得 \(2x_2 -20 \geq 80 \Rightarrow x_2 \geq 50\)。同时 \(x_1 \leq 40 \Rightarrow x_2 \leq 60\)。取 \(x_2=50, x_1=30\)，则 \(\eta = 370-2*50=270\)，目标 = \(2*30+3*50+270=60+150+270=480\)。
检查其他顶点：如 \(x_1=20, x_2=60\)（来自之前解），此时 \(\eta = \max(370-120=250, 330-40=290) = 290\)，目标 = \(40+180+290=510\)。
如 \(x_1=40, x_2=40\)，则 \(\eta = \max(370-80=290, 330-80=250)=290\)，目标 = \(80+120+290=490\)。
如 \(x_1=40, x_2=60\)（不可行，因为 \(x_1+x_2=100 \geq 80\) 可行，但 \(\eta=\max(370-120=250, 330-80=250)=250\)，目标 = \(80+180+250=510\)。
最优似乎是 \(x_1=30, x_2=50\)，目标=480。但需验证可行性：产能 \(x_1=30 \leq 40, x_2=50 \leq 60\)，且 \(x_1+x_2=80 \geq 80\) 满足。
主问题最优解：\(\bar{x}_1=30, \bar{x}_2=50, \eta=270\)。

步骤11：第四次迭代

给定主问题解：\(\bar{x}_1=30, \bar{x}_2=50\)。
求解子问题：运输问题，供应约束：\(y_{1A}+y_{1B} \leq 30, y_{2A}+y_{2B} \leq 50\)。
最优运输：
市场A需求30：从工厂1运30（成本4），工厂2运0。
市场B需求50：工厂1剩余0，工厂2运50（成本3）。
运输成本 = \(30*4 + 50*3 = 120+150=270\)。
此时子问题最优值 = 270，等于主问题中 \(\eta=270\)，说明上下界相等，算法收敛。

步骤12：输出最优解
最优生产计划：\(x_1=30, x_2=50\)，总生产成本 = \(2*30+3*50=60+150=210\)。
最优运输计划：\(y_{1A}=30, y_{1B}=0, y_{2A}=0, y_{2B}=50\)，总运输成本 = 270。
总成本 = 210+270=480。
算法结束。

这个示例展示了Benders分解如何通过迭代主问题和子问题，逐步添加可行割和最优割，最终收敛到原问题的最优解。

基于线性规划的Benders分解算法求解示例题目描述：考虑一个两阶段生产-运输问题。一个公司需要生产并运输一种产品，以满足两个不同市场的需求。第一阶段决策是在两个工厂（工厂1和工厂2）的生产量，这两个工厂的生产成本不同且有产能限制。第二阶段决策是将产品从工厂运输到市场（市场A和市场B），产生运输成本，且必须满足每个市场的需求。目标是确定生产和运输计划，使总成本（生产成本 + 运输成本）最小。这是一个典型的具有“主问题”（生产决策）和“子问题”（运输决策）的两阶段优化问题，适合用Benders分解算法求解。具体数据如下：工厂产能：工厂1为40单位，工厂2为60单位。市场需求：市场A需求30单位，市场B需求50单位。生产成本：工厂1为2元/单位，工厂2为3元/单位。运输成本（元/单位）：从工厂1到市场A为4元，到市场B为5元；从工厂2到市场A为6元，到市场B为3元。解题过程： Benders分解算法用于求解具有复杂结构的线性规划问题，特别是当变量可分解为“复杂”变量和“简单”变量时。在本问题中，生产决策是“第一阶段的复杂变量”，运输决策是“第二阶段的简单变量”，但运输问题依赖于生产量。算法将原问题分解为主问题（处理生产变量）和子问题（处理运输变量），通过迭代求解主问题和子问题，逐步添加“Benders割”来逼近原问题的最优解。步骤1：建立原问题的线性规划模型设生产变量：\( x_ 1 \) = 工厂1的生产量，\( x_ 2 \) = 工厂2的生产量。设运输变量：\( y_ {ij} \) 表示从工厂i到市场j的运输量（i=1,2；j=A,B）。原问题（P）如下： \[ \text{最小化} \quad 2x_ 1 + 3x_ 2 + 4y_ {1A} + 5y_ {1B} + 6y_ {2A} + 3y_ {2B} \] 约束条件：产能约束：\( x_ 1 \leq 40, \quad x_ 2 \leq 60 \) 需求约束：\( y_ {1A} + y_ {2A} = 30, \quad y_ {1B} + y_ {2B} = 50 \) 供应约束：\( y_ {1A} + y_ {1B} \leq x_ 1, \quad y_ {2A} + y_ {2B} \leq x_ 2 \) 非负约束：\( x_ 1, x_ 2, y_ {ij} \geq 0 \) 步骤2：分解为Benders主问题和子问题主问题（MP）：只包含生产变量 \( x_ 1, x_ 2 \) 和一个辅助变量 \( \eta \)，其中 \( \eta \) 表示对第二阶段运输成本的下界估计。初始主问题没有Benders割，因此是一个松弛。子问题（SP）：给定固定的生产量 \( \bar{x}_ 1, \bar{x}_ 2 \)，求解运输问题。子问题是一个线性规划，其最优值用来生成Benders割添加到主问题。步骤3：求解初始主问题初始主问题（MP₀）为： \[ \text{最小化} \quad 2x_ 1 + 3x_ 2 + \eta \] 约束： \[ x_ 1 \leq 40, \quad x_ 2 \leq 60, \quad x_ 1, x_ 2 \geq 0, \quad \eta \text{ 无约束（但在迭代中会逐步约束）}. \] 由于 \( \eta \) 初始无约束，目标函数最小化会驱动 \( \eta \to -\infty \)，但算法中我们通常初始化 \( \eta \) 为一个足够小的数（例如 -∞）或通过第一次迭代生成割来约束。实际上，Benders分解从主问题的任意可行解开始。这里，为启动迭代，我们可任意选择一组生产量，例如令 \( x_ 1 = 0, x_ 2 = 0 \)。但更有效的方法是先求解主问题忽略 \( \eta \)，即最小化 \( 2x_ 1 + 3x_ 2 \)，得到 \( x_ 1 = 0, x_ 2 = 0 \)，然后进入子问题。步骤4：第一次迭代给定主问题解：\( \bar{x}_ 1 = 0, \bar{x}_ 2 = 0 \)。求解子问题（SP）：运输问题，但供应约束为 \( y_ {1A} + y_ {1B} \leq 0, y_ {2A} + y_ {2B} \leq 0 \)，因此所有运输变量必须为0。但需求约束 \( y_ {1A} + y_ {2A} = 30, y_ {1B} + y_ {2B} = 50 \) 无法满足，因此子问题不可行。这表明生产量不足，需要添加“可行割”到主问题。步骤5：处理子问题不可行并生成可行割当子问题不可行时，我们需要求解子问题的可行性问题（Phase I问题）。引入人工变量 \( s_ 1, s_ 2 \geq 0 \) 到需求约束，并最小化人工变量之和。可行性问题（FSP）为： \[ \text{最小化} \quad s_ 1 + s_ 2 \] 约束： \[ y_ {1A} + y_ {2A} + s_ 1 = 30, \quad y_ {1B} + y_ {2B} + s_ 2 = 50, \] \[ y_ {1A} + y_ {1B} \leq \bar{x} 1, \quad y {2A} + y_ {2B} \leq \bar{x} 2, \quad y {ij}, s_ 1, s_ 2 \geq 0. \] 代入 \( \bar{x}_ 1 = 0, \bar{x} 2 = 0 \)，则 \( y {ij} = 0 \)，因此最优解为 \( s_ 1 = 30, s_ 2 = 50 \)，最优值 = 80。对偶变量：设需求约束的对偶变量为 \( \alpha_ 1, \alpha_ 2 \)（符号取决于问题形式，但Benders割的生成标准形式为：若原问题是最小化，子问题为最小化，则可行割为 \( 0 \geq b^T \alpha + (x - \bar{x})^T \rho \)，其中 \( \alpha \) 是可行性问题的对偶解）。具体地，可行性问题的对偶为：最大化 \( 30\alpha_ 1 + 50\alpha_ 2 + \bar{x}_ 1 \rho_ 1 + \bar{x}_ 2 \rho_ 2 \) 约束：\( \alpha_ 1 \leq 0, \alpha_ 2 \leq 0, \alpha_ 1 + \rho_ 1 \leq 0, \alpha_ 2 + \rho_ 1 \leq 0, \alpha_ 1 + \rho_ 2 \leq 0, \alpha_ 2 + \rho_ 2 \leq 0 \)（这里 \( \rho_ 1, \rho_ 2 \) 是供应约束的对偶变量）。求解得对偶最优解为 \( \alpha_ 1 = -1, \alpha_ 2 = -1, \rho_ 1 = 1, \rho_ 2 = 1 \)（注意符号，需满足对偶约束）。则可行割为： \[ 0 \geq (30\alpha_ 1 + 50\alpha_ 2) + (x_ 1 - \bar{x}_ 1)\rho_ 1 + (x_ 2 - \bar{x}_ 2)\rho_ 2 \] 代入值：\( 0 \geq (30* (-1) + 50* (-1)) + (x_ 1 - 0) 1 + (x_ 2 - 0) 1 \)，即： \[ 0 \geq -80 + x_ 1 + x_ 2 \quad \Rightarrow \quad x_ 1 + x_ 2 \geq 80. \] 将此割加入主问题。步骤6：更新主问题并第二次迭代主问题（MP₁）变为： \[ \text{最小化} \quad 2x_ 1 + 3x_ 2 + \eta \] 约束： \[ x_ 1 \leq 40, \quad x_ 2 \leq 60, \quad x_ 1 + x_ 2 \geq 80, \quad x_ 1, x_ 2 \geq 0. \] 求解得最优解：最小化目标，由于 \( x_ 1 \) 更便宜，优先使用 \( x_ 1 \)。但 \( x_ 1 \leq 40 \)，所以 \( x_ 2 \) 必须至少为 40 以满足 \( x_ 1 + x_ 2 \geq 80 \)。因此最优解为 \( x_ 1 = 40, x_ 2 = 40 \)，此时生产成本 = \( 2 40 + 3 40 = 200 \)，但 \( \eta \) 仍无下界约束，所以主问题目标会趋向 -∞？实际上，在Benders分解中，主问题每次迭代会添加割来约束 \( \eta \)。第一次迭代只添加了可行割，还没有最优割，所以 \( \eta \) 可以任意小。但算法中，我们求解主问题时，如果没有最优割，可暂时忽略 \( \eta \) 或设 \( \eta = -\infty \)，然后得到生产解 \( (40, 40) \)。现在进入第二次迭代。步骤7：第二次迭代给定主问题解：\( \bar{x}_ 1 = 40, \bar{x}_ 2 = 40 \)。求解子问题（SP）：运输问题，目标最小化运输成本 \( 4y_ {1A} + 5y_ {1B} + 6y_ {2A} + 3y_ {2B} \)，约束：需求：\( y_ {1A} + y_ {2A} = 30, \quad y_ {1B} + y_ {2B} = 50 \) 供应：\( y_ {1A} + y_ {1B} \leq 40, \quad y_ {2A} + y_ {2B} \leq 40 \) 非负。这是一个运输问题，可用简单规则求解：从工厂1到市场B成本高（5），从工厂2到市场A成本高（6），所以优先分配低成本路线。最优解：市场A需求30：从工厂1运30（成本4），因为工厂1到A成本4 < 工厂2到A成本6。市场B需求50：工厂1剩余产能 = 40 - 30 = 10，运10到市场B（成本5）；工厂2运40到市场B（成本3），但工厂2产能只有40，所以市场B还需0单位，但需求50已满足（10+40=50）。计算：运输成本 = \( 30 4 + 10 5 + 0 6 + 40 3 = 120 + 50 + 0 + 120 = 290 \)。子问题最优值 = 290。由于子问题可行且达到最优，我们生成“最优割”。子问题的对偶变量：设需求约束对偶变量为 \( \lambda_ A, \lambda_ B \)，供应约束对偶变量为 \( \mu_ 1, \mu_ 2 \leq 0 \)（因为约束是 ≤）。对偶问题为：最大化 \( 30\lambda_ A + 50\lambda_ B + 40\mu_ 1 + 40\mu_ 2 \) 约束：\( \lambda_ A + \mu_ 1 \leq 4, \lambda_ B + \mu_ 1 \leq 5, \lambda_ A + \mu_ 2 \leq 6, \lambda_ B + \mu_ 2 \leq 3 \)。代入解：在原始最优解中，非基变量为 \( y_ {2A} = 0 \)，其约化成本 = \( 6 - \lambda_ A - \mu_ 2 \geq 0 \)。可求解对偶最优解，例如由互补松弛性，当 \( y_ {1A} = 30 > 0 \)，有 \( \lambda_ A + \mu_ 1 = 4 \)；\( y_ {1B} = 10 > 0 \)，有 \( \lambda_ B + \mu_ 1 = 5 \)；\( y_ {2B} = 40 > 0 \)，有 \( \lambda_ B + \mu_ 2 = 3 \)。解方程组： (1) \( \lambda_ A + \mu_ 1 = 4 \) (2) \( \lambda_ B + \mu_ 1 = 5 \) (3) \( \lambda_ B + \mu_ 2 = 3 \) 另由 \( y_ {2A} = 0 \) 的约化成本非负：\( 6 - \lambda_ A - \mu_ 2 \geq 0 \)。可令 \( \mu_ 1 = 0 \)（因为供应约束不一定紧？实际上工厂1供应约束：\( y_ {1A}+y_ {1B}=40 \)，是紧的，所以 \( \mu_ 1 \) 可非零）。但为简单，求解：从(1)(2)得 \( \lambda_ A = 4 - \mu_ 1, \lambda_ B = 5 - \mu_ 1 \)。代入(3)：\( 5 - \mu_ 1 + \mu_ 2 = 3 \Rightarrow \mu_ 2 = \mu_ 1 - 2 \)。由 \( \mu_ 1, \mu_ 2 \leq 0 \)，可取 \( \mu_ 1 = 0 \)，则 \( \lambda_ A=4, \lambda_ B=5, \mu_ 2=-2 \)。检验：\( 6 - \lambda_ A - \mu_ 2 = 6-4-(-2)=4 \geq 0 \)，可行。则对偶最优解：\( \lambda_ A=4, \lambda_ B=5, \mu_ 1=0, \mu_ 2=-2 \)，对偶目标值 = \( 30 4 + 50 5 + 40 0 + 40 (-2) = 120 + 250 - 80 = 290 \)，等于原始最优值。最优割形式：\( \eta \geq (\lambda_ A d_ A + \lambda_ B d_ B) + \mu_ 1 x_ 1 + \mu_ 2 x_ 2 \)，其中 \( d_ A=30, d_ B=50 \) 是需求常数。代入： \[ \eta \geq (4 30 + 5 50) + 0 x_ 1 + (-2) x_ 2 = 120 + 250 - 2x_ 2 = 370 - 2x_ 2. \] 将此割加入主问题。步骤8：更新主问题并第三次迭代主问题（MP₂）变为： \[ \text{最小化} \quad 2x_ 1 + 3x_ 2 + \eta \] 约束： \[ x_ 1 \leq 40, \quad x_ 2 \leq 60, \quad x_ 1 + x_ 2 \geq 80, \quad \eta \geq 370 - 2x_ 2, \quad x_ 1, x_ 2 \geq 0. \] 求解：目标 = \( 2x_ 1 + 3x_ 2 + \eta \geq 2x_ 1 + 3x_ 2 + 370 - 2x_ 2 = 2x_ 1 + x_ 2 + 370 \)。在约束下最小化 \( 2x_ 1 + x_ 2 \)，满足 \( x_ 1 \leq 40, x_ 2 \leq 60, x_ 1+x_ 2 \geq 80 \)。显然，最小化时让 \( x_ 1 \) 尽可能大（因为系数2 > 1？实际上系数2 > 1，所以应最小化 \( x_ 1 \)？不，目标是最小化 \( 2x_ 1 + x_ 2 \)，所以应优先减小 \( x_ 1 \)，因为其系数更大）。但约束 \( x_ 1+x_ 2 \geq 80 \)，所以取 \( x_ 1=0, x_ 2=80 \) 违反 \( x_ 2 \leq 60 \)，所以 \( x_ 2 \) 最大为60，则 \( x_ 1 \geq 20 \)。因此最优解为 \( x_ 1=20, x_ 2=60 \)，此时 \( 2x_ 1+x_ 2 = 40+60=100 \)，总目标下界 = 100+370=470。但还要考虑 \( \eta \) 可能更大？实际上，主问题会精确求解线性规划。我们直接求解MP₂：目标：最小化 \( 2x_ 1+3x_ 2+\eta \) 约束：\( \eta \geq 370-2x_ 2 \)，所以最优时取 \( \eta = 370-2x_ 2 \)（因为增大 \( \eta \) 会增加目标）。代入目标：\( 2x_ 1+3x_ 2+370-2x_ 2 = 2x_ 1 + x_ 2 + 370 \)。在约束 \( x_ 1 \leq 40, x_ 2 \leq 60, x_ 1+x_ 2 \geq 80, x_ 1, x_ 2 \geq 0 \) 下最小化 \( 2x_ 1+x_ 2 \)。作图或单纯形法：顶点有 (20,60), (40,40), (40,60) 等。计算： (20,60)：\( 2 20+60=100 \) (40,40)：\( 2 40+40=120 \) (40,60)：\( 2 40+60=140 \) 所以最优解为 \( x_ 1=20, x_ 2=60 \)，目标值 = 100+370=470。主问题最优解：\( \bar{x}_ 1=20, \bar{x}_ 2=60, \eta=370-2 60=250 \)。步骤9：第三次迭代给定主问题解：\( \bar{x}_ 1=20, \bar{x}_ 2=60 \)。求解子问题：运输问题，供应约束：\( y_ {1A}+y_ {1B} \leq 20, y_ {2A}+y_ {2B} \leq 60 \)，需求同上。求解最优运输：市场A需求30：从工厂1运20（成本4），从工厂2运10（成本6）。市场B需求50：工厂1无剩余，全部从工厂2运50（成本3）。运输成本 = \( 20 4 + 10 6 + 50 3 = 80 + 60 + 150 = 290 \)。对偶变量：设对偶变量同上形式，解对偶问题。由互补松弛性： \( y_ {1A}=20>0 \Rightarrow \lambda_ A+\mu_ 1=4 \) \( y_ {2A}=10>0 \Rightarrow \lambda_ A+\mu_ 2=6 \) \( y_ {2B}=50>0 \Rightarrow \lambda_ B+\mu_ 2=3 \) 供应约束：工厂1紧（20=20）⇒ \( \mu_ 1 \) 可非零；工厂2紧（10+50=60）⇒ \( \mu_ 2 \) 可非零。解方程组：从 \( \lambda_ A+\mu_ 2=6 \) 和 \( \lambda_ B+\mu_ 2=3 \) 得 \( \lambda_ A - \lambda_ B = 3 \)。从 \( \lambda_ A+\mu_ 1=4 \) 和 \( \lambda_ B+\mu_ 1=5 \)（？第二个方程应为 \( \lambda_ B+\mu_ 1=5 \) 来自 \( y_ {1B}=0 \) 的约化成本？实际上 \( y_ {1B}=0 \)，所以其约束 \( \lambda_ B+\mu_ 1 \leq 5 \) 不一定紧）。更严谨地，我们直接求解对偶最优值等于290，可设 \( \mu_ 1=0, \mu_ 2=-2, \lambda_ A=4, \lambda_ B=5 \) 也满足？检验：\( \lambda_ A+\mu_ 2=4-2=2 \neq 6 \)，不满足。所以需要新解。解方程： (1) \( \lambda_ A+\mu_ 1=4 \) (2) \( \lambda_ A+\mu_ 2=6 \) (3) \( \lambda_ B+\mu_ 2=3 \) 由(1)(2)得 \( \mu_ 2-\mu_ 1=2 \)。由(3)得 \( \lambda_ B=3-\mu_ 2 \)。对偶目标：\( 30\lambda_ A+50\lambda_ B+20\mu_ 1+60\mu_ 2 = 290 \)。代入 \( \lambda_ A=4-\mu_ 1 \) 和 \( \lambda_ B=3-\mu_ 2 \)： \( 30(4-\mu_ 1)+50(3-\mu_ 2)+20\mu_ 1+60\mu_ 2 = 120-30\mu_ 1+150-50\mu_ 2+20\mu_ 1+60\mu_ 2 = 270 -10\mu_ 1+10\mu_ 2 = 290 \Rightarrow -10\mu_ 1+10\mu_ 2=20 \Rightarrow \mu_ 2-\mu_ 1=2 \)，与上面一致。所以有无穷多解，取一组简单解：令 \( \mu_ 1=0 \)，则 \( \mu_ 2=2 \)，但 \( \mu_ 2 \leq 0 \) 是约束吗？在子问题中，供应约束是 ≤，对偶变量 \( \mu_ 1, \mu_ 2 \leq 0 \)。所以 \( \mu_ 2=2 \) 无效。需满足 \( \mu_ 1, \mu_ 2 \leq 0 \)。取 \( \mu_ 2=0 \)，则 \( \mu_ 1=-2 \)，代入得 \( \lambda_ A=6, \lambda_ B=3 \)，检验：\( \lambda_ A+\mu_ 1=6-2=4 \) 满足(1)，\( \lambda_ A+\mu_ 2=6+0=6 \) 满足(2)，\( \lambda_ B+\mu_ 2=3+0=3 \) 满足(3)。且对偶目标 = \( 30 6+50 3+20 (-2)+60 0=180+150-40=290 \)，正确。所以对偶最优解：\( \lambda_ A=6, \lambda_ B=3, \mu_ 1=-2, \mu_ 2=0 \)。生成最优割：\( \eta \geq 30 6+50 3 + (-2)x_ 1 + 0 x_ 2 = 180+150 -2x_ 1 = 330 - 2x_ 1 \)。将此割加入主问题。步骤10：更新主问题并继续迭代主问题（MP₃）加入新割 \( \eta \geq 330-2x_ 1 \) 和之前的割 \( \eta \geq 370-2x_ 2 \)。求解主问题：最小化 \( 2x_ 1+3x_ 2+\eta \) 约束： \( x_ 1 \leq 40, x_ 2 \leq 60, x_ 1+x_ 2 \geq 80 \) \( \eta \geq 370-2x_ 2 \) \( \eta \geq 330-2x_ 1 \) 非负。最优解应使 \( \eta = \max(370-2x_ 2, 330-2x_ 1) \)。为最小化目标，我们需平衡 \( x_ 1 \) 和 \( x_ 2 \)。枚举顶点：交点1：\( 370-2x_ 2 = 330-2x_ 1 \Rightarrow 2x_ 1 - 2x_ 2 = -40 \Rightarrow x_ 1 = x_ 2 - 20 \)。结合 \( x_ 1+x_ 2 \geq 80 \) 和边界。在可行域内，计算目标值。可求解线性规划：设目标为 \( 2x_ 1+3x_ 2+\eta \)，且 \( \eta \geq 370-2x_ 2, \eta \geq 330-2x_ 1 \)。在最优解处，至少一个割是紧的。尝试同时紧：\( 370-2x_ 2 = 330-2x_ 1 \Rightarrow x_ 1 = x_ 2 - 20 \)。代入 \( x_ 1+x_ 2 \geq 80 \) 得 \( 2x_ 2 -20 \geq 80 \Rightarrow x_ 2 \geq 50 \)。同时 \( x_ 1 \leq 40 \Rightarrow x_ 2 \leq 60 \)。取 \( x_ 2=50, x_ 1=30 \)，则 \( \eta = 370-2 50=270 \)，目标 = \( 2 30+3* 50+270=60+150+270=480 \)。检查其他顶点：如 \( x_ 1=20, x_ 2=60 \)（来自之前解），此时 \( \eta = \max(370-120=250, 330-40=290) = 290 \)，目标 = \( 40+180+290=510 \)。如 \( x_ 1=40, x_ 2=40 \)，则 \( \eta = \max(370-80=290, 330-80=250)=290 \)，目标 = \( 80+120+290=490 \)。如 \( x_ 1=40, x_ 2=60 \)（不可行，因为 \( x_ 1+x_ 2=100 \geq 80 \) 可行，但 \( \eta=\max(370-120=250, 330-80=250)=250 \)，目标 = \( 80+180+250=510 \)。最优似乎是 \( x_ 1=30, x_ 2=50 \)，目标=480。但需验证可行性：产能 \( x_ 1=30 \leq 40, x_ 2=50 \leq 60 \)，且 \( x_ 1+x_ 2=80 \geq 80 \) 满足。主问题最优解：\( \bar{x}_ 1=30, \bar{x}_ 2=50, \eta=270 \)。步骤11：第四次迭代给定主问题解：\( \bar{x}_ 1=30, \bar{x}_ 2=50 \)。求解子问题：运输问题，供应约束：\( y_ {1A}+y_ {1B} \leq 30, y_ {2A}+y_ {2B} \leq 50 \)。最优运输：市场A需求30：从工厂1运30（成本4），工厂2运0。市场B需求50：工厂1剩余0，工厂2运50（成本3）。运输成本 = \( 30 4 + 50 3 = 120+150=270 \)。此时子问题最优值 = 270，等于主问题中 \( \eta=270 \)，说明上下界相等，算法收敛。步骤12：输出最优解最优生产计划：\( x_ 1=30, x_ 2=50 \)，总生产成本 = \( 2 30+3 50=60+150=210 \)。最优运输计划：\( y_ {1A}=30, y_ {1B}=0, y_ {2A}=0, y_ {2B}=50 \)，总运输成本 = 270。总成本 = 210+270=480。算法结束。这个示例展示了Benders分解如何通过迭代主问题和子问题，逐步添加可行割和最优割，最终收敛到原问题的最优解。