求解整数规划的割平面法的研究  

Research about Cutting Plane Method for Solving Integer Programming

作　　者：杨明歌[1] 常水珍[1] 

机构地区：[1]洛阳师范学院数学科学学院,河南洛阳471022

出　　处：《洛阳师范学院学报》2014年第5期1-4,12,共5页Journal of Luoyang Normal University

基　　金：国家自然科学基金数学天元基金项目(11226228);河南省基础与前沿技术研究计划项目(122300410256);河南省教育厅自然科学研究计划项目(2011B110025);洛阳师范学院教学改革项目(2010-025)

摘　　要：在使用割平面法求解整数规划时,寻找Gomory约束是其中最为关键的一步.一般地,选取非整数解变量中分数部分最大的一个基变量,写下相应行的约束,由此推导出Gomory约束.本文主要讨论当非整数解变量中分数部分最大的基变量有两个以上时,如何通过比较选取切割条件较强的Gomory约束,以减少切割次数和运算量,较快地找到最优解.When using cutting plane method for solving integer programming, of the key steps. In general, we choose the basis variable whose fraction is largest finding Gomory constraint is one among all variables of the non- integer solution. Then write the equality constraint in the corresponding row, and derive Gomory constraint. In this paper, we mainly discuss the case that there are more than two basis variables whose fractions are variables of the non-integer solution. By comparison we choose ting and the amount of computation can be lessened. We can largest among all stronger Gomory constraint. Thus the number of cut- find the optimal solution more quickly.

关 键 词：整数规划 割平面法 Gomory约束 对偶单纯形法 

分 类 号：O221.4[理学—运筹学与控制论]