表1z(x)X;=(X1,X2)(0,0)(0,1)(0,2)(0,3)(0,4)(1,0)(1,1)*10(1,2)*13(1,3)(2,0)(2,1)
i x1 xi=(x1 ,x2 ) z(xi ) (0,0) (0,1) (0,2) (0,3) (0,4) (1,0) (1,1) (1,2) 10 * (1,3) 13 * (2,0) (2,1) (2,2) 14 * 表1
取整法思路：利用单纯形法对LIP取消整数约束后的LP求最优解，设为若其中某些分量x =(x,x ...x)人非整数，则将其取整[x,]，并将如此取得的解作为LIP的近似最优解，如例1，x'= (x,[x,],[x,],x4 ...x,)首先去掉x1,x2为整数之约束，求解LP：maxz=4xj+3x24xj+5x2≤20s.t2X)+X2 ≤6X1,X2≥0x=(5/3,8/3)，注意到由图解法可得最优点A(5/3,8/3)或1<5/3<2，2<≤8/3≤3，故对内文下量取整有如表2所示，可得多种取整结果，取整法有多种结果，其误差不好估计
⚫ 取整法思路：利用单纯形法对LIP取消整数约束后的LP 求最优解，设为 ，若其中某些分量 非整数，则将其取整 ，并将如此取得的解 作为LIP的近似最优解，如例1， 首先去掉x1 ,x2为整数之约束，求解LP: max z=4x1+3x2 s.t 4x1+5x2≤20 2x1+x2 ≤6 x1 ,x2≥0 由图解法可得最优点A(5/3,8/3)或 ，注意到 1≤5/3≤2， 2≤8/3≤3，故对 两分量取整有如表2所示， 可得多种取整结果，取整法有多种结果，其误差不好 估计。 T n x x x x ) ~ ~ , ~( ~ = 1 2 j x ~ ] ~[ j x T n x x x x x x ) ~ ~ ], ~ ],[ ~ ,[ ~( ~ = 1 2 3 4 (5/ 3, 8/ 3) ~ x = x ~
表2xxi(1,2)(2,2)(2,3)(1,3)(2,2)z(xi)不满足约束条件
i x i (1,2) (2,3) (1,3) (2,2) (2,2) z(xi ) 不满足 约束条 件 表2 x ~
分支定界法(BranchandBoundMethod)基本思想：它是一种综合穷举法与取整法求解思想并采用有序的“分支”和定界（取整）步骤，逐步舍弃非格子点区域，然后来寻求LIP最优解的方法，也是目前较为成功地求解纯整数规划与混合整数规划的方法之一。其基本思路可通过下述案例介绍：例1: max z=4x,+3x2max z=4xj+3x2s.t 4xi+5x2≤20s.t 4xj+5x2≤20去掉LIA:LA:2Xi+X2 ≤62Xi+X2 ≤6整数X1,X2≥0X1,X2≥0约束X1,X2为整数22X3最优值求最优解xz(x)2-3z(xA=14
分支定界法 (Branch and Bound Method) ⚫ 基本思想：它是一种综合穷举法与取整法求解思想， 并采用有序的“分支”和定界（取整）步骤，逐步舍 弃非格子点区域，然后来寻求LIP最优解的方法，也是 目前较为成功地求解纯整数规划与混合整数规划的方 法之一。其基本思路可通过下述案例介绍： ⚫ 例1：max z=4x1+3x2 max z=4x1+3x2 s.t 4x1+5x2≤20 s.t 4x1+5x2≤20 LIA: 2x1+x2 ≤6 LA: 2x1+x2 ≤6 x1 ,x2≥0 x1 ,x2≥0 x1 ,x2为整数 求最优解 最优值 3 2 ( ) 14 ) 3 2 ,2 3 2 (1 = = A A T z x x x ~ ) ~ z(x 去掉 整数 约束