割平面法求解整数规划

Question

如题所述

Answer 1

割平面法求解整数规划如下：

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

割平面必须具有两条性质：从线性规划问题的可行域中至少割掉的非整数最优解；不割掉任何整数可行域，然后在缩小的可行域上继续解线性规划问题。重复以上做法，经有限次切割后，必可在缩小的可行域的一个整数极点上达到整数规划问题的最优解。

割平面法是1958年由美国学者高莫利(R.E.GoMory)提出的求解全整数规划的一种比较简单的方法。其基本思想和分枝定界法大致相同，即先不考虑变量的取整约束，用单纯形法求解相应的线性规划。

如果所得的最优解为整数解，那么它也是原整数规划问题的最优解3如果最优解不是整数解，那么分枝定界法是任取一个取分数值的变量Xk=bk将原整数规划分成两枝。

其实质是用两个垂直于坐标轴的平行平面Xk=[bk]和Xk=[bk]+1将原可行域R分成两个可行域R1和R2，并将两个平行平面之间的不含有整数解的那一部分可行域去掉，以缩小可行域。

切割平面法由RalphGomory在20世纪50年代提出，用于解决整数规划和混合整数规划问题。然而，当时的大多数专家，包括Gomory自己都认为由于数值上的不稳定性，这种方法没有实际运用价值；同时由于求解过程中需要进行过多轮的切割，该方法可能是无效的。