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

最小费用网络流的若干新问题研究

作　者: 鲁海燕
导　师: 姚恩瑜
学　校: 浙江大学
专　业: 运筹学与控制论
关键词: 组合优化网络流最小费用流网络单纯形法供应链等流问题
分类号: O233
类　型: 博士论文
年　份: 2007年
下　载: 528次
引　用: 3次
阅　读: 论文下载

内容摘要

近几十年来，组合优化经历了飞速的发展。网络流在生产和社会实践中有着广泛的应用，是组合优化中被广泛研究的问题之一。网络流上的优化问题涉及多个学科领域，包括应用数学、计算机科学、管理学以及运筹学等。最小费用流是最为基本的网络流模型，对于该模型已有丰富的研究成果。随着人类活动和生产过程的日益复杂，新问题不断出现，这对原有的网络模型构成了挑战，也为网络流的进一步发展提供了新的源泉。本文主要就近年来出现的来自生产实践的若干最小费用流问题进行研究，提出了进一步的模型，并给出了求解新模型的网络单纯形算法。全文共分七章。第一章主要介绍了本文要研究的主要问题，并对文献中相关问题的研究成果作了简要的回顾。第二章介绍了有关网络流的若干基本概念和知识，为后面各章的展开做好准备。第三章我们对近年来新提出的一类网络流问题—最小费用分配流，做了进一步的研究，给出了用单纯形法求解该问题时寻找初始基本可行解的方法，并把经典网络流中的一些概念和方法推广到了最小费用分配流模型上。第四章给出了上述最小费用分配流问题的一种推广，并对推广的模型进行了研究，探讨了该问题的基本可行解的网络结构和性质，设计出了求解该问题的网络单纯形法。第五章提出了广义网络上的最小费用分配流问题，称为广义最小费用分配流问题，第三章和第四章中研究的问题都是这种问题的特殊情形。我们研究了此类问题的基本可行解的网络结构和性质，并给出了求解该问题的网络单纯形法，并对如何有效的执行算法进行了探讨。第六章主要研究了广义等流(general equal flow)问题。我们不仅推广了广义等流的概念，而且还把广义等流问题推广到了广义网络上，称为广义比例流问题。通过对该问题的基本可行解的网络结构的分析，提出了求解该问题的网络单纯形法，并对如何有效的执行算法进行了研究。第七章对本文的研究结果作了总结，并提出了若干值得进一步研究的问题。

全文目录

摘要  4-6
Abstract  6-11
第一章序言  11-18
  1.1 组合优化简介  11-12
  1.2 算法和计算复杂性  12-15
  1.3 网络流问题  15-16
  1.4 论文主要结果  16-18
第二章网络流基本知识  18-32
  2.1 基本概念  18-24
    2.1.1 图  18-20
    2.1.2 有向图  20-21
    2.1.3 连通性  21-22
    2.1.4 关联矩阵和邻接矩阵  22-23
    2.1.5 割集  23
    2.1.6 树与支撑树  23-24
  2.2 网络流问题简介  24-28
    2.2.1 最小费用流问题  24-25
    2.2.2 最短路问题  25-26
    2.2.3 最大流问题  26
    2.2.4 指派问题  26
    2.2.5 运输问题  26
    2.2.6 环流问题  26-27
    2.2.7 凸费用流问题  27
    2.2.8 广义流问题  27-28
    2.2.9 多物品流问题  28
    2.2.10 其他网络问题  28
  2.3 网络单纯形法的基本概念和性质  28-29
  2.4 广义网络单纯形法的基本概念和性质  29-32
第三章最小费用分配流问题  32-46
  3.1 引言  32-33
  3.2 问题描述  33-37
    3.2.1 MNF 模型中的顶点  33-35
    3.2.2 最小费用分配流问题  35-37
  3.3 已有结果  37-40
    3.3.1 基本可行图的网络结构  38-39
    3.3.2 网络单纯形算法  39-40
  3.4 构造初始基本可行解的方法  40-42
  3.5 MDCF 问题中的转轴图-扩展圈(Extented Cycle)  42-45
  3.6 结论  45-46
第四章最小费用分配流问题的一种推广  46-65
  4.1 引言  46
  4.2 问题描述  46-51
    4.2.1 MDCF_(≤)问题的重新描述  47-49
    4.2.2 MDCF_(≥)问题的重新描述  49-51
  4.3 基本可行图  51-57
  4.4 最优性条件  57-58
  4.5 基本可行解和对偶变量的计算  58-60
  4.6 分配流网络单纯形法  60-61
  4.7 计算实例  61-62
  4.8 结论  62-65
第五章广义最小费用分配流问题  65-83
  5.1 引言  65-66
  5.2 问题描述  66-70
  5.3 基本可行图的网络结构  70-73
  5.4 最优性条件  73-76
  5.5 广义分配流网络单纯形法  76-80
    5.5.1 计算基本可行流  76-79
    5.5.2 计算顶点/弧的势  79-80
    5.5.3 广义分配网络单纯形法  80
  5.6 计算实例  80-81
  5.7 结论  81-83
第六章广义最小费用比例流问题  83-109
  6.1 引言  83-85
  6.2 问题的变形和性质  85-87
  6.3 基本可行解的网络结构  87-92
  6.4 广义比例流网络单纯形法  92-102
    6.4.1 构造初始基本可行解  92-93
    6.4.2 计算基本解  93-96
    6.4.3 计算检验数  96-99
    6.4.4 确定离基变量以及转轴  99-102
  6.5 计算实例  102-108
    6.5.1 计算初始基本可行解  102-103
    6.5.2 第一次迭代  103-104
    6.5.3 第二次迭代  104-106
    6.5.4 第三次迭代  106-108
    6.5.5 第四次迭代  108
  6.6 结论  108-109
第七章结论  109-112
  7.1 论文结果简要总结  109-111
  7.2 进一步的问题及研究展望  111-112
参考文献  112-119
致谢  119-121
在学期间完成的论文  121-122

最小费用网络流的若干新问题研究

内容摘要

全文目录

相似论文