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

Study on Cutting Plane Method in Integer Programming

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

Cutting Plane Method （CPM for short） is one of the approaches adopted frequently for solving Integer Programming problems. Its basic idea is： the optimal solution is found firstly for the relaxed linear program problem in which integer conditions are cancelled from the original integer program problem. Moreover, if the solution＇s values are all integer, this solution is also optimal for the original problem. If the solution＇s values are not all integer, that is, there exists non-integer value for certain basis variable, an equality constraint is obtained from the corresponding row of the optimal simplex table, then according to this constraint, an cutting plane equation is constructed which is subsequently joined in the optimal simplex table.Further, by using dual simplex method in the table, a new optimal solution is obtained. Continuously constructing cutting plane equations, until an optimal solution in which all values are integer is derived. This paper mainly investigate the following four critical aspects： the first is to consider the process that： according to the equality constraint obtained from the optimal simplex table, by decomposing each coefficient into an integer and a nonnegative proper fraction, an inequality which is less than or equal to zero is obtained. The second is that： four methods are summarized, under which cutting plane equations are constructed. The third is to analyze the differentiation and relation among the four methods. The fourth is to study the geometry significance of CPM. From the analysis and study of these four aspects, CPM is thoroughly explored so that people can comprehensively understanding it.