# 从分数排班到整数最优：完整题解与验收证书

## 任务

完成三个层次不同的工作：

1. 为四人四任务分配模型证明 LP 整数性，并把给定分数排班拆成真正的一对一排班
2. 求解带五圈冲突及条件容量的设备选择问题，给出全局割、局部分支割、原始可行解及同值上界
3. 对指定三角形证明 CG rank 恰为四，分别提供足够性和不可更早完成的证据

另有两项独立练习：从一条 tableau 行推出 Gomory 分数割；对二维整数规划完整展开一棵分支定界树。它们检验割与上界的基础机制，不与最终设备模型混用。

## 运行方式与文件约定

```sh
python foundation-integer-capstone.py results.json
```

脚本只使用 Python 3 标准库。所有 LP 点、对偶乘子、分解权重与行列式均以 Fraction 精确计算。JSON 中整数按整数输出，非整数有理数写为 p/q 字符串。

LP 子程序仅用于本题有界多面体：枚举独立紧约束组，精确求交点、检查全部约束，再取目标最大者。有限最优结点另外寻找非负对偶乘子并核对 Aᵀy=c、bᵀy=cᵀx。无顶点被解释为不可行只因为调用者已经保证可行域有界；不能把这个教学子程序直接用于一般含直线的多面体。

## 一、四对四分配与实际排班

### 1. 先证明整个模型整数

每人恰做一项任务、每项任务恰分配一人，变量矩阵满足 X≥0，全部行和与列和均为一。这是完全二分图上的完美匹配模型。

点边关联矩阵每列有两个一；把人员侧对应行乘负一，得到有向图的关联矩阵。任意方形子矩阵若有零列则行列式为零，若某列只含一个非零则沿列展开，若每列都含两个非零则每列一正一负、行和为零。因此所有子式只能为 0、±1，矩阵 TU。

等式拆成正反两条不等式，加入非负单位行，仍保留 TU。整数右端一通过 Cramer 法则给出整数顶点，所以这份 LP 描述的整个可行域就是置换矩阵的凸包。这个证明适用于所有该规模分配目标，并不是只观察下面一份矩阵得到了漂亮分解。

### 2. 输入与三次扣减

给定

X =

| | 任务0 | 任务1 | 任务2 | 任务3 |
|---|---:|---:|---:|---:|
| 人0 | 1/2 | 1/3 | 1/6 | 0 |
| 人1 | 0 | 1/2 | 1/3 | 1/6 |
| 人2 | 1/6 | 0 | 1/2 | 1/3 |
| 人3 | 1/3 | 1/6 | 0 | 1/2 |

保持残余矩阵 R 的所有行和、列和都等于共同剩余质量 ρ，不在每轮重新归一化。

- 初始 ρ=1，选择置换 π₀=(0,1,2,3)，扣去 α₀=1/2，四个对角元归零，ρ=1/2
- 选择 π₁=(1,2,3,0)，扣去 α₁=1/3，四个循环移位位置归零，ρ=1/6
- 剩余正支撑只有 π₂=(2,3,0,1)，扣去 α₂=1/6，R=0

因此 X=(1/2)Pπ₀+(1/3)Pπ₁+(1/6)Pπ₂。三权重均非负、和为一，每项由对应置换位置逐项重构。分六个相等时段运行，三段用 π₀、两段用 π₁、一段用 π₂，就得到实际时分排班。

每轮的匹配存在性来自 Hall 条件。若 S 是一些行，其质量为 ρ|S|，只能流向正支撑邻列 N(S)，后者容量至多 ρ|N(S)|。ρ>0 时可除去，得到 |S|≤|N(S)|。扣匹配后每行每列减去同一个 α，因此不变量保持。

初始正元数 s=12，每个非最终步骤至少去掉一个正元，最终正质量残余至少有 n=4 个正元，所以轮数上界 s−n+1=9，本例实际为三轮。程序使用 Hopcroft–Karp 找支撑完美匹配，并维护删边支撑集合，没有枚举全部置换来冒充多项式匹配算法。另对全部 512 个 3×3 零一支撑图，与枚举置换的独立存在性判定对照。

## 二、有效割的基础练习

### 1. Gomory 分数行

原行是 xB=3/2−(1/2)x₁−(1/4)x₂，三变量都要求非负整数。分数割为 (1/2)x₁+(1/4)x₂≥1/2，即 2x₁+x₂≥2。

推导：把各系数整数部分移到左边，得到一个整数等于 1/2−[(1/2)x₁+(1/4)x₂]。括号内非负，且与 1/2 相差整数，所以不能小于 1/2。当前基点 x₁=x₂=0、xB=3/2 被排除，全部非负整数解保留。

原行的非负整数解恰为：

| xB | x₁ | x₂ |
|---:|---:|---:|
| 1 | 0 | 2 |
| 1 | 1 | 0 |
| 0 | 0 | 6 |
| 0 | 1 | 4 |
| 0 | 2 | 2 |
| 0 | 3 | 0 |

负系数必须向下取整：f(−1/4)=3/4。连续变量会使同余证明失效，例如 xB=3/2−(3/2)z、z=1/3、xB=1 合法，但误用纯整数割会要求 (1/2)z≥1/2，删掉这个点。

### 2. 不要把一条割等同于全部整数包

每条割只保证整数有效性和对当前点的分离。重新求 LP 还可能得到其他分数点；任意选择下一条割也不自动获得有限或多项式终止保证。下一部分用“同时加全部合法割”的几何闭包，才能严格定义轮数 rank。

## 三、CG rank 恰为四

### 1. 几何定义和表示无关性

对非空有理 P，定义 hP(c)=max{cᵀx:x∈P}，只取有限支持值的整数法向 c。一次闭包是 P 与全部 cᵀx≤floor(hP(c)) 的交。

若 P={Ax≤b}，强对偶保证有限 hP(c) 可写成最优非负乘子 λ 的 λᵀb，其中 Aᵀλ=c。任意其他可行乘子只给更大的右端，所以乘子形式与支持值形式相同，闭包取决于 P，不取决于缩放或冗余行的选择。

令 P⁽⁰⁾=P，P⁽ᵗ⁺¹⁾为 P⁽ᵗ⁾的一次闭包。rank 是第一次达到整数包的轮数，不是一个有限证明里出现了多少行不等式。

### 2. 四轮足够的证书

原多胞形 T₂=conv{(0,0),(1,0),(1/2,2)}，等价于 0≤x≤1、y≥0、y≤4x、y≤4−4x。仅有两个整数点 (0,0)、(1,0)，整数包为底边。

| 轮 | 整数法向 | 可认证支持上界 | 取整割 | 得到的高度上界 |
|---|---|---:|---|---:|
| 1 | (1,1)、(−1,1) | 5/2、3/2 | x+y≤2，−x+y≤1 | 3/2 |
| 2 | (0,1) | 3/2 | y≤1 | 1 |
| 3 | (1,1)、(−1,1) | 7/4、3/4 | x+y≤1，−x+y≤0 | 1/2 |
| 4 | (0,1) | 1/2 | y≤0 | 0 |

第三轮的支持上界只需在原三角形与 y≤1 的交上计算；它是实际第二闭包的外包络，故上界有效。脚本展示的是这些指定割形成的逐轮外包络，不声称用有限几个方向完整枚举了中间所有 CG 割。

第四轮仍保留两个整数底点，又被 y≥0、y≤0 夹住，因此等于整数包，rank≤4。

### 3. 三轮不够必须证明所有方向

对半整数 h≥1/2，令 Th=conv{(0,0),(1,0),(1/2,h)}。证明其一次闭包包含 T(h−1/2)。只需证明 q=(1/2,h−1/2) 通过所有整数法向 (a,b) 的取整割。

- 若 b≤0，q 的目标值≤max(0,a)，而 max(0,a) 已是两个整数底点给出的整数值
- 若 b≥1，q 的目标值比旧顶点少 b/2≥1/2；旧支持值是三个数 0、a、a/2+bh 的最大值，只能是整数或半整数，所以向下取整损失至多 1/2，q 仍通过

两个底点也保留，取凸包便得到包含关系。再用闭包单调性 Q⊆P⇒Q′⊆P′，从 T₂ 依次得到前三轮仍含点 (1/2,3/2)、(1/2,1)、(1/2,1/2)。它们都不在整数底边，因此 rank≥4，与上界相遇。

程序对每个 h 额外检查 −12≤a,b≤12 的 624 个非零整数法向，四次共 2496 次。这只是核对实现与算术，真正覆盖无限方向的是上面的两情况证明。

## 四、二维分支定界树

最大化 8x+5y，满足 3x+2y≤7、0≤x≤2、0≤y≤3，x,y 为整数。

| 结点 | LP 点 | 值/上界 | 认证方式 |
|---|---|---:|---|
| 根 | (2,1/2) | 37/2 | (5/2)资源+(1/2)(x≤2) |
| y≤0 | (2,0) | 16 | 8(x≤2)+5(y≤0) |
| y≥1 | (5/3,1) | 55/3 | (8/3)资源+(1/3)(−y≤−1) |
| y≥1,x≤1 | (1,2) | 18 | (5/2)资源+(1/2)(x≤1) |
| y≥1,x≥2 | 不可行 | — | 资源+3(−x≤−2)+2(−y≤−1)给0≤−1 |

先找到整数解 16，再找到 18；剩下结点不可行，结束时全局上下界同为 18。若先找到 18，左支上界 16 可以直接界剪。若利用整数目标取整，根界 18.5 也可降为 18，说明更强证书能够减少搜索；此树展示的是未使用该额外剪枝时的完整执行。

## 五、全局奇圈割与局部容量割

### 1. 原模型

x₀,…,x₄∈{0,1}，冲突约束 ei 为 xi+x(i+1 mod5)≤1，条件容量 g 为 2x₂−2x₀≤1，目标

z=5x₀+5x₁+8x₂+7x₃+7x₄。

非负性和冲突约束已给每个变量上界一。选择 (1,0,1,0,0) 的收益是 13，但必须证明没有其他整数方案更好。

### 2. 每个阶段都有原始点和上界

| 阶段 | LP 最优点 | 上界 |
|---|---|---:|
| 根 | (1/2,1/2,1/2,1/2,1/2) | 16 |
| 加全局奇圈割 h:Σxi≤2 | (1/4,0,3/4,1/4,3/4) | 57/4 |
| 左支 x₀≤0，尚未加局部割 | (0,1/2,1/2,0,1) | 27/2 |
| 左支再加局部割 x₂≤0 | (0,1,0,0,1) | 12 |
| 右支 x₀≥1 | (1,0,1,0,0) | 13 |
| 错误地全局加入 x₂≤0 | (0,1,0,0,1) | 12，但模型已错误 |

根上界由 e₀+4e₁+4e₂+3e₃+4e₄ 得到，系数恰为目标、右端 16。奇圈割由每条 ei 乘 1/2，聚合得到 Σxi≤5/2，再用整数性取整。

加奇圈割后的上界证书是 (13/2)h+(3/4)g+(1/2)e₃+(3/2)(−x₁≤0)，右端 57/4。

左支尚未加局部割时，上界由 5e₁+7e₃+(3/2)g+8(x₀≤0) 给出，右端 27/2。

局部割的证书是 (1/2)g+(x₀≤0)，得到 x₂≤1/2，再取整成 x₂≤0。加入后用 5e₀+7e₃+8(x₂≤0) 得到上界 12，且有同值整数点，可以关闭左支。

右支 x₀=1 迫使 x₁=x₄=0，x₂+x₃≤1，所以 z=5+8x₂+7x₃≤13，在 (1,0,1,0,0) 达到。也可以使用报告中的完整非负对偶乘子核验：8h+3(−x₀≤−1)+3(−x₁≤0)+(−x₃≤0)+(−x₄≤0)，右端 13。

### 3. 作用域为什么不能丢

左支的 x₂≤0 用到了 x₀≤0，它只能在该子树继承。右支最优点恰有 x₂=1，若跨支复用，真实唯一最优点被删，错误模型最多得到 12。程序枚举全部 32 个二元赋值，验证原模型有九个整数可行点，唯一最优为 (1,0,1,0,0)。

全局提升形式是 x₂−x₀≤0：原容量除二后左端已经整数，直接 floor 右端即可。保留 x₀ 项是全局有效，代入 x₀=0 才成为左支的 x₂≤0。本次展示的根仅选择奇圈割后分支，不声称做了完整 CG 闭包。选择性加割与全部闭包是两个不同过程。

### 4. 最终闭合

根的二元分支覆盖全部整数点，左支最优 12、右支最优 13，所以全局上界为 max(12,13)=13；已有整数可行解收益 13，故上下界闭合。每条割都保留其作用域里的全部整数点，没有用“当前分数点被切掉”替代整数有效性证明。

## 六、额外小例子与测试范围

- 对四行五列有向关联矩阵，枚举全部方形子式，验证只取 0、±1；三角形关联矩阵行列式为 2
- 对普通二分四环度多胞形，验证全部顶点为整数；三角形度松弛恰出现全一半分数顶点；加入全部奇集后，三角形与五环的顶点全为匹配
- 三棱柱每边 1/3 的紧奇割例，验证三个完美匹配 {ad,bc,ef}、{be,ac,df}、{cf,ab,de} 的均值逐边重构；每份匹配都覆盖六个不同顶点
- 对权重矩阵 ((5,4),(4,1))，验证交叉匹配收益 8，整数顶点价格 (4,3,1,0) 可行且总价同为 8
- 对分数多边形 2x+y≤3、x+2y≤3、x,y≥0，验证四个整数点的凸包是单位正方形；最大化 x 的 LP 值 3/2，而整数最优为 1

这些小规模精确计算不是对所有规模定理的证明；普遍结论依靠正文的 TU 子式归纳、Hall 条件、奇割收缩以及全部整数法向论证。

## 七、最终验收

1. 分配矩阵行列和、非负性、每份置换、每轮剩余质量、权重总和及逐项重构全部通过
2. Gomory 行的全部变量类型明确，负数使用 floor；连续变量反例确实违反误套的割
3. CG 上界割逐轮合法，下界覆盖无限法向；未把有限割外包络误称完整中间闭包
4. 每个有限 LP 结点检查原始可行性、对偶非负性、Aᵀy=c 与目标相等；不可行叶检查 0≤−1 证书
5. 分支完整，incumbent 整数可行，活结点均关闭；局部割只在其祖先作用域内使用
6. 最终全局值 13 与唯一整数方案一致；错误跨支复用确实造成 12 的错误答案
7. 报告枚举 LP 顶点的教学成本与真正分支切割求解器成本区别；大有理数的位运算成本不被当作常数