简答题

简述分枝定界法的基本步骤。

正确答案

分枝定界法是先求解整数规划的线性规划问题。如果其最优解不符合整数条件,则求出整数规划的上下界,用增加约束条件的办法,把相应的线性规划的可行域分成子区域(称为分枝),再求解这些子区域上的线性规划问题,不断缩小整数规划的上下界的距离,最后得整数规划的最优解。
基本思路:
1、先求出线性规划的解。
2、确定整数规划的最优目标函数值z*初始上界和下界z。
3、将一个线性规划问题分为两枝,并求解。
4、修改最优目标函数上、下界。
5、比较与剪枝:各分枝的目标函数值中,若有小于。Z者,则剪掉此枝,表明此子问题已经探清,不必再分枝了;否则继续分枝。
6、如此反复进行,直到得到Z=Z*为止,即得最优解X*

答案解析

相似试题
  • 分枝定界法和割平面法的基础都是用()求解整数规划。

    填空题查看答案

  • 分枝定界法一般每次分枝数量为()

    填空题查看答案

  • 求解纯整数规划的方法是()。求解混合整数规划的方法是分枝定界法。

    填空题查看答案

  • 在下列整数规划问题中,分枝定界法和割平面法都可以采用的是()。

    单选题查看答案

  • 用分枝定界法求极大化的整数规划问题时,任何一个可行解的目标函数值是该问题目标函数值的()

    填空题查看答案

  • 分枝定界法中() a.最大值问题的目标值是各分枝的下界; b.最大值问题的目标值是各分枝的上界; c.最小值问题的目标值是各分枝的上界; d.最小值问题的目标值是各分枝的下界; e.以上结论都不对

    单选题查看答案

  • 用分支定界法求解一个极大化的整数规划问题时,任何一个可行解的目标函数值是该问题的下界。

    判断题查看答案

  • 简述表上作业法的基本步骤。

    简答题查看答案

  • 群体继代选育法的基本步骤有哪些?

    简答题查看答案