第5章 · 第三部分

整数线性规划的全单位模矩阵

当LP松弛自动给出整数最优解——TUM的理论与应用

⚡ 核心问题

整数规划通常比线性规划难得多（NP-hard）。但有一类特殊的整数规划，其LP松弛的最优解自动是整数——这背后的数学基础是什么？

✅ 正确！这正是全单位模矩阵（Totally Unimodular Matrix, TUM）的神奇之处。当约束矩阵是TUM且右端向量为整数时，线性规划松弛的所有顶点都是整数点——求解LP即求解ILP！网络流、二分图匹配等经典组合优化问题都有此性质。

❌ 再想想。整数规划确实难，但也存在"免费午餐"——当约束矩阵具有特殊的代数结构（全单位模性），线性规划的解自然就是整数。这是连接连续优化和组合优化的关键桥梁。

🎯 学习目标

理解整数线性规划（ILP）的三种形式及其计算复杂性
掌握全单位模矩阵（TUM）的定义与基本性质
理解并证明 Hoffman-Kruskal 定理（ILP ⇔ LP 的充要条件）
掌握 TUM 的充分条件判别定理（Theorem 3）
理解 TUM 与组合优化（网络流、匹配、运输问题）的深刻联系
能判断给定矩阵是否为 TUM

1 整数线性规划的三种形式

$$\begin{aligned} \min \;& c^T x \\ \text{s.t.} \;& Ax = b,\; x \ge 0,\; x \in \Z^n \end{aligned}$$

所有变量都必须取整数。即使去掉整数约束后是标准 LP，ILP 也是NP-hard。

$$x_j \in \B$$

0-1变量常用于建模逻辑决策。看似限制更强，但计算复杂性与纯ILP等价。

$$x_j \in \Z \text{ (部分)}, \quad x_k \in \R \text{ (部分)}$$

部分变量整数、部分连续。实际应用中最常见的形式。

⚠️ 为什么 ILP 难？

LP的可行域是凸多面体；ILP的可行域是其中的离散格点——非凸、不连通
ILP的可行解数量有限，但全枚举不现实（指数级）
LP松弛的最优解可能远离最优整数解

2 全单位模矩阵的定义

全单位模矩阵（Totally Unimodular Matrix, TUM）
矩阵 $A$ 称为全单位模的，如果它的每一个方子矩阵的行列式值都是 $0, 1$ 或 $-1$。

特别地，TUM 的每个元素只能是 $0, 1$ 或 $-1$（因为 $1 \times 1$ 子矩阵也是方子矩阵）。

🔍 为什么这很重要？

考虑标准形式 ILP：$\min \{c^T x \mid Ax = b,\; x \ge 0,\; x \in \Z^n\}$

若 $A$ 为方阵且可逆，则 $x = A^{-1}b$。由 Cramer 法则：

$$x_j = \frac{\det(A_j)}{\det(A)}$$

若 $\det(A) = \pm 1$ 且 $b$ 为整数，则 $x$ 自动为整数！这就是 TUM 发挥作用的核心机制。

3 Hoffman-Kruskal 定理（1956）

Hoffman-Kruskal 定理
设 $A$ 为整数矩阵且行满秩。以下命题等价：

对 $A$ 的每个基矩阵 $B$，$\det(B) = 1$ 或 $-1$
对任意整数右端向量 $b$，多面体 $\{x \mid Ax = b,\; x \ge 0\}$ 的每个顶点都是整数向量
对 $A$ 的每个基矩阵 $B$，$B^{-1}$ 是整数矩阵

📖 证明思路（(1) ⇒ (2) ⇒ (3) ⇒ (1)）

(1) ⇒ (2)：任取顶点 $x$，它是某个基 $B$ 对应的基本可行解。非基变量 $x_N = 0$，基变量 $x_B = B^{-1}b$。由 Cramer 法则，$x_B$ 的每个分量 = $\det(B_j)/\det(B)$。由于 $B$ 是 $A$ 的子矩阵，$\det(B_j)$ 是 $A$ 的某个子式的行列式 = $0,\pm1$（因 $A$ 为TUM）。又 $\det(B) = \pm1$，故 $x_B$ 各分量为整数。

(2) ⇒ (3)：取基矩阵 $B$，构造整数向量 $y$ 使 $B^{-1}y$ 的各分量可控制。对每个单位向量 $e_i$，取合适的 $b$ 使 $x_B = B^{-1}e_i$，由(2)知为整数。因此 $B^{-1}$ 的每一列都是整数——即 $B^{-1}$ 为整数矩阵。

(3) ⇒ (1)：$B^{-1}$ 为整数矩阵且 $B$ 为整数矩阵 ⇒ $\det(B)$ 和 $\det(B^{-1}) = 1/\det(B)$ 均为整数 ⇒ $|\det(B)| = 1$。

4 TUM 的基本性质

TUM 的封闭性

若 $A$ 是 TUM，则以下矩阵也是 TUM：

$A^T$	转置矩阵
$-A$	取负矩阵
$(A, A)$	水平拼接
$(A, I)$	拼接单位矩阵
$(A, O)$	拼接零矩阵

💎 关键推论

当 $A$ 为 TUM 时，以下整数规划问题：

$$\min \{c^T x \mid Ax = b,\; x \ge 0,\; x \in \Z^n\}$$ $$\min \{c^T x \mid Ax \le b,\; x \ge 0,\; x \in \Z^n\}$$

的 LP 松弛自动给出整数最优解。可以直接用单纯形法求解！

5 TUM 的充分条件（判别定理）

定理 3（TUM 的充分条件）
设矩阵 $A$ 的元素只取 $0, 1, -1$。如果 $A$ 同时满足以下两个条件，则 $A$ 是 TUM：

$A$ 的每一列至多包含两个非零元素
$A$ 的行可以划分为两个集合 $A_1$ 和 $A_2$，使得：
- 若一列中两个非零元素符号不同，则对应的行在同一集合中
- 若一列中两个非零元素符号相同，则对应的行在不同集合中

📖 证明（数学归纳法）

只需证任意 $k$ 阶方子矩阵 $B$ 的 $\det(B) = 0, 1, -1$。对 $k$ 归纳。

$k=1$ 时显然（元素本身就是 $0,1,-1$）。假设对 $k-1$ 成立。

考虑 $k$ 阶子矩阵 $B$。三种情形：

情形1：$B$ 的某一列全为 $0$ → $\det(B)=0$。

情形2：$B$ 的某一列只有一个非零元 $a_{ij} = \pm 1$ → 按该列展开，$\det(B) = \pm \det(B')$，由归纳假设 $\det(B') = 0,\pm1$。

情形3：$B$ 的每一列恰好两个非零元 → 将属于 $A_1$ 的行相加，属于 $A_2$ 的行相加。由条件(2)知两者相等，即行向量线性相关 → $\det(B)=0$。

6 🧪 交互式 TUM 检测器

输入矩阵（元素用空格分隔，每行一个换行）

点击"检测 TUM"查看结果。

7 TUM 与组合优化的深刻联系

两个核心结论

结论 1：有向图的关联矩阵是 TUM
对有向图 $G=(V,E)$，其点-弧关联矩阵每列恰好一个 $+1$ 和一个 $-1$（弧的起点和终点），满足定理3的条件（所有行放入同一集合即可）。

结论 2：无向图的关联矩阵是 TUM ⟺ 该图是二分图
对无向图，每列有两个 $+1$（边的两个端点）。由定理3条件(2)，两个 $+1$ 必须在不同行集合中——这恰好等价于图的顶点二染色，即该图是二分图。

🎯 为何这如此重要？

以下经典组合优化问题的约束矩阵都是 TUM，因此它们的 ILP 可以直接用 LP 求解（单纯形法保证整数解）：

最短路问题 (SP)	约束矩阵为有向图的关联矩阵
最大流问题 (MF)	点弧关联矩阵 + 容量约束
运输问题 (Hitchcock)	二分图结构 ⇒ TUM
指派问题	完全二分图的匹配
二分图的最大权匹配	二分图的关联矩阵为TUM

🏛️ 统一的视角

TUM 理论揭示了离散优化与连续优化的统一：

$$\text{组合优化问题} \quad\longrightarrow\quad \text{ILP模型} \quad\overset{\text{TUM}}{\longrightarrow}\quad \text{LP可解！}$$

这解释了为什么最短路、最大流、最小费用流等问题存在多项式时间算法——它们本质上是"伪装的"线性规划。

8 本章知识图谱

概念	关键点
ILP难度	NP-hard，可行域非凸离散
TUM定义	任意方子矩阵行列式 ∈ {0, ±1}
Hoffman-Kruskal	TUM ⟺ LP顶点全是整数（对任意整数b）
充分条件	每列≤2非零元 + 行可二划分（定理3）
网络流	有向图关联矩阵 → TUM → LP可解
二分图匹配	二分图关联矩阵 → TUM → LP可解

📝 章节检测（共3题）

每题选择后查看详细解析。

1 TUM 的定义

以下哪个矩阵一定是全单位模矩阵（TUM）？

2 Hoffman-Kruskal 定理的应用

根据 Hoffman-Kruskal 定理，当约束矩阵 $A$ 是 TUM 且 $b$ 为整数时，标准形式 ILP 可以直接用什么方法求解？

3 TUM 与二分图

无向图的关联矩阵是 TUM 当且仅当：