文档介绍：第二节分支界定法
(Branch and Bound Method)
如果通过对全体可行的整数解逐个比较优劣,
得到最优解的方法,
称为完全枚举法(穷举法)。
但在解的个数很多时,这往往是不可能的。
如果能通过仅对部分可行整数解的讨论,
就得到原问题的最优解,
称为部分枚举法或隐枚举法。
分枝定界法就是一种隐枚举法,
这是一种应用很广的求解方法。
分枝定界法可以用来求解纯整数规划和混合整数规划,它是整数规划的常用解法。
算法的依据:
“对于目标函数值来讲,
整数规划的最优解不会更优于相应的线性规划问题
的最优解”。
具体说就是,对极大化问题,
与整数规划问题相应的线性规划问题(即松弛问题)
的目标函数值,
是该整数规划问题目标函数的上界;
任何满足整数条件的可行解的目标函数值将是其下界。
下面给出分枝定界法具体作法
第一步:
具体作法是:
首先,删去整数条件,
把原整数规划化成相应线性规划。
其次,求解相应线性规划。
主要特征就是放宽条件。
最后,①如果相应线性规划没有可行解,
则原整数规划也没有可行解。则停止;
②如果相应线性规划有最优解,
且符合原整数规划问题的整数条件,
则这个最优解也是原整数规划的最优解,
那么整个计算过程结束;
③如果相应线性规划有最优解,
但不符合原整数规划问题的整数条件,
则这个最优解不是原整数规划的最优解,
记此最优值为原整数规划问题Z*的上界,
然后, 用观察法求出下界,
转入第二步。
主要特征是分支。
具体作法:
从相应线性规划的最优解中,
任意选择一个不满足原整数规划整数条件
的决策变量xj=bj
以使相应线性规划增加一个约束条件;
xj小于bj的最大整数(或xj大于bj的最小整数),
因而得到两个新的线性规划称为分支,
也称为后继问题。
列出两分支各自的数学模型,
计算每支的最优解和最优值。
第二步:
经过分支之后,就有如下结论:
分支后并没有减少整数解,
故原整数规划的可行域真包含于两支可行域的并集。
原整数规划的最优解不大于两支最优值的最大值。
主要特征就是定界.
具体作法:
以每个后继问题为一分支标明求解的结果,
与其他问题的解的结果中,
找出最优目标函数值最大者作为新的上界;
从已符合整数条件的各分支中,
找出目标函数值为最大者作为新的下界z,
若无可行解, z=0
第三步:
z
第四步:比较与剪支:
各分支的最优目标函数中若有小于 z 者,
则剪掉这支,即以后不再考虑了。
若有大于z ,但不符合整数条件,则继续分支,
一直到最后得到z*=z为止,
得最优整数解xj*,j=1,…,n
用分支定界法可解纯整数线性规划问题和混合整数线性规划问题。它比穷举法优越。
因为它仅在一部分可行解的整数解中寻求最优解,
计算量比穷举法小。
若变量数目很大,其计算工作量也是相当可观的。
解:它属于最大化纯整数规划。为便于叙述,我们将其记作A。现在利用分枝定界法求解之。
例: 利用分枝定界法求解:
A
:由A得到相应线性规划,记作B。