关于割平面法中Gomory约束构造的研究  

Research about the Construction of Gomory Constraint in Cutting Plane Method

作　　者：杨明歌[1] 蒋观敏[2] 常水珍[3] YANG Ming-ge JIANG Guan-min CHANG Shui-zhen(School of Management, Shanghai University, Shanghai 200444, China College of Mobile Telecommunications, Chongqing University of Posts and Telecom, Chongqing 401520 China College of Mathematics Science, Luoyang Normal University, Luoyang 471022, China)

机构地区：[1]上海大学管理学院,上海200444 [2]重庆邮电大学移通学院,重庆401520 [3]洛阳师范学院数学科学学院,河南洛阳471022

出　　处：《数学的实践与认识》2016年第22期195-201,共7页Mathematics in Practice and Theory

基　　金：国家自然科学基金(11301253;11301254);河南省高等学校重点科研项目(15A110036)

摘　　要：在使用割平面法求解整数规划时,寻找Gomory约束是其中最为关键的一步.一般地,选取非整数解变量中分数部分最大的一个基变量,写下相应行的约束.将这个约束等式中的系数进行整数和非负真分数的分解,再加上整数条件进行逼迫,得到一个小于等于0的不等式.从这个小于等于0的不等式出发,有五种方法构造Gomory约束.通过具体例子,详细讲解这五种方法,并进行比较,从而更加深刻地理解Gomory约束的构造,在以后的解题中可以灵活运用.When using cutting plane method for solving integer programming,finding Gomory constraint is one of the key steps.In general,we choose the basis variable whose fraction is lagest among all variables of the non-integer solution.Then write the constraint in the corresponding row.By decomposing each coefficient in this equality constraint into an integer and a nonnegative proper fraction,we use integer conditions for persecution,and obtain an inequality which is less than or equal to zero.According to this inequality which is less than or equal to zero,five methods are summarizd,under which Gomory constraints are constructed.We give an example to illustrate and compare this five methods.Thus the readers can deeply understand the construction of Gomory constraint,and flexibly use the cutting plane method in the after.

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

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