解ILP的割平面法中导出方程的选取准则

解整数规划问题的割平面法在应用时,必须要选出合适的割平面方程,才能使收敛的速度快,迭代的次数少.通过对割平面法的一般性推导,指出最优值减少的越多,则割平面的约束能力就越强,从而在尽量少的迭代次数下得到最优整数解,并给出了割平面方程选取准则的具体计算方法.

整数规划中割平面法的研究

割平面法是求解整数规划问题常用方法之一.用割平面法求解整数规划的基本思路是:先用单纯形表格方法去求解不考虑整数约束条件的松弛问题的最优解,如果获得的最优解的值都是整数,即为所求,运算停止.如果所得最优解不完全是整数,即松弛问题最优解中存在某个基变量为非整数值时,就从最优表中提取出关于这个基变量的约束等式,再从这个约束式出发构造一个割平面方程加入最优表中,再求出新的最优解,这样不断重复的构造割平面方程,直到找到整数解为止.主要研究以下四个关键点:一是研究从最优表中提取出的、关于基变量的约束等式出发,通过将式中的系数进行整数和非负真分数的分解,从而得到一个小于等于0的另外一个不等式的推导过程;二是总结出从小于等于0的那个约束不等式出发构造割平面方程的四种方法;三是分析构造割平面方程的这四种方法相互之间的区别和联系;四是探讨割平面法的几何意义.通过对这四个方面的分析和研究,对割平面法进行透彻的剖析,使读者能够全面把握割平面法.