在求解整数线性规划问题的分枝定界算法中,如何判定子问题已经完全探明
发布网友
发布时间：2023-04-29 23:43
共1个回答
热心网友
时间：2023-10-05 11:53
分枝定界法是由学者查理德·卡普（Richard M.Karp）在20世纪60年代发明，该方法把问题的可行解展开如树的分枝，再经由各个分枝中寻找最佳解。
分枝定界法也能够使用在混合整数规划问题上，其为一种系统化的解法，一般用单纯形法解出线性规划最佳解后，将非整数值的决策变量分割成最接近的两个整数，加入原问题中，形成两个子问题(或分枝)分别求解，如此便可求得目标函数的上限（上界）或下限（下界），从而寻得最佳解。
分枝定界法求解步骤如下所述：
(1) 如果问题的目标为最小化，则设定最优解的值Z=∞；
(2) 根据分枝法则（Branching rule），从尚未被遍历（Fathomed）且需要变为整数的节点（局部解）中选择一个节点，并在此节点的下一阶层中分为几个新的分支。一般分为两个新的分支，分别是对该节点的其中一个决策变量进行向上取整和向下取整；
(3) 对每一个新分枝出来的节点验证是否满足定义域，若满足，则可以继续进行分支，否则不再考虑该分支，计算每一个新分枝出来的节点的下限值（Lower bound，LB）；
(4) 判断当前分支的下限值是否小于Z值，若前者较小，则需更新Z值，以此分支为可行解的值，否则此节点不可能包含最优解；
(5) 判断是否仍有尚未被遍历且需要变为整数的节点，如果有，则进行步骤（2），如果没有，则算法停止，并得到最优解。
