邻域整点搜索法求解标准型纯整数规划  

Neighborhood integral point search method of solving standard form pure integer programming

作　　者：宛士春[1] 郭永发[2] 陶凤玲[3] 

机构地区：[1]青海大学经管系,青海西宁810016 [2]青海大学基础部,青海西宁810016 [3]青海大学水电系,青海西宁810016

出　　处：《武汉大学学报（工学版）》2004年第5期13-17,共5页Engineering Journal of Wuhan University

基　　金：教育部人文社会科学研究"十五规划"第一批研究项目(01JA630076).

摘　　要：从探索线性规划的优化机理入手,借鉴分枝定界法求解整数规划的基本原理和目标排序法求解0 1规划的思路,在完成一系列理论分析和证明之后,提出求解资源分配型整数规划的一种新方法———邻域整点搜索法.该方法是迄今为止求解整数规划的最为简捷有效的方法,是分枝定界法合乎逻辑的发展,也是用常规方法求解整数规划问题走向成熟的标志.使用该法,既可以求解纯整数规划,也可以求解混合整数规划问题,对于求解大规模整数规划问题具有无可比拟的优越性.Through anatomizing optimization mechanism of linear programming, and based on basic principle of solving integer programming by branch-bound method, and thought of solving 0-1 programming by objective ordering; a new method, which is most shortcut and efficient so far after finishing a series of theory analysis and proof, is put forward. This method is named neighborhood integral point search method. It is tally with logical development of branch-bound method, also is a mature mark in solving integer programming by analytic method. Pure integer programming and mixed integer programming can be solved by this method. It is the most efficient method to solve a scale integer programming.

关 键 词：整数规划 松弛问题 单纯形法 分枝界定法 邻域 

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