maxZ=bx,+4x2 2x1+4x,≤13 x1+x2≤1 > x1,x2为整数 首先,将该问题的限制条件予以整数化,并加松弛变量。 maxZ=6x,+4 (5) 2x1+4x2+x3=13 (1) 2x1+x2=7 x≥0,j=12,34 x为整数 (4) 不考虑整数约束(4),用单纯形方法求解相应LP得最优解表(见表4-2) 表4-2 0 b x1 x2 x2 C x1不合整数要求,于是找(第一个)割平面(即考虑整数要求),由表得 XI x4为整数 使各系数均为正,有: 是整数,因为所有变量均为整数,则上式至少是一,则有: 11 ≥1 (6) x3+2x4≥3 (6)即为切割方程,其通式为:f+∑fkx21 其等式形式就是割平面,为了在图上表示,由约束(1)、(2)可以把(6)变为 x,+x、<4 (7)
1 2 1 2 1 2 1 2 1 2 max 6 4 2 4 13 1 1 1 . 3 6 , 0 , 1 6 Z x x x x x x s t x x x x = + + ≤ + ≤ ≥ 为整数 首先，将该问题的限制条件予以整数化，并加松弛变量。 （ 1 2 1 2 3 1 2 max 6 4 2 4 1 2 7 . 0, 1,2,3,4 j j Z x x x x x x x s t x j x = + + + = + = ≥ = 为整数 3 （5） （1） 2） （3） （4） 不考虑整数约束（4），用单纯形方法求解相应 LP 得最优解表（见表 4-2）。 表 4-2 Cj 6 4 0 0 CB XB b 1 x 2 x 3 x 4 x 4 2 x 2 0 1 1 3 1 3 − 6 1 x 1 2 2 1 0 1 6 2 3 C Z j j − 0 0 1 3 − 2 2 3 − 1 x 不合整数要求，于是找（第一个）割平面（即考虑整数要求），由表得： 1 3 1 1 2 2 2 6 3 4 x = + x − x 为整数 使各系数均为正，有： 3 4 1 1 1 2 6 3 + x + x 是整数，因为所有变量均为整数，则上式至少是一，则有： 3 4 1 1 1 1 2 6 3 + + x x ≥ （6） 即 3 4 x x + ≥ 2 3 （6）即为切割方程，其通式为： 1 j jK K K f f +∑ x ≥ 其等式形式就是割平面，为了在图上表示，由约束（1）、（2）可以把（6）变为 1 2 x x + ≤ 4 （7）
(7)是切割方程的另一种表现形式,割平面就表示为:x+x2=4 它就是图4-5所表示的EF直线。直观地看,它割去了(除EF直线上的所有点) △EFB部分:x1+x2>4 其中不含整数(坐标)点。留下部分是:x+x24 即多边形 OAEFC,从图4-5看,所有整数(坐标)点都保留下来了。 B 图4-5 把切割方程作为新约束条件加入原问题,变为 nax Z=6x,+4x, 2x+4x2≤13 2x1+x2≤7 ≤4 x1,x2≥0 x12x2为整数 按上述步骤,解相应LP得最优解:x=3,x2=1,x=3,x4=x=0,maxZ=22 实际上就是F点。因为它已经满足整数约束,所以就是原IP的最优解。 割平面方程的另一种表达方法也是常用的,再经此法求解例3: 由表4-2知,x不满足整数约束,则 变为 (1+0)x1-1 移项 R x3+x4
（7）是切割方程的另一种表现形式，割平面就表示为： 1 2 x x + = 4 它就是图 4-5 所表示的 EF 直线。直观地看，它割去了（除 EF 直线上的所有点） ∆EFB 部分： x x 1 2 + > 4 其中不含整数（坐标）点。留下部分是： 1 2 x x + ≤ 4 即多边形OAEFC ，从图 4-5 看，所有整数（坐标）点都保留下来了。 2 x d E C 1 x 5 , 2 2 i c A B F 0 图 4-5 把切割方程作为新约束条件加入原问题，变为： 1 2 1 2 1 2 1 2 1 2 1 2 max 6 4 2 4 1 2 7 . 4 , 0 , 3 Z x x x x x x s t x x x x x x = + + ≤ + ≤ + ≤ ≥ 为整数 按上述步骤，解相应 LP 得最优解： 1 2 3 4 5 x x = 3, = = 1， ， x 3, x = x = 0 max Z = 22 。 实际上就是 F 点。因为它已经满足整数约束，所以就是原 IP 的最优解。 割平面方程的另一种表达方法也是常用的，再经此法求解例 3： 由表 4-2 知， 1 x 不满足整数约束，则 1 3 4 1 2 2 6 3 x x − + x = 1 2 变为 1 3 4 5 2 (1 0) 1 0 2 6 3 x x x + − − + + = + 1 2 移项： 1 3 3 4 1 5 2 2 2 6 3 x x x − − = − + x
因为要求所有变量均为整数,则 x1-x3 为整数 2(6x+3亦为整数 又 2 6+x1为整数,所以有: 此即所求之切割方程,切割平面是 52 x3+,x4 (8)加入松弛变量x作为新约束条件,并入最优解表4-3,得 表4-3 C b Xu x2 2 6 0 6 4_545 2 由表4-3知,此不是可行解,需用对偶单纯形法继续求解。x为出基变量,由 下式确定进基变量为x3 B=m la<o 63 mIn 15 再按原单纯形法计算,得表4-4
因为要求所有变量均为整数，则 x x 1 3 − − 2 为整数， 3 1 5 2 2 6 3 4 x x − + 亦为整数， 又 3 5 2 6 3 4 x + x 为整数，所以有： 3 4 1 5 2 0 2 6 3 x x − + ≤ 即 3 4 5 2 6 3 − − x x ≤ 1 2 （8） 此即所求之切割方程，切割平面是： 3 4 5 2 6 3 x x 1 2 + ≥ （8）加入松弛变量 5 x 作为新约束条件，并入最优解表 4-3，得 表 4-3 Cj 6 4 0 0 0 CB XB b 1 x 2 x 3 x 4 x 5 x 4 2 x 2 0 1 1 3 3 5 − 0 6 1 x 2 5 1 0 1 6 − 4 5 0 0 5 x 1 2 − 0 0 5 6 − 4 5 1 C Z j j − 0 0 1 3 − 2 2 3 − 0 由表 4-3 知，此不是可行解，需用对偶单纯形法继续求解。 5 x 为出基变量，由 下式确定进基变量为 3 x ： 1 2 2 3 3 min | 0 min , 5 2 6 3 j j ij j j ij C Z a a θ − − = < = − − − 6 6 min ,4 j 15 15 = = 再按原单纯形法计算，得表 4-4