学位论文 > 优秀研究生学位论文题录展示

整数规划算法效率的研究

作　者: 彭凤
导　师: 陈小松
学　校: 中南大学
专　业: 计算数学
关键词: 整数规划 Groebner基分枝定界法割平面法
分类号: O221.4
类　型: 硕士论文
年　份: 2010年
下　载: 138次
引　用: 0次
阅　读: 论文下载

内容摘要

本论文主要研究了几种整数线性规划的算法效率问题,全文共由三章组成。第一章对整数规划、Maple的使用、Groebner基的理论、分枝定界法和割平面法的历史背景及研究现状进行了概述,并将本文所做的工作进行了简单的介绍。第二章介绍了Groebner基的理论基础知识。给出了多项式项序、Groebner基、S-多项式等的定义,以及域上和环上的Groebner基的性质,进一步给出了计算Groebner基的方法,为第三章研究用Groebner基解整数规划问题提供了坚实的理论依据。第三章比较了用Groebner基解整数规划问题、分枝定界法和割平面法的算法效率。对整数规划问题利用第二章中给出的Groebner基理论基础知识给出了解决方法和步骤,并分别介绍了分枝定界法和割平面法,再结合具体实例对三种方法的算法时间和算法效率进行了比较。

全文目录

摘要  3-4
ABSTRACT  4-6
第一章绪论  6-11
  1.1 整数规划  6-7
  1.2 MAPLE简介  7-8
  1.3 GROEBNER基理论综述  8-9
  1.4 分枝定界法  9
  1.5 割平面法简介  9
  1.6 本文的主要工作  9-11
第二章预备知识  11-20
  2.1 环论基础  11-12
  2.2 GROEBNER基理论  12-20
    2.2.1 项序  12-14
    2.2.2 域上的Groebner基及其计算  14-17
    2.2.3 环上的Groebner基及其计算  17-20
第三章用GROEBNER基、分枝定界法和割平面法解整数规划  20-62
  3.1 用GROEBNER基解整数规划问题  20-23
  3.2 分枝定界法的步骤  23-24
  3.3 割平面法也是求解整数规划问题常用方法之一  24-62
    3.3.1 基本思路  24
    3.3.2 求解步骤  24-62
结论  62-63
参考文献  63-67
致谢  67-68
攻读硕士学位期间发表的论文  68

整数规划算法效率的研究

内容摘要

全文目录

相似论文