網(wǎng)絡(luò)容量擴(kuò)張問(wèn)題研究.pdf

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

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

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