SHUFE 分枝定界法 分枝定界过程 问题1 上界:41 x1=2-x,=3-,Z=41 下界:O 问题2: 问题3 上界:41 x1=2,x2=3,Z=41 x1=3,x2=3,Z=39 下界:39 问题4 问题5 上界:41 x1=2,x2=3,Z=34 4 2=4,Z=41 下界:39 问题6 问题7: 上界:40 4 x1=1,x2=4-,2=40 无可行解 下界:39 5 问题8: 问题9 上界:40 1,x2=4,z=37 1=0,x2=5,Z=40 下界:40 上海财经大学国际工商管理学院上海财经大学国际工商管理学院 SHUFE 8 • 分枝定界过程 9 1 , 41 9 8 2, 3 2 x1 = x2 = Z = 问题 ： 4 1 , 41 4 3 , 3 4 1 2 1 x1 = x2 = Z = 问题 ： 3, 3, 39 3 x1 = x2 = Z = 问题 ： 2, 3, 34 4 x1 = x2 = Z = 问题 ： , 4, 41 5 4 1 5 x1 = x2 = Z = 问题 ： 9 5 , 40 9 4 1, 4 6 x1 = x2 = Z = 问题 ： 无可行解 问题7： 1, 4, 37 8 x1 = x2 = Z = 问题 ： 0, 5, 40 9 x1 = x2 = Z = 问题 ： x1≤2 x1 ≥3 x2≤3 x2 ≥4 x1≤1 x1 ≥2 x2≤4 x2 ≥5 0 4 1 41 下界： 上界： 39 9 1 41 下界： 上界： 39 41 下界： 上界： 39 9 5 40 下界： 上界： 40 40 下界： 上界： 分枝定界法