3.2分枝定界法.ppt

文档介绍：分枝定界法
一、分枝定界法的原理:
1、分枝
· · · · · · · · · ·
· · · · · · · ·
0 1 2 3 4 5 6 7 8
·
松弛问题的可行域
增加x1≤3
增加x1≥4
L1
L2
x1≤3
x1≥4
父问题
子问题
结论1 :(IP)的最优解一定在某个子问题中
父问题的最优值
≤
3 :子问题中的整数解都是(IP)的可行解
子问题的最优解
2 :子问题的可行域
父问题的可行域
∩
2、定界
1、(LP)的最优值是(IP)的最优值的上界
IP
松弛问题L0
L1
L2
通过对(L0)分枝,使(IP)的最优值
的上界不断下降,
L3
L4
L5
L6
下界不断上升,
上界=下界
得最优值
分枝定界法的基本思路:
不断降低(IP)最优值的上界,提高下界,
当上界等于下界时,得到最优解
通过对松弛问题的分枝,
分枝定界法计算过程:
上界
x1≤[x*01]
x1≥[x*01]+1
当所有的子问题均被关闭或剪枝后
目标函数值最大的整数解既为所求的最优解
· · · · · · · · · ·
· · · · · · · ·
0 1 2 3 4 5 6 7 8
·
x1≤3
x1≥4
z=30x1+20 x2
4x1+x2=
2x1+3x2=
x2≤2
x2≥3
x1≤2
x1≥3
课堂练习: