分支定界法的基本步骤

2021年10月6日17:19:41分支定界法的基本步骤已关闭评论

分支定界法的一般步骤如下:

①首先不考虑整数条件,求解整数规划相应的线性规划问题。若相应的线性规划问题没有可行解,停止计算,这时原整数规划也没有可行解。

②定界过程。对于极大化的整数规划问题,当前所有未分支子问题中最大的目标函数值为整数规划问题上界;在满足整数约束的子问题的解中,最大的目标函数值为整数规划问题的下界。当上下界相同时,则已得最优解;否则,转入“剪枝”过程。

③“剪枝”过程。在下述情况下剪除这些分支:

若某一子问题相应的线性规划问题无可行解;

在分支过程中,求解某一线性规划所得到的目标函数值 不优于现有下界。

④分支过程。当有多个待求分支时,应先选取目标函数值最优的一支继续分。选取一个不符合整数条件的变量 作为分支变量,若 的值是 ,构造两个新的约束条件: ≤[ ]或 ≥[ ] +1,分别并入相应的数学模型中,构成两个子问题。对任一个子问题,转步骤①。

  • 版权声明:本篇文章(包括图片)来自网络,由程序自动采集,著作权(版权)归原作者所有,如有侵权联系我们删除,联系方式(QQ:452038415)。