文档介绍：该【分支定界法和割平面法 】是由【海洋里徜徉知识】上传分享，文档一共【5】页，该文档可以免费在线阅读，需要了解更多关于【分支定界法和割平面法 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。(完整word)分支定界法和割平面法
(完整word)分支定界法和割平面法
(完整word)分支定界法和割平面法
分支定界法和割平面法
在上学期课程中学习的线性规划问题中，有些最优解可能是分数或消失，但现实中某些具体的问题，常要求最优解必须是整数，这样就有了对于整数规划的研究.
整数规划有以下几种分类：（1）如果整数规划中所有的变量都限制为（非负）整数，就称为纯整数规划或全整数规划；（2)如果仅一部分变量限制为整数，则称为混合整数规划；（3）整数规划还有一种特殊情形是0—1规划，他的变量取值仅限于0或1。本文就适用于纯整数线性规划和混合整数线性规划求解的分支定界法和割平面法，做相应的介绍。
分支定界法
在求解整数规划是，如果可行域是有界的，首先容易想到的方法就是穷举变量的所有可行的整数组合，然后比较它们的目标函数值以定出最优解。对于小型问题，变量数量很少,可行的整数组合数也是很小时，这个方法是可行的，,可行的整数组合数很大时，这种方法就不可取了。所以我们的方法一般是仅检查可行的整数组合的一部分，就能定出最有的整数解。分支定界法就是其中一个。
分枝定界法可用于解纯整数或混合的整数规划问题。在二十世纪六十年代初由Land Doig和Dakin等人提出。由于这方法灵活且便于用计算机求解，、旅行推销员问题、工厂选址问题、背包问题及分配问题等.
设有最大化的整数规划问题，与它相应的线性规划为问题，从解问题开始，若其最优解不符合的整数条件，那么的最优目标函数必是的最优目标函数z＊的上界,记作；而的任意可行解的目标函数值将是z*的一个下界z。,最终求到z＊。现用下例来说明:
例1 求解下述整数规划
解 （1)先不考虑整数限制，即解相应的线性规划，得最优解为：
可见它不符合整数条件。这时是问题A的最优目标函数值z*的上界，记作。而X1=0，X2=0显然是问题A的一个整数可行解，这时，是z* 的一个下界,记作z，即0≤z*≤356 。
(2）因为X1X2当前均为非整数，故不满足整数要求,任选一个进行分枝。设选X1进行分枝,于是对原问题增加两个约束条件:
(完整word)分支定界法和割平面法
(完整word)分支定界法和割平面法
(完整word)分支定界法和割平面法
于是可将原问题分解为两个子问题B1和B2（即两支）,给每支增加一个约束条件并不影响问题A的可行域,不考虑整数条件解问题B1和 B2 ,称此为第一次迭代。得到最优解为:
问题B1
问题B2
Z1=349
X1=4。00
X2=2。10
Z2=341
X1=
X2=1。57
显然没有得到全部变量时整数的解，于是再定界：。
问题B
X1=
X2=
Z =356
(3）继续对问题B1和B2因Z1＞Z2 ，故先分解B1为两支，增加条件X2≤2，称为B3;增加条件X2≥3，称为B4。再舍去X2＞2与X3＜3之间的可行域，再进行第二次迭代。解题过程如图：
问题B6
无可行解
问题B5
X1=
X2=
Z5 =308
问题B4
X1=1。42
X2=3。00
Z4 =327
问题B3
X1=
X2=2。00
Z3 =340
问题B1
X1=4。00
X2=
Z1 =349
=356，z = 0
X1≤4 X2≥5
问题B2
X1=
X2=1。57
Z2 =341
=349,z = 0
X2≤2 X2≥3
=341，z = 340
X2≤1 X2≥2
z* =340=z
由图可知，B3的解已都是整数，他的目标函数值Z3 =340，可取为z ，而它大于Z4 =，再分解B4已无必要。而问题B2的Z2 =341，所以z* ,得问题B5，既非整数解且Z5 =308＜Z3，问题B6为无可行解。于是有
z＊ =z3=z=340
问题B3的解X1=,X2=。
(完整word)分支定界法和割平面法
(完整word)分支定界法和割平面法
(完整word)分支定界法和割平面法
从以上解题过程可得用分枝定界法求解整数规划（最大化）问题的步骤为：
开始，将要求解的整数规划问题称为问题,将与它相应的线性规划问题称为问题.
(1）解问题可能得到以下情况之一：
（a）没有可行解,这时也没有可行解，则停止．
（b)有最优解，并符合问题的整数条件，B的最优解即为的最优解，则停止。
（c）有最优解，但不符合问题的整数条件，记它的目标函数值为.
(2）用观察法找问题的一个整数可行解，一般可取,试探，求得其目标函数值，＊表示问题的最优目标函数值；这时有
进行迭代.
第一步：分枝，在的最优解中任选一个不符合整数条件的变量xj，其值为bj，以［bj］表示小于 bj 的最大整数。构造两个约束条件
和
将这两个约束条件,分别加入问题B，求两个后继规划问题B1和B2。不考虑整数条件求解这两个后继问题。
定界,以每个后继问题为一分枝标明求解的结果，与其它问题的解的结果中，找出最优目标函数值最大者作为新的上界。从已符合整数条件的各分支中，找出目标函数值为最大者作为新的下界z ，若无作用z = 0.
第二步：比较与剪枝，各分枝的最优目标函数中若有小于z者，则剪掉这枝， ,且不符合整数条件,则重复第一步骤。一直到最后得到z* =z 为止。得最优整数解。
割平面法
割平面法德基础仍然是用解线性规划得方法去解整数规划问题,首先不考虑变量Xi 是整数这一条件,但增加线性约束条件使得有缘可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平面，是切割后最终得到这样的可行域，它的一个有整数坐标的几点恰好是问题的最优解。现用下例来说明：
例2
增加松弛变量x3和x4 ，得到初始单纯形表和最优单纯形表如下图：
Cj
0
1
0
0
CB
XB
b
X1
X2
X3
X4
初始
计
算表
0
x3
6
0
3
-3
2
2
1
0
0
1
0
x4
－Z
0
0
1
0
0
最终
0
x1
1
1
0
1/6
—1/6
(完整word)分支定界法和割平面法
(完整word)分支定界法和割平面法
(完整word)分支定界法和割平面法
计
算表
3/2
0
1
1/4
1/4
x2
－Z
-3/2
0
0
-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，仍不是整数解。继续以x1为源行生成割平面，其条件为：
用上表的约束解出x4 和s1 ，将它们带入上式得到等价的割平面条件：x1 ≥ x2 ,见图：
(完整word)分支定界法和割平面法
(完整word)分支定界法和割平面法
(完整word)分支定界法和割平面法
将生成的割平面条件加入松弛变量，然后加到表中：
得到：
至此得到最优表，其最优解为 X＊= (1 ， 1） , Z = 1， 这也是原问题的最优解。