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

运输问题的直接算法

作　者: 蒋宏锋
导　师: 彭岳林
学　校: 中南大学
专　业: 应用数学
关键词: 线性规划运输问题强多项式算法等值界面最优解集
分类号: O221
类　型: 硕士论文
年　份: 2002年
下　载: 496次
引　用: 1次
阅　读: 论文下载

内容摘要

运输问题是一类常见而又极其典型的线性规划问题．本文基于标准线性规划逐维选优强多项式算法的基本理论，结合运输问题模型的特殊结构，提出了运输问题直接算法的基本定理和直接算法的一般步骤．该算法根据目标函数的梯度向量在可行域的低维界面上的投影，通过确定运输问题在可行域上的低维等值界面，直接得出运输问题的最优解集．全文共有五章：第一章是绪论，简单介绍了线性规划与运输问题的起源、发展，运输问题的传统理论及算法，算法复杂性分析等；第二章介绍了线性规划强多项式直接算法的基本理论．第三章主要是给出了运输问题直接算法的基本定理和算法复杂性分析；第四章为运输问题的直接算法的算例，通过几个简单实例说明了该算法的计算过程：第五章结束语．本人的所做的研究主要在第三章和第四章，它包括以下几个方面： (1)利用投影矩阵简化了逐维选强多项式算法理论的表达． (2)提出了运输问题直接算法的基本理论． (3)给出了运输问题直接算法的一般步骤，进行了算法时间复杂性分析． (4)对几个规模较小的运输问题，利用运输问题直接算法进行实际计算．对比求解运输问题最常用的表上作业法，该方法具有几何意义明确、计算过程操作方便、且求解效率高等特点．理论分析和大量的计算实例说明了直接算法是一种有效算法．从现有文献资料表明，运输问题的直接算法是首次提出：对比运输问题的主要解法——表上作业法，该算法求解效率更高，因而该算法具有十分重要的理论意义和实际意义．

全文目录

第一章绪论  7-15
  1．1 线性规划和运输问题  7-8
  1．2 运输问题的传统理论和算法  8-12
    1．2．1 平衡运输问题的数学模型  8-10
    1．2．2 运输问题的数学模型的特性  10-11
    1．2．3 运输问题的算法  11-12
  1．3 算法时间复杂性分析  12-15
    1．3．1 多项式算法与非定多项式算法  12-13
    1．3．2 强多项式算法  13-15
第二章线性规划逐维选优算法的基本理论  15-21
  2．1 法向消元最小法向消元  15-18
  2．2 逐维选优算法的基本定理  18-19
  2．3 逐维选优算法的步骤和时间复杂度  19-21
第三章运输问题的直接算法  21-33
  3．1 逐维选优算法的矩阵表示  21-26
    3．1．1 投影矩阵  21-24
    3．1．2 运输问题的投影矩阵  24-26
  3．2 运输问题直接算法的基本理论  26-31
  3．3 运输问题直接算法的一般步骤  31
  3．4 算法时间复杂度分析  31-33
第四章运输问题直接算法的算例  33-48
  4．1 平衡运输问题  33-38
  4．2 产销不平衡的运输问题  38-44
  4．3 可转化为运输问题的其它规划问题  44-48
第五章结束语  48-49
参考文献  49-53
致谢  53

运输问题的直接算法

内容摘要

全文目录

相似论文