網絡理論

在圖論基礎上研究網絡一般規律和網絡流問題各種優化理論和方法的學科，是運籌學的一個分支。網絡是用節點和邊聯結構成的圖，表示研究諸對象及其相互關係，如鐵路網、電力網和通信網等。網絡中的節點代表任何一種流動的起點、運轉點和終點（如車站、港口、城鎮、計算機終端和工程項目的事件等）。網絡中的邊代表任何物流、能流或信息流通過的通道（如輸電線、通信線、鐵路線和各事件之間的次序等）。在網絡中每條邊上賦予某個正數，稱為該邊的權，它可以表示路程、流量、時間和費用等。建立網絡的目的都在於把某種規定的物質、能量或信息從某個供應點最優地輸送到另一個需求點去。例如，在管道網絡中要以最短的距離、最大的流量和最小的費用把水、石油或天然氣從供應點送到用户那裏。

網絡理論起源於圖論 ^[1]  。1845年G.R.基爾霍夫應用圖論和 ^[2]  矩陣理論證明了電網絡中兩個重要定律，即基爾霍夫電流定律和電壓定律，不僅為圖論的發展作出了貢獻，也奠定了網絡理論的基礎。20世紀50年代以來，隨着網絡理論的廣泛應用，許多學者提出優化計算的方法。1956年L.R.小福特和D.R.富爾克森提出尋找最大流量的標號算法。1959年E.W.戴克斯特拉提出尋找最短路徑的標號算法。1961年，富爾克森提出求解更一般的最小費用流的狀態算法，這是解最短路徑、最大流量與最小費用流的統一方法，是網絡理論中最基本的結果之一。此後又相繼提出了各種類型的網絡流問題，諸如帶下界容量的網絡流、動態流、帶增益的流和多種物資流等問題，並得到一系列結果。

當物質流或信息流通過給定的網絡時（圖1）,在流過每條邊的流量xij不超過該邊允許通過的流量cij的條件下,求出從發點s向收點t輸出的最大流量f，即在滿足的條件下,使f最大。最大流量問題是一個特殊的線性規劃問題，有許多求解方法。一種有效的計算方法是福特-富爾克森法，它是根據最大流量-最小割集原理，通過標號算法，求出在上述約束條件下從發點s到收點t的最大流量f 的數值。其計算步驟如下：①繪製一個能滿足上述約束條件的網絡可行流（圖2）。邊上的數字為允許流量cij，括號內的數字為給定的可行流。②找出一條增廣鏈。增廣鏈是指從發點s到收點t的鏈中，滿足正向邊上xij<cij和反向邊上xji>0的鏈。圖2中用粗線表示的{vs，v2,v3,v4,v6,vt} 是一條增廣鏈。其中【v2,v3】為反向邊,其餘均為正向邊。③調整可行流,即在增廣鏈的各邊上，屬正向邊加上一個修正量ε，屬反向邊減去一個修正量ε，即xij+εj，xji-εj。

一般提法是：尋找網絡中兩點間的最短路徑,即尋找連接這兩點的邊的總權數(可以是距離、時間、費用等)為最小的通路。圖4為最短路徑問題的一個例子。最短路徑問題有兩種算法。戴克斯特拉法　1959年提出。其計算方法是：從始點vs,標以零值,並記在vs旁的方括號內。然後依節點序號順序找出到達各點的最短距離,並説明來自何方,例如在節點v3處標上【v2,4】,即表示來自節點v2，距離累計為4。戴克斯特拉法可以通過編制計算程序,在計算機上運算。

圖6示出最短樹問題的一個例子。一城市擬在6個地點架設電纜線路,每條邊上的數字表示兩點間的距離，要設計一個使電纜總長度為最短的鋪設方案。求解最短樹有兩種方法。①克羅斯卡爾法:從兩點間找出最短的邊聯結成一個最短支撐樹（圖7）。 ②破圈法：從網絡的每一個圈中去掉具有最大權的邊，直到無圈時為止，即可求出最短樹（圖8）。上述例子的計算結果是：最短樹的總距離為17。最短樹問題的求解可用於城市煤氣和自來水管道、電話線、電纜等線路網絡的優化問題。

在網絡中，若每條邊【vi，vj】除容量cij外,還給一個數aij，表示從vi到vj運輸單位物資所需支付的費用,則問題便是尋找一個可行流{fij},其流值為給定的數值r*，並使總費用取最小值。這樣的可行流稱為最小費用流。最小費用流問題可用對應於線性規劃的原始算法和對偶算法求解。例如,若對偶算法是：從各邊流fij=0和流值r=0的最小費用流開始,如果r<r*，則採用以費用作邊長求最短路徑的方法尋找關於{fij}的增廣鏈，把{fij}調整為流值r′(r<r′≤r*)的最小費用流，直到流值為r*為止。