分支定界法和割平面法

《分支定界法和割平面法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、分支定界法和割平面法在上学期课程中学习的线性规划问题中，有些最优解可能是分数或消失，但现实中某些具体的问题，常要求最优解必须是整数，这样就有了对于整数规划的研究。整数规划有以下几种分类：（1）如果整数规划中所有的变量都限制为（非负）整数，就称为纯整数规划或全整数规划；（2）如果仅一部分变量限制为整数，则称为混合整数规划；（3）整数规划还有一种特殊情形是0-1规划，他的变量取值仅限于0或1。本文就适用于纯整数线性规划和混合整数线性规划求解的分支定界法和割平面法，做相应的介绍。一、分支定界法在求解整数规划是，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，然后比较它们的目标

2、函数值以定出最优解。对于小型问题，变量数量很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。而对于大型的问题，可行的整数组合数很大时，这种方法就不可取了。所以我们的方法一般是仅检查可行的整数组合的一部分，就能定出最有的整数解。分支定界法就是其中一个。分枝定界法可用于解纯整数或混合的整数规划问题。在二十世纪六十年代初由LandDoig和Dakin等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。设有最大化的整数规划问题，与它相应的线性规划为问题，从解问题开始，若其最

3、优解不符合的整数条件，那么的最优目标函数必是的最优目标函数z*的上界，记作；而的任意可行解的目标函数值将是z*的一个下界z。分枝定界法就是将的可行域分成子区域再求其最大值的方法。逐步减小和增大z，最终求到z*。现用下例来说明：例1求解下述整数规划解（1）先不考虑整数限制，即解相应的线性规划，得最优解为：可见它不符合整数条件。这时是问题A的最优目标函数值z*的上界，记作。而X1=0，X2=0显然是问题A的一个整数可行解，这时，是z*的一个下界，记作z，即0≤z*≤356。（2）因为X1X2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选X1进行分枝，于是对原问题增加两个约束条件：于是可将

4、原问题分解为两个子问题B1和B2（即两支），给每支增加一个约束条件并不影响问题A的可行域，不考虑整数条件解问题B1和B2，称此为第一次迭代。得到最优解为：问题B1问题B2Z1=349X1=4.00X2=2.10Z2=341X1=5.00X2=1.57显然没有得到全部变量时整数的解，于是再定界：。问题BX1=4.81X2=1.82Z=356（3）继续对问题B1和B2因Z1＞Z2，故先分解B1为两支，增加条件X2≤2，称为B3；增加条件X2≥3，称为B4。再舍去X2＞2与X3＜3之间的可行域，再进行第二次迭代。解题过程如图：问题B6无可行解问题B5X1=5.44X2=1.00Z5=308问题B4X

5、1=1.42X2=3.00Z4=327问题B3X1=4.00X2=2.00Z3=340问题B1X1=4.00X2=2.10Z1=349=356，z=0X1≤4X2≥5问题B2X1=5.00X2=1.57Z2=341=349，z=0X2≤2X2≥3=341，z=340X2≤1X2≥2z*=340=z由图可知，B3的解已都是整数，他的目标函数值Z3=340，可取为z，而它大于Z4=327。所以，再分解B4已无必要。而问题B2的Z2=341，所以z*可能在340和341之间有整数解。于是对B2分解，得问题B5，既非整数解且Z5=308＜Z3，问题B6为无可行解。于是有z*=z3=z=340问题B3的

6、解X1=4.00，X2=2.00为最优整数解。从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：开始，将要求解的整数规划问题称为问题，将与它相应的线性规划问题称为问题。（1）解问题可能得到以下情况之一：（a）没有可行解，这时也没有可行解，则停止．（b）有最优解，并符合问题的整数条件，B的最优解即为的最优解，则停止。（c）有最优解，但不符合问题的整数条件，记它的目标函数值为。（2）用观察法找问题的一个整数可行解，一般可取，试探，求得其目标函数值，并记作z。以z*表示问题的最优目标函数值；这时有进行迭代。第一步：分枝，在的最优解中任选一个不符合整数条件的变量xj，其值为bj，以［b

7、j］表示小于bj的最大整数。构造两个约束条件和将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界z，若无作用z=0。第二步：比较与剪枝，各分枝的最优目标函数中若有小于z者，则剪掉这枝，