分支定界法和割平面法

分支定界法和割平面法
在上学期课程中学习的线性规划问题中，有些最优解可能是分数或消失，但现实中某些具体的问题，常要求最优解必须是整数，这样就有了对于整数规划的研究。

整数规划有以下几种分类：（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 求解下述整数规划 219040Max
x x z +=
⎪⎩⎪
⎨⎧≥≥+≤+且为整数0,7020756792
12121x x x x x x
解 （1）先不考虑整数限制，即解相应的线性规划B ，得最优解为：
124.81, 1.82,356
x x z ===
可见它不符合整数条件。

这时z 是问题A 的最优目标函数值z *的上界，记作z 。

而X 1=0，X 2=0显然是问题A 的一个整数可行解，这时0=z ，是z * 的一个下界，记作z ，即0≤z *≤356 。

（2）因为X 1X 2当前均为非整数，故不满足整数要求，任选一个进行分枝。

设选X 1进行分枝，于是对原问题增加两个约束条件：
[][]114.814, 4.8115
x x ≤=≥+=
于是可将原问题分解为两个子问题B 1和B 2（即两支），给每支增加一个约束条件并不影响问题A 的可行域，不考虑整数条件解问题B 1和 B 2 ，称此为第一次迭代。

得到最优解
为：
显然没有得到全部变量时整数的解，于是再定界：3490*
≤≤z 。

（3）继续对问题B 1和B 2因Z 1＞Z 2 ，故先分解B 1为两支，增加条件X 2≤2，称为
B 3；增加条件X 2≥3，称为B 4。

再舍去X 2＞2与X 3＜3之间的可行域，再进行第二次迭代。

解题过程如图：
z * =340=z
由图可知，B 3的解已都是整数，他的目标函数值Z 3 =340，可取为z ，而它大于Z 4 =327。

所以，再分解B 4已无必要。

而问题B 2的Z 2 =341，所以z * 可能在340和341之间有整数解。

于是对B 2分解，得问题B 5，既非整数解且Z 5 =308＜Z 3，问题B 6为无可行解。

于是有
z * =z 3=z=340
问题B 3的解X 1=4.00，X 2=2.00为最优整数解。

从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：
开始，将要求解的整数规划问题称为问题A ，将与它相应的线性规划问题称为问题B 。

（1）解问题B 可能得到以下情况之一：
（a ）B 没有可行解，这时A 也没有可行解，则停止．
（b ）B 有最优解，并符合问题A 的整数条件，B 的最优解即为A 的最优解，则停止。

（c ）B 有最优解，但不符合问题A 的整数条件，记它的目标函数值为z 。

（2）用观察法找问题A 的一个整数可行解，一般可取n j x j ,,1,0 ==，试探，求得其目标函数值，并记作z 。

以z *表示问题A 的最优目标函数值；这时有 z z z ≤≤*
进行迭代。

第一步：分枝，在B 的最优解中任选一个不符合整数条件的变量x j ，其值为b j ，以［b j ］表示小于 b j 的最大整数。

构造两个约束条件
][j j b x ≤ 和 1][+≥j j b x
将这两个约束条件，分别加入问题B ，求两个后继规划问题B 1和B 2。

不考虑整数条件求解这两个后继问题。

定界，以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界z 。

从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界z ，若无作用z = 0。

第二步：比较与剪枝，各分枝的最优目标函数中若有小于z 者，则剪掉这枝，即以后不再考虑了。

若大于z ，且不符合整数条件，则重复第一步骤。

一直到最后得到z * =z 为止。

得最优整数解n j x j ,,1,* =。

二、割平面法
割平面法德基础仍然是用解线性规划得方法去解整数规划问题，首先不考虑变量X i 是整数这一条件，但增加线性约束条件使得有缘可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。

这个方法就是指出怎样找到适当的割平面，是切割后最终得到这样的可行域，它的一个有整数坐标的几点恰好是问题的最优解。

现用下例来说明：
例2
增加松弛变量x 3和x 4 ，得到初始单纯形表和最优单纯形表如下图：
⎪⎩⎪
⎨⎧≥≤+-≤+=且为整数
0,023623 max 2121212
x x x x x x x Z
C j 0 1 0 0 C B
X B b X 1 X 2 X 3 X 4 初始 计 算表 0 x 3 6 0 3 -3 2 2 1 0 0 1 0
x 4
－Z 0 0 1 0 0 最终 计 算表
0 x 1 1 3/2 1 0 0 1 1/6 1/4 -1/6 1/4
x 2 －Z
-3/2
-1/4
-1/4
此题的最优解为：X*= (1 , 3/2)，Z = 3/2，但不是整数最优解，引入割平面。

以x 2为源行生成割平面，由于 1/4=0+1/4, 3/2=1+1/2, 我们已将所需要的数分解为整数和分数，所以，生成割平面的条件为: 也即：
将 x 3=6-3x 1-2x 2 , x 4=3x 1-2x 2 ,带入
得到等价的割平面条件： x 2≤ 1,见下图。

现将生成的割平面条件加入松弛变量，然后加到表中：
21
414143≥
+x x )4
1
41(21121141412
3
4141432432432x x x x x x x x x +-=-+=++=++0
)4
1
41(21 43≤+-∴x x 2141
41143-=+--s x x 2
1414143≥+x x
从而得到：
此时，X1 ＝(2/3, 1), Z=1,仍不是整数解。

继续以x1为源行生成割平面，其条件为：
用上表的约束解出x4 和s1 ，将它们带入上式得到等价的割平面条件：x1 ≥ x2 ，见图：
将生成的割平面条件加入松弛变量，然后加到表中：
得到：
至此得到最优表，其最优解为 X*= (1 , 1) , Z = 1, 这也是原问题的最优解。

32323214≥
+s x 323232214-
=+--s s x。