管理远筹学 谢家平博士副教授 研究领域:系统建模与优化、生产与运作管理、物流与供应链管理 讲授课程:管理运筹学、管理系统工程、生产运作管理、 供应链管理、国际物流管理、企业资源计划 单位:上海财经大学国际工商管理学院供应链管理研究中心 E-mail:jiapingxie@sina.com.cn 电话:55036936(m)65903541(O)
管理运筹学 谢家平 博士 副教授 研究领域：系统建模与优化、生产与运作管理、物流与供应链管理 讲授课程：管理运筹学、管理系统工程、生产运作管理、 供应链管理、国际物流管理、企业资源计划 单 位：上海财经大学国际工商管理学院供应链管理研究中心 E-mail：jiaping_xie@sina.com.cn 电 话：55036936(H) 65903541(O)
SHUFE 分枝定界法 分枝定界法( Branch and bound method 基本思想: 先求出整数规划相应的线性规划(即不考虑整数限制)的最优解, 若求得的最优解符合整数要求,则这个解就是原整数规划的最优 解 若不满足整数条件,则任选一个不满足整数条件的变量来构造新 的约束,在原可行域中剔除部分非整数解。 然后,再在缩小的可行域中求解新构造的线性规划的最优解,这 样通过求解一系列线性规划问题,最终得到原整数规划的最优解。 定界的含义: 整数规划是在相应的线性规划的基础上增加变量为整数的约束条 件,整数规划的最优解不会优于相应线性规划的最优解。 对极大化问题来说,相应线性规划的目标函数最优值是原整数规 划函数值的上界; 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 2 分枝定界法 • 分枝定界法(Branch and Bound Method) • 基本思想： ▪ 先求出整数规划相应的线性规划(即不考虑整数限制)的最优解， ▪ 若求得的最优解符合整数要求，则这个解就是原整数规划的最优 解； ▪ 若不满足整数条件，则任选一个不满足整数条件的变量来构造新 的约束，在原可行域中剔除部分非整数解。 ▪ 然后，再在缩小的可行域中求解新构造的线性规划的最优解，这 样通过求解一系列线性规划问题，最终得到原整数规划的最优解。 • 定界的含义： ▪ 整数规划是在相应的线性规划的基础上增加变量为整数的约束条 件，整数规划的最优解不会优于相应线性规划的最优解。 ▪ 对极大化问题来说，相应线性规划的目标函数最优值是原整数规 划函数值的上界；
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
SHUFE 分枝定界法 问题2:mxz=5x1+8x2 问题3 z=5x1+8x2 +x,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
SHUFE 分枝定界法 问题4:mxz=5x1+8x2 问题5:mxz=5x1+8x x1+x2<9 +x2≤9 5xn+9x2≤45 5x1+9x2≤45 x1<2 12 1 x1x2取整数 xnx2取整数 求解问题相应的线性规划的最优解:x1=2,x2=3,Z=34 求解问题5相应的线性规划的最优解:xr1+45,x2=4,z5=41 第六步,定界过程 下界39; 上界41。 °第七步,分枝过程 将不满足整数约束的变量x1进行分枝,构造两个新的约束条件: ≤1,x12 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 5 分枝定界法 问题4：maxZ=5x1 +8 x2 问题5：maxZ=5x1 +8 x2 x1 + x2 ≤9 x1 + x2 ≤9 5x1 +9 x2 ≤45 5x1 +9 x2 ≤45 x1≤2 x1 ≤2 x2≤3 x2 ≥4 x1 , x2 ≥0 x1 , x2 ≥0 x1 , x2取整数 x1 , x2取整数 求解问题4相应的线性规划的最优解：x1=2，x2 =3，Z4=34 求解问题5相应的线性规划的最优解：x1=1+4/5，x2 =4，Z5=41 • 第六步，定界过程 ▪ 下界39； ▪ 上界41。 • 第七步，分枝过程 ▪ 将不满足整数约束的变量x1进行分枝，构造两个新的约束条件： x1≤ 1，x1≥ 2
SHUFE 分枝定界法 诗题6:maxz=5x1+8x2 问题7:mxz=5x1+8x2 +x,0 px2≥0 xpx2取整数 xnx2取整数 求解问题6相应的线性规划的最优解:x=,x2=4+秒9,Z6=40+59 求解问题7相应的线性规划的最优解:无可行解 °第八步,定界过程 LP7的无最优解,不必再分枝,下界39; 上界为40+5/9。 °第九步,分枝过程 将不满足整数约束的变量x进行分枝,构造两个新的约束条件: 2≤4,x25 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 6 分枝定界法 问题6：maxZ=5x1 +8 x2 问题7：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 ≥ 2 x1 , x2 ≥0 x1 , x2 ≥0 x1 , x2取整数 x1 , x2取整数 求解问题6相应的线性规划的最优解：x1=1，x2 =4+4/9，Z6=40+5/9 求解问题7相应的线性规划的最优解：无可行解 • 第八步，定界过程 ▪LP7的无最优解，不必再分枝，下界39； ▪上界为40+5/9。 • 第九步，分枝过程 ▪ 将不满足整数约束的变量x2进行分枝，构造两个新的约束条件： x2≤ 4，x2≥ 5
SHUFE 分枝定界法 题8:mxz=5x1+8x 问题9:mxz=5x1+8x +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
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 下界： 上界： 分枝定界法
SHUFE 分枝定界法 上界:41 3-,Z=41 4 下界:0 >4 问题2: 可题3 上界 x1=3,x2=3,Z=39 下界:3 4,z=41 问题4: 题5: 上界:40 x1=1,x2=4,=40 无可行解 下界:39 问题6 问题7 上界:40 1,x,=4,Z=37 5.2=40 上海财经大学国际工商管理学院
上海财经大学国际工商管理学院 SHUFE 9 , 4, 41 5 4 1 3 x1 = x2 = Z = 问题 ： 4 1 , 41 4 3 , 3 4 1 2 1 x1 = x2 = Z = 问题 ： 3, 3, 39 2 x1 = x2 = Z = 问题 ： 9 5 , 40 9 4 1, 4 4 x1 = x2 = Z = 问题 ： 无可行解 问题5： 1, 4, 37 6 x1 = x2 = Z = 问题 ： 0, 5, 40 7 x1 = x2 = Z = 问题 ： x2≤3 x2 ≥4 x1≤1 x1≥2 x2≤4 x2 ≥5 0 4 1 41 下界： 上界： 39 41 下界： 上界： 39 9 5 40 下界： 上界： 40 40 下界： 上界： 分枝定界法