管理远筹学 谢家平博士副教授 研究领域:系统建模与优化、生产与运作管理、物流与供应链管理 讲授课程:管理运筹学、管理系统工程、生产运作管理、 供应链管理、国际物流管理、企业资源计划 单位:上海财经大学国际工商管理学院供应链管理研究中心 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,<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
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