Groebner基理论及其在一些优化问题上的应用

作     者：朱玉莲 

作者单位：中南大学 

学位级别：硕士

导师姓名：陈小松

授予年度：2007年

学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学] 

主      题：Groebner基 约化 逻辑命题 最短路径 停机位分配 

摘      要：论文的主要工作是研究和讨论Groebner基理论及其应用。 全文由四章组成,第一章是关于计算代数的综述,介绍了计算代数及计算机代数中的相关概念、Groebner基理论的形成及常用的数学软件—Maple。第二章阐述多项式约化问题并介绍了Groebner基约化算法。第三章介绍了Groebner基理论在整数规划中的应用,得到一个关于0-1规划的算法,并应用到离散数学中的一些逻辑推理问题上:将逻辑命题中的变项看成多项式的项,根据题设条件将它转化成相应的多项式,然后计算Groebner基,从而得到问题的结论。文章第四章是关于Groebner基的应用。一是应用Groebner基求城市交通双向路线的最短路径:针对城市交通路线双向这一特征,先找到起始点和目标点必须要经过的第一个路口和最后一个路口,然后转化成有向图,建立双向路线的多项式模型,并应用Groebner基理论对该模型给出了一种可用计算机计算求解的代数方法;另一个则是运用Groebner基和约化理论对机场分配问题进行讨论:通过分析各个航班使用停机位的时间上的冲突情况,建立多项式模型,然后运用计算代数方面的知识,计算理想的Groebner基,得到了一种求机场停机位分配的方法。