網(wǎng)絡容量擴張問題研究.pdf

1、網(wǎng)絡容量擴張問題是運籌學的一個經(jīng)典問題，與實際生活密切相關(guān)，具有很強的理論意義以及現(xiàn)實背景。城市交通網(wǎng)絡改造、電力網(wǎng)絡升級、通信網(wǎng)絡優(yōu)化等，都要用到網(wǎng)絡容量擴張方面的知識。
　　 本文第一章介紹了關(guān)于網(wǎng)絡容量擴張的一些基本知識以及幾種基于不同的網(wǎng)絡容量定義下的模型。其中張建中、楊超將網(wǎng)絡容量定義為最大網(wǎng)絡支撐樹的容量，而支撐樹的容量定義為該支撐樹上最小邊的容量，具有很強的效用性，因此他們的定義方法被大量引用。隨機性模型是當前研究

2、的熱點，隨機性涉及費用的隨機性、需求的隨機性以及路徑選擇的隨機性等各種不確定因素，是一個非常寬廣的研究領(lǐng)域。
　　 第二章主要研究了網(wǎng)絡容量按需擴張的模型。給定的網(wǎng)絡為連通網(wǎng)絡，運用Floyd-Warshall算法找出任意兩點之間的最短路作為兩點之間的流量路徑。每條路徑都有一定的流量需求，網(wǎng)絡中每條邊的容量不小于經(jīng)過該邊的所有路徑的需求之和，否則需要對其容量進行擴張。每種擴張方案的擴張費用是關(guān)于擴張容量的函數(shù)。本文給出了解決該問

3、題的一個復雜性為O(n3)的多項式時間算法，使得各邊容量達到需求，且總的擴張費用最小。本文考慮了兩種情況下的最短路：(1)節(jié)點無阻滯，即路徑上節(jié)點的個數(shù)對路徑長度無影響；(2)節(jié)點有阻滯作用，即節(jié)點對網(wǎng)絡流有延時作用，從而需要考慮對路徑長度的影響。在第二種情況下，根據(jù)需要對Floyd-Warshall算法做了改進，生成新的FWE算法。
　　 第三章主要研究了路徑選擇的隨機性對網(wǎng)絡容量擴張決策的影響。影響路徑選擇的因素有很多，其中