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