一、分枝定界法的原理,
1、分枝
为整数对
21
21
21
21
21
,
0,0
5.164
5.1432
.
2030m a x
xx
xx
xx
xx
ts
xxz
0,0
5.164
5.1432
.
2030m a x
)(
21
21
21
21
0
xx
xx
xx
ts
xxz
L,松弛问题
5.2,5.3 21 xx
松弛问题的最优解：
· · · · · · · · · ·
· ·
·
·
·
·
·
·
0 1 2 3 4 5 6 7 8
·
松弛问题的可行域
L1
L2
0,0
5.164
5.1432
.
2030m a x
)(
21
21
21
21
0
xx
xx
xx
ts
xxz
L,松弛问题
0,0
3
5.164
5.1432
.
2030m a x)(
21
1
21
21
211
xx
x
xx
xx
ts
xxzL
0,0
4
5.164
5.1432
.
2030m a x)(
21
1
21
21
212
xx
x
xx
xx
ts
xxzL
父问题子问题结论 1,（ IP）的最优解一定在某个子问题中父问题的最优值≤
为整数
）对（
21
21
21
21
21
,
0,0
5.164
5.1432
.
2030m a x
xx
xx
xx
xx
ts
xxzIP
5.2
,5.3
2
1
x
x
最优解：
3,子问题中的整数解都是（ IP）的可行解子问题的最优解
2,子问题的可行域 父问题的可行域
2、定界
为整数对整数规划问题
jx
X
bAX
ts
CXz
IP
0.
m a x
0.
m a x
X
bAXts
CXz
LP及其松弛问题
1、（ LP）的最优值是 (IP)的最优值的上界
，可以找到一个整数解、若 XLP2
最优值的下界是则 IPXC
IP
IZ最优值松弛问题 L0
0LZ最优值
0LI ZZ?
L1 L2
1LZ最优值 2LZ最优值
01 LL ZZ? 02 LL ZZ?
1,LI ZZ? 2
LI ZZ?或通过对（ L0）分枝，使（ IP）的最优值的上界不断下降，
L3 L4 L5 L6
是整数解的最优解若某个 00 * ii XL
的可行解是则 )(* 0 IPX i Ii ZCX?
0*,有
,* 0ikk CXZL?的最优值若的下界即找到 IZ
,* kCX将下界改为
0,iL关闭是整数解最优解 kX *)1(
剪枝
：的最优值若 0* ikk CXZL?
:kL讨论子问题
0*iCX
L关闭,
不是整数解最优解 kX *)2(
分枝继续对 kL
下界不断上升，
上界 =下界得最优值分枝定界法的基本思路,
不断降低（ IP）最优值的上界，提高下界，
当上界等于下界时，得到最优解通过对松弛问题的分枝，
分枝定界法计算过程：
:0L讨论松弛问题无最优解，,01 L 无最优解则 )( IP 结束
002010 ),*,,**(*2 zxxxX on 最优值，、最优解
为整数解0*)1( X 的最优解为，则 )(* 0 IPX
中至少有一个是分数,0*)2( X
结束是分数设 01*x,分枝上界
:1L子问题,
2L子问题无最优解，,11 L 剪枝为下界1,z 关闭继续分枝
1
112111 ),*,,**(*2 z xxxX n最优值,、最优解
为整数解1*)1( X
中至少有一个是分数：1*)2( X
,* 0ikk CXZL?的最优值若
：设已找到下界 0iZ
,* kCX将下界改为是整数解最优解 kX *)1(
剪枝
：的最优值若 0* ikk CXZL?
:kL讨论子问题
L关闭,
不是整数解最优解 kX *)2(
分枝继续对 kL
当所有的子问题均被关闭或剪枝后目标函数值最大的整数解既为所求的最优解
为整数21
21
21
21
21
,
0,0
5.164
5.1432
.
2030m a x
xx
xx
xx
xx
ts
xxz
0,0
5.164
5.1432
.
2030m a x
21
21
21
21
0
xx
xx
xx
ts
xxz
L,松弛问题
· · · · · · · · · ·
· ·
·
·
·
·
·
·
0 1 2 3 4 5 6 7 8
·
:0L 155,5.25.3 021 zxx,
:1L
3
440
,6173
1
21
z
xx,
4x1+x2=16.5
2x1+3x2=14.5
2321xx：
1303?z
关闭
3411 21 xx,
2
285
4?z 3z?
2
72
21 xx,
1305?z 无可行解剪枝
2
14
21 xx,
1302?z 剪枝
,5.25.3 21 xx,最优解：
:2L
3L 4L
5L
剪枝
6L
1 3 0*
23)( 21
Z
xxIP
最优值：
，的最优解：
课堂练习：
为整数
21
21
21
21
21
,
0,0
1432
92
.
23m a x
xx
xx
xx
xx
ts
xxz
14*
14 21
Z
xx
最优值：
，答案：最优解：
取整数求例
21
3321
421
321
21
,
0,,,
5.164
5.1432
.
2030m a x
xx
xxxx
xxx
xxx
ts
xxz
0,,,
5.164
5.1432
.
2030m a x
3321
421
321
21
0
xxxx
xxx
xxx
ts
xxz
L ；松弛问题混合型
:0L
155
,00
,5.25.3
0
43
21
z
xx
xx
，
，
:1L,2L
0,,,
3
5.164
5.1432
.
2030m a x
3321
1
421
321
21
1
xxxx
x
xxx
xxx
ts
xxz
L ；
351 xx
L0的最 优单纯型表：
x1 x2 x3 x4 常数项检 0 0 -5 -5 Z-155
x2 0 1 2/5 -1/5 5/2
x1 1 0 -1/10 3/10 7/2
x5
x5
1 0 0 0 1 3
0
0
0
:0L
155
,00
,5.25.3
0
43
21
z
xx
xx
，
，
:1L
:3L
得下界1303?z 剪枝
:4L
3z?
:2L
3
440,0,
3
5
0,6173
154
321
zxx
xxx,
0,0
2/52/5
,23
65
43
21
xx
xx
xx
，，
，
0,41
2
50
,3411
65
43
21
xx
xx
xx
，，
，
22854?z
:5L
3z?
2
1,1
50
,272
65
43
21
xx
xx
xx
，，
，
1305 3?z
:6L
x1 x2 x3 x4 解检 0 0 -5 -5 Z-155
x2 0 1 2/5 -1/5 5/2
x1 1 0 -1/10 3/10 7/2
x5
x5
1 0 0 0 1 3
0
0
0
:1L求解子问题
x1 x2 x3 x4 解检 0 0 -5 -5 Z-155
x2 0 1 2/5 -1/5 5/2
x1 1 0 -1/10 3/10 7/2
x5
x5
0 0 1/10 -3/10 1 -1/2
0
0
0
x1 x2 x3 x4 解检 0 0 -20/3 0 -50/3 Z-440/3
x2 0 1 1/3 0 -2/3 17/6
x1 1 0 0 0 1 3
0 0 -1/3 1 -10/3 5/3x4
x5
3
4 4 0
,0,
3
5
0,
6
173
1
54
3211
z
xx
xxxL
最优值：
，最优解：
x1 x2 x3 x4 x5 解检 0 0 -20/3 0 -50/3 Z-440/3
x2 0 1 1/3 0 -2/3 17/6
x1 1 0 0 0 1 3
x4 0 0 -1/3 1 -10/3 5/3
x6 0 1 0 0 0 1 2
x6
0
0
0
0
:3L求解子问题
x1 x2 x3 x4 x5 x6 解检 0 0 -20/3 0 -50/3 0 Z-440/3
x2 0 1 1/3 0 -2/3 0 17/6
x1 1 0 0 0 1 0 3
x4 0 0 -1/3 1 -10/3 0 5/3
x6 0 0 -1/3 0 2/3 1 -5/6
x1 x2 x3 x4 x5 x6 解检 0 0 0 0 -30 -20 Z-130
x2 0 1 0 0 0 1 2
x1 1 0 0 0 1 0 3
x4 0 0 0 1 -4 -1 5/2
x3 0 0 1 0 -2 -3 5/2
0,02/5 2/5,23 654 321 xxx xxx,,，
最优解：
1303?z最优值：
x1 x2 x3 x4 x5 解检 0 0 -20/3 0 -50/3 Z-440/3
x2 0 1 1/3 0 -2/3 17/6
x1 1 0 0 0 1 3
x4 0 0 -1/3 1 -10/3 5/3
x6 0 -1 0 0 0 1 -3
x6
0
0
0
0
:4L求解子问题
x1 x2 x3 x4 x5 x6 解检 0 0 -20/3 0 -50/3 0 Z-440/3
x2 0 1 1/3 0 -2/3 0 17/6
x1 1 0 0 0 1 0 3
x4 0 0 -1/3 1 -10/3 0 5/3
x6 0 0 1/3 0 -2/3 1 -1/6
0,4125
0,3411
654
321
xxx
xxx
，
，，
最优解：
22 8 53?z最优值：
x
1
x2 x3 x4 x5 x6 解检 0 0 -15 0 0 -25 Z-285/2
x2 0 1 0 0 0 -1 3
x1 1 0 1/2 0 0 3/2 11/4
x4 0 0 -2 1 0 -5 5/2
x5 0 0 -1/2 0 1 -3/2 1/4
x1 x2 x3 x4 x5 x6 解检 0 0 -15 0 0 -25 Z-285/2
x2 0 1 0 0 0 -1 3
x1 1 0 1/2 0 0 3/2 11/4
x4 0 0 -2 1 0 -5 5/2
x5 0 0 -1/2 0 1 -3/2 1/4
:5L求解子问题
X7
0
0
0
0
0
x7 1 0 0 0 0 0 1 2
x1 x2 x3 x4 x5 x6 x7 解检 0 0 -20/3 0 0 0 -50/3 Z-130
x2 0 1 1/3 0 0 0 -2/3 7/2
x1 1 0 0 0 0 0 1 2
x4 0 0 -1/3 1 0 0 -10/3 5
x5 0 0 0 0 1 0 -1 1
x6 0 0 1/3 0 0 1 -2/3 1/2
0 0 -1/2 0 0 -3/2 1 -3/4
21,15
0,272
654
321
xxx
xxx
，
，，
最优解：
1303?z最优值：
如何选择分枝的节点及分枝变量？
1、分枝节点选择的原则：尽快找到好的整数解，减少搜索节点，
提高搜索效率。
方法：
（ 1）深探法：
（ 2）广探法：
最后打开的节点最先选择选择有最大目标函数值的节点继续向下分枝
2、分枝变量选择的原则：
寻找那些对问题影响最大的变量首先分枝
（ 1）按目标函数系数选择：
选择目标函数系数绝对值最大的变量首先分枝
（ 2）按非整数变量选择：
选择与整数值相差最大的非整数变量进行分枝
（ 3）按人为给定的顺序选择
:0L 155,5.25.3 021 zxx,
:1L
3
4 4 0
,6173
1
21
z
xx,
:3L,23 21 xx,
得下界1303?z
关闭
:4L 3
4
11
21 xx,
4
570
4?z 3
z?
:5L
2
72
21 xx,
1305?z 剪枝
:6L 无可行解剪枝
:2L
2
14
21 xx,
1302?z 剪枝
0,0
5.164
5.1432
.
2030m a x
21
21
21
21
0
xx
xx
xx
ts
xxz
L,松弛问题
