SHUFE 分枝定界法 例 maxz= 5x, +8 十 5x 9r 2≤45 x1,x2≥0 x1,x2取整数 第一步,不考虑变量的整数约束,求相应LP(问题1)的最优解 x1=2+/4,x2=3+3/4,Z=41+1 第二步,定界过程 上界41+1/4; 下界为0。 第三步,分枝过程 将不满足整数约束的变量x进行分枝,构造两个新的约束条件: xI 3 上海财经大学国际工商管理学院上海财经大学国际工商管理学院 SHUFE 3 分枝定界法 例 maxZ= 5x1 +8 x2 x1 + x2 ≤6 5x1 +9 x2 ≤45 x1 , x2 ≥0 x1 , x2取整数 • 第一步,不考虑变量的整数约束,求相应LP(问题1)的最优解： x1=2+/4，x2 =3+3/4，Z1=41+1/4 • 第二步,定界过程 ▪ 上界41+1/4； ▪ 下界为0。 • 第三步，分枝过程 将不满足整数约束的变量x1进行分枝，构造两个新的约束条件： x1≤ 2，x1≥ 3