运筹学 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 显然，二者差别甚大！ 于是，求解整数规划的新算法的引入成为必要