分支定界算法是求组合优化问题最优解的常用方法,它实际上是一种隐枚举技术:首先, FBMH1608HM151-T它生成一个根节点,再由根节点逐层向下产生新的节点,每个节点代表一个部分解并根据问题性质赋予下界值,最终形成一个枚举树,问题的所有可能解只能在枚举树的最底层节点(称为叶节点)获得;然后结合各节点的下界值,采用一定的搜索策略对枚举树进行搜索,在搜索过程中动态更新当前问题的最优解,在搜索完所有节点后得到问题最优解。

   由上可知,分支定界算法求解步骤如下。

   第一步:不考虑整数约束,用单纯形法求解整数规划问题相应的线性规划问题。第二步:检查判别。

   (1)若线性规划问题无解,则原问题也无可行解。

   (2)若线性规划问题有最优解,则检查其解是否满足整数条件,若满足,则此最优解也就是原问题的最优解,否则转入第三步。

第三步:在相应线规划的最优解中,任选一个不符合整数约束的变量。将其分别取灼≤3(小于勿最大整数),≥3(大于勿最小整数),分别加入相应的线性规划中分解成两个线性规划子问题。

   第四步:再用单纯形法求解第三步的子问题。

   第五步:重复步骤第二步至第四步,直到得到整数解为止。

   第六步:对子问题己得到整数最优解后,其他子问题是否要继续求   解,则由目标函数的大小来确定。若其他问题均劣于已取得的解,则均可舍去,不再进行分支求解。