基于线性规划的零一整数规划的分支定界法与分数割平面法求解示例
我将为您讲解如何结合分支定界法与分数割平面法来求解一个具体的零一整数规划问题。这个方法是解决NP难整数规划问题的经典精确算法框架，通过线性规划松弛、割平面添加和分支搜索，逐步逼近最优整数解。
第一步：问题描述
考虑一个简单的零一背包问题（0-1 Knapsack Problem）的变体，用于展示该方法：
问题：
一个投资者有100万元资金，有4个潜在项目可选择投资。每个项目有预期收益和所需投资额。项目可以部分投资（0 ≤ 投资比例 ≤ 1），但必须满足整体投资额不超过总资金。目标是最大化总收益。
数据：
- 项目1：收益 40万，投资额 60万
- 项目2：收益 20万，投资额 40万
- 项目3：收益 30万，投资额 50万
- 项目4：收益 25万，投资额 30万
- 总投资预算：100万
决策变量：
\[x_j \in \{0,1\}, \quad j=1,2,3,4 \]
\(x_j = 1\) 表示投资项目 \(j\)，否则不投资。
整数规划模型：
\[\begin{aligned} \max \quad & 40x_1 + 20x_2 + 30x_3 + 25x_4 \\ \text{s.t.} \quad & 60x_1 + 40x_2 + 50x_3 + 30x_4 \leq 100 \\ & x_j \in \{0,1\}, \quad j=1,2,3,4 \end{aligned} \]
第二步：初始线性规划松弛
我们首先求解线性规划松弛，即把整数约束 \(x_j \in \{0,1\}\) 松弛为连续约束 \(0 \leq x_j \leq 1\)。
松弛后的线性规划：
\[\begin{aligned} \max \quad & 40x_1 + 20x_2 + 30x_3 + 25x_4 \\ \text{s.t.} \quad & 60x_1 + 40x_2 + 50x_3 + 30x_4 \leq 100 \\ & 0 \leq x_j \leq 1, \quad j=1,2,3,4 \end{aligned} \]
用单纯形法求解这个线性规划，得到最优解：
\[x_1 = 1, \quad x_2 = 0, \quad x_3 = 0.8, \quad x_4 = 1 \]
最优目标值：
\[z_{LP} = 40 \times 1 + 20 \times 0 + 30 \times 0.8 + 25 \times 1 = 40 + 0 + 24 + 25 = 89 \]
注意：这个解中 \(x_3 = 0.8\) 不是整数，违反整数约束。因此我们需要通过割平面和分支来寻找整数最优解。
第三步：生成分数割平面（Gomory割）
观察松弛解中 \(x_3 = 0.8\) 是分数。我们从单纯形表的最终行中提取关于 \(x_3\) 的约束。
假设单纯形表给出基变量 \(x_3\) 的表达式为：
\[x_3 = 0.8 - 0.2x_2 + 0.4s \]
其中 \(s\) 是松弛变量，且 \(x_2\) 是非基变量（值为0），\(s\) 是非基变量（值为0）。但更标准的方法是直接从最终单纯形表中取基变量 \(x_3\) 所在行的方程。
实际上，单纯形表给出基变量 \(x_3\) 的方程为：
\[x_3 + 0.2x_2 - 0.4s = 0.8 \]
其中 \(x_2\) 和 \(s\) 是非基变量（在松弛解中为0）。
Gomory割构造：
- 将系数和右端项分解为整数部分和分数部分。记 \(a = \lfloor a \rfloor + f\)，其中 \(0 \leq f < 1\)。
- 对系数：
\[x_3: 1 = 1 + 0 \]
\[ x_2: 0.2 = 0 + 0.2 \]
\[ s: -0.4 = -1 + 0.6 \quad (\text{因为} -0.4 = -1 + 0.6) \]
- 右端项：
\[0.8 = 0 + 0.8 \]
分数部分：
- 对于 \(x_3\) 系数：分数部分 0
- 对于 \(x_2\) 系数：分数部分 0.2
- 对于 \(s\) 系数：分数部分 0.6
- 右端项：分数部分 0.8
Gomory割：
\[\sum_{j \in N} f_j x_j \geq f_0 \]
其中 \(N\) 是非基变量集合，\(f_j\) 是系数的分数部分，\(f_0\) 是右端项的分数部分。
因此得到割平面：
\[0.2x_2 + 0.6s \geq 0.8 \]
但 \(s\) 是松弛变量，我们需要用原始变量表示。从预算约束：
\[s = 100 - 60x_1 - 40x_2 - 50x_3 - 30x_4 \]
代入割平面：
\[0.2x_2 + 0.6(100 - 60x_1 - 40x_2 - 50x_3 - 30x_4) \geq 0.8 \]
化简：
\[0.2x_2 + 60 - 36x_1 - 24x_2 - 30x_3 - 18x_4 \geq 0.8 \]
\[ -36x_1 - 23.8x_2 - 30x_3 - 18x_4 \geq 0.8 - 60 \]
\[ -36x_1 - 23.8x_2 - 30x_3 - 18x_4 \geq -59.2 \]
乘以 5 去掉小数：
\[-180x_1 - 119x_2 - 150x_3 - 90x_4 \geq -296 \]
整理：
\[180x_1 + 119x_2 + 150x_3 + 90x_4 \leq 296 \]
添加割平面后的新线性规划：
\[\begin{aligned} \max \quad & 40x_1 + 20x_2 + 30x_3 + 25x_4 \\ \text{s.t.} \quad & 60x_1 + 40x_2 + 50x_3 + 30x_4 \leq 100 \\ & 180x_1 + 119x_2 + 150x_3 + 90x_4 \leq 296 \\ & 0 \leq x_j \leq 1, \quad j=1,2,3,4 \end{aligned} \]
求解这个线性规划，得到新解：
\[x_1 = 1, \quad x_2 = 0, \quad x_3 = 2/3 \approx 0.667, \quad x_4 = 1 \]
目标值：
\[z_{LP1} = 40 + 0 + 30 \times 2/3 + 25 = 40 + 0 + 20 + 25 = 85 \]
注意：目标值下降（从89到85），并且 \(x_3 = 2/3\) 仍然是分数。可以继续添加割平面，但通常更高效的做法是转入分支。
第四步：分支定界法
我们以当前最优节点（目标值85，分数解）为起点，进行分支。
分支变量选择：选择分数值最远离整数的变量。这里 \(x_3 = 0.667\)，分数部分0.667，选择 \(x_3\) 进行分支。
创建两个子问题：
子问题A：\(x_3 = 0\)
\[\begin{aligned} \max \quad & 40x_1 + 20x_2 + 30 \times 0 + 25x_4 \\ \text{s.t.} \quad & 60x_1 + 40x_2 + 50 \times 0 + 30x_4 \leq 100 \\ & 0 \leq x_1, x_2, x_4 \leq 1 \end{aligned} \]
求解得：
\[x_1 = 1, \quad x_2 = 0, \quad x_4 = 1, \quad z_A = 40 + 0 + 0 + 25 = 65 \]
这是整数可行解。记录为当前最优整数解，目标值65。
子问题B：\(x_3 = 1\)
\[\begin{aligned} \max \quad & 40x_1 + 20x_2 + 30 \times 1 + 25x_4 \\ \text{s.t.} \quad & 60x_1 + 40x_2 + 50 \times 1 + 30x_4 \leq 100 \\ & 0 \leq x_1, x_2, x_4 \leq 1 \end{aligned} \]
简化：
\[\max \quad 40x_1 + 20x_2 + 25x_4 + 30 \]
\[ 60x_1 + 40x_2 + 30x_4 \leq 50 \]
求解这个线性规划：
- 尝试 \(x_1 = 1\)，则 \(40x_2 + 30x_4 \leq -10\) 不可能，所以 \(x_1 = 0\)。
- 约束变为 \(40x_2 + 30x_4 \leq 50\)。
- 为使收益最大，优先选单位投资收益高的：\(x_4\) 单位收益 \(25/30 \approx 0.833\)，\(x_2\) 单位收益 \(20/40 = 0.5\)，所以尽量让 \(x_4 = 1\)，则 \(40x_2 \leq 20\)，\(x_2 \leq 0.5\)。
- 取 \(x_2 = 0.5, x_4 = 1\)，目标值 = \(0 + 20 \times 0.5 + 25 \times 1 + 30 = 10 + 25 + 30 = 65\)。
得到解：\(x_1=0, x_2=0.5, x_3=1, x_4=1\)，目标值65。
注意：子问题B的目标值也是65，但有分数解 \(x_2=0.5\)，且目标值等于当前最优整数解65。因为这是最大化问题，子问题B的线性规划松弛目标值65，其任何整数解的目标值不会超过65，所以子问题B可以被剪枝（不会产生比65更好的整数解）。
此时搜索结束，因为所有节点都已处理（子问题A给出整数解65，子问题B被剪枝）。
第五步：验证与总结
最优整数解：从子问题A得到 \(x_1=1, x_2=0, x_3=0, x_4=1\)，总投资额 \(60+0+0+30=90 \leq 100\)，总收益 \(40+0+0+25=65\)。
检查是否还有其他整数解：
- 枚举几个组合：选择项目1和3：投资额110 > 100，不可行。
- 选择项目3和4：投资额80 ≤ 100，收益55 < 65。
- 选择项目2、3、4：投资额120 > 100，不可行。
- 选择项目1、2：投资额100 ≤ 100，收益60 < 65。
- 选择项目1、4：投资额90 ≤ 100，收益65（即最优解）。
因此最优解唯一，收益65万。
方法总结
- 线性规划松弛：将整数约束放松，快速得到上界。
- 割平面法：当松弛解非整数时，添加Gomory割等割平面，切割掉当前分数解但不切掉任何整数可行解，从而收紧上界。
- 分支定界：对分数变量分支，分为两个子问题（变量=0 或 =1），递归求解。
- 剪枝：若子问题的上界不超过当前最优整数解，则剪枝；若得到整数解，则更新最优解。
- 组合应用：通常先添加少量割平面，再分支，可以加速搜索。
这种方法能确保找到全局最优解，是求解中小规模零一整数规划问题的有效精确算法。