割平面法

出自 MBA智库百科(https://wiki.mbalib.com/)

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

　　割平面法的关键在于，如何构造切割不等式，使增加该约束后能达到真正的切割而且没有切割掉任何整数可行解。

　　(1)先不考虑变量的取整约束，用单纯形法求解相应的线性规划问题，如果该问题没有可行解或最优解已是整数则停止，否则转下步。

　　在求解相应的线性规划时，首先要将原问题的数学模型进行标准化。这里的“标准化”有两个含义：第一是将所有的不等式约束全部转化成等式约束，这是因为要采用单纯形表进行计算的缘故。第二是将整数规划中所有非整数系数全部转换成整数，这是出于构造“切割不等式”的需要。

　　(2)求一个“切割不等式”及添加到整数规划的约束条件中去，即对上述线性规划问题的可行域进行“切割”，然后返回步骤1。

　　用割平面法求解整数规划的基本思路是：先不考虑整数约束条件，求松弛问题的最优解，如果获得整数最优解，即为所求，运算停止．如果所得到最优解不满足整数约束条件，则在此非整数解的基础上增加新的约束条件重新求解．这个新增加的约束条件的作用就是去切割相应松弛问题的可行域，即割去松弛问题的部分非整数解(包括原已得到的非整数最优解)．而把所有的整数解都保留下来，故称新增加的约束条件为割平面．当经过多次切割后，就会使被切割后保留下来的可行域上有一个坐标均为整数的顶点，它恰好就是所求问题的整数最优解．即切割后所对应的松弛问题，与原整数规划问题具有相同的最优解。