割平面法-经典

《割平面法-经典》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、解纯整数规划的割平面法割平面法的基础仍然是用解LP的方法去解整数规划问题.其基本的步骤是:(1)把约束条件中所有的系数整数化;(2)不考虑决策变量的整数约束条件,增加线性约束条件(cuttingplane),使得原可行域中切割掉一部分,这部分只包含非整数部分,但没有切割掉任何整数可行解;(3)求解上面的LP问题,若所得的最优解为整数,则该解也是原整数规划问题的最优解;否则,转(2)割平面法的内涵:通过找适当的割平面,使得切割后最终得到这样的可行域(不一定一次性得到),它的一个有整数坐标的顶点恰好是问题的最优解.－

2、Gomory割平面法例:求解解(一)、求解松驰问题)相应的松驰问题为:松驰问题标准化,得:列单纯形表得:(初始单纯形表)cj1100CBXBbx1x2x3x40x31-11100x44310101100(最终单纯形表)cj1100CBXBbx1x2x3x41x13/410-1/41/41x27/4013/41/400-1/2-1/2x20.511x1o0.5RA(3/4,7/4)C(1,1)R`x20.511x1o0.5A(3/4,7/4)C(1,1)(二)确定割平面由最终单纯表可得如下的关系式:将系数和常数项均

3、分解成整数与真分数之和移项,以上两式变为：由于x1,x2,x3,x4均为非负整数,显然,上面两式的右边必小于0,从而有整数约束条件可由下的不等式所替代.上式就是所要求的一个切割方程(割平面).引入松驰变量x5,从而可得到一等式约束条件,将所得等式约束加入到原标准化的松驰问题之中,得到如下新的松驰问题.将所得等式约束加入到原标准化的松驰问题的最优单纯形表之中,得cj11000CBXBbx1x2x3x4x51x13/410-1/41/401x27/4013/41/400x5-300-3-1100-1/2-1/20由对

4、偶单纯形法,x5为换出变量,x3为换入变量,得cj11000CBXBbx1x2x3x4x51x111001/31/121x2101001/40x31001-1-1/3000-1/2-1/6显然,上表为最优单纯形表,且x1,x2的值已为整数,从而知原IP问题的最优解为(1,1),最优值为2问题的关键是求切割方程求切割方程的步骤归纳为:(1)令xi是相应的松驰问题最优解中为分数值的一个基变量,由单纯形表的最终表得到(2)将与aik都分解成整数部分N(不超过　的最大整数)与非负真分数f之和,即从而得到(3)由变量(包括

5、松驰变量)的非负整数条件,从而可得上式即为所要求的切割方程割平面法是Gomory在1958年提出的,当时引起了人们广泛注意,但至今完全用它解决实际问题仍是少数,因为其收敛性很慢.但若下其它方法(如分枝定界法)配合使用,也是有效的.