文档介绍：管理运筹学
谢家平博士副教授
研究领域:系统建模与优化、生产与运作管理、物流与供应链管理
讲授课程:管理运筹学、管理系统工程、生产运作管理、
供应链管理、国际物流管理、企业资源计划
单位:上海财经大学国际工商管理学院供应链管理研究中心
E-mail:jiaping_xie@
电话:55036936(H) 65903541(O)
1
分枝定界法
分枝定界法(Branch and Bound Method)
基本思想:
先求出整数规划相应的线性规划(即不考虑整数限制)的最优解,
若求得的最优解符合整数要求,则这个解就是原整数规划的最优解;
若不满足整数条件,则任选一个不满足整数条件的变量来构造新的约束,在原可行域中剔除部分非整数解。
然后,再在缩小的可行域中求解新构造的线性规划的最优解,这样通过求解一系列线性规划问题,最终得到原整数规划的最优解。
定界的含义:
整数规划是在相应的线性规划的基础上增加变量为整数的约束条件,整数规划的最优解不会优于相应线性规划的最优解。
对极大化问题来说,相应线性规划的目标函数最优值是原整数规划函数值的上界;
2
分枝定界法
例 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
3
分枝定界法
问题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
4
分枝定界法
问题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
5
分枝定界法
问题6: maxZ= 5x1 +8 x2 问题7: maxZ= 5x1 +8 x2
x1