《运筹学》课程教学讲义（Operations Research）第六章（6.2）具有整数解的线性规划问题

运筹学讲义 §6.2具有整数解的线性规划问题 对纯整数规划 max (IP): s.t. Ax=b x20整数,j=12…n 若取消决策变量的整数性要求(即将决策变量作为连续型变量),即得其松弛线性规划问题( linear programming relaxation max 2=C x (LP): s.L. Ax=b 0 命题1(1)K(P)sK(LP):(2)=(m)≤={u) (3)设利用单纯形法求解(LP)得最优解x',若x为整数解,则x必为(P)的最优解 证明:(1)√.(2)∵K(P)K(LP)(在一个更大的可行域内寻找最优解) (3)∵x为整数解,当然x”∈K(LP),又x为整数解,∴x∈K(P) x∈K(P),由(1)知,x∈K(LP):又x是(LP)的最优解,∴c'x≤cx 故由x的任意性知,x是(P)的最优解.■ 推论若(LP)不可行,则(P)也不可行 证明:∵K(lP)K(LP) 个“朴素的( naive)”的设想:为求解(lP),可先求解其松弛线性规划问题(LP),不妨设求 得(LP)的最优解为x.若x为整数向量,则x即为(P)的最优解;否则,将x“取整”( rounding, 四舍五入法或进一法)作为(P)的最优解 上述想法不可行!这是因为取整后的x未必是(P)的最优解,甚至根本不是可行解 例如,给定整数规划问题

运 筹 学 讲 义 1 §6.2 具有整数解的线性规划问题 对纯整数规划       = = = x j n st Ax b z c x IP j T 0, , 1,2, , . . max ( ) : 整数  若取消决策变量的整数性要求（即将决策变量作为连续型变量），即得其松弛线性规划问题（linear programming relaxation）       = = 0 . . max ( ) : x st Ax b z c x LP T 命题 1（1） K(IP)  K(LP) ；（2） (IP) (LP) z  z ； （3）设利用单纯形法求解 (LP) 得最优解  x ，若  x 为整数解，则  x 必为 (IP) 的最优解. 证明：（1）√.（2）  K(IP)  K(LP) （在一个更大的可行域内寻找最优解）. （3）   x 为整数解，当然 x  K(LP)  ，又  x 为整数解，  x  K(IP)  .  x  K(IP) ,由（1）知， x  K(LP) ；又  x 是 (LP) 的最优解，   c x  c x T T . 故由 x 的任意性知，  x 是 (IP) 的最优解.▌ 推论 若 (LP) 不可行，则 (IP) 也不可行. 证明：  K(IP)  K(LP) .▌ 一个“朴素的（naive）”的设想：为求解 (IP) ，可先求解其松弛线性规划问题 (LP) ，不妨设求 得 (LP) 的最优解为  x .若  x 为整数向量，则  x 即为 (IP) 的最优解；否则，将  x “取整”（rounding， 四舍五入法或进一法）作为 (IP) 的最优解. 上述想法不可行！这是因为取整后的  x 未必是 (IP) 的最优解，甚至根本不是可行解. 例如，给定整数规划问题

运筹学讲义 max ==x, +x2 sL.-2x1+2x2≥1 8x1+10x,≤13 x1,x2≥0,整数 其松弛线性规划问题为 max ==x +x2 x+2x2≥1 (LP) 8x1+10x2≤13 x1,x2≥0 利用图解法 1 易见,(LP)的最优解为(4,)2,最优值为取整后,得(P)的“最优解”为(4,5),“最优 值”为9但实际上,(P)的最优解为(1,2),最优值为3.显然,二者差别甚大! 于是,求解整数规划的新算法的引入成为必要 然而,遗憾的是,迄今为止,还没有一种方法能有效地求解一切整数规划!§6.3.1和§6.3.2 将介绍求解整数规划的两种特殊方法-—割平面法和分支定界法 但是,也确有一些线性规划问题,其本身的结构就决定了它必然存在整数解 单(幺)模阵( unimodular matrix):行列式的值为0,-1,1的整数方阵

运 筹 学 讲 义 2         − +  − +  = + , 0,整数 8 10 13 . . 2 2 1 max ( ) : 1 2 1 2 1 2 1 2 x x x x st x x z x x IP ， 其松弛线性规划问题为         − +  − +  = + , 0 8 10 13 . . 2 2 1 max ( ) : 1 2 1 2 1 2 1 2 x x x x st x x z x x LP . 利用图解法解之： 易见， (LP) 的最优解为 T ) 2 9 (4, ，最优值为 2 17 .取整后，得 (IP) 的“最优解”为 T (4,5) ，“最优 值”为 9.但实际上， (IP) 的最优解为 T (1,2) ，最优值为 3 .显然，二者差别甚大！ 于是，求解整数规划的新算法的引入成为必要. 然而，遗憾的是，迄今为止，还没有一种方法能有效地求解一切整数规划！§6.3.1 和§6.3.2 将介绍求解整数规划的两种特殊方法---割平面法和分支定界法. 但是，也确有一些线性规划问题，其本身的结构就决定了它必然存在整数解. 单（幺）模阵（unimodular matrix）：行列式的值为 0，-1，1 的整数方阵

运筹学讲义 全单(幺)模阵( total unimodular matriⅸx):任一子方阵均为单模阵的矩阵 如 单模阵(非全单模阵)全单模阵 注:(1)全单模阵的元素仅可能为0,-1,1(∵全单模阵的元素是其一阶子矩阵) (2)幺模阵与全幺模阵无必然联系 下面,给出判断全单模阵的一个充分条件 命题2设矩阵A=(an)mn,a1=0,-1,1,A的每列至多有两个非零元素 若可将A的行指标划分为1和l2,使得 (1)当A的某列含有两个同号的非零元素时,这两个非零元素所在的行指标分属l1和l2 (2)当A的某列含有两个异号的非零元素时,这两个非零元素所在的行指标同属l1和2 则A必为全单模阵.■ 例1判断矩阵 10100 01-10 A 1000-1 01000 是否为全单模阵? 解:令1={1,2},12={34},则由命题2知,A为全单模阵■ Thl(具有整数解的线性规划问题)对线性规划问题 max二=cX (LP):1s1.Ax=b,若A是全单模阵,b是整数向量,则(LP)的任一基本解均为整数解 证明:设B是(LP)的任一基,则(LP)关于基B的基本解为x= B-b A是全单模阵,∴B是整数方阵,且|B|=±1;

运 筹 学 讲 义 3 全单（幺）模阵（total unimodular matrix）：任一子方阵均为单模阵的矩阵. 如         1 3 2 5 单模阵（非全单模阵）         1 0 −1 1 1 0 全单模阵 注：（1）全单模阵的元素仅可能为 0，-1，1（  全单模阵的元素是其一阶子矩阵）. （2）幺模阵与全幺模阵无必然联系. 下面，给出判断全单模阵的一个充分条件： 命题 2 设矩阵 A = (aij)mn ,aij = 0,−1,1， A 的每列至多有两个非零元素. 若可将 A 的行指标划分为 1 I 和 2 I ，使得 （1）当 A 的某列含有两个同号的非零元素时，这两个非零元素所在的行指标分属 1 I 和 2 I ； （2）当 A 的某列含有两个异号的非零元素时，这两个非零元素所在的行指标同属 1 I 和 2 I ， 则 A 必为全单模阵.▌ 例 1 判断矩阵               − − − = 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 A 是否为全单模阵？ 解：令 {1,2} I 1 = ， {3,4} I 2 = ，则由命题 2 知， A 为全单模阵.▌ Th1（具有整数解的线性规划问题）对线性规划问题       = = 0 . . max ( ) : x st Ax b z c x LP T ，若 A 是全单模阵， b 是整数向量，则 (LP) 的任一基本解均为整数解. 证明：设 B 是 (LP) 的任一基，则 (LP) 关于基 B 的基本解为         =        = − 0 1 B b x x x N B .  A 是全单模阵，   B 是整数方阵，且 | B |= 1 ；

运筹学讲义 又b是整数向量,∴x=Bb≈B b=±Bb为整数向量 B 故x为(LP)的整数解■ Cor对整数规划 (IP): s.L. Ax=b x≥0整数=12…,n 其松弛线性规划问题为 max (LP):{st.Ax=b,其中A是全单模阵,b是整数向量 x≥0 若利用单纯形法求解(LP)得最优解x,则x必定也是(P)的最优解. 证明:由Th知,x为整数解.由命题(3)知,x是(P)的最优解■ 例2求证:运输问题 min ∑∑cn (TP).sL. r=a, i=1,2,,m xi=bj,j= xn≥0,i=1,2 必有整数解,其中a,b∈Z 证明:(TP)的约束条件方程组的系数矩阵为

运 筹 学 讲 义 4 又 b 是整数向量，  b B b B B xB B b   − = = =  | | 1 为整数向量. 故 x 为 (LP) 的整数解.▌ Cor 对整数规划       = = = x j n st Ax b z c x IP j T 0, , 1,2, , . . max ( ) : 整数  ， 其松弛线性规划问题为       = = 0 . . max ( ) : x st Ax b z c x LP T ，其中 A 是全单模阵， b 是整数向量. 若利用单纯形法求解 (LP) 得最优解  x ，则  x 必定也是 (IP) 的最优解. 证明：由 Th1 知，  x 为整数解. 由命题（3）知，  x 是 (IP) 的最优解.▌ 例 2 求证：运输问题             = = = = = = =    = = = = x i m j n x b j n st x a i m z c x TP ij m i ij j i n j ij m i n j ij ij 0, 1,2, , ; 1,2, , , 1,2, , . . , 1,2, , min ( ) : 1 1 1 1     必有整数解，其中 + ai ,bj Z . 证明： (TP) 的约束条件方程组的系数矩阵为

运筹学讲义 x11x12 x 100 0 200 0 00 0 A 00 000 0 m+110 0 m+n(00…1 令1={,2,…,m},l2={m+1,m+2,…,m+m},则由命题2知,A是全单模阵 又b=(a1a2…,an、b、b2…,b)是整数向量,故由Th知,(TP)必有整数解■

运 筹 学 讲 义 5                           + + + = 0 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 0 0 0 2 1 2 1 1 1 1 2 1 2 1 2 2 2 1 2                                                         m n m m m x x x x x x x x x A n n m m m n . 令 {1,2, , }, { 1, 2, , } I 1 =  m I 2 = m+ m+  m+ n ，则由命题 2 知， A 是全单模阵； 又 T b a a am b b bn ( , , , , , , , ) = 1 2  1 2  是整数向量，故由 Th1 知, (TP) 必有整数解.▌