第三节 分枝定界法
• 分枝定界法基本思想 • 分枝定界法计算步骤
1. 分枝定界法基本思想
分 枝
最优值比界坏
舍
弃
最优解为整数 最优值比界好
最优解为非整 数最优值比界好
分
枝
边 界
1. 分枝定界法基本思想续
0
N
B N1Βιβλιοθήκη 1 cB B bI
B 1b
xr br Z
b x b 1
z3 3.25x3 (2.25,1)T
x1 2
z5 3x5 (2,1)T
( P5 )
( P3 )
( P6 )
无解
2. 分枝定界法计算步骤
2. 分枝定界法计算步骤-例题
• 例3.3.1
minZ ( x1 x2 ) s.t.4 x1 2 x2 1 4 x1 2 x2 11 2 x 1 2 x1x2 整数
例3.3.1解答
3 5 x0 ( , )T z0 4 2 2
x1 1
5 3 z1 x1 (1, )T 2 2 ( P1 )
( P)
x1 1
3 7 x 2 (2, )T z2 2 2
( P2 ) x2 1
x2 2 ( P4 ) x1 3
无解
r r r
1. 分支定界法基本思想续
• 分枝的方法 min c x
Ax b s.t. x 0, x为整数
min c x Ax b s.t. xr br x 0, x为整数
1. 分枝定界法基本思想续
• 分枝方法示意图
1. 分枝定界法基本思想续
• 定界 1. 当前得到的最好整数解的目标函数值 2. 分枝后计算松弛的线性规划的最优解
整数解且目标值小于原有最好解的值则替代原有 最好解 整数解且目标值大于原有最好解的值则 删除该分 支其中无最优解 非整数解且目标值小于原有最好解的值则继续分 支 非整数解且目标值大于等于原有最好解的值则删 除该分支其中无最优解