§6.2具有整数解的线性规划问题
对纯整数规划

若取消决策变量的整数性要求（即将决策变量作为连续型变量），即得其松弛线性规划问题（linear programming relaxation）

命题1（1）；（2）；
（3）设利用单纯形法求解得最优解，若为整数解，则必为的最优解.
证明：（1）√.（2）（在一个更大的可行域内寻找最优解）.
（3）为整数解，当然，又为整数解，.
,由（1）知，；又是的最优解，.
故由的任意性知，是的最优解.▌
推论 若不可行，则也不可行.
证明：.▌
一个“朴素的（naive）”的设想：为求解，可先求解其松弛线性规划问题，不妨设求得的最优解为.若为整数向量，则即为的最优解；否则，将“取整”（rounding，四舍五入法或进一法）作为的最优解.
上述想法不可行！这是因为取整后的未必是的最优解，甚至根本不是可行解.
例如，给定整数规划问题
，
其松弛线性规划问题为
.
利用图解法解之：

易见，的最优解为，最优值为.取整后，得的“最优解”为，“最优值”为.但实际上，的最优解为，最优值为.显然，二者差别甚大！
于是，求解整数规划的新算法的引入成为必要.
然而，遗憾的是，迄今为止，还没有一种方法能有效地求解一切整数规划！§6.3.1和§6.3.2将介绍求解整数规划的两种特殊方法---割平面法和分支定界法.
但是，也确有一些线性规划问题，其本身的结构就决定了它必然存在整数解.
单（幺）模阵（unimodular matrix）：行列式的值为0，-1，1的整数方阵.
全单（幺）模阵（total unimodular matrix）：任一子方阵均为单模阵的矩阵.
如

单模阵（非全单模阵）

全单模阵
注：（1）全单模阵的元素仅可能为0，-1，1（全单模阵的元素是其一阶子矩阵）.
（2）幺模阵与全幺模阵无必然联系.
下面，给出判断全单模阵的一个充分条件：
命题2设矩阵，的每列至多有两个非零元素.
若可将的行指标划分为和，使得
（1）当的某列含有两个同号的非零元素时，这两个非零元素所在的行指标分属和；
（2）当的某列含有两个异号的非零元素时，这两个非零元素所在的行指标同属和，
则必为全单模阵.▌
例1判断矩阵

是否为全单模阵？
解：令，，则由命题2知，为全单模阵.▌
Th1（具有整数解的线性规划问题）对线性规划问题
，若是全单模阵，是整数向量，则的任一基本解均为整数解.
证明：设是的任一基，则关于基的基本解为.
是全单模阵，是整数方阵，且；
又是整数向量，为整数向量.
故为的整数解.▌
Cor 对整数规划
，
其松弛线性规划问题为
，其中是全单模阵，是整数向量.
若利用单纯形法求解得最优解，则必定也是的最优解.
证明：由Th1知，为整数解.由命题（3）知，是的最优解.▌
例2求证：运输问题

必有整数解，其中.
证明：的约束条件方程组的系数矩阵为
.
令，则由命题2知，是全单模阵；
又是整数向量，故由Th1知,必有整数解.▌