【作者】 刘耕；

【导师】 杨超；

【作者基本信息】 华中科技大学 ， 管理科学与工程， 2007， 博士

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

【Abstract】 We live in a network world. In our real life there are many kinds of network. All these networks play important roles in our economic life and they are the carriers of the country economic growth, such as urban traffic network, telecommunication network, power generation network and computer network.. During all these years of quick development of Chinese economy, network is going through deep changes. For example, China’s transport network, telecommunication network, electricity network are all the largest but two in the world. China’s annual expansion capacity and the amount of money spent on these are all huge. According to the forecast:in the next 20 years, China’s power development task will be very difficult. From 2000 to 2020, the amount of electricity capacity need to be increased is 630,000,000 kW, with an average annual additional installed capacity of over 30,000,000kw, the scale of construction will be even greater considering of updating the equipments. Therefore, research on network optimization is very critical reference for decision makers in real network constructions.In this dissertation, we mainly study capacity expansion problems. For, in reality, a certain network’s capacity could be limited,such as the quantity of vehicles through the urban transportation network and the information flow of telecommunication network. When the capacity need be expanded because of increasing demand, the network capacity expansion comes up. This paper studies capacity expansion problems on different aspects: the largest flow, the spanning tree, the paths. We also study on how to eliminate blocking.At first, this article introduces the application background of the models, research methods and creative ideas in detail. There is an overview of the literature, too. Then, the article presents basic models and basic algorithms in network flow theory and capacity expansion models: the largest flow theory, the minimum cost flow problem and the minimum spanning tree theory. These issues and algorithms are the basis for our further research; meanwhile, the heuristic algorithm is also introduced.Secondly, the article studies paths expansion problems. They are: the path between designated nodes, the path between arbitrary nodes. We solve these problems by network switching. We transform these problems into some types of shortest paths problems. Thirdly, the largest flow expansion problem is discussed. Considering of the three kinds of expansion models: node-expanding model, arc-expanding model, the combination of arc-expanding and node-expanding model, we discuss the problems in detail and build a unified model model. Through an example, we compare the merits of the three models and draw the conclusion.Forthly, a model on multiperiod capacity expansion problems on directed networks is proposed. We solve the problem through dynamic programming. We discuss the algorithm in detail under these two situations: the largest flow and the largest capacity spanning tree.Fifthly, the paper studies on how to eliminate blocking in the capacity expansion process. The algorithm is developed and an example is also shown..Finally, this article concludes the main content, innovated points and a prospect on further studies.更多还原