第二节用分支定界法求解整数规划 通常，混合整数规划问题一般有无限多个可 行解。即使是纯整数规划问题， 随着问题规模的 扩大，其可行解的数目也将急剧增加。因此通过 枚举全部可行解，并从中筛选出最优解的算法无 实际应用价值。分支定界法(branch and bound method)是一种隐枚举法(implicit enumeration). 或部分枚举法，它是在枚举法基础上的改进。分 支定界法的关键是分支和定界
13 第二节 用分支定界法求解整数规划 通常，混合整数规划问题一般有无限多个可 行解。即使是纯整数规划问题，随着问题规模的 扩大，其可行解的数目也将急剧增加。因此通过 枚举全部可行解，并从中筛选出最优解的算法无 实际应用价值。分支定界法(branch and bound method)是一种隐枚举法(implicit enumeration) 或部分枚举法，它是在枚举法基础上的改进。分 支定界法的关键是分支和定界
第二节用分支定界法求解整数规划 若整数规划的松弛问题的最优解不符合整数 要求，假设X=b*不符合整数要求；[b*]是不超过 b*的最大整数，则构造两个约束条件：X,≤[b*] 和X,≥[b]+1。分别将其并入上述松弛问题中 从而形成两个分支，即两个后继问题。 这两个后 继问题的可行域中包含原整数规划问题的所有可 行解。而在原松弛问题可行域中，满足的一部分 区域在以后的求解过程中被遗弃了，然而它不包 含整数规划的任何可行解
14 第二节 用分支定界法求解整数规划 若整数规划的松弛问题的最优解不符合整数 要求，假设Xi=b*不符合整数要求；[b*]是不超过 b *的最大整数，则构造两个约束条件：Xi ≤ [b*] 和Xi ≥[b*]+1。分别将其并入上述松弛问题中， 从而形成两个分支，即两个后继问题。这两个后 继问题的可行域中包含原整数规划问题的所有可 行解。而在原松弛问题可行域中，满足的一部分 区域在以后的求解过程中被遗弃了，然而它不包 含整数规划的任何可行解
第二节用分支定界法求解整数规划 根据需要，各个后继问题可以类似地产生自 已的分支，即自已的后继问题。如此不断继续 直到获得整数规划最优解。这就是所谓“分支 所谓“定界”，是在分支过程中，若某个后 继问题恰巧获得整数规划问题的一个可行解，那 么，它的目标函数值就是一个“界限”，可作为 衡量处理其他分支的一个依据。因为整数规划问 题的可行解集是它的松弛问题可行解集的一个子 集，前者最优解的目标函数值不会优于后者
15 根据需要，各个后继问题可以类似地产生自 己的分支，即自己的后继问题。如此不断继续， 直到获得整数规划最优解。这就是所谓“分支” 。 所谓“定界” ，是在分支过程中，若某个后 继问题恰巧获得整数规划问题的一个可行解，那 么，它的目标函数值就是一个“界限” ，可作为 衡量处理其他分支的一个依据。因为整数规划问 题的可行解集是它的松弛问题可行解集的一个子 集，前者最优解的目标函数值不会优于后者。 第二节 用分支定界法求解整数规划
第二节用分支定界法求解整数规划 所以，对于那些相应松弛问题最优解的目标 函数值比上述“界限”值差的后继问题，就可以 剔除而不再考虑了。当然，如果在以后的分支过 程中出现了更好的“界限”，则以它来取代原来 的界限，这样可以提高定界的效果 分支”为求出整数规划最优解创造了条件， 而“定界”则可以提高搜索的效率。 经验表明 根据对实际问题的了解，事先选择一个合理的 “界限”，可以提高分支定界的搜索效率 16
16 所以，对于那些相应松弛问题最优解的目标 函数值比上述“界限”值差的后继问题，就可以 剔除而不再考虑了。当然，如果在以后的分支过 程中出现了更好的“界限” ，则以它来取代原来 的界限，这样可以提高定界的效果。 “分支”为求出整数规划最优解创造了条件， 而“定界”则可以提高搜索的效率。经验表明， 根据对实际问题的了解，事先选择一个合理的 “界限” ，可以提高分支定界的搜索效率。 第二节 用分支定界法求解整数规划
第二节用分支定界法求解整数规划 下面介绍分之定界法的基本步骤 步骤1：称整数规划问题为问题A,它的松弛 问题为问题B,以Z表示问题A的目标函数的初始 界（如已知问题A的一个可行解，则可取它的目标 函数值Z,)。对于最大化问题A,Z,为下界；对最小 化问题A,Z为上界。解问题郾。转步骤2； 17
17 下面介绍分之定界法的基本步骤。 步骤1：称整数规划问题为问题A，它的松弛 问题为问题B，以Zb表示问题A的目标函数的初始 界(如已知问题A的一个可行解，则可取它的目标 函数值Zb )。对于最大化问题A，Zb为下界；对最小 化问题A，Zb为上界。解问题B。转步骤2； 第二节 用分支定界法求解整数规划