分枝定界法(branch and bound method)是指以有限投资为约束，迫切度为权值，将问题的所有可行解空间恰当地进行系统搜索，以求得最优解的方法。可行解空间反复分割为越来越小的子集(分枝)，并为每个子集内的解值计算下一个界(定界)，直到不再分割为止，为有限投资方向决策模型之一，亦是一种优化方法。

简介

分枝定界法(branch and bound method)是指以有限投资为约束，迫切度为权值，将问题的所有可行解空间恰当地进行系统搜索，以求得最优解的方法。可行解空间反复分割为越来越小的子集(分枝)，并为每个子集内的解值计算下一个界(定界)，直到不再分割为止，为有限投资方向决策模型之一，亦是一种优化方法1。

决策模型

决策模型由主程序和交通流分配、最短路网费用等子程序所组成1。

优化问题发展现状

最优化理论与算法是一个重要的数学分支，它所讨论的问题是怎样在众多的方案中找到一个最优的方案。例如，在工程设计中，选择怎样的设计参数，才能使设计方案既满足要求又能降低成本；在资源分配中，资源有限时怎样分配，才能使分配方案既可以满足各方面的要求，又可以获得最多的收益；在生产计划安排中，怎样设计生产方案才能提高产值和利润；在军事指挥中，确定怎样的最佳作战方案，才能使自己的损失最小，伤敌最多，取得战争的胜利；在我们的生活中，诸如此类问题，到处可见，最优化作为数学的一个分支，为这些问题的解决提供了一些理论基础和求解方法。

最优化是个古老的课题，长期以来，人们一直对最优化问题进行着探讨和研究，在二十世纪四十年代末，Dantzig提出了单纯形法，有效地解决了线性规划问题，从而最优化成为了一门独立的学科2。

线性规划

有关线性规划方面的理论和算法发展得相当完善，但是关于非线性规划问题的理论和算法还有待进一步的研究，实际应用中还有待进一步的完善。传统的非线性全局最优化方法只能求出问题的局部最优解，但由于许多问题的局部最优解不一定是全局最优解，使得传统的非线性最优化方法不能直接成功地应用于求解非线性全局最优化问题。另外，没有一个固定的评判标准来判断得到的局部最优解是否为全局最优解。随着科学技术的发展和计算机计算能力的提高，最优化理论得到了迅速的发展，涌现出了许多新的算法，如打洞函数法，填充函数法，lagrangian乘子函数方法，信赖域方法，虑子方法等3。

本词条内容贡献者为:

石季英 - 副教授 - 天津大学

分枝定界法

图文简介

分枝定界法(branch and bound method)是指以有限投资为约束，迫切度为权值，将问题的所有可行解空间恰当地进行系统搜索，以求得最优解的方法。可行解空间反复分割为越来越小的子集(分枝)，并为每个子集内的解值计算下一个界(定界)，直到不再分割为止，为有限投资方向决策模型之一，亦是一种优化方法。