信息技術(shù)--網(wǎng)絡分析與網(wǎng)絡計劃

1、第六章網(wǎng)絡分析與網(wǎng)絡計劃網(wǎng)絡分析是圖論的一個應用分支它主要是應用圖論的理論與方法來解決具有網(wǎng)絡性質(zhì)的管理決策問題在現(xiàn)實生活和生產(chǎn)實踐中，網(wǎng)絡分析方法有很廣泛的應用如在企業(yè)管理中，如何制訂管理計劃或設(shè)備購置計劃，使收益最大或費用最??；在組織生產(chǎn)中，如何使各工序銜接好，使生產(chǎn)任務完成得既快又好；在交通網(wǎng)絡中，如何使調(diào)運的物資數(shù)量多且費用最小等由于網(wǎng)絡分析具有圖形直觀，方法簡便，容易掌握的特點，因此得到迅速的發(fā)展，且廣泛地應用在各個領(lǐng)域，成為經(jīng)濟活動中許多管理決策的優(yōu)化問題的重要手段網(wǎng)絡計劃方法是上世紀50年代發(fā)展起來的計劃控制技術(shù)，主要包括計劃評審技術(shù)(programme evaluation a

2、nd review technique，簡稱PERT)和關(guān)鍵路徑方法(critical path method或critical path analysis，簡稱CPM、CPA)網(wǎng)絡計劃方法特別適用于現(xiàn)代管理中的多因素多環(huán)節(jié)的復雜計劃的優(yōu)化控制，成為管理運籌學的重要應用分支本章在引入有關(guān)圖的一些基本概念的基礎(chǔ)上，介紹最小生成樹、網(wǎng)絡最短路、最大流、最小費用最大流等網(wǎng)絡分析模型及其解法；并對網(wǎng)絡計劃圖（統(tǒng)籌圖）的制作、作業(yè)時間參數(shù)計算、關(guān)鍵線路方法和計劃評審技術(shù)等網(wǎng)絡計劃基本技術(shù)和方法進行初步介紹第一節(jié) 圖的基本概念一、圖現(xiàn)實世界中有許多具體事物及關(guān)系可以用圖形來抽象表示例如，路線關(guān)系、工序安排

3、、區(qū)位規(guī)劃等都可以用圖來表達我們先通過幾個直觀的例子，來認識什么是圖例6-1 歌尼斯堡七橋問題哥尼斯堡(Konigsbergs)城域有一個普雷格爾河系，由新河、舊河及其交匯而成的大河組成，它把該城分成了一島三岸共四塊陸地，陸地之間有七座橋連通，如圖6-1(a)所示當時城內(nèi)居民在散步時熱衷于這樣一個問題：從某陸地出發(fā)，能否走遍七橋且每橋只過一次而最終回到原出發(fā)地圖6-1（a）圖6-1（b）歐拉在1736年解決了這一問題他用四個點表示四塊陸地，用相應兩點間的邊表示橋，從而建立了該問題的圖的模型，見圖6-1(b)于是問題歸結(jié)為：在這個連通多重圖中，能否找出一條回路，過每邊一次且僅僅一次歐拉在求解該問

4、題時，把圖6-1（a）所示的實際問題抽象為圖6-1（b）所示圖形例6-2 比賽安排問題5個球隊之間安排賽事其中a球隊分別與b，c，d球隊有賽事；b球隊還與c球隊，d球隊還與e球隊有賽事綜上，這5個球隊之間的比賽關(guān)系可用圖6-2(a)來表示，也可用圖6-2(b)來反映圖6-2（a）圖6-2（b）以上兩例都忽略了問題的具體細節(jié)，而把問題的關(guān)鍵性質(zhì)或關(guān)系抽象為圖的形式例6-1中兩岸和島的形狀及橋的曲直都被忽略，但陸地間的關(guān)聯(lián)情況卻得到保持例6-2中把比賽關(guān)系抽象為連接關(guān)系簡單些說，一個圖代表了某些對象集合之間的關(guān)系，而圖論是主要研究這些對象在上述表示法中的許多可能的性質(zhì)中的某些性質(zhì)詳細些說，一個圖指

5、的是一些點以及連接這些點的一些線的總體這種連接方式可以具有許多特征，而圖論本質(zhì)上就是研究這種特征的注意，這里所講的圖并不是解析幾何與微積分書中常見的圖，在那里，點的位置，線的長度和斜率是它的重要部分而在圖論中，這些都是不重要的，而重要的只是哪些點之間有線相連有時，連接的先后次序也是重要的二、幾個基本概念1無向圖一個圖定義為一個有序二元組（，），記為：（，）其中，V是一個有限非空的集合，其元素稱為G的結(jié)點或頂點，簡稱點，而V稱為G的結(jié)點集或頂點集，簡稱點集，一般表示為：，而E稱為G的邊集，表示為：，其中由中元素對(，)所構(gòu)成如果(，)是無序?qū)?，則稱為無向圖中元素稱為的無向邊，一般表示為(，)對于

6、給定的圖可以作出其幾何圖例6-3 無向圖（，），其中點集，,，邊與頂點的關(guān)聯(lián)情況由表6-1給出表6-1 邊與頂點的關(guān)聯(lián)情況(，)(,)(,)(,)(,)(,)(,)(,)(,)根據(jù)表6-1，可作其幾何圖，如圖6-3所示在作幾何圖時，僅要求表示出頂點、邊以及它們間的關(guān)聯(lián)關(guān)系，而對頂點的位置以及邊的曲直、長短都沒有任何規(guī)定圖6-3基于無向圖的結(jié)構(gòu)特點，我們給出下列一些術(shù)語：平行邊若兩條不同的邊與具有相同的端點，則稱與為的平行邊圖6-3中與是平行邊，因為它們的端點均為、簡單圖若無平行邊，則稱圖為簡單圖完備圖圖中任兩個頂點間恰有一條邊相關(guān)聯(lián)，為完備圖2有向圖設(shè)頂點的非空集合（，），邊的集合（，）如果中

7、任一條邊是的一個有序元素對(，)(這里，)，則稱為有向邊集，中元素稱為有向邊或弧，記為(，)其中為的起點，為的終點和組成了一個有向圖，記作（，）例6-4 給有向圖（，），其中（，），（，），邊與頂點的關(guān)聯(lián)情況如表6-2所給表6-2 邊與頂點的關(guān)聯(lián)情況(，)(,)(,)(,)(,)(,)(,)(,)(,)根據(jù)表6-2也可作出有向圖，如圖6-4（a）圖6-4(a)圖6-4(b)圖6-4（c）有向圖區(qū)別于無向圖的關(guān)鍵，在于它的邊（或?。┦怯蟹较虻?，圖6-4（a）中邊上的箭頭所指即邊的方向在有向圖中(，)(，)類似于無向圖，有向圖也有下列術(shù)語：平行邊不同的弧與(，)的起點與終點都相同圖6-4（a）中、

8、是平行邊，而、卻不是，(,)；而(,)簡單圖無平行邊的有向圖稱為簡單圖完備圖圖中任兩個頂點與間，恰有兩條有向邊(，)及(，)，則稱該有向圖為完備圖基本圖把有向圖的每條邊除去方向就得到一個相應的無向圖，稱為的基本圖例如圖6-4（b）是圖6-4（a）的基本圖3同構(gòu)對于無向圖和有向圖，如果圖（，）和(，)的頂點集合和，以及邊集E和E之間在保持關(guān)聯(lián)性質(zhì)的條件下一 一對應，則圖和同構(gòu)例如圖6-2(a)、(b)所示的兩個圖看似不同，其實是同構(gòu)圖由于同構(gòu)的圖被認為是相同的，這就給我們在網(wǎng)絡規(guī)劃中建立網(wǎng)絡模型帶來許多方便，當我們用幾何圖來反映和分析實際問題的內(nèi)在關(guān)系而構(gòu)建網(wǎng)絡模型時，點的位置可以任意布置，邊的

9、長短曲直也可任意，故而我們盡量設(shè)計那種反映問題清晰、簡練的幾何圖4鏈、路和連通性給定一個無向圖（，），其中的一個點與邊的交錯序列，如果序列中所有都滿足（，），（1，2，1），則稱交錯序列為聯(lián)結(jié)和的鏈，記為（，）或簡記為（，）和（，）當0，且，則鏈的起點等于終點，稱為閉鏈閉鏈中除起點和終點外沒有相同的結(jié)點和邊，則該閉鏈稱為圈當，時稱為開鏈若開鏈中所有結(jié)點均不相同，稱為初等鏈例如圖6-5中：圖6-51（，）是閉鏈，但不是圈；2（，）是閉鏈，同時也是圈； 3（，）是開鏈；4（，）是初等鏈對于有向圖（，），可以通過其相應的基本圖來定義它的鏈但由于有向圖中弧是有方向的，可能出現(xiàn)鏈中的弧的方向與鏈的方向不

10、一致的情況如果鏈中所有弧的方向與鏈的方向一致，則稱該鏈為單向路，簡稱路顯然，在有向圖中鏈和路的概念并不一致，而在無向圖中兩者沒有區(qū)別如果路的起點和終點相同，則稱為回路對于無向圖而言閉鏈和回路概念一致在圖6-4（a）中：1（，）是鏈，但不是路；2（，）是鏈，同時也是路和回路在中任意兩個結(jié)點i1和ik，從i1到ik存在路，則稱i1可達ik若中任意兩結(jié)點間存在鏈，則稱為連通圖若中任意兩結(jié)點間相互可達，則稱為強連通圖對于無向圖而言連通圖等價于強連通圖例如圖6-4（a）所示的是強連通圖，因為、都是相互可達的如果我們將圖中弧刪去，如圖6-4（c）所示，則成為一般的連通圖因為這時、不能相互可達5網(wǎng)絡一個圖連

11、同定義在其邊集上的實函數(shù)一起稱為一個網(wǎng)絡網(wǎng)絡一般是連通圖定義在邊集上的實函數(shù)稱為邊的權(quán)數(shù)記為(，)它與邊(，)具有一一對應關(guān)系，可以用以表達網(wǎng)絡上的各種有關(guān)性質(zhì)，如路長、流量、費用等等網(wǎng)絡的圖解即在每條邊旁標上相應的權(quán)數(shù)若一網(wǎng)絡的每條邊都是無向邊，則稱為無向網(wǎng)絡，記為（，）或(，)若一網(wǎng)絡的每條邊都是有向邊，則稱為有向網(wǎng)絡，記為（，）或(，)若一網(wǎng)絡中既有無向邊，也有有向邊，則稱為混合網(wǎng)絡所謂網(wǎng)絡分析，簡單地說，即對網(wǎng)絡進行定性和定量分析，以便為實現(xiàn)某種優(yōu)化目標而尋求最優(yōu)方案這方面的典型問題有：最小樹問題，最短路問題，中心問題，重心問題，最大流問題，最小費用最大流問題，最短回路問題，網(wǎng)絡計劃問

12、題，等等第二節(jié) 最小樹問題一、樹的基本概念1子圖、真子圖、生成子圖設(shè)有圖(，)和圖(，)，如果，則稱為的子圖，并記為，而則為的原圖當子圖的邊集或點集不同于原圖時，即時，稱子圖為的真子圖，記為當子圖的點集等于原圖的點集時，則稱子圖為原圖的生成子圖或支撐子圖在圖6-6中，（a），（b），（c），（d）均是（a）的子圖；（a），（b），（c）是（a）的真子圖；（a），（b），（c）均是（a）的生成子圖由于（d）比（a）少一個點，所以（d）不是（a）的生成子圖圖6-62樹無圈且連通的無向圖稱為樹樹一般記為作為樹定義還可以有以下幾種表述：(1)連通且無圈或回路；(2)無圈且有n1條邊（如果有n個結(jié)點）；

13、(3)連通有n1條邊；(4)無回路，但不相鄰的兩個結(jié)點之間聯(lián)以一邊，恰得一個圈；(5)連通，但去掉T的任意一條邊，就不連通了；(6)的任意兩個結(jié)點之間恰有一條初等鏈二、最小生成樹及其算法1最小生成樹如果是無向圖的生成子圖，同時又是樹，則稱是的生成樹或支撐樹例如圖6-7（b），（c）是（a）的生成樹圖6-7一個網(wǎng)絡圖可以有多個生成樹記N的所有生成樹的集合為： | 1，2，L 設(shè)（，）是網(wǎng)絡圖N（，）的一棵生成樹，則邊集中所有邊的權(quán)數(shù)之和稱為樹的權(quán)數(shù)，記為（）若，使（）（）則稱為網(wǎng)絡的一棵最小生成樹，簡稱最小樹2最小樹的求法定理8-1如果把網(wǎng)絡的點集分割成兩個不相交的非空集合和，則聯(lián)結(jié)和的最小邊必

14、包含于N的最小樹內(nèi)根據(jù)定理8-1，可以給出求最小樹的兩種方法，這就是避圈法與破圈法，分述如下：(1)避圈法其計算步驟如下：從網(wǎng)絡中任選一點，令，；從聯(lián)結(jié)與的邊中選取最小邊，不妨設(shè)為(，)，則它必包含于最小樹內(nèi)；令Þ，Þ；若，則停止，已選出的諸邊即給出最小樹；否則返例6-5試求圖6-8所示網(wǎng)絡的最小樹，各邊旁邊的數(shù)字為各邊的權(quán)圖6-8解由題意可知這是一個最小樹問題先按原圖畫出7個點，令1，2，3，4，5，6，7由于聯(lián)結(jié)與的邊共有三條，其中最短邊為(1，2)故用線把點1和2連結(jié)起來，令1，2，3，4，5，6，7，如圖6-8(a)所示，重復上述步驟，直到7個點全都連通為止具體求解

15、過程如圖6-8（a）到圖6-8（f）所示，其中圖6-8（f）)即給出本例的最小樹，()13圖6-8（a）（b）圖6-8（c）（f）(2)破圈法用破圈法求最小樹時，先從圖中任取一圈，去掉該圈的一條最大邊，然后重復這一步驟，直到無圈為止例6-6 圖6-9所示的一賦權(quán)連通圖是某一具有9個居民點的交通網(wǎng)絡圖，其中邊權(quán)表示該段道路的長，現(xiàn)欲沿小區(qū)道路架設(shè)一聯(lián)絡各個居民點的閉路電視系統(tǒng)，求可使閉路電視系統(tǒng)所架線路總長最短的方案圖6-9解 這是一個求網(wǎng)絡最小樹的問題可利用破圈法求解過程如圖6-9（ai）所示圖6-9（ai）圖6-9（i）所示的是網(wǎng)絡最小樹按圖安排閉路電視系統(tǒng)可使所架線路總長最短，()19第三

16、節(jié) 最短路徑問題在生產(chǎn)實踐，運輸管理和工程建設(shè)的很多活動中，諸如各種工藝路線的安排、廠區(qū)及貨場的布局、管道線網(wǎng)的鋪設(shè)及設(shè)備的更新等等問題，都與尋找一個“圖的最短路徑”問題(shortest-path problem )密切相關(guān)，它是網(wǎng)絡規(guī)劃中的一個最基本的問題一、基本概念給定一個賦權(quán)有向圖(，)，對每一條弧(，)，相應地有權(quán)（），又有兩點、V，設(shè)是中從到的一條路，路的權(quán)是中所有弧的權(quán)之和，記為()最短路問題就是求從到的路中一條權(quán)最小的路：()()二、最短路問題的算法1Dijkstra算法(Dijkstra algorithm)該算法是由Dijkstra于1959年提出來，用于求解指定兩點之間的

17、最短路，或從指定點到其余各點的最短路，目前被認為是求解最短路問題的最好方法算法的基本思路基于以下原理.定理6-2若是從到的最短路，是中的一個點，那么從沿到的路必定是從到的最短路引理若是從到的最短路，是中的一個點，則從到的最短路必定包含于之內(nèi)根據(jù)定理6-2及引理，我們可以從s出發(fā)試探所有可能到達t的下一個結(jié)點i，取距離最短的一個弧（，），則必然包含于從到的最短路中；從開始對沒有試探過的結(jié)點進行進一步的試探、推進，直至，最終可以找出從到的最短路Dijstra算法采用（雙標號法）T標號與P標號，來實現(xiàn)這一試探、推進過程T標號為試探性標號；P為永久性標號給點一個P標號時，表示從到點的最短路權(quán)，一旦點得

18、到P標號則意味著從到點的最短距離已經(jīng)確定，標號不再改變給點一個T標號時，表示從到點的估計最短路權(quán)的上界，這是一種臨時標號凡沒有得到P標號的點都有T標號算法每一步都把某一點的T標號改為P標號，當終點得到P標號時，全部計算結(jié)束Dijstra算法基本步驟：(1)給以P標號，P()0，其余各點均給T號，T()(2)若點為剛得到P標號的點，考慮，(，)A且為T標號對的T標號進行如下的更改：T()minT()，P() (6-1)(3)比較所有具有T標號的點，把最小者改為P標號，即：P()min T() (6-2)當存在兩個以上最小者時，可同時改為P標號(4)若全部點均為P標號，則停止計算否則用代替并轉(zhuǎn)至步

19、驟（2）例6-7用Dijkstra算法求圖6-10中從到的最短距離，以及相應的路線圖6-10解（1）首先給以P標號，P（ ） 0，給其余所有點T標號，T（i）（i = 2，3， 7）（2）考察，由于（，），（，），（，）A，且、是T標號，所以修改T標號為：T（）min T（），P（） min ，022T（）min T（），P（）min ，055T（）min T（），P（）min ，033在所有T標號中，T()2最小，于是令P()2將結(jié)果記在圖6-10（a）上：P標號以（）形式標在結(jié)點旁邊，T標號以不帶（）的數(shù)字標在結(jié)點旁邊，圖中沒有標號的結(jié)點均代表T（）(3)考察因為（，），（，）A，且、是T

20、標號，故、新的T標號為：T（）min T（），P（）min ，224T（）min T（），P（）min ，279在所有T標號中，T()3最小，故令P()3圖上標號如圖6-10（b）(4)考察，因（，）A，T（）min T（），P（）min ，358在所有T標號中，T()4最小，令P()4圖上標號如圖6-10（c）(5)考察，（，），（，）A，T（）min T（），P（）min ，437T（）min T（），P（）min ，459在所有T標號中，T()7最小，令P()7圖上標號如圖6-10（d）(6)考察，（，），（，）A，T（）min T（），P（）min ，718T（）min T（），P（）

21、min ，7714在所有T標號中，T()8最小，故令P()8圖上標號如圖6-10（e）(7)考察，（，）A，T（）min T（），P（） min 14，8513令P()13，圖上標號如圖6-10（f）所有點都標上P標號，計算結(jié)束從到的最短路徑，可從開始根據(jù)永久性標號數(shù)值回溯得到最短路徑是：，路長13同時得到到其余各點的最短路，即各點的永久性標號P（i）Dijkstra算法只適用于所有0的情形，當賦權(quán)有向圖中存在負權(quán)時，則算法失效圖6-10（a）（b）（c）（d）（e）（f）2逐次逼近算法為方便起見，不妨設(shè)從任一點到任一點都有一條弧，如果在中，不存在弧(，)，則添加虛設(shè)弧(，)，令從起點到任意點

22、的最短路可以視為一個兩階段過程，如圖6-11所示：圖6-11(1)從出發(fā)，沿著一條路走1步到某點，其最短距離表示為(，)(2)再從沿(，)到，其最短距離就是弧(，)上的權(quán) 所以，從到的最短距離必滿足如下遞推公式：(，)（1，2，n） （6-3）(，)(，) （6-4）式（6-3）是任意兩點間的一步距離，由前面假設(shè)可知其存在，這可以作為初始條件式（6-4）是任意兩點間的k步距離，這是一個遞推公式利用初始條件和遞推公式通過逐步迭代就可以確定網(wǎng)絡中任意點之間經(jīng)步到達的最短距離并得到與之相應的路線下面以實例來說明迭代過程例6-8用逐次逼近算法求例6-6圖6-10中從到各點的最短距離解根據(jù)初始條件可知(

23、，)0(，)2(，)5(，)3(，)(，)(，)；初始條件僅僅表達了從出發(fā)到的一步到達的距離，在有向簡單網(wǎng)絡中即為從到各點的最短距離到各點的步距離由公式（6-4）遞推得出為方便、直觀可列表計算如表6-3：表6-3到各點的步距離jvii(，)(，)k=1k=2k=3k=4k=5k=60253000000027222222013554444405333333017877770598880141313表的左半部是一個n×n的關(guān)于結(jié)點兩兩之間的一步距離矩陣，由式（6-3）可知，到的一步距離就是?。?，）上的權(quán)一步距離矩陣中0元素表示原地踏一步，沒有填寫數(shù)字的空格是的省略表右半部是公式（6-4）

24、的計算結(jié)果k=h時，第h+n列數(shù)據(jù)表示到各點的h步最短距離譬如k=3為第 列，表示經(jīng)3步到達各點的最短距離計算過程如下：（1）當k=1時(，)這是初始條件，表示從出發(fā)到各點的一步距離，將其依次列于第 列由此推算(，)（2）k=2時(，)(，)即用表中第 列數(shù)字與表左邊一步距離矩陣中第列相應數(shù)字相加取小，得到從出發(fā)到各點的二步距離：（0 0）（ 2）（ 5）(，)min （ 3） 0（ ）（ ）（ ）（2 0）（0 2）（ 5）(，)min （ 3） 2（ ）（ ）（ ）同理： (，)4(，)3(，)8(，)(，)得：024(，) 38將其填入表6-3第 列（3）重復上述步驟得到(，)、(，)、

25、(，)、(，)；分別填入表6-3第 、 列（4）當k=6時，發(fā)現(xiàn)(，)(，)，說明對于整個有向圖D而言，繼續(xù)增加步數(shù)已不起作用，即已得到從到各點的最短距離，即表中 或 列數(shù)字：0；原地一步2；一步到達4；二步到達3；一步到達7；三步到達 8；四步到達 13；五步到達從表6-3中還可以用回溯方法推知到各點最短距離的相應最短路線，以到為例：由第列行可知，到經(jīng)5步到達，最短距離13回溯13的來源：（，）=13因（，） 列行 列行 （，）8513故記下（，）因（，） 列行 列行 （，）718故記下（，）.因（，） 列行 列行 （，）437故記下（，）因（，） 列行 列行 （，）224故記下（，）因（，

26、）022，記下（，） 得到最短路徑：當網(wǎng)絡圖存在負權(quán)時，Dijkstra算法失效，必須采取逐次逼近算法來求解最短路例6-9試求網(wǎng)絡圖6-12中到各點的距離圖6-12解初始條件：(，)0(，)1(，)(，)2(，)(，)計算結(jié)果如表6-4所示：表6-4到各點的距離vjvi(，)=1=2=3=4=501200000034111-1-1-2051411140-322222330-1-1-1-120求得到各點的最短距離：(，)0；原地一步(，)-1；四步到達(，)1；三步到達(，)2；一步到達(，)-1；二步到達(，)；無法到達逐次逼近算法，因其類似于矩陣乘法，在有些書籍表述為距離矩陣摹乘法，它們的實

27、質(zhì)一致這種算法在n個結(jié)點的網(wǎng)絡圖中，至多經(jīng)過n-1次迭代必然收斂但前提條件是圖中不含有總權(quán)小于0的回路，否則最短路權(quán)沒有下界第四節(jié)最大流問題網(wǎng)絡流(network flow)是一類普遍存在的現(xiàn)象例如在交通運輸網(wǎng)絡中有人流、車流、貨物流；供水網(wǎng)絡中有水流；金融系統(tǒng)中有現(xiàn)金流；通訊系統(tǒng)中有信息流；等等在20世紀50年代Ford和Fulkerson建立的“網(wǎng)絡流理論”是網(wǎng)絡應用的重要組成部分網(wǎng)絡最大流問題(max-flow problem)尤為重要這是因為絕大部分網(wǎng)絡流研究，旨在尋求在一定條件下使網(wǎng)絡流達到最大的方法如圖6-13是輸油管道網(wǎng)，為起點，是終點，為中轉(zhuǎn)站，弧上的數(shù)表示該管道的最大輸油能力

28、，問應如何安排各管道輸油量，才能使從到的總輸油量最大?圖6-13一、基本概念和基本定理1網(wǎng)絡流所謂網(wǎng)絡流，是指在一定的條件下流過一個網(wǎng)絡的某種流在各邊上的流量的集合表達為(，)| (，)所謂一定條件，一般是指如下規(guī)定：(1)網(wǎng)絡有一個始點和一個終點，始點是流的源，終點是流的匯；(2)流具有一定的方向，流經(jīng)各弧的流，其方向就是相應弧的方向；(3)對每一弧(，)，都賦予一個容量(，)0，簡記為，表示容許通過該弧的最大流量并稱(，)為通過弧(，)流，簡記為凡做出上述規(guī)定的網(wǎng)絡都可稱為容量網(wǎng)絡，記為（，）圖6-13所示的就是一個容量網(wǎng)絡圖中每條弧上的數(shù)對為(，)，標明了弧的容量以及流經(jīng)該弧的流量2可行

29、流和最大流可行流是指滿足容量限制條件和平衡條件的流(1)容量限制條件：對于任一弧(，)，都有0，即任何弧上的流量不能超過弧的容量(2)平衡條件：對于任一中間點，都有即每個中間點的流出量必須等于流入量，其凈流量為0對于始點和終點，有即始點流出量等于終點的流入量，這個流量即是可行流的流量，記為（）所謂最大流問題，就是在可行流恒存在的前提下，滿足max () . 0 、0； 這是一個特殊的線性規(guī)劃問題，可用單純形法求解但用圖形方法求解更為直觀和簡單3增廣鏈如果是網(wǎng)絡中聯(lián)結(jié)始點和終點的一條鏈，且鏈的方向從到，則與鏈方向一致的弧稱為前向弧，用來表示前向弧集合；與鏈方向相反的弧稱為后向弧，用來表示后向弧集

30、合如圖6-13中(，)，(，)，(，)(，)，(，)設(shè)是一個可行流，是一條從到的鏈，若滿足下列條件，則是可行流的一條增廣鏈：（1）在弧(，)上， 0；（2）在弧(，)上， 0這就意味著在增廣鏈上每一個前向弧的流量都沒有達到最大容量（即不飽和前向?。?而每一個后向弧的流量均不為0（即非零后向?。┤鐖D6-13中鏈、 、 都是增廣鏈可以指出，沿增廣鏈調(diào)整各弧的流量可以使網(wǎng)絡流量（）增大，而尋求網(wǎng)絡最大流的方法正是以增廣鏈為基礎(chǔ)的4截集與截量在一個網(wǎng)絡(，)中，若把點集V剖分成不相交的兩個非空集合和，使，且中各點不須經(jīng)由中的點而均連通，中各點也不須經(jīng)由中的點而均連通，則把始點在中而終點在中的一切弧所構(gòu)

31、成的集合，稱為一個分離和的截集，記為(，)截集實質(zhì)上是網(wǎng)絡從到通路的橫截面表達，它反映了網(wǎng)絡從到的必經(jīng)之路一個網(wǎng)絡可以有多個截集，表6-5反映了圖6-13網(wǎng)絡的截集集合表6-5圖6-13網(wǎng)絡的截集集合S截集(S，)=(，)截量(S，)s1,2,3,4,t(s,1), (s,2)14s,12,3,4,t(s,2), (1,2), (1,3), (1,4)15s,21,3,4,t(s,1), (2,4)14s,1,23,4,t(1,3), (1,4), (2,4)12s,1,2,32,4,t(s,2),(1,2),(1,4),(3,4),(3,t)19s,2,41,3,t(s,1), (4,t)1

32、6s,1,2,34,t(1,4), (2,4), (3,4), (3,t)16s,1,2,43,t(1,3), (4,t)11s,1,2,3,4t(3,t), (4,t)13給定一截集(，)，其中所有弧的容量之和稱為這個截集的截量，記為(，)|（，）(，)一個網(wǎng)絡可以有多個截集和截量，其中截量最小的截集稱為最小截集，記為(，)，其截量稱為最小截量(min-cut)，記為(，)圖6-13的最小截量由表6-5看出為11，最小截集為(，)(1,3), (4,t)二、基本原理為了介紹一種尋求網(wǎng)絡最大流的標號法，這里將闡述其原理定理6-3（流量截量定理）在網(wǎng)絡=(，)中，設(shè)為一可行流，(，)是任一截集，

33、則（）(，)定理6-3表明，網(wǎng)絡的任一可行流的流量恒不超過任一截集的截量因此，網(wǎng)絡的最大流量也不會超過最小截量定理6-4（最大流量最小截量定理）網(wǎng)絡中從s到t的最大流的流量等于分離s和t的最小截集的截量即，（）(，)定理6-4實際上是定理6-3的推論定理6-5（最大流的充要條件）設(shè)是網(wǎng)絡(，)的一個可行流，則為最大流的充要條件是：網(wǎng)絡中不存在關(guān)于的增廣鏈()定理6-6（增廣鏈調(diào)整法）設(shè)是(V，A，)的一個可行流，是關(guān)于f 的一條增廣鏈令 當 當 當 （6-5） 當min（，）構(gòu)造一個新的可行流，令 當（，） 當（，） （6-6） 當（，）則()也是的一個可行流，其流量為（）（） （6-7）定理

34、6-4表明：只要網(wǎng)絡中還存在關(guān)于可行流的增廣鏈，則就非最大流，起碼其流量還能增大這樣就給出了一種沿著增廣鏈上的各弧去調(diào)整流量，從而得到一個流量增大的新可行流的方法，故稱之為增廣鏈調(diào)整法三、尋求網(wǎng)絡最大流的標號法這種標號法由福特(Ford)和富爾克遜(Fulkerson)于1956年提出，故稱為福特一富爾克遜標號法(Ford- Fulkerson algorithm)1基本算法思想：該法從某一可行流出發(fā)，按一定規(guī)則找出一條增廣鏈()，并按定理8-6的方法調(diào)整，得到一個流量增大的新可行流對重復上述做法直到找不出增廣鏈為止，這時就得到一個最大流，同時還得到一個最小截集2算法步驟（1）給出一個初始可行

35、流初始可行流可以是零流或非零流；（2）標號、檢查過程：給頂點標號，標號用，L()表示，其中第一個分量表示該標號是從哪個點得到的，用以反向追蹤找出增廣鏈，第二個分量是為確定的調(diào)整量用的點標號(0，)，則已標號待檢查；取一個已標號待檢查的點，所謂檢查是對所有與相鄰而未標號的點依次執(zhí)行下述a）、b）兩種考察：a）若聯(lián)結(jié)與的弧(，)為前向弧，則當該弧上的流量小于容量，即時給標號，L()，其中L()min（L()，一）這里L()表示弧(，)上流量的最大可調(diào)整量而當弧(，)上的時，弧(，)是飽和前向弧，則不給標號b）若關(guān)聯(lián)與弧(，)為后向弧，則當該弧上的流量大于零，即0 時給標號-，L()，其中L()mi

36、nL()，而當0時不給標號當所有與相鄰而未標號的點都完成了a）、b）兩種考察后，給打，表示對它的檢查完畢重復，如果終點得到標號，則可以從沿標號點回溯到第一個標號，從而找出一條從到的增廣鏈，轉(zhuǎn)至；如果所有標號點均已打，而t又未得標號這說明不存在關(guān)于當前可行流的增廣鏈，由定理6-3可知當前可行流即最大流，算出流量，計算停止取增廣鏈的流量調(diào)整量L（），對增廣鏈上的流量進行調(diào)整，對增廣鏈上的前向弧，令對增廣鏈上的后向弧，令非增廣鏈上的弧流量不變刪除原有所有標號，返回例6-10用Ford-Fulkerson標號法求圖6-14所示網(wǎng)絡的最大流圖6-14解 第一步：圖中給出了網(wǎng)絡的初始可行流；第二步：首先給

37、s以標號(0，)，此時待查點是，相鄰而未標號的點有、檢查：弧(，)，3，為飽和前向弧，所以不對標號弧(，)，為非飽和前向弧，所以給點標號，L()其中L()min L()，min，51 4.檢查完成，對其打此時有了標號成為待查點，相鄰而未標號的點有、，如圖6-15（a）所示檢查點：弧(，)，為飽和前向弧，所以不對標號.弧(，)，0，為非零流后向弧，所以給標號，L()，其中L()min L()，12min4，1 1.檢查完成，對其打此時完成檢查的點有、，因有了標號成為待查點，相鄰而未標號的點有、如圖6-15（b）所示檢查點：弧(，)，為不飽和前向弧，所以給標號，L()，其中L()min L()，m

38、in1，43 1.弧(，)，為不飽和后向弧，所以給標號-，L()，其中L()min L()，min1，21 1.檢查完成，對其打此時完成檢查的點有、，和因有了標號成為待查點，相鄰而未標號的點有如圖6-15（c）所示.檢查點：弧(，)，為不飽和前向弧，所以給標號，L(),其中L()min L()，min1，53 1.檢查完成，對其打由于已得到標號，已經(jīng)可以得到一條增廣鏈，不需再檢查（如果檢查而不檢查可以得到另一條增廣鏈，可自行驗證）,如圖6-15（d）所示圖6-15（a）、（b）、（c）、（d）第三步：利用各點已標號的第一個分量，從反向追蹤得增廣鏈，如圖6-15（d）中粗箭頭線所示其中前向弧(，

39、)、(，)、(，),后向弧(，).由標號的第二個分量知1，于是在已知增廣鏈上進行調(diào)整： 112 （，） 314 （，） 314 （，） 110 （，） （，）調(diào)整后的可行流如圖6-16所示對這個新的可行流重新在圖中進行標號，尋找新的增廣鏈圖6-16第四步：再標號給以標號(0，)，檢查：弧(，)為飽和前向弧，不標號弧(，)為非飽和前向弧，標號，L()，L()3.檢查：弧(，)為零流后向弧，不標號弧(，)為飽和前向弧，不標號此時已標號的點均已打，而又未得標號，由算法步驟可知網(wǎng)絡中不存在增廣鏈，目前的可行流就是最大流第五步：確定最小截集和最大流量此時已標號且打的點構(gòu)成集，而未標號的點構(gòu)成集，最小截集

40、為(，)如圖6-16所示,，,（，）最小截量(，)最大流量5.第五節(jié) 最小費用流問題在實踐中，人們考慮網(wǎng)絡流問題不僅僅考慮流量，還必須考慮流的費用例如，在運輸網(wǎng)絡中，從發(fā)點到收點所經(jīng)過的路程，往往因為交通工具不同或道路本身結(jié)構(gòu)不同而產(chǎn)生各段路程交通費用不同，這時問題就變成了不僅要求到的一定運輸量，而且要求這種運輸方案的總費用最小這類問題就屬于本節(jié)要介紹的最小費用流問題(min-cost-flow)一、最小費用流算法在給定網(wǎng)絡=(，)中，對每條弧(, )，除已給出弧容量外，還給出單位流量的費用0設(shè)=是中的可行流，其流量總費用為（）=最小費用流問題是考慮在給定可行流量條件下，使得總費用（）最低因此

41、其數(shù)學模型為：()=min在最小費用流問題中，有很大一部分是尋求使（）為最小且流量為最大流的流量方案這是最小費用流的特例問題，稱為最小費用最大流問題1求最小費用流的基本思想是：從零流（）=0的費用有向圖（）開始，先用一定方法尋找關(guān)于的從到的最小費用增廣鏈，并對按FordFulkerson標號法進行流量的調(diào)整，得到一個新的可行流，新的可行流必是最小費用可行流如果()達到流量目標要求，則計算終止否則，重新構(gòu)造關(guān)于的費用有向圖N（），繼續(xù)在（）上求出由到的最小費用增廣鏈，并在上進行流量的調(diào)整，如此下去，直到求出目標流量為的可行流為止如果是最大流的流量，則此最小費用流就是最小費用最大流由此可見，求最小

42、費用流的方法就是求最小費用增廣鏈和求最大流方法的綜合所謂最小費用增廣鏈，即諸多增廣鏈中費用權(quán)之和最小的一條增廣鏈其求算方法要借助于網(wǎng)絡N的輔助賦權(quán)有向網(wǎng)絡2輔助賦權(quán)有向網(wǎng)絡構(gòu)造方法是原圖的輔助圖，構(gòu)造的目的是為了在中尋找關(guān)于最小費用可行流的從到的最小費用增廣鏈構(gòu)造時，總體上是要將N中所有可能的弧流量變動特性集中表現(xiàn)于中，并同時為它們的弧重新賦權(quán)，具體方法如下：設(shè)L（）(，)，其中的，分別是網(wǎng)絡的點集，弧集、弧容量和費用集，它與（，）的關(guān)系如下：(1)頂點集：（L）（），即的頂點即原有的網(wǎng)絡N的頂點(2)弧集及方向和賦權(quán)方法：A集中的零流?。哼@類弧流量的變動只能增加弧流量，這一流變動特性，在原圖

43、中已充分體現(xiàn)，因此在集中，弧的方向與原中的相同，賦權(quán)不變； 集中的飽和弧：這類弧流量的變動只能減少流量，因此在集中，弧的方向與原中的相反，賦權(quán)：；集中的非飽和、非零流?。哼@類弧的流量變動，既可增流又可減流因此在集中，點,之間，應該有正反兩個方向的弧同時存在，其中方向與原中相同的弧(, )上 ，方向與原中相反的弧(,)上，例6-11已知原圖（圖6-17所示），其弧權(quán)的含義為（，），求其輔助賦權(quán)網(wǎng)絡圖6-17解（1）N中零流弧只有一條，在L中該弧的方向、賦權(quán)均不變（2）中飽和流弧也只有一條，在L中該弧的方向相反，賦權(quán)改變：2，4（3）N中非飽非零弧有三條、，這些弧在L中分別有相應的正、反向兩條弧存

44、在，賦權(quán)情況： 523； 2： 2；2： 422； 2： 2；2： 321； 4： 2；4綜上，構(gòu)造原圖N的輔助圖，如圖6-18所示弧旁數(shù)字為（，）圖6-18在中找關(guān)于的從到的最小費用增廣鏈，就等價于在賦權(quán)有向網(wǎng)絡中，找從到的最小費用鏈這樣，就把在N中尋找最小費用增廣鏈問題轉(zhuǎn)化為在中尋找最小費用鏈問題，而這在形式上等同于在中尋找最短路3最小費用流算法步驟第1步：從一流量為（）的初始最小費用可行流開始，(也可以是零流，=0)，在第1步得到最小費用可行流記為 第2步：構(gòu)造輔助賦權(quán)有向網(wǎng)絡L（），并在L（）中求到的最小費用鏈，若不存在最小費用鏈，則此時的即為最小費用最大流(轉(zhuǎn)第4步)；若存在最小費用

45、鏈，則在中得到相應的最小費用增廣鏈 (轉(zhuǎn)第3，流調(diào)整)第3步：在最小費用增廣鏈上按照定理6-6作調(diào)整，得到新的最小費用可行流k，若k已經(jīng)達到目標流量轉(zhuǎn)第4步，否則轉(zhuǎn)第2步，重復第4步：停止運算，并輸出當前最小費用可行流，作為中的最小費用最大流；或輸出當前最小費用可行流流量作為中流量（）的最小費用流二、實例例6-12試求圖6-19網(wǎng)絡（）7的最小費用流和最小費用最大流（弧旁的數(shù)字為（，），其中表示弧容量，表示單位物質(zhì)運費）圖6-19解（一）求流量為7的最小費用流（1）因為原圖流量0，故先利用Dijkstra標號法對圖6-19的網(wǎng)絡求最小費用鏈，顯然這時的最小費用鏈即是最小費用增廣鏈：，如圖6-2

46、0（a），調(diào)整量min（）， =7，5，5，7，5=5，按照定理6-6對上的各弧進行流量調(diào)整，調(diào)整后上各弧流量：，同時（）055如圖6-20（b）（2）在圖6-20（b）中尋找從到的最小費用增廣鏈為此對圖6-20（b）作輔助賦權(quán)有向網(wǎng)絡L（）：A集中：， 均為零流弧；A集中相應的弧不變A集中：，均為飽和前向??；A集中相應的弧方向反轉(zhuǎn)，賦權(quán)A集中：，均為不飽和前向弧；A集中相應的弧不變，添加反方向的弧并賦權(quán)得到圖6-20（c）圖6-20（c）是圖6-20（b）的輔助賦權(quán)有向網(wǎng)絡，其構(gòu)造目的是尋找圖6-20（b）中有關(guān)的從到的最小費用增廣鏈，我們知道等價于圖6-20（c）中的從到的最小費用鏈（或最

47、短路）求圖6-20（c）的最短路：由于圖6-20（c）含有負權(quán)，不能使用Dijkstra標號法，可以用逐次逼近法求得圖6-20（c）網(wǎng)絡的最小費用鏈：，如圖6-20（c）中粗線所示；也是圖6-20（b）中關(guān)于的從到的最小費用增廣鏈回到圖6-20（b），對進行調(diào)整：min（），ij （）min（75），（70），（150）2調(diào)整后上各弧的流量為：，同時（）（）527，如圖6-20（d）所示（3）作圖6-20（d）的輔助賦權(quán)有向網(wǎng)絡（如圖6-20（e）所示），其中不存在負回路，證明圖6-20（d）所示的網(wǎng)絡流是=7的最小費用可行流(這里不加證明地引入為中流量為的最小費用流的判別條件：為中流量為的最

48、小費用流的充要條件是，相應的中沒有負回路即中的任意回路C，有0)（二）求圖6-19的最小費用最大流承接以上結(jié)果對圖6-20（e）所示網(wǎng)絡，求其最小費用鏈得為 ，5，（）12調(diào)整后上各弧的流量為：，如圖6-20（f）所示對圖6-20（f）所示網(wǎng)絡作輔助賦權(quán)有向網(wǎng)絡如圖6-20（g），求其最小費用鏈得為 ，5，（）17調(diào)整后上各弧的流量為：，得到圖6-20（h）所示網(wǎng)絡對圖6-20（h）所示網(wǎng)絡作輔助賦權(quán)有向網(wǎng)絡圖，其中不存在從到的通路，說明圖6-20（h）所示網(wǎng)絡流為最小費用最大流圖6-20（a）（b）（c）（d）（e）（f）（g）（h）第六節(jié)網(wǎng)絡計劃（統(tǒng)籌方法）網(wǎng)絡計劃（Network Pla

49、nning）是一種計劃管理的科學方法，它是編制大型工程進度計劃的有效工具對于計劃人員清楚地掌握整個工程進度，預見可能發(fā)生的問題，協(xié)調(diào)和控制各項活動，達到合理組織，統(tǒng)籌安排，使工程任務能順利地按期或提前完成，起到了重要的作用已故著名數(shù)學家華羅庚先生將這些方法總結(jié)概括為統(tǒng)籌方法一、統(tǒng)籌圖的基本概念和基本規(guī)則統(tǒng)籌圖（project diagram）也可稱為工序流程圖，它可以直觀地反映組成管理的各項活動及其相互間的內(nèi)在關(guān)系正確、完備、詳盡的統(tǒng)籌圖是網(wǎng)絡計劃工作必不可少的前提和工具(一)工程的分解及工序間的關(guān)系工序：根據(jù)工藝技術(shù)和組織管理上的需要，將工程劃分為按一定順序執(zhí)行而又相對獨立的若干項活動，這些活動稱為工序在統(tǒng)籌圖上，工序k用箭線 “”表示工序也可以用（，）表