文档介绍：§ 分支定界法
引入:复面的思想
(P) (P0)
(P)
x0
。。
。。
费用减少的方向
(P0)
x1
。。
。。
费用减少的方向
(P1)
。。
。。
1、分支定界法的基本思想
xk
xi
。。。。。。
。。。。。。
。。。。。。
。。。。。。
。。。。。。
。。。。。。
(P5) (P6)
。
X3
X1
Xk≤[X2k]
Xk≥[X2k]+1
(P4)
(P3)
。
X2
。
X0
X4
(P2)
(P1)
Xi≤[X0i] Xi≥[X0i]+1
(P) (P0)
设原问题(P)的松弛问题(P0)的最优解为。若的某个分量不是整数,由于(P)的整数最优解的第i个分量必定落在区域或中,因此可将原问题(P)分解为两个子问题来求解,
(P1) (P2)
某个点不需要分支的条件:(1)相应的松弛问题的最优解是整数向量,或(2)相应的松弛问题没有可行解
记, 若,则对的任何一个整数可行解都有
所以原问题的最优整数解一定不在中,所以对就无须继续分支,在这种情况下,我们说被剪枝,并把它称为死点(也称为已查明),尚未查明的点称为活点。若,则对需继续考察。若,则记。
2、分支定界法的计算步骤
解:
作业:P93 3, 6(1)