这样实际上将LP的可行域D缩小成了LP1的可行域D1和LP2的可行域D2，而D中不包含整数解的一部分（3<x<4）被去掉了（图5-2）且保证LP的最优解不会重复出现X2D.X65D,431B(3.J5,2.25)21t+X234567891图5-2本例中LP1的最优解为xj=3，x2=3，最优值为Z(1)=39；LP2的最优解为x,=4，x2=1.8，最优值为Z(2)=41
这样实际上将LP的可行域D缩小成了LP1的 可行域D1和LP2的可行域D2，而D中不包含整 数解的一部分（3 < x1< 4）被去掉了（图5-2）, 且保证LP的最优解不会重复出现。 o 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 B(3.75,2.25) • • • • • • • • • • • • • x1 x2 • • • • • • • • • • • • D1 D2 图5-2 本例中LP1的最优解为x1＝3，x2＝3，最优值为 Z (1)＝39；LP2的最优解为x1＝4，x2＝1.8，最优值 为Z (2)＝41
第4步：修改上、下界。按照以下两点规则进行：①在各分枝问题中，找出目标函数值最大者作为新的上界乙；②从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界乙Z =Z(2)=41本例Z=Z(1)=39。第5步剪枝与比较。对每一分枝，求解时可能出现三种情形：①无可行解；②得到整数最优解；③得到非整数最优解，其最优值为Z
第4步：修改上、下界。按照以下两点规则进行： ①在各分枝问题中，找出目标函数值最大者作为 新的上界 Z ； ②从已符合整数条件的分枝中，找出目标函数值 最大者作为新的下界 Z. 本例 ＝Z Z (2)＝41 Z＝Z (1)＝39。 第5步 剪枝与比较。对每一分枝，求解时可能出现 三种情形：①无可行解；②得到整数最优解；③得 到非整数最优解，其最优值为Z
对于情形、②，分枝的情况已探明，无需再继续往下分，计算停止，称为剪枝。对于情形③，需将Z与已求得的下界Z比较，若Z<Z，亦应剪枝若Z>Z，则返回第3步，继续分枝，然后重复第4、第5步，直到每一分枝的情况均已探清楚，无需再分枝，此时必可得到Z*= Z=Ｚ。本例LP1的最优解（xi=3，x2=3）为整数解，这一枝不用再分，剪掉。LP2的最优解为x,=4，x2=1.8，最优值为Z(2)=41 > Z =39因此在其可行域D.内可能存在目标函数值大于或等于39的整数解，继续分枝
若Z > ， 则返回第3步，继续分枝，然后重复第4、 第5步，直到每一分枝的情况均已探清楚，无需再 分枝，此时必可得到Z ＝ ＝ 。 Z Z Z 对于情形①、②，分枝的情况已探明，无需再继续 往下分，计算停止，称为剪枝。对于情形③，需将 Z与已求得的下界 Z 比较，若Z < Z ，亦应剪枝. 本例LP1的最优解（x1＝3，x2＝3）为整数解， 这一枝不用再分，剪掉。 LP2的最优解为x1 ＝4，x2 ＝1.8，最优值为 Z (2)＝41 > Z ＝39 因此在其可行域D2内可能存在目标函数值大于 或等于39的整数解，继续分枝
对x2=1.8，构造约束条件x2≤1和x2≥2，得MaxZ =8x, +5x,MaxZ=8x, +5x2Xi +x, ≤6X, +x, ≤6LP3:LP4:9x, +5x,≤459x, + 5x, ≤ 45s.t.xi,x, ≥0s.t.:xi,x, ≥0x ≥4x ≥4[x ≥2[x, ≤1分枝LP4无可行解，剪去
对x2＝1.8，构造约束条件x2 1和x2 2，得 + + = + 1 4 , 0 9 5 45 6 . . 8 5 2 1 1 2 1 2 1 2 1 2 x x x x x x x x s t MaxZ x x + + = + 2 4 , 0 9 5 45 6 . . 8 5 2 1 1 2 1 2 1 2 1 2 x x x x x x x x s t MaxZ x x LP3： LP4： 分枝LP4无可行解，剪去
分枝LP3的可行域为D，（图5-3），最优解为xi=40/9，x,=1，最优值为Z(3)=365/9。在分枝LP1LP3、LP4中Z(3)为目标函数值中的最大者，于是新的上界修改为Z=365/9。即此时有：X2XD,39= Z ≤Z≤Z =365/94D33D=((5,0))为2IP最优解D5789x23456图5-3由于LP3的最优解不是整数，最优值为Z(3)=365/9 > Z=39继续分枝
分枝LP3的可行域为D3（图5-3），最优解为x1 ＝40/9，x2 ＝1，最优值为Z (3)＝365/9。在分枝LP1、 LP3、LP4中Z (3)为目标函数值中的最大者，于是 新的上界修改为 Z ＝365/9。即此时有： 39＝ Z Z Z ＝365/9 由于LP3的最优解不是整数，最优值为 Z (3)＝365/9 > Z ＝39 继续分枝. o 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 • • • • • • • • • • • • • x1 x2 • • • • • • • • • • • • D3 D1 D5 D6＝{(5,0)}为 IP最优解 图5-3