整数规划问题中割平面法和分支定界法分别适用于什么类型

发布网友发布时间：2022-04-26 00:19

共1个回答

热心网友时间：2023-10-24 02:57

割平面法主要用于求解整数规划问题；分支定界法适用于求解纯整数规划。

割平面法主要用于求解整数规划问题的方法，1958年由美国格莫理提出。内容为先不考虑整数性约束，求解相应的线性规划问题。若线性规划问题的最优解恰好是整数解，则此解为整数规划问题的最优解。否则就增加一个新的约束条件，为割平面。

分支定界法为一种求解整数规划问题的最常用算法，这种方法不但可以求解纯整数规划，还可以求解混合整数规划问题，分支定界法为一种搜索与迭代的方法，选择不同的分支变量和子问题进行分支。对于两个变量的整数规划问题，使用网格的方法有时更为简单。

扩展资料：

整数规划问题的相关要求规定：

1、对于线性规划的日常应用问题而言，如果算法的实现良好，基于单纯形法和内点法的算法之间的效率没有太大差别，只有在超大型线性规划中，顶点几成天文数字，内点法有机会领先单形法。

2、单纯形算法利用多面体的顶点构造一个可能的解，然后沿着多面体的边走到目标函数值更高的另一个顶点，直至到达最优解为止。

参考资料来源：百度百科-割平面法

参考资料来源：百度百科-分支定界法