SHUFE 分枝定界法 问题2:mxz=5x1+8x2 问题3 z=5x1+8x2 +x,<6 x1+x2≤6 x,s2 2 5 9 45 5x1+9x2<45 x1>3 Ei.x>l xB,x2≥0 xpx2取整数 xpx2取整数 求解问题2相应的线性规划的最优解:x产=2,x2=3+89,Z2=41+19 求解问题3相应的线性规划的最优解:x3,x2=3,Z3=39 第四步,定界过程 下界39; 上界41+1/9。 第五步,分枝过程 将不满足整数约束的变量x进行分枝,构造两个新的约束条件: x2≤3,x224 上海财经大学国际工商管理学院上海财经大学国际工商管理学院 SHUFE 4 分枝定界法 问题2：maxZ= 5x1 +8 x2 问题3： maxZ= 5x1 +8 x2 x1 + x2 ≤6 x1 + x2 ≤6 5x1 +9 x2 ≤45 5x1 +9 x2 ≤45 x1≤2 x1 ≥3 x1 , x2 ≥0 x1 , x2 ≥0 x1 , x2取整数 x1 , x2取整数 求解问题2相应的线性规划的最优解：x1=2，x2 =3+8/9，Z2=41+1/9 求解问题3相应的线性规划的最优解：x1=3，x2 =3，Z3=39 • 第四步，定界过程 ▪ 下界39； ▪ 上界41+1/9。 • 第五步，分枝过程 ▪ 将不满足整数约束的变量x2进行分枝，构造两个新的约束条件： x2≤ 3，x2≥ 4