线性规划的分解算法求解示例
题目描述
考虑一个大型线性规划问题，其约束矩阵具有特殊的块角结构（Block Angular Structure）。这类问题常见于多工厂、多产品的生产规划场景。假设某公司有两个工厂（工厂1和工厂2），每个工厂生产两种产品（产品A和产品B）。每个工厂有各自的资源约束（如劳动力、原材料），同时公司有整体的共享资源约束（如总预算）。目标是在满足所有约束下最大化总利润。
具体模型如下：
决策变量：
- \(x_{ij}\)：工厂i生产产品j的数量（i=1,2；j=A,B）
目标函数：
最大化总利润：
\[\max Z = 5x_{1A} + 4x_{1B} + 6x_{2A} + 3x_{2B} \]
约束条件：
- 共享资源约束（公司级）：
\[ x_{1A} + 2x_{1B} + 3x_{2A} + x_{2B} \leq 10 \quad \text{(共享资源限制)} \]
- 工厂1的局部约束：
\[ 2x_{1A} + x_{1B} \leq 8 \quad \text{(工厂1产能)} \]
\[ x_{1A} + 2x_{1B} \leq 7 \quad \text{(工厂1原材料)} \]
- 工厂2的局部约束：
\[ x_{2A} + 3x_{2B} \leq 9 \quad \text{(工厂2产能)} \]
\[ 2x_{2A} + x_{2B} \leq 6 \quad \text{(工厂2原材料)} \]
- 非负性：
\[ x_{ij} \geq 0 \quad \text{对所有i,j} \]
该问题的约束矩阵呈现块角结构：
- 共享约束涉及所有变量，
- 工厂1的约束仅涉及 \(x_{1A}, x_{1B}\)，
- 工厂2的约束仅涉及 \(x_{2A}, x_{2B}\)。
解题过程
分解算法（如Dantzig-Wolfe分解）将问题分解为一个主问题（Master Problem）和多个子问题（Subproblems），通过迭代求解主问题和子问题来避免直接处理大规模模型。以下是逐步推导：
步骤1：问题分解
- 主问题：处理共享约束（式1），代表资源协调层。
- 子问题：每个工厂独立求解其局部问题（式2-5），生成可行生产方案。
- 子问题1（工厂1）：约束为式2和式3，变量为 \(x_{1A}, x_{1B}\)。
- 子问题2（工厂2）：约束为式4和式5，变量为 \(x_{2A}, x_{2B}\)。
步骤2：子问题的可行顶点枚举
每个子问题的可行域是多面体，其极点（顶点）代表基础生产方案。
-
子问题1的顶点（通过枚举约束交点）：
- 顶点P1: \((x_{1A}, x_{1B}) = (0,0)\)，利润贡献：0
- 顶点P2: \((4,0)\)（由 \(2x_{1A} + x_{1B} = 8\) 和 \(x_{1B}=0\) 解得），利润：\(5*4 + 4*0 = 20\)
- 顶点P3: \((3,2)\)（由 \(2x_{1A} + x_{1B} = 8\) 和 \(x_{1A} + 2x_{1B} = 7\) 解得），利润：\(5*3 + 4*2 = 23\)
- 顶点P4: \((0,3.5)\)（由 \(x_{1A}=0\) 和 \(x_{1A} + 2x_{1B} = 7\) 解得），利润：14
- 顶点P5: \((2,3)\)（由 \(x_{1A} + 2x_{1B} = 7\) 和 \(x_{1A}=2\) 插值？实际需验证可行性：代入式2: \(2*2+3=7 \leq 8\)；式3: \(2+2*3=8>7\) 不可行？修正：正确顶点应为约束交点。重新计算：
- 式2和式3的交点：解方程 \(2x_{1A} + x_{1B} = 8\) 和 \(x_{1A} + 2x_{1B} = 7\)，得 \(x_{1A}=3, x_{1B}=2\)（顶点P3）。
- 其他顶点：与坐标轴交点：\((0,0)\)、\((4,0)\)、\((0,3.5)\)。
- 因此子问题1有4个顶点：P1(0,0), P2(4,0), P3(3,2), P4(0,3.5)。
-
子问题2的顶点：
- 顶点Q1: \((0,0)\)，利润：0
- 顶点Q2: \((3,0)\)（由 \(2x_{2A} + x_{2B} = 6\) 和 \(x_{2B}=0\) 解得），利润：18
- 顶点Q3: \((0,3)\)（由 \(x_{2A} + 3x_{2B} = 9\) 和 \(x_{2A}=0\) 解得），利润：9
- 顶点Q4: \((2,2)\)（由 \(2x_{2A} + x_{2B} = 6\) 和 \(x_{2A} + 3x_{2B} = 9\) 解得？验证：式4: \(2+3*2=8 \leq 9\)；式5: \(2*2+2=6 \leq 6\)，利润：\(6*2 + 3*2 = 18\)）
- 顶点Q5: \((1,4)\)（由 \(x_{2A} + 3x_{2B} = 9\) 和 \(x_{2A}=1\) 得 \(x_{2B}=8/3 \approx 2.67\)，但代入式5: \(2*1 + 2.67=4.67>6\) 不可行）。修正：正确顶点为约束交点：
- 式4和式5的交点：解 \(x_{2A} + 3x_{2B} = 9\) 和 \(2x_{2A} + x_{2B} = 6\)，得 \(x_{2A}=1.8, x_{2B}=2.4\)（顶点Q4）。
- 其他顶点：\((0,0)\)、\((3,0)\)、\((0,3)\)。
- 因此子问题2有4个顶点：Q1(0,0), Q2(3,0), Q3(0,3), Q4(1.8,2.4)。
步骤3：主问题构建
主问题的变量是子问题顶点的权重（凸组合系数）：
- \(\lambda_k\)：代表工厂1采用顶点Pk的方案权重（k=1,...,4）。
- \(\mu_m\)：代表工厂2采用顶点Qm的方案权重（m=1,...,4）。
主问题形式：
\[\max Z = \sum_{k=1}^4 (5p_{kA} + 4p_{kB}) \lambda_k + \sum_{m=1}^4 (6q_{mA} + 3q_{mB}) \mu_m \]
约束：
- 共享资源约束：
\[ \sum_{k=1}^4 (p_{kA} + 2p_{kB}) \lambda_k + \sum_{m=1}^4 (3q_{mA} + q_{mB}) \mu_m \leq 10 \]
（其中 \(p_{kA}\) 是顶点Pk的x_{1A}值，例如P3的 \(p_{3A}=3, p_{3B}=2\)）
2. 凸组合约束（保证权重和为1）：
\[ \sum_{k=1}^4 \lambda_k = 1, \quad \sum_{m=1}^4 \mu_m = 1 \]
- 非负性： \(\lambda_k, \mu_m \geq 0\)。
步骤4：迭代求解（列生成）
由于顶点数量多，直接枚举低效，采用列生成法逐步添加顶点。
- 初始主问题：仅包含部分顶点（如每个子问题的原点顶点P1和Q1）。
- 初始主问题：
\[ \max Z = 0\lambda_1 + 0\mu_1 \]
约束：
- 共享资源： $ (0+2*0)\lambda_1 + (3*0+0)\mu_1 \leq 10 $ → 0 ≤ 10
- 凸组合： $ \lambda_1 = 1, \mu_1 = 1 $
解： $ \lambda_1=1, \mu_1=1, Z=0 $。
- 子问题求解（生成新列）：
- 主问题共享约束的对偶变量记为 \(\pi\)（本例中只有一个共享约束）。
- 子问题1的减少成本（Reduced Cost）为：
\[ \text{RC1} = (5 - \pi \cdot 1)x_{1A} + (4 - \pi \cdot 2)x_{1B} \]
其中 $ \pi $ 是主问题共享约束的对偶值。初始主问题中，共享约束宽松（0 ≤ 10），故 $ \pi = 0 $。
子问题1的目标：最大化 $ 5x_{1A} + 4x_{1B} $，解为顶点P3(3,2)，利润=23。
- 同理，子问题2在 \(\pi=0\) 下最大化 \(6x_{2A} + 3x_{2B}\)，解为顶点Q2(3,0)，利润=18。
- 添加新列：
- 将顶点P3和Q2加入主问题，主问题变为：
\[ \max Z = 23\lambda_3 + 18\mu_2 \]
约束：
- 共享资源： $ (3 + 2*2)\lambda_3 + (3*3 + 0)\mu_2 \leq 10 $ → $ 7\lambda_3 + 9\mu_2 \leq 10 $
- 凸组合： $ \lambda_1 + \lambda_3 = 1 $, $ \mu_1 + \mu_2 = 1 $
- 非负性。
求解：尝试组合：若 $ \lambda_3=1, \mu_2=1 $，则共享资源：7+9=16>10不可行。需线性规划求解：
- 最优解： $ \lambda_3=1, \mu_2=0.333 $（满足 $ 7*1 + 9*0.333 = 10 $），Z=23 + 18*0.333=29。
- 下一次迭代：
- 更新对偶变量 \(\pi\)（主问题共享约束的边际价值）。通过主问题求解得到 \(\pi \approx 2\)（具体值需计算对偶）。
- 子问题1的新目标：最大化 \((5-2*1)x_{1A} + (4-2*2)x_{1B} = 3x_{1A} + 0x_{1B}\)，最优解为P2(4,0)，减少成本=12>0，可加入。
- 子问题2的新目标：最大化 \((6-2*3)x_{2A} + (3-2*1)x_{2B} = 0x_{2A} + 1x_{2B}\)，最优解为Q3(0,3)，减少成本=3>0，可加入。
- 添加新列后主问题重新求解，直至所有减少成本非正（最优条件）。
步骤5：终止与还原
当子问题的减少成本均非正时，主问题达到最优。最终主问题的解通过顶点权重组合还原原变量：
- 例如最优权重 \(\lambda_3=1, \mu_4=1\)（假设），则 \(x_{1A}=3, x_{1B}=2, x_{2A}=1.8, x_{2B}=2.4\)。
通过分解，将6个约束的原问题转化为多次小规模问题求解，提升计算效率。