分支定界法和割平面法.doc

分支定界法和割平面法 在上学期课程中学习的线性规划问题中，有些最优解可能是分数或消失，但现实中某些具体的问题，常要求最优解必须是整数，这样就有了对于整数规划的研究。整数规划有以下几种分类：（1）如果整数规划中所有的变量都限制为（非负）整数，就称为纯整数规划或全整数规划；（2）如果仅一部分变量限制为整数，则称为混合整数规划；（3）整数规划还有一种特殊情形是0-1规划，他的变量取值仅限于0或1。本文就适用于纯整数线性规划和混合整数线性规划求解的分支定界法和割平面法，做相应的介绍。1、 分支定界法在求解整数规划是，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，然后比较它们的目标函数值以定出最优解。对于小型问题，变量数量很少，可行的整数组合数也是很小时，这个方法是可行的，也是有效的。而对于大型的问题，可行的整数组合数很大时，这种方法就不可取了。所以我们的方法一般是仅检查可行的整数组合的一部分，就能定出最有的整数解。分支定界法就是其中一个。分枝定界法可用于解纯整数或混合的整数规划问题。在二十世纪六十年代初由Land Doig和Dakin等人提出。由于这方法灵活且便于用计算机求解，所以现在它已是解整数规划的重要方法。目前已成功地应用于求解生产进度问题、旅行推销员问题、工厂选址问题、背包问题及分配问题等。设有最大化的整数规划问题，与它相应的线性规划为问题，从解问题开始，若其最优解不符合的整数条件，那么的最优目标函数必是的最优目标函数z*的上界，记作；而的任意可行解的目标函数值将是z*的一个下界z。分枝定界法就是将的可行域分成子区域再求其最大值的方法。逐步减小和增大z，最终求到z*。现用下例来说明：例1 求解下述整数规划 解 （1）先不考虑整数限制，即解相应的线性规划，得最优解为： 可见它不符合整数条件。这时是问题A的最优目标函数值z*的上界，记作。而X1=0，X2=0显然是问题A的一个整数可行解，这时，是z* 的一个下界，记作z，即0z*356 。（2）因为X1X2当前均为非整数，故不满足整数要求，任选一个进行分枝。设选X1进行分枝，于是对原问题增加两个约束条件： 于是可将原问题分解为两个子问题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因Z1Z2 ，故先分解B1为两支，增加条件X22，称为B3；增加条件X23，称为B4。再舍去X22与X33之间的可行域，再进行第二次迭代。解题过程如图：问题B6无可行解问题B5X1=5.44X2=1.00Z5 =308问题B4X1=1.42X2=3.00Z4 =327问题B3X1=4.00X2=2.00Z3 =340问题B1X1=4.00X2=2.10Z1 =349 =356，z = 0 X14 X25问题B2X1=5.00X2=1.57Z2 =341 =349，z = 0 X22 X23 =341，z = 340 X21 X22 z* =340=z 由图可知，B3的解已都是整数，他的目标函数值Z3 =340，可取为z ，而它大于Z4 =327。所以，再分解B4已无必要。而问题B2的Z2 =341，所以z* 可能在340和341之间有整数解。于是对B2分解，得问题B5，既非整数解且Z5 =308Z3，问题B6为无可行解。于是有 z* =z3=z=340问题B3的解X1=4.00，X2=2.00为最优整数解。从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：开始，将要求解的整数规划问题称为问题，将与它相应的线性规划问题称为问题。（1）解问题可能得到以下情况之一： （a）没有可行解，这时也没有可行解，则停止 （b）有最优解，并符合问题的整数条件，B的最优解即为的最优解，则停止。 （c）有最优解，但不符合问题的整数条件，记它的目标函数值为。（2）用观察法找问题的一个整数可行解，一般可取，试探，求得其目标函数值，并记作z。以z*表示问题的最优目标函数值；这时有 进行迭代。第一步：分枝，在的最优解中任选一个不符合整数条件的变量xj，其值为bj，以bj表示小于 bj 的最大整数。构造两个约束条件 和 将这两个约束条件，分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。 定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界z ，若无作用z = 0。第二步：比较与剪枝，各分枝的最优目标函数中若有小于z者，则剪掉这枝，即以后不再考虑了。若大于z ，且不符合整数条件，则重复第一步骤。一直到最后得到z* =z 为止。得最优整数解。2、 割平面法割平面法德基础仍然是用解线性规划得方法去解整数规划问题，首先不考虑变量Xi 是整数这一条件，但增加线性约束条件使得有缘可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平面，是切割后最终得到这样的可行域，它的一个有整数坐标的几点恰好是问题的最优解。现用下例来说明：例2增加松弛变量x3和x4 ，得到初始单纯形表和最优单纯形表如下图：Cj0100CBXBbX1X2X3X4初始计算表0x3603-32210010x4Z00100最终计算表0x113/210011/61/4-1/61/4x2Z-3/200-1/4-1/4此题的最优解为：X*= (1 , 3/2)，Z = 3/2，但不是整数最优解，引入割平面。以x2为源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为: 也即： 将 x3=6-3x1-2x2 , x4=3x1-2x2 ,带入得到等价的割平面条件： x2 1,见下图。 现将生成的割平面条件加入松弛变量，然后加到表中： 从而得到： 此时，X1 (2/3, 1), Z=1,仍不是整数解。继续