分支定界法和割平面法
在上学期课程中学习的线性规划问题中?/p>
有些最优解可能是分数或消失?/p>
但现实中某些
具体的问题,常要求最优解必须是整数,这样就有了对于整数规划的研究?/p>
整数规划有以下几种分类:
?/p>
1
)如果整数规划中所有的变量都限制为(非负)整数,就
称为纯整数规划或全整数规划;
?/p>
2
)如果仅一部分变量限制为整数,则称为混合整数规划;
?/p>
3
)整数规划还有一种特殊情形是
0-1
规划,他的变量取值仅限于
0
?/p>
1
。本文就适用?/p>
纯整数线性规划和混合整数线性规划求解的分支定界法和割平面法,做相应的介绍?/p>
一、分支定界法
在求解整数规划是?/p>
如果可行域是有界的,
首先容易想到的方法就是穷举变
量的所有可行的整数组合?/p>
然后比较它们的目标函数值以定出最优解?/p>
对于小型
问题,变量数量很少,可行的整数组合数也是很小时,这个方法是可行的,也?/p>
有效的。而对于大型的问题,可行的整数组合数很大时,这种方法就不可取了?/p>
所以我们的方法一般是仅检查可行的整数组合的一部分,就能定出最有的整数
解。分支定界法就是其中一个?/p>
分枝定界法可用于解纯整数或混合的整数规划问题?/p>
在二十世纪六十年代初
?/p>
Land Doig
?/p>
Dakin
等人提出。由于这方法灵活且便于用计算机求解,所以现
在它已是解整数规划的重要方法?/p>
目前已成功地应用于求解生产进度问题?/p>
旅行
推销员问题、工厂选址问题、背包问题及分配问题等?/p>
设有最大化的整数规划问?/p>
A
,与它相应的线性规划为问题
B
,从解问?/p>
B
开始,?/p>
其最优解不符?/p>
A
的整数条件,那么
B
的最优目标函数必?/p>
A
的最优目标函?/p>
z
*
的上界,
记作
z
?/p>
?/p>
A
的任意可行解的目标函数值将?/p>
z
*
的一个下?/p>
z
?/p>
分枝定界法就是将
B
的可?/p>
域分成子区域再求其最大值的方法。逐步减小
z
和增?/p>
z
,最终求?/p>
z
*
。现用下例来说明?/p>
?/p>
1
求解下述整数规划
2
1
90
40
Max
x
x
z
?/p>
?/p>
?/p>
?/p>
?
?/p>
?/p>
?/p>
?/p>
?/p>
?/p>
?/p>
且为整数
0
,
70
20
7
56
7
9
2
1
2
1
2
1
x
x
x
x
x
x
?/p>
?/p>
1
)先不考虑整数限制,即解相应的线性规?/p>
B
,得最优解为:
1
2
4.81,
1.82,
356
x
x
z
?/p>
?/p>
?/p>
可见它不符合整数条件?/p>
这时
z
是问?/p>
A
的最优目标函数?/p>
z
*
的上界,
记作
z
?/p>
?/p>
X
1
=0
?/p>
X
2
=0
显然是问?/p>
A
的一个整数可行解,这?/p>
0
?/p>
z
,是
z
*
的一个下界,记作
z
,即
0
?/p>
z
*
?/p>
356
?/p>
?/p>
2
)因?/p>
X
1
X
2
当前均为非整数,故不满足整数要求,任选一个进行分枝。设?/p>
X
1
进行
分枝,于是对原问题增加两个约束条件:
?/p>
?/p>
?/p>
?/p>
1
1
4.81
4,
4.81
1
5
x
x
?/p>
?/p>
?/p>
?/p>
?/p>
于是可将原问题分解为两个子问?/p>
B
1
?/p>
B
2
(即两支?/p>
,给每支增加一个约束条件并?/p>
影响问题
A
的可行域,不考虑整数条件解问?/p>
B
1
?/p>
B
2
,称此为第一次迭代。得到最优解