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

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

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

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

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

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

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

7、任一條邊是的一個(gè)有序元素對(，)(這里，)，則稱為有向邊集，中元素稱為有向邊或弧，記為(，)其中為的起點(diǎn)，為的終點(diǎn)和組成了一個(gè)有向圖，記作（，）例6-4 給有向圖（，），其中（，），（，），邊與頂點(diǎn)的關(guān)聯(lián)情況如表6-2所給表6-2 邊與頂點(diǎn)的關(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ù)語：平行邊不同的弧與(，)的起點(diǎn)與終點(diǎn)都相同圖6-4（a）中、

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

31、成的集合，稱為一個(gè)分離和的截集，記為(，)截集實(shí)質(zhì)上是網(wǎng)絡(luò)從到通路的橫截面表達(dá)，它反映了網(wǎng)絡(luò)從到的必經(jīng)之路一個(gè)網(wǎng)絡(luò)可以有多個(gè)截集，表6-5反映了圖6-13網(wǎng)絡(luò)的截集集合表6-5圖6-13網(wǎng)絡(luò)的截集集合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給定一截集(，)，其中所有弧的容量之和稱為這個(gè)截集的截量，記為(，)|（，）(，)一個(gè)網(wǎng)絡(luò)可以有多個(gè)截集和截量，其中截量最小的截集稱為最小截集，記為(，)，其截量稱為最小截量(min-cut)，記為(，)圖6-13的最小截量由表6-5看出為11，最小截集為(，)(1,3), (4,t)二、基本原理為了介紹一種尋求網(wǎng)絡(luò)最大流的標(biāo)號法，這里將闡述其原理定理6-3（流量截量定理）在網(wǎng)絡(luò)=(，)中，設(shè)為一可行流，(，)是任一截集，

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

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

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

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

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

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

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

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

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

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

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

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)于的從到的最小費(fèi)用增廣鏈，就等價(jià)于在賦權(quán)有向網(wǎng)絡(luò)中，找從到的最小費(fèi)用鏈這樣，就把在N中尋找最小費(fèi)用增廣鏈問題轉(zhuǎn)化為在中尋找最小費(fèi)用鏈問題，而這在形式上等同于在中尋找最短路3最小費(fèi)用流算法步驟第1步：從一流量為（）的初始最小費(fèi)用可行流開始，(也可以是零流，=0)，在第1步得到最小費(fèi)用可行流記為 第2步：構(gòu)造輔助賦權(quán)有向網(wǎng)絡(luò)L（），并在L（）中求到的最小費(fèi)用鏈，若不存在最小費(fèi)用鏈，則此時(shí)的即為最小費(fèi)用最大流(轉(zhuǎn)第4步)；若存在最小費(fèi)用

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

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

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

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

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