LP5:Maxz=8x,+5x2LP6:MaxZ =8x +5xx, +x, ≤6X +x, ≤69x, + 5x2 ≤ 459x, +5x, ≤ 45s.t.Jxi,x, ≥0Xi,x, ≥0x,≥4s.t.3X≥4X≤1X≤1x≤4(x, ≥5分枝LP5的可行域为D，（图5-3），最优解为x,4，x2=1，是整数，最优值为Z(4)=37<Z=39，剪去
+ + = + 4 1 4 , 0 9 5 45 6 . . 8 5 1 2 1 1 2 1 2 1 2 1 2 x x x x x x x x x s t MaxZ x x + + = + 5 1 4 , 0 9 5 45 6 . . 8 5 1 2 1 1 2 1 2 1 2 1 2 x x x x x x x x x s t LP5： LP6： MaxZ x x 分枝LP5的可行域为D5（图5-3），最优解为x1 ＝4， x2 ＝1，是整数，最优值为Z (4)＝37< Z ＝39，剪去
分枝LP6的的可行域为D只含一个点（5，0）（图5-3），最优解为x,=5，×2=0，是整数，最优值为Z(5)=40>Z39，修改新的下界：Z=Z(5)=40。而Z(5)又是在分枝LP1、LP4、LP5、LP6中目标函数值的最大者（即到现在为止所有未被分枝问题的目标函数值中的最大者），于是新的上界修改为 Z =Z(5)=40Z = Z=40至此已出现所以Z*=40，最优解为Xi=5，x2=0
分枝LP6的的可行域为D6只含一个点（5，0） （图5-3），最优解为x1 ＝5，x2 ＝0，是整数，最 优值为Z (5)＝40> Z ＝39，修改新的下界： Z＝Z (5)＝40。而Z (5)又是在分枝LP1、LP4、LP5、 LP6中目标函数值的最大者（即到现在为止所有 未被分枝问题的目标函数值中的最大者），于是 新的上界修改为 Z ＝Z (5)＝40 所以 Z ＝40，最优解为x1＝5，x2＝0。 至此已出现 Z = =40 Z
LP图5-4Z=-00, Z =41.25x=3.75， x2=2.25,例Z(0)=41.252X≤3≥4分LP2LP1枝定界法求解树形xi=3,x2=3xj=4，x2=1.8Z=39,Z=41Z(1)=39Z(2)=41≥2x≤lZ =39LP3LP4x无可行解x,=40/9, xz=1Z =365/9Z(3)=365/91x≤4≥5x图LP6LP5Z = Z = 40 = Z*xi=4,x2=1xi=5,x2=0Z(5)=37Z(6)=40（注：×代表剪枝）11xx
= = 40 = Z Z Z Z =39， Z ＝41 Z =-， Z ＝41.25 x1 5 x2 1 x1 3 LP x1 ＝3.75，x2 ＝2.25， Z (0)＝41.25 LP1 x1 ＝3，x2 ＝3 Z (1)＝39 LP2 x1 ＝4，x2 ＝1.8 Z (2)＝41 LP3 x1 ＝40/9，x2 ＝1 Z (3)＝365/9 LP4 无可行解 LP5 x1 ＝4，x2 ＝1 Z (5)＝37 LP6 x1 ＝5，x2 ＝0 Z (6)＝40 x1 4 x2 2 x1 4 （注：代表剪枝） 例 2 分 枝 定 界 法 求 解 树 形 图 图5-4 Z =39 Z ＝365/9
对目标函数极小化的整数规划注意定界和剪枝规则的不同。【例3】用分枝定界法求解整数规划IPmin Z = -x; -5xxi - x ≥-25xi + 6x, ≤ 30s.t.≤4X1Xi,X≥0且全为整数
【例3】 用分枝定界法求解整数规划IP + − − = − − , 0且全为整数 4 5 6 30 2 . . min 5 1 2 1 1 2 1 2 1 2 x x x x x x x s t Z x x 对目标函数极小化的整数规划注意定界和剪 枝规则的不同
LP例3分枝定界法求解树形图Z =-19.8， Z =0x,=18/11, x,=40/11Z(0)=—19.8X≤1Xi≥ 2LP2LP1Z =-18.7, Z =-16x;=1, x=3x,=2, x,=10/3Z(1)=—16Z(2)= —18.7X23312 ≥ 4Z =-17.4,xLP3LP4x,=12/5, x,=3无可行解Z=-16Z(3)=—17.41xi≤2≥3xLP5LP6xi=2, x,=3xj =3， x,=2.5Z =Z=-17=ZZ(5)=—17Z(6)=—15.5x合x
x1 3 x2 3 x1 1 LP x1 ＝18/11，x2 ＝40/11 Z (0)＝－19.8 LP1 x1 ＝1，x2 ＝3 Z (1)＝－16 LP2 x1 ＝2，x2 ＝10/3 Z (2)＝－18.7 LP3 x1 ＝12/5，x2 ＝3 Z (3)＝－17.4 LP4 无可行解 LP5 x1 ＝2，x2 ＝3 Z (5)＝－17 LP6 x1 ＝3，x2 ＝2.5 Z (6)＝－15.5 x1 2 x2 4 x1 2 Z = Z =－17=Z Z Z =－17.4， =－16 Z =－19.8， Z ＝0 Z =－18.7， Z ＝-16 例 3 分 枝 定 界 法 求 解 树 形 图