由x,=4.81产生两个约束条件x,≤4,x,≥5Maxz40x,90x2Max z40x 90x29x7569x7x256B17x20x2707x20x27054xxX，X 0Xx没有减少可行解Bi: xi=4 x2 =2.1Z1 = 349B2: xj =5x2 =1.57B,的可行域B,的可行域2 = 3414,都不是A的可行解1(5,157)注意：这样分枝并没有减少A的可行解，但增加了可能符合整数条件的顶点
B1的可行域 B2的可行域 （4， 2.1） （5,1.57） 由x1 =4 .81产生两个约束条件x1≤4, x1≥5 注意：这样分枝并没 有减少A的可行解，但 增加了可能符合整数条 件的顶点 1 没有减少可行解
北京交通大学经济管理学院nics and ManagomentSchool of EconoBoijing Jiaotong UniversityBX2=1.82z=0x,=4.81Z=356Zo=356X5x4BB2x2=1.57xi=5.00z=0x,=4.00x,=2.10Z=349QQZ,=341Zj=349北京交通大学
x1 =5.00 x2 =1.57 B1 x1 =4.00 x2 =2.10 z1=349 x14 x15 z2=341 B2 z =0 B x1 =4.81 x2 =1.82 z0=356 z =0
再将B,分枝,在B,中分别加x,,x,B得到Max z. =M0494990x219+ 5619x2070-7020x1x+33B4B3ix35xir3:irat, 21X 3ixi0其解是X=2B3 X = 4B的可行域B,的可行域Z,=340(1.42.3)B41.42X2 =3(4,2)Z4A的可行解，Z3>Z
B4的可行域 B3的可行域 （4,2） （1.42,3） 再将B1分枝, 在B1中分别加x2 2, x2 3得到： A的可行解， z3＞
北京交通大学经济管理学院School of Econonics and ManagomentBoijing Jiaotong UniversityB2Z=0=1.82x,=4.81Zo=356X5x,4BBzx;=5.00 x=1.57xi=4.00 x2=2.10Z=0Z,=341Zi=34952X3B3Bx,=1.42 x2=3.00x,=4.00 x2=2.00Z=340要Z,=327Z3=340北京交通大学
B4 x22 B3 x1 =4.00 x2 =2.00 z3=340 x1=1.42 x2 =3.00 z4=327 x23 z =340 x1 =5.00 x2 =1.57 B1 x1 =4.00 x2 =2.10 z1=349 x14 x15 z2=341 B2 z =0 B x1 =4.81 x2 =1.82 z0=356 z =0
更新 340，得到新的界 Z 由于z,<Z 知B的可行域内不可能含有比(4，2)T更优的解，故B4不再分枝。回到B,，由于z,>Z，不排除B,的可行域中有比(4，2)T更好的整数解的可能,故要继续分枝.在B,中分别加约束条件：x,□，x，,得到问题B,和B其最优解分别为Bs xi = 5.44 x2 = 1Zs = 308B无可行解(5.44,1)<zB5不继续分Z5枝B.更不用继续分B,的可行域枝至此知 x*=(4 2)Tz"=340
B5的可行域 （5.44,1） 更新 =340，得到新的界 。由于z4 < ，知B4 的可行域内不可能含有比(4，2)T更优的解，故B4不 再分枝。 回到B2，由于z2 > , 不排除B2的可行域中有比 (4，2)T更好的整数解的可能, 故要继续分枝. 在B2中 分别加约束条件：x2 1，x2 2, 得到问题B5和B6