论文部分内容阅读
网络容量扩张问题是运筹学的一个经典问题,与实际生活密切相关,具有很强的理论意义以及现实背景。城市交通网络改造、电力网络升级、通信网络优化等,都要用到网络容量扩张方面的知识。
本文第一章介绍了关于网络容量扩张的一些基本知识以及几种基于不同的网络容量定义下的模型。其中张建中、杨超将网络容量定义为最大网络支撑树的容量,而支撑树的容量定义为该支撑树上最小边的容量,具有很强的效用性,因此他们的定义方法被大量引用。随机性模型是当前研究的热点,随机性涉及费用的随机性、需求的随机性以及路径选择的随机性等各种不确定因素,是一个非常宽广的研究领域。
第二章主要研究了网络容量按需扩张的模型。给定的网络为连通网络,运用Floyd-Warshall算法找出任意两点之间的最短路作为两点之间的流量路径。每条路径都有一定的流量需求,网络中每条边的容量不小于经过该边的所有路径的需求之和,否则需要对其容量进行扩张。每种扩张方案的扩张费用是关于扩张容量的函数。本文给出了解决该问题的一个复杂性为O(n3)的多项式时间算法,使得各边容量达到需求,且总的扩张费用最小。本文考虑了两种情况下的最短路:(1)节点无阻滞,即路径上节点的个数对路径长度无影响;(2)节点有阻滞作用,即节点对网络流有延时作用,从而需要考虑对路径长度的影响。在第二种情况下,根据需要对Floyd-Warshall算法做了改进,生成新的FWE算法。
第三章主要研究了路径选择的随机性对网络容量扩张决策的影响。影响路径选择的因素有很多,其中节点的阻滞作用以及弧上不确定事件(例如突发事件)的阻滞作用是影响路径选择的重要因素,而弧上阻滞因素的不确定性必然导致了路径选择的随机性。本文建立了该问题的模型,并对第二章的算法加以改进,有效地解决了该问题。