最优整数解特性与幺模矩阵

最短路、指派等模型常具有整数最优解特性：其线性松弛模型的最优解本身就是整数向量，因而与对应整数规划的最优解一致。下面先借一个二维小例子与图 2.12 说明该性质在几何上意味着什么；再给出幺模（部分中文文献亦作「么模」，与英文 unimodular 同指）与全幺模矩阵的定义及常用判定思路。可参见陈景良、陈向晖 (2010)、Shapiro (1979) 等专书中的系统论述。

2.4.3 最优整数解特性的理解

考虑一个仅含两个决策变量的整数规划，及其去掉整数约束后的线性松弛。

将 (1) 的全部可行整数点画在 – 平面上（图 2.12(a)），再观察这些点张成的凸包与 (2) 的可行域（图 2.12(b)）：二者完全重合。由此可见：

• 线性规划的最优解若取在可行域的极点（顶点）上，而该可行域的极点又全部是 (1) 的可行整数点，则松弛问题与整数规划共享同一组「角点最优」结构。
• 一般地，若某整数规划所有可行解的凸包恰等于其线性松弛的可行域，则松弛最优解必为整数最优解。

图 2.12：(a) 整数规划可行解（黑点）；(b) 线性松弛可行域，与 (a) 中可行整数点的凸包一致。正文中的 (1)、(2) 即与之对应的两个小模型。

2.4.4 幺模矩阵和整数最优解特性

要判断一般整数规划的约束矩阵是否带来「松弛解必为整数」等性质，需借助矩阵的整数性与幺模性。

定义 2.4.1（整数矩阵）

若矩阵 的每个元素均为整数，则称 为整数矩阵。

定义 2.4.2（幺模矩阵）

设 为整数矩阵，。若 的每一个非奇异 子式（子行列式）的取值均为 或 ，则称 为幺模矩阵（unimodular matrix）。特别地，当 时，整数方阵 幺模当且仅当 。

定义 2.4.3（全幺模矩阵）

若 为幺模矩阵，且 的各阶子式取值均属于 ，则称 为全幺模矩阵（totally unimodular matrix，常缩写为 TU）。

由定义可直接得到：全幺模矩阵的每个元素必属于 ；两个 幺模矩阵的乘积仍是幺模矩阵（此为常用结论，证明见上列专书）。

定理 2.4.1

设 。对任意整数向量 ，方程组

的所有基本解都是整数向量的充要条件是： 为幺模矩阵。

定理 2.4.2

设 为整数矩阵。若对任意整数向量 ，不等式组

的所有基本解都是整数向量，则 必为全幺模矩阵。

定理 2.4.3（保持全幺模的运算）

设 为全幺模矩阵，则对 作下列任一操作后，仍得全幺模矩阵：

1. 交换两行或两列；
2. 转置；
3. 将某行或某列乘以 ；
4. 追加一行或一列，其中恰有一个非零元，且该非零元为 或 。

注：上述结论刻画了：在 满足适当结构时， 或 所对应线性规划（在标准形或松弛形式下）的基解、极点向量为整数，从而与整数约束相容；与 最短路问题、最大流问题 等网络模型中常见的整数性现象可合读。本页中「定义/定理 2.4.x」的编号与上文二维例、网络章节的体例并陈，仅作站内导航，不以外部式号为阅读前提。