§4蕘数规划的分枝定界法(2) 2、对当前问题进行分枝和定界: 分技:无妨设当前问题为(A),其松弛问题(B)的最优解不符合整数约束,任取非整数的分 量x。构造两个附加约束:x≤[x和x≥[xH+1,对(A)分别加入这两个约束,可得到两 个子问题(A1)和(A2),显然这两个子问题的可行解集的并是(A)的可行解集; 定界:根据前面分析,对每个当前问题(A)可以通过求解松弛问题(B),以及找(A)的可行解 得到当前问题的上、下界z和z。 对一般迭代步,设根据分枝定界方法得到了原问题(A的一个同层子问题(A1),i=1,2,…, n之和的分解。这里的同层子问题是指每个子问题(A)都是(A)经过相同分枝次数得到的。 3、比较与剪枝: 对当前子问题进行考察,若不需再进行计算,则称之为剪枝。一般遇到下列情况就需剪 枝 ①(B)无可行解 ②(B)的最优解符合整数约束 ③(B)的最优值z≥z。 通过比较,若子问题不剪枝则返回2。 分枝定界法当所有子问题都剪枝了,即没有需要处理的子问题时,达到当前上界z的可 行解即原问题的最优解,算法结束。§4整数规划的分枝定界法(2) 2、对当前问题进行分枝和定界： 分技：无妨设当前问题为(A)，其松弛问题(B)的最优解不符合整数约束，任取非整数的分 量 xr 。构造两个附加约束： xr ≤ [xr ] 和 xr ≥ [xr ]+1 ，对(A)分别加入这两个约束，可得到两 个子问题(A1 )和(A2 )，显然这两个子问题的可行解集的并是(A)的可行解集； 定界：根据前面分析，对每个当前问题(A)可以通过求解松弛问题(B)，以及找(A)的可行解 得到当前问题的上、下界 z¯和 z 。 对一般迭代步，设根据分枝定界方法得到了原问题(A)的一个同层子问题(AI )，i＝1，2，...， n 之和的分解。这里的同层子问题是指每个子问题(AI )都是(A)经过相同分枝次数得到的。 3、比较与剪枝： 对当前子问题进行考察，若不需再进行计算，则称之为剪枝。一般遇到下列情况就需剪 枝： ①(B)无可行解； ②(B)的最优解符合整数约束； ③(B)的最优值 z ≥ z¯ 。 通过比较，若子问题不剪枝则返回 2 。 分枝定界法当所有子问题都剪枝了，即没有需要处理的子问题时，达到当前上界 z¯ 的可 行解即原问题的最优解， 算法结束