分支定界法的推广应用.doc

青岛农业大学毕 业 论 文（设计）题 目： 分枝定界法的推广应用 姓 名： 刘立英 学 院： 理学与信息科学学院 专 业： 信息与计算科学 班 级： 2007级1班 学 号： 20073497 指导教师： 李桂玲 2011 年 5 月 20 日目 录中文摘要1Abstract2引言31 整数最优解问题的提出32 分枝定界法简介4 2.1分枝定界法的基本思想42.2 分枝定界法求解的基本步骤52.3 分支定界法的一些应用73 分枝定界法的推广103.1非线性规划的求解方法103.2非线性整数规划的分枝定界法12 3.3 应用133.3.1 两个变量的非线性规划问题133.3.2 三个及三个以上变量的非线性整数规划问题144 总结15致谢16参考文献17分枝定界法的推广应用信息与计算科学专业 刘立英 指导教师 李桂玲摘要：整数规划是线性规划的重要分支，整数规划的求解具有重要的实际意义。分枝定界法则是目前求解整数规划问题较成功的方法之一。分枝定界法不仅适应于线性整数规划问题，同样也可以适应于非线性整数规划问题。本文主要先介绍分枝定界法的基本思想，再将其推广应用于求解非线性规划和其他的非线性整数规划中。关键词:整数规划；分枝定界法；可行域；非线性规划The Application of Branch and Bound MethodInformation and computer science Liu Liying Tutor Li GuilingAbstract：Integer programming is an important branch of linear programming, integer programming to solve an important practical significance. Branch and bound rules for solving integer programming problem is the more successful methods. Branch and bound method is not only suitable for linear integer programming problem, the same can also be adapted to the nonlinear integer programming problem. This paper first describes the basic branch and bound ideas, and then applied to solve the nonlinear programming and other nonlinear integer planning. Key words: Integer Programming；Branch and bound；Feasible region；Nonlinear Programming引言规划是将实际问题建立数学模型进行求解，进而反过来指导并预测实际问题的一种方法。在数学上，规划包括线性规划和非线性规划。线性规划的理论，求解方法等现在发展已比较成熟；非线性规划方面的理论，求解方法等现在尚处于发展中，并不成熟。在规划中，要求变量取整数的规划称为整数规划。整数规划对许多实际问题的解决有重要的指导意义，例如，投资决策问题，货郎担问题等。相应的，求解整数规划的方法也有很多，例如枚举法，割平面法，分支定界法等。分支定界法是目前求解整数规划的较成功高效的方法之一。分支定界法的两个重要步骤分支与定界从理论上决定了它可以解决大部分的规划问题，因此，分支定界法在解决规划问题方面得到广泛应用。本文介绍分枝定界法的基本思想，在求解整数线性规划中的应用，进而推广到非线性规划中，希望使其得到更广泛的应用。1 整数最优解问题的提出线性规划是运筹学的一个重要组成部分，而其中的整数线性规划则是解决实际问题的重要指导方法。因此，研究整数线性规划就显得很有意义。要求变量取整数值的线性规划问题称为整数线性规划( integer linear programming,简记作ILP)，简称为整数规划。整数规划与线性规划有着密不可分的关系，它的一些基本算法的设计都是以相应的线性规划为出发点的，我们首先介绍整数规划。对于整数规划问题, 我们记为,把它的整数约束条件去掉, 得到一个普通的线性规划问题, 这个规划问题叫做原问题的一个松弛LP问题,记为（）。设整数规划问题为 其相应的松弛线性规划问题为 给定一个整数规划问题,求解思路是先求它的松弛问题。松弛问题的最优解可以利用单纯形方法和图解法等方法求解。如果松弛问题的最优解中每一个变量( 即分量) 的值都为整数，即满足各自的整数约束,则原问题得到解决，松弛问题()的最优解也就是原问题（P）的最优解。如果松弛问题的最优解中, 至少有某个变量的值不是整数, 则可以利用分枝定界法进行分枝与定界求解。2 分枝定界法简介分枝定界法是20世纪60年代由Land-Doig和Dakin等人提出的。这种方法既可用于纯整数线性规划问题，也可用于混合整数线性规划问题，而且便于用计算机求解，所以很快成为解整数规划的最主要的方法。2.1 分枝定界法的基本思想有界ILP问题的可行集合中的格点数目（也就是整数解）是有限的。分枝定界法以“巧妙”地枚举ILP问题的可行解的思想为依据设计的。给定一个ILP问题，我们记为，去掉整数约束条件，得到原问题的松弛LP问题，记为,则与的解之间存在如下关系：（1）若无解，则ILP问题无解；（2）若的最优解是满足整数要求的向量，则是ILP问题的最优解；（3）若不满足整数的要求，则有两条不同的途径：一是不断改进松弛问题，以期求得的最优解；另一条途径就是利用分解技术，将要求解的ILP问题分解为几个子问题的和，如果对每个子问题的可行域（简称为子域）能做到：或者找到了这个子域内的最优解，或者明确原问题的最优解肯定不在这个子域内，这样原问题就容易解决了。我们就可以用分枝定界法来求解了。2.2 分支定界法求解的基本步骤设整数线性规划问题为其松弛线性规划问题为用单纯形法来求解问题的最优解，最优解记为，若最优解已经是整数，则已经求的最优解；若的某个分量，不妨记为第个分量不满足整数要求，由于的整数最优解的第个分量必定落在区域或中（表示不超过的最大整数），因此可将原问题分解成两个子问题来求解，子问题是： 和 这两个子问题将的可行域分成两部分，并且把不满足整数要求的的最优解排斥在外。对于整数线性规划和，仍然是求解它的相应的松弛LP问题。比如说对问题的松弛问题的解是满足整数要求的，这个子域就查清了，不需要再分枝；若问题的松弛问题的最优解不满足整数要求，我们又可以根据它的某个不满足整数要求的分量，不妨设为，按或，将问题像分解问题一样的分解为问题和，如此继续下去，直到某个子域求的解符合最优解整数要求。这个过程称为分枝，分枝过程可能在某个点上（自变量）停止，这是因为：相应松弛LP问题的解是满足整数要求的，或相应松弛LP问题是不可行的。上述是分枝定界法的分支部分。显然，如果我们只用分枝过程，最后一定可以求的整数最优解。但是这样计算量非常大，尤其是在自变量很多的情况。下面我们来描述定界过程。定界过程则是利用对ILP问题目标函数界的一个估值，删去一些不必要的点的分枝，使计算量大大减少。不妨设某一时刻，所得到的最好的满足整数要求的解的目标函数值是，而且我们正打算由某一点开始分枝，不妨设这一点为，该点子域对应的ILP的下界为。若，这意味着点的所有后代得到的各个解的目标函数值均有，则不必再由向下继续分枝，已被剪掉。这个过程称为定界过程。我们将上述分枝定界法求解的过程写成基本步骤，如下： 对于某一ILP问题，首先求的其松弛LP问题； 求松弛LP问题，最优解记为，此时最优值记为； 若的最优解记符合整数要求，则计算停止，已求得最优整数解。若中至少有一个分量不为整数，不妨设为，则将分为和两部分，分别添加到中，形成两个子域，不妨记为和。计算到此时所得到的最好的满足整数要求的解的目标函数值,一般。 分别求解和，结果要求与，相同。 若对某一点要进行分解，不妨设这一点为，该点子域对应的ILP的下界为。若，则将此点剪枝，不必再从此点分枝。 如此反复继续，直至所求的最优解为整数最优解。用分枝定界法解整数规划问题比穷举法优越。因为它仅在一部分可行解的整数解中寻求最优解，计算量比穷举法小。若变量数目很大，其计算工作量也是相当可观的。 2.3 分支定界法的一些应用例1 用分枝定界法解下述ILP问题 解：首先求的松弛LP问题，记为，如下： 其可行域入下图1所示：图 1易求得其松弛LP问题的最优解为，最优值为，它是原ILP问题最优值的一个下界。这里均为非整数分量，我们不妨从先开始分枝，引进两个约束和，生成两个子问题，记为和，如下： 和 ILP问题的松弛LP问题的最优解为，最优值为，的松弛LP问题的最优解，最优值为。两个问题均可继续分枝，一般我们选取目标函数较优的那个点先分枝。显然，所以将问题先分解。增加约束和，将问题分解成两个子问题和。问题无解，的松弛LP问题的解为，最优值为。又因为，所以点被剪枝，所以最后得到的点的解一定是原ILP问题的最优解，对应的最优值为。例2 用分枝定界法求下面的ILP问题 解：首先求的松弛LP问题，记为，如下： 对于三个及三个以上的变量的线性规划，我们可以先用单纯形法求的最优解，用单纯形法求得的最优解为，最优值为。不妨先将分枝。增加约束和，生成两个子问题，记为和，如下： 和 用单纯形法求得的最优解为，最优值为。我们再来求，根据的可行域的构造，我们可以将化简如下： 问题如下图2图3对应的松弛LP问题的解为，最优解为。将先分解，增加约束和，将问题分解成两个子问题和。的松弛LP问题的最优解为，最优值为。的松弛问题的最优解为，最优值为。比较，的最优解及最优值，易知，原ILP问题的最优解为，最优值为。3 分支定界法的推广3.1 非线性规划的求解方法线性规划是指目标函数和约束函数均是自变量的线性函数时的规划。当目标函数和约束函数中至少有一个是自变量的非线性函数，那么这个规划就称为非线性规划。非线性规划的求解方法主要有图解法，惩罚函数法和障碍函数法，图解法主要解决变量为两个的非线性规划。惩罚函数法的基本思想是，利用问题中的约束函数作出适当的带有参数的惩罚函数，然后在原来的目标函数上加上惩罚函数构造出带参数的增广目标函数，把原问题的求解转化为求解一系列无约束非线性规划问题。障碍函数法的基本思想是，在可行区域的边界上筑起一道“墙”来，当迭代点靠近边界时，所构造的增广目标函数值陡然增大，于是最优点就被挡在可行区域内部了。例3 求解下述非线性规划问题解：上述问题的可行域及目标函数如下图3图 3由图3易知，当目标函数与可行域仅相切于点时，目标函数达到最优值，此时最优值为，最优解为。例4 求解下述非线性规划问题解：用惩罚函数求解，取，则,原问题转化为求解无约束最优化问题。首先求，再令，求得,可见，当逐渐增大时，是逐渐趋于其最优解的，最优值为。例5 求解下述非线性规划问题解：用障碍函数法求解，取，采用对数形式的障碍函数，取，则，求，令，求得，可见当无限增大时，即无限减小时，是逐渐趋于其最优解的，最优值为。3.2非线性整数规划的分支定界法用分支定界法解非线性整数规划问题无论从理论上还是实践中都容易实现。非线性整数规划的分支定界法的方法和步骤如下：设某非线性整数规划问题为：s.t. 我们先对目标函数求对于各变量的偏导数，并令，可以求得一个初始解，再根据约束函数（及条件）求得可行域，这里我们不考虑初始解是否在可行域内，因为对于非线性规划问题，初始解是否在可行域内并不影响目标函数最优解及最优点的实现。因此，我们主要考虑初始解是否为整数。若初始解为整数，且在可行域内，则最优解及最优值已经得到，分别为，；若不在可行域内，则根据初始解，目标函数，及可行域的构造，继续寻找最优解和最优值。若初始解至少有某个分量，不妨设为不为整数，则可将分为和两部分区域约束，表示不大于的最大整数，再分别添加到原规划中，形成两个子规划，记为，再对这两个子规划进行求解。若子规划中，求得的解为整数，则问题得到解决；若不为整数，则继续上述过程，直到所有分量（解）均为整数为止，这就是分支过程。对于定界，假设在某一时刻得到的最优整数目标函数值为，此时正要由进行分支，对应的两个子规划的最优值下界为，且有，因此不必从再开始分支，这就是定界过程。 3.3应用3.3.1两个变量的非线性规划问题例6 s.t. 首先解上述规划问题的目标函数，按照上述说明求极小值点也是最优解为：，最优值。这里不为整数，所以我们分为和两部分，分别加入到原规划中，形成两个子规划，分别称为,。对于，由约束条件可知，显然无解，所以我们只考虑。由上述分析方法，再利用图解法，易知，在约束条件下的最优解为，此时的最优值为：。如下图4：图4上面用分枝定界技术分析和求解有约束的二次整数规划问题的算法,可以结合计算机语言编写出程序用计算机求解，从而大大使计算简化。分支定界法要求先分支，再定界，所以这种方法在理论上可以说对绝大多数的规划都可以给出一定的方法。另外，分支定界法在一般非线性规划中也有着广泛应用。 3.3.2三个及三个以上变量的非线性整数规划问题例7 求解下述非线性整数规划问题 解：同例4一样，用惩罚函数求解。取，令，根据目标函数的构造，可行域的要求，及解得形式，易知，当时，目标函数达到最优值，最优解为。例8 求解下述非线性整数规划问题解：同例5一样，用障碍函数法求解，取，采用对数形式的障碍函数，令，易知，点为的极值点，经检验，也为原问题的最优解，最优值为。 4 总结分枝定界法在解决线性规划问题方面有着显著的优点，可以求得最优解、平均速度快。因为从最小下界分支，找出限界最小的结点，此结点即为下次分支的结点。这种优点是检查子问题较少，能较快的求得最佳解。 但也有不少缺点：要存储很多结点的限界和对应的耗费矩阵，计算量大。另外更重要的是，在解决非线性方面,尤其是二次规划问题，有其广泛应用，但限于现在技术水平，还不能完全应用于实践，相信以后会慢慢发展起来。致谢 值此本科毕业论文完成之际，我首先要诚挚地感谢我的指导老师李桂玲老师。起初，在论文方向的选定的时候，李老师帮我具体分析了文章需要涉及的各个方面，让我在写作时有了