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

运输问题的新算法

作　者: 刘徽
导　师: 严从荃
学　校: 四川大学
专　业: 基础数学
关键词: 线性规划运输问题内点算法时间约束
分类号: O221.1
类　型: 硕士论文
年　份: 2005年
下　载: 363次
引　用: 4次
阅　读: 论文下载

内容摘要

本文论讨了两类运输问题的算法,传统运输问题的算法和受时间约束运输问题的方案及算法。对于传统的运输问题,应用线性规划内点算法的基本理论,结合运输问题模型的特殊性,提出了运输问题内点算法的基本理论和一般步骤。该算法从运输问题可行域的内部出发,沿着中心路径的方向,通过反复迭代寻找运输问题的近似最优解。受时间约束运输问题给出了求解的一种新方案,并举例说明了其可行性。全文共分五部分:第一部分引言,第二部分对线性规划和运输问题的历史做一个小结性的回忆。第三部分,对内点算法的一些理论做一些简单的介绍,当然其中大部分引用了前人的工作,其中Yinyu Ye和Andersen对我有很大的帮助,这部分内容主要是他们的一些卓有成效的工作。第四部分,运输问题的新算法,给出了运输问题内点算法的相关理论和步骤及受时间约束运输问题的解决方案。第五部分,结束语,对所做工作的一个自我评价。本人所做的工作主要在第四部分,包括下面几个方面: (1) 总结性给出运输问题的特点; (2) 提出运输问题内点算法的构想和理论; (3) 给出运输问题内点算法的一般步骤; (4) 提出最优准则下受时间约束运输问题的配送方案; (5) 通过实际的例子说明了受时间约束运输问题的具体算法。

全文目录

中文摘要  2-3
英文摘要  3-6
1 引言  6-8
2 线性规划与运输问题回顾  8-10
  2.1 多项式时间算法  8
  2.2 线性规划  8-9
  2.3 运输问题  9-10
3 内点算法  10-14
  3.1 内点算法的基本理论  10-13
  3.2 算法分析  13-14
4 运输问题的新算法  14-25
  4.1 运输问题的数学模型及特点  14-16
  4.2 新算法的构想  16-17
  4.3 运输问题内点算法的基本理论及算法  17-22
    4.3.1 牛顿法  18-19
    4.3.2 中心路径及终止条件  19-20
    4.3.3 初始内点  20-21
    4.3.4 步长  21
    4.3.5 算法  21-22
  4.4 受时间约束运输问题的一种方案  22-25
    4.4.1 方案及算法  22-23
    4.4.2 一个例子  23-25
5 结束语  25-26
参考文献  26-28
声明  28-29
致谢  29

运输问题的新算法

内容摘要

全文目录

相似论文