Of Groebner Base Theory And Its Applications In A Number Of Optimization Problems

The major task of the article is to study and discuss the theory and the application of Groebner basis.The article has four chapters. The first chapter is introduction of computer algebra. The author introduces the principle concepts in computational algebraic and computer algebra, formation of the theory of Groebner basis and common mathematical software in computer algebra—Maple. Chapter 2 gives an account of the reducing of polynomials and the reducing algorithm of Groebner basis. Chapter 3 tells about the application of Groebner basis in integer programming, then an algorithm about 0-1 programming is given and used in inference question of discrete mathematic: the propositional logic item is variable as the polynomial item, with the conditions that it is transformed into the equivalent of polynomials, then calculates Groebner basis, thus obtains the conclusion of the proposition. The last chapter is the application of Groebner basis. First, the theory of Groebner basis is to research the shortest path for two-way transportation routes of cities: for the feature of two-way line against city traffic, a kind of polynomial model for two-way line against city traffic is set up, then the first and the last traffic junctions can be found, after changing the traffic line map into the directed graph, the theory of Groebner basis is used to give the kind of algebra method which can be solved with computer. Another is about the gate assignment in airport: we set a kind of polynomial model after analyzing the relation among all of the flights, then compute reduced Groebner basis of ideal according with the knowledge about computer algebra, thus a new kind of solution for gate assignment is obtained.