运筹学 Operations Research §4.2具有整数解的线性规划问题 对纯整数规划 maX Z=C X (P): s.t. Ax= b x≥0,整数,=1,2,…,n 其松弛线性规划问题(1 inear programming relaxation) maX 2=C x (LP): s.t. Ax=b x≥0 2021/2/20
2021/2/20 1 运 筹 学 Operations Research §4.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
运筹学 Operations Research 命题1(1)K(P)≤K(LP) (2) LP (3)设利用单纯形法求解(LP)得最优解x,若x'为整数解, 则必为(P)的最优解 证 推论若(LP)不可行,则(P)也不可行 个“朴素的( nal ve)”的设想: 将(LP)的最优解取整得(P舶的最优解? 2021/2/20 2
2021/2/20 2 运 筹 学 Operations Research ( ) . (3) ( ) (2) 1(1) ( ) ( ) 则必为 的最优解 设利用单纯形法求解 得最优解 ，若 为整数解， 命题 IP LP x x z z K IP K LP IP LP 推论若(LP)不可行，则(IP)也不可行. 证：…… ▌ 一个“朴素的（naive）”的设想： 将(LP)的最优解取整得(IP)的最优解？
运筹学 Operations Research 上述想法不可行!如 max z=x, +x st 2x1+2x2≥1 -8x1+10x2≤13 x1,x2≥0,整数 max 2=x, +x2 st 2x1+2x,≥1 (LP) -8x,+10x<13 x,≥0 2021/2/20 3
2021/2/20 3 运 筹 学 Operations Research 上述想法不可行！ 如 − + − + = + , 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
运筹学 Operations Research 图解法 13 2=x1 +z A 2021/2/20 4
2021/2/20 4 运 筹 学 Operations Research 图解法：
运筹学 Operations Research (LP)的最优解为4。),最优值为7 2 取整得(P)的最优解为(4,5),最优值为9 实际上,(IP)的最优解为(,2),最优值为3. 显然,二者差别甚大! 于是,求解整数规划的新算法的引入成为必要 2021/2/20
2021/2/20 5 运 筹 学 Operations Research ( ) (1,2 3. ( ) (4,5) 9. . 2 17 ) 2 9 ( ) (4, 实际上， 的最优解为 ），最优值为 取整得 的最优解为 ，最优值为 的最优解为 ，最优值为 T T T IP IP LP 显然，二者差别甚大！ 于是，求解整数规划的新算法的引入成为必要
运筹学 Operations research 但是,也确有一些线性规划问题,其本身的结构就决定 了它必然存在整数解 单(幺)模阵( unimodular matrix):行列式的值为0 1,1的整数方阵. 全单(幺)模阵( total unimodular matrix):任一子方 阵均为单模阵的矩阵. 10 2021/2/20 6
2021/2/20 6 运 筹 学 Operations Research 单（幺）模阵（unimodular matrix）：行列式的值为0，- 1，1的整数方阵. 全单（幺）模阵（total unimodular matrix）：任一子方 阵均为单模阵的矩阵. 1 3 2 5 1 0 −1 1 1 0 但是，也确有一些线性规划问题，其本身的结构就决定 了它必然存在整数解
运筹学 Operations Research 命题2设矩阵A=(an)mn4n=0.-1,A的每列至多有两个非零元素 若可将A的行指标划分为1和2,使得 (1)当A的某列含有两个同号的非零元素时,这两个非零元素所在的 行指标分属l1和Ⅰ2; (2)当4的某列含有两个异号的非零元素时,这两个非零元素所在的 行指标同属和,■ 则A必为全单模阵 2021/2/20 7
2021/2/20 7 运 筹 学 Operations Research . (2) (1) 2 ( ) , 0, 1,1 . 1 2 1 2 1 2 则 必为全单模阵 行指标同属 和 ， 当 的某列含有两个异号的非零元素时，这两个非零元素所在的 行指标分属 和 ； 当 的某列含有两个同号的非零元素时，这两个非零元素所在的 若可将 的行指标划分为 和 ，使得 命题 设矩阵 ， 的每列至多有两个非零元素 A I I A I I A A I I A = ai j mn ai j = − A ▌
运筹学 Operations Research 例1判断矩阵是否为全单模阵? 10100 100 0-00 0 解:1={12},12={3,4}口 Th1(具有整数解的线性规划问题)对线性规划问题 T maX Z=C x (LP): s.t. Ax=b x≥0 2021/2/20 8
2021/2/20 8 运 筹 学 Operations Research 例1 判断矩阵是否为全单模阵？ − − − = 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 A {1,2} {3 4} 解：I 1 = ，I 2 = ， ▌ Th1（具有整数解的线性规划问题）对线性规划问题 = = 0 . . max ( ) : x st Ax b z c x LP T
运筹学 Operations Research 若A是全单模阵,b是整数向量,则(LP)的任一基本解 均为整数解 证:设(LP关于任一基的基本解为x=6 B b 则xB=Bbb b=±B'b是整数向量 B 2021/2/20
2021/2/20 9 运 筹 学 Operations Research . ( ) 均为整数解 若A是全单模阵，b是整数向量，则 LP 的任一基本解 证：设 关于任一基 的基本解为 ， = = − 0 ( ) 1 B b x x LP B x N B . | | 则 1 b B b是整数向量 B B xB B b − = = = ▌
运筹学 Operations Research 例2求证:运输问题必有整数解,其中a;2b,∈Z+ mIn z=∑∑Cxn (TP) ∑x=b,j xn≥0,i=1,2,…,m,j=1,2,…,n 证:b=(a12a2,…,an,b12b2…b)是整数向量 2021/2/20 10
2021/2/20 10 运 筹 学 Operations Research 例2 求证：运输问题必有整数解， , . + 其中ai bj Z = = = = = = = = = = = x i m j n x b j n st x a i m z c x TP i j m i i j j i n j i j m i n j i j i j 0, 1,2, , ; 1,2, , , 1,2, , . . , 1,2, , min ( ) : 1 1 1 1 ( , , , , , , , ) . 证：b = a1 a2 am b1 b2 bn T 是整数向量