基于特征列算法的0-1整数规划问题  

Solving 0-1 integer programming problem with the method of character sets

作　　者：邢振宇[1] 周楠[1] 李永彬[1] 

机构地区：[1]电子科技大学数学科学学院,成都611731

出　　处：《西南民族大学学报（自然科学版）》2011年第6期863-867,共5页Journal of Southwest Minzu University(Natural Science Edition)

基　　金：国家自然科学基金(10671134)

摘　　要：特征列方法又称吴方法,其在数学理论研究、理论物理等诸多领域都得到了广泛的应用,是计算机代数领域的一种重要的方法,它通过引入三角列和升列等概念来达到多项式方程组的消元求解目的.解整数规划问题即是先将问题转化为多项式方程组的求解问题,然后再求解此方程组的过程.本文探讨了特征列算法在整数规划中的0-1规划的应用.通过特征列消元算法理论的研究得出了一个基于吴方法的0-1规划问题的算法,并给出了利用数学软件maple的求解方法.Characteristic sets method which is also called Wu method,has been widely used in the mathematic theory research,theoretical physics and many other fields.It is an crucial approach in the field of computer algebra.It reaches the elimination purpose in order to solve the polynomial equation group problem by introducing the concept of triangular sets and rising sets.We should transform the integer programming problem into the problem polynomial equation group,then solve the equation of the process.This paper discusses the application of the characteristic sets method to solve the 0-1 integer programming problem.The studies of characteristic sets and the elimination algorithm theory conclude a method of solving 0-1 integer programming problem based on the theory of Wu method,and the approach of using mathematical software is conduced.

关 键 词：三角列 特征列 吴方法 0-1整数规划 

分 类 号：O189.11[理学—数学]