分支定界法(branch and bound)是一种求解整数规划问题的最常用算法。这种方法不但可以求解纯整数规划,还可以求解混合整数规划问题。请简述使用分支定界法求解整数规划问题的步骤是什么?
第1步:放宽或取消原问题的某些约束条件,如求整数解的条件。如果这时求出的最优解是原问题的可行解,那么这个解就是原问题的最优解,计算结束。否则这个解的目标函数值是原问题的最优解的上界。第2步:将放宽了某些约束条件的替代问题分成若干子问题,要求各子问题的解集合的并集要包含原问题的所有可行解,然后对每个子问题求最优解。这些子问题的最优解中的最优者若是原问题的可行解,则它就是原问题的最优解,计算结束。否则它的目标函数值就是原问题的一个新的上界。另外,各子问题的最优解中,若有原问题的可行解的,选这些可行解的最大目标函数值,它就是原问题的最优解的一个下界。第3步:对最优解的目标函数值已小于这个下界的问题,其可行解中必无原问题的最优解,可以放弃。对最优解的目标函数值大于这个下界的子问题,都先保留下来,进入第4步。第4步:在保留下的所有子问题中,选出最优解的目标函数值最大的一个,重复第1步和第2步。如果已经找到该子问题的最优可行解,那么其目标函数值与前面保留的其他问题在内的所有子问题的可行解中目标函数值最大者,将它作为新的下界,重复第3步,直到求出最优解。
举一反三
内容
- 0
分枝定界法是求解整数规划的一种常用的有效的方法,它既能解决纯整数规划的问题,又能解决混合整数规划的问题。
- 1
使用分支定界法求解整数规划问题最优解时，只要所得分支线性规划问题最优解不为整数，就需要进一步分支。
- 2
【多选题】以下关于整数规划的命题中正确的是()。 A. 用分枝定界法求解整数规划问题时首先要求解放松整数要求的线性规划松弛问题 B. 整数规划解的数目比线性规划少得多,但整数规划问题也可能有无数多个可行解 C. 求解整数规划问题要比求解线性规划问题难得多 D. 分枝定界方法不能求解有连续变量的混合整数规划问题
- 3
分支定界法求解一个极大化整数规划问题时，松弛问题的目标函数值是该整数规划问题的下界。
- 4
利用分支定界法求解整数规划问题时，只要某分支出现整数解，即得到最优解。