SHUFE 分枝定界法 题8:mxz=5x1+8x 问题9:mxz=5x1+8x +x,<6 x1+x2≤6 5x1+9x2≤45 5x1+9x2<45 x1<2 x,>4 1 x1x2取整数 px2取整数 求解问题8相应的线性规划的最优解:xr=1,x2=4,Z8=37 求解问题9相应的线性规划的最优解:x=0,x2=5,Z=40 第十步,定界过程 下界为40; 上界为40。 上界=下界,得整数规划问题的最优解:x1=0,x2=5,z=40 上海财经大学国际工商管理学院上海财经大学国际工商管理学院 SHUFE 7 分枝定界法 问题8：maxZ=5x1 +8 x2 问题9：maxZ=5x1 +8 x2 x1 + x2 ≤6 x1 + x2 ≤6 5x1 +9 x2 ≤45 5x1 +9 x2 ≤45 x1≤2 x1 ≤2 x2 ≥4 x2 ≥4 x1≤1 x1 ≤1 x2≤4 x2 ≥5 x1 , x2 ≥0 x1 , x2 ≥0 x1 , x2取整数 x1 , x2取整数 求解问题8相应的线性规划的最优解：x1=1，x2 =4，Z8=37 求解问题9相应的线性规划的最优解：x1=0，x2 =5，Z9=40 • 第十步，定界过程 ▪ 下界为40； ▪ 上界为40。 ▪ 上界=下界，得整数规划问题的最优解：x1=0，x2 =5，Z=40