什么时候应该使用割平面法

问题描述

精选答案

割平面法是1958年由美国学者高莫利(R.E.GoMory)提出的求解全整数规划的一种比较简单的方法。其基本思想和分枝定界法大致相同，即先不考虑变量的取整约束，用单纯形法求解相应的线性规划。如果所得的最优解为整数解，那么它也是原整数规划问题的最优解3如果最优解不是整数解，那么分枝定界法是任取一个取分数值的变量X_k=b_k将原整数规划分成两枝，其实质是用两个垂直于坐标轴的平行平面X_k=[b_k]和X_k=[b_k]+1将原可行域R分成两个可行域R_1和R_2，并将两个平行平面之间的不合有整数解的那一部分可行域去掉，以缩小可行域。而割平面法是用一张平面(不一定垂直于某个坐标轴)，将含有最优解的点但不含任何整数可行解的那一部分可行域切割掉，这只要在原整数规划基础上增加适当的线性不等式约束(我们称之为切割不等式；当切割不等式取等号时，叫做割平面)。然后继续解这个新的整数规划，再在这个新的整数规划的基础上增加适当的线性不等式约束，直至求得最优整数解为止。也就是说，通过构造一系列平面来切割掉不含有任何整数可行解的部分，最终获得一个具有整数坐标的顶点的可行域，而该顶点恰好是原整数规划的最优解。

其他回答

考研大师兄

割平面法通常用于求解线性规划问题，当约束条件是线性的，且需要求解的目标函数是线性的，就可以使用割平面法。这种方法通过将线性规划问题转换为一个或多个半平面约束条件，再逐个加入约束条件来逼近最优解，以达到求解线性规划问题的目的。这种方法通常用于复杂的、高维的线性规划问题。