2、定界：记（IP）的目标函数最优值为Z*，以Z(O)作为Z*的上界，记为Z=Z(O。再用观察法找的一个整数可行解X'，并以其相应的目标函数值Z'作为Z*的下界，记为Z= Z'，也可以令Z=－，则有：Z<Z*≤ 3、分枝：在(LP)的最优解X(O)中，任选一个不符合整数条件的变量，例如X=b’（不为整数），以b’表示不超过b,的最大整数。构造两个约束条件X,<[b,] 和x,>[b, ]+ 1
2、定界： 记( IP )的目标函数最优值为Z* ,以Z(0) 作为Z* 的上 界，记为 ＝ Z(0) 。再用观察法找的一个整数可行解 X′，并以其相应的目标函数值 Z′作为Z* 的下界，记 为Z＝ Z′，也可以令Z＝－∞，则有： Z ≤ Z* ≤ Z Z 3、分枝： 在( LP )的最优解 X(0)中，任选一个不符合整数条件 的变量，例如xr= （不为整数），以 表示不超过 的最大整数。构造两个约束条件 x r≤ 和xr≥ ＋1 r b′ [ ]r b′ r b′ [ ]r b′ [ ]r b′
将这两个约束条件分别加入问题（IP），形成两个子问题(IPI)和(IP2），再解这两个问题的松弛问题(LPI)和(LP2) 。4、修改上、下界：按照以下两点规则进行(1).在各分枝问题中，找出目标函数值最大者作为新的上界；(2).从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。5、比较与剪枝：各分枝的目标函数值中，若有小于Z者，则剪掉此枝，表明此子问题已经探清，不必再分枝了；否则继续分枝。如此反复进行，直到得到Z=Z*=Z为止，即得最优解X*
如此反复进行，直到得到 Z ＝ Z * ＝ 为止，即得最优解 X* 。 将这两个约束条件分别加入问题 ( IP ) ，形成两个子 问题 ( IP1 ) 和 ( IP2 ) ，再解这两个问题的松弛问题( LP1 ) 和( LP2) 。 4、修改上、下界：按照以下两点规则进行。 ⑴.在各分枝问题中，找出目标函数值最大者作为 新的上界； ⑵.从已符合整数条件的分枝中，找出目标函数值 最大者作为新的下界。 5 、比较与剪枝 ： 各分枝的目标函数值中，若有小于Z 者，则剪掉此 枝，表明此子问题已经探清，不必再分枝了 ;否则继续 分枝。 Z
例二、用分枝定界法求解整数规划问题（单纯形法)maxZ=3x,+2x2x, + x2 ≤ 9(IP)2x; +3x2 ≤14Xi,Xx2≥0且为整数解：用单纯形法解对应的(LP)问题,如表所示,获得最优解。02003203bbCBCBXBXBX1X2X1X2X3X4X3X413/409211010-1/49/233/4X3X11/2030114/21-1/2142205/2X2X403↑200-z0-Z-59/405/4-1/4初始表最终表
⎪⎩ ⎪⎨⎧ ≥ + ≤ + ≤ = + , 0且为整数 2 3 14 2 9 ( ) max 3 2 1 2 1 2 1 2 1 2 x x x x x x IP Z x x -Z 0 3 2 0 0 14 2 3 0 1 14/2 x4 0 x 9 2 1 1 0 9/2 3 0 x4 x3 x2 x1 CB XB b 3 2 0 0 -Z -59/4 0 0 -5/4 -1/4 x 5/2 0 1 -1/2 1/2 2 2 x 13/4 1 0 3/4 -1/4 1 3 x4 x3 x2 x1 CB XB b 3 2 0 0 解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。 初始表 最终表 例二、用分枝定界法求解整数规划问题（单 纯形法）
x,=13/4 x2=5/2Z(0) =59/4=14.75选x,进行分枝，即增加两个约束，2>x，≥3有下式max Z = 3xi +2x2max Z = 3xi +2x2[2x + 2≤9[2x + X2≤92x +3x2≤142x +3x2≤14(IP1)(IP2)X ≤2X2 ≥3,≥0且为整数[Xi,X2≥0且为整数分别在(LPI)和(LP2)中引入松弛变量x,和x6，将新加约束条件加入上表计算。即x,+x5=2，-x2+x=-3 得下表;
x 1 =13/4 x 2 =5/2 Z(0) =59/4=14.75 选 x2 进行分枝，即增加两个约束， 2 ≥ x 2 ≥3 有下式： ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ≤ + ≤ + ≤ = + , 0且为整数 2 2 3 14 2 9 ( 1 ) max 3 2 1 2 2 1 2 1 2 1 2 x x x x x x x IP Z x x ⎪ ⎪ ⎩ ⎪ ⎪ ⎨ ⎧ ≥ ≥ + ≤ + ≤ = + , 0且为整数 3 2 3 14 2 9 ( 2 ) max 3 2 1 2 2 1 2 1 2 1 2 x x x x x x x IP Z x x 分别在 (LP1 ) 和 (LP2 )中引入松弛变量 x 5 和 x 6 ，将新加 约束条件加入上表计算。即 x 2+ x 5= 2 , － x 2+x 6 = － 3 得 下表 :
32000LP1bCBXBX3X5X1×2×413/40031-1/43/4X10120-1/21/25/2X21001020X50-Z00-59/4-5/4-1/4013/4031-1/43/4X10120-1/21/25/2X20100-1/2-1/21/2X5X,=7/2, X,=2-Z00-1/4↑0-5/4-59/4Z(1) =29/2=14.500311/2-1/2712X1继续分枝，加0101202X2入约束1-20001-1X43>X/ >4000-Z-3/2-29/2-1/2
-1/4 0 1/2 -1/4 x4 0 x 5/2 0 1 -1/2 0 2 2 -Z -59/4 0 0 -5/4 0 x 2 0 1 0 1 5 0 x 13/4 1 0 3/4 0 1 3 x5 x3 x2 x 1 C B X B b 3 2 0 0 -1/4 -1/2 1/2 -1/4 x 5/2 0 1 -1/2 0 2 2 -Z -59/4 0 0 -5/4 0 x -1/2 0 0 1/2 1 5 0 x 13/4 1 0 3/4 0 1 3 0 1 0 0 x 2 0 1 0 1 2 2 -Z -29/2 0 0 -3/2 -1/2 x 1 0 0 -1 -2 4 0 x 7/2 1 0 1/2 -1/2 1 3 x 1=7/2, x 2=2 Z(1) =29/2=14.5 继续分枝，加 入约束 3 ≥ x 1 ≥ 4 LP1