论文部分内容阅读
我们生活在一个网络世界中,这些网络在我们的生活中起着重要的作用,例如城市交通网络,电信通讯网络,电力输送网络,计算机网络等等;同时,这些网络也是经济发展的载体和桥梁,在现代化建设中发挥着重要的作用。我国是个发展中的大国,随着经济建设的迅速发展,各种网络都在发生着翻天覆地的变化。比如,我国的交通网络里程数已经达到世界第二位,电力网络容量水平居世界第二,电信通讯网络用户数量也居世界前列。我国每年各种网络要扩张的数量巨大,所花费的资金也庞大。据预测:今后20年内,我国电力发展的任务将是十分艰巨的。从2000年起到2020年的20年内需要增加装机容量将在6.3亿kW,平均每年要新增装机容量3000多万kW,如再考虑期间还有大量寿命期已到需要更新改造的设备,其建设规模将更为巨大。因此研究网络优化模型对于实际网络建设的决策具有很重要的参考价值。本文所研究的内容主要是网络优化中的容量扩张问题。在实际生活中,特定的网络所能提供的容量一般而言是有限的,比如说交通网络中所能通过的车流量,电信网络所能处理的信号量等,也就是说,网络的容量是有一定约束的。所以当网络所能提供的容量不能满足顾客对网络容量的需求时,就会出现网络容量扩张要求。论文从路、流、树等不同的方面系统地论述了网络容量扩张问题,同时也研究了如何在网络容量扩张过程中消除堵塞现象。本文首先介绍选题的依据,从交通、通讯、和电力等方面分析了研究的背景和意义,对有关容量扩张的文献进行了概述,并提出本文的主要研究目标和内容;也论述了网络容量扩张问题的基本理论和算法:网络最大流理论、最小费用流理论、最小树理论,这些问题及算法是我们进一步研究的基础。我们还简单介绍了文献中常用到的启发式算法。在此基础上,开始研究有向网络中的容量扩张问题,首先是路的容量扩张问题:主要是指定节点对之间的路的容量扩张问题、任意节点对之间的路的容量扩张问题和第二费用路问题。我们通过构建辅助网络,将其转换为已知的问题求解。接着研究了最大流扩张的两个问题:给定扩张容量,如何扩张才能使费用最小;给定扩张费用,如何扩张才能使网络容量最大。我们定义了网络容量扩张的三种方式:弧扩张、点扩张、弧扩张和点扩张相结合。针对上述问题,分别展开讨论,并给出网络容量扩张的统一模型。给出了算例,比较了三种方式的优劣。本文还研究了多阶段情形下的网络容量扩张问题。首先介绍了动态规划的相关知识,接着给出单阶段容量扩张的一般模型;在此基础上,建立了多阶段容量扩张模型,并通过动态规划求解;以最大流和根在指定节点的最大容量树为例,讨论了具体算法。我们还研究了网络容量扩张过程中如何防止堵塞的问题,即消除结构堵塞点的问题,这在现实中也有着广泛的应用。建立了相关模型,并给出算法和算例。最后一章对全文内容以及创新之处进行了总结,并对文中相关研究有待进一步深化的地方提出继续研究的展望。