目标等值面切割定界与割平面法结合求解整数规划  

Combining Cutting-and-bound Principle of Objective Equivalent Plane with the Cutting Plane Method for Solving Integer Linear Programming

作　　者：高培旺[1] 唐忠旺[2] 

机构地区：[1]中南大学铁道校区数学科学与计算技术学院,湖南长沙410075 [2]长沙电力学院,湖南长沙410077

出　　处：《广西师范学院学报（自然科学版）》2003年第1期12-16,共5页Journal of Guangxi Teachers Education University(Natural Science Edition)

摘　　要：把目标等值面切割定界原理与Gomory的割平面法结合起来求解整数线性规划 (ILP)问题 .首先通过目标函数等值面的平行移动来切去 (LP)可行域中含其非整数最优解但不含 (ILP)可行解的“无用部分” ;然后 ,应用Gomory的割平面在通过 (ILP)最优解的目标等值面上切割其最优解 .This paper combines a cutting_and_bound principle of objective equivalent plane with the Gomory cutting plane method for solving integer linear programming problems.In the algorithm presented,the 'insignificant parts' of the feasible domain of (LP) associated with (ILP) would be cut off by decreasing the optimal objective value of the (LP),and simultaneously,the corresponding objective value is taken as an upper bound to the solution of (ILP).Finally,the solutions to(ILP) would be obtained on an objective equivalent plane through the cutting of the Gomory's cutting planes.

关 键 词：整数线性规划 目标等值面切割定界原理 割平面法 目标函数 最优解 

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