预置示例
max 7x₁+9x₂，两个线性约束，LP松弛解为分数，需多轮割平面
问题参数
问题形式
max7x₁ + 9x₂
s.t.-x₁ + 3x₂ ≤ 6
s.t.7x₁ + x₂ ≤ 35
s.t.x₁, x₂ ≥ 0
s.t.x₁, x₂ 整数
| 约束 \ 变量 | x₁ℤ | x₂ℤ | ≤ b |
|---|---|---|---|
| 约束 1 | -1 | 3 | 6 |
| 约束 2 | 7 | 1 | 35 |
| 目标系数 c | 7 | 9 | — |
最优结果
最优值
55.000
割平面数
0
x* = [4, 3]
步骤 1 / 12
Gomory 分数割平面算法。变量数: 2，约束数: 2
112
速度:
可行域（2变量）
步骤日志
1.Gomory 分数割平面算法。变量数: 2，约束数: 2
2.初始化单纯形表，松弛变量已添加。
3.Pivot: x₂ 入基，s1 出基。目标值 = 18
4.Pivot: x₁ 入基，s2 出基。目标值 = 63
5.LP 松弛最优，目标值 = 63
6.第 1 轮：LP 最优解含分数值。选择诱导行: x₂，RHS = 3.5，分数部分 r_{i0} = 0.5
7.生成 Gomory 割平面 #1：0.0455s2 + 0.3182s1 ≥ 0.5
8.对偶单纯形 pivot: s1 入基，s3 出基
9.第 2 轮：LP 最优解含分数值。选择诱导行: x₁，RHS = 4.5714，分数部分 r_{i0} = 0.5714
10.生成 Gomory 割平面 #2：0.1429s2 + 0.8571s3 ≥ 0.5714
11.对偶单纯形 pivot: s2 入基，s4 出基
12.所有整数变量已取整数值，找到最优整数解。目标值 = 55