登录

割平面法

百科 > 决策方法 > 割平面法

1.割平面法概述

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

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

2.割平面法的基本步骤

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

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

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

3.割平面法的基本思路

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

评论  |   0条评论