第二節(jié) 網(wǎng)絡(luò)優(yōu)化理論

我們生活的網(wǎng)絡(luò)社會，是一個由計算機信息網(wǎng)絡(luò)、電話通信網(wǎng)絡(luò)、運輸服務(wù)網(wǎng)絡(luò)、物質(zhì)分派網(wǎng)絡(luò)等和能源所組成的復(fù)雜的網(wǎng)絡(luò)系統(tǒng)。謝凡榮（2009）提出，對一個網(wǎng)絡(luò)系統(tǒng)進行有效的計劃、管理以及控制，并讓該網(wǎng)絡(luò)系統(tǒng)達到最大的社會和經(jīng)濟效益，這個過程被稱為網(wǎng)絡(luò)優(yōu)化。

網(wǎng)絡(luò)優(yōu)化是運籌學（Operations Research）中的一個經(jīng)典和重要分支，所研究的問題涉及物資管理、經(jīng)濟管理、工業(yè)工程、交通運輸、計算機科學與信息技術(shù)、通信與網(wǎng)絡(luò)技術(shù)、控制論及軍事運籌學等諸多領(lǐng)域。

在網(wǎng)絡(luò)優(yōu)化的過程中，最短路問題、最小飽和流問題、最大流問題、最小費用最大流問題、最小費用流問題、最大利潤流問題、最大容量路問題等都是一些最基本的問題。國內(nèi)外有不少學者對這些問題進行了深入的研究，并且取得了很好的成果。例如，在最大流的問題上，國內(nèi)學者徐周波（2005）和江錦成（2014）分別應(yīng)用ADD算法和SAPR算法對其進行求解；而Dijkstra算法和Floyd算法在求解最短路問題上應(yīng)用比較廣泛。

Thomas（2006）指出最短路問題的基本內(nèi)容是：若網(wǎng)絡(luò)中的每條邊都有一個基于長度、成本或時間的數(shù)值，則找出源點和末點之間總權(quán)和最小的路徑就是最短路問題，可用來解決最短運輸路線計算、車輛路徑安排以及廠區(qū)的選址和布局等一些現(xiàn)實問題。

1956年福特和福克遜提出了最大流標號算法，并建立了“網(wǎng)絡(luò)流理論”。最大流問題（maximum flow problem）是一種組合最優(yōu)化問題，它的作用是在對設(shè)備合理利用的情況下，通過使運輸流量最大來提高效率，以達到最好的效果。

錢頌迪（1990）對網(wǎng)絡(luò)中最小費用最大流問題進行了詳細論述。任意一個網(wǎng)絡(luò)中都存在著路徑，而且每段路徑都有“容量”和“費用”兩個條件的限制。此類問題的研究試圖解決一個問題：從起點到終點如何選擇路徑以及分配經(jīng)過路徑的流量，可以在流量最大的前提下，達到所需的費用最小的要求。

盧虎生等（2003）闡述了在網(wǎng)絡(luò)優(yōu)化中，最大利潤流是以運輸利潤最大為目標。一個利潤可行流可分解為若干個路流和圈流，相應(yīng)地該可行流的利潤也等于這些路流和圈流的利潤之和。

研究網(wǎng)絡(luò)優(yōu)化問題的多目標規(guī)劃模型與算法中，考慮到人的有限理性以及問題的復(fù)雜性這兩方面因素，往往在追求最優(yōu)解的時候更趨向于尋找滿意解或者有效解。周樹發(fā)等（2004）以工程網(wǎng)絡(luò)優(yōu)化為研究對象，綜合考慮工程的質(zhì)量、工期、成本、資源等多個因素，建立多目標規(guī)劃模型，以求網(wǎng)絡(luò)優(yōu)化的全面性。