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