運籌學交通運輸專業(yè)規(guī)劃教材17十一月2025第2頁下篇

本篇包含圖與網(wǎng)絡、統(tǒng)籌方法、排隊論、存儲論四個方面的內容。在圖與網(wǎng)絡中，首先給出了圖的相關概念及其相關知識，在此基礎上，給出了網(wǎng)絡的概念以及相關知識。針對賦有權的網(wǎng)絡，介紹了此類網(wǎng)絡的三個應用問題，即最短路徑問題、最小生成樹問題、中國郵路問題；針對賦有容量、流量的網(wǎng)絡，介紹了網(wǎng)絡流的相關知識，然后重點介紹了此類網(wǎng)絡的最大流問題及其算法；針對賦有容量、流量和權的網(wǎng)絡，介紹了此類網(wǎng)絡的最小費用流問題及其算法、最小費用最大流問題及其算法。最后為了擴展運用思路，介紹了復雜問題的網(wǎng)絡應用，主要包括有條件限制的網(wǎng)絡極值應用、有條件要求的網(wǎng)絡流應用、網(wǎng)絡的擴展應用問題。17十一月2025第3頁下篇

在統(tǒng)籌方法中，首先給出了統(tǒng)籌圖的概念以及統(tǒng)籌圖的繪制規(guī)則，同時介紹了統(tǒng)籌圖的關鍵路線問題，在此基礎上介紹了確定關鍵路線的方法即時間參數(shù)法；針對工程費用，介紹了如何制定最少工程費方案問題；另外，針對非確定型統(tǒng)籌問題也作了一定的介紹。在排隊論中，首先介紹了排隊論的組成、特征以及排隊模型的表示方法，通過對隨機過程基礎知識的介紹，給出了幾個主要的馬爾可夫排隊模型及愛爾朗排隊模型；另外，給出了關于定長分布和一般分布的兩個排隊模型。最后初步介紹了排隊系統(tǒng)的最優(yōu)決策問題。在存儲論中，首先給出了存儲論的基本概念，針對確定型存儲問題，分別介紹了簡單經濟訂貨存儲模型、經濟生產批量存儲模型、具有附加條件的存儲模型中幾個比較常見的確定型存儲模型。另外，針對隨機型存儲問題，基于隨機變量的離散性和連續(xù)性，介紹了幾個比較常見的隨機型存儲模型。17十一月2025第4頁下篇

1.圖論與網(wǎng)絡3.排隊論4.存儲論2.統(tǒng)籌方法（3）運輸網(wǎng)絡問題隨機服務系統(tǒng)（隨機過程）（1）基本知識（2）常見模型*排隊最優(yōu)化確定性存儲模型隨機存儲模型（1）圖的基本概念（2）網(wǎng)絡規(guī)劃問題確定型統(tǒng)籌問題：（1）統(tǒng)籌圖概念、規(guī)則（2）關鍵路線（3）時間參數(shù)及其計算主要內容17十一月2025第5頁第9章圖與網(wǎng)絡

在日常生活和工作中，經常會遇到各種各樣的圖或網(wǎng)絡，如一個國家或地區(qū)的地圖、國家鐵路運輸網(wǎng)、城市交通網(wǎng)、工程圖、電信公司鋪設的光纖網(wǎng)、自來水管道網(wǎng)等等。如果對某項工程的有關分析、決策等只是在實體上進行，那將會非常困難，這就需要把現(xiàn)實中的實體抽象成一種既簡單而且又可以量化的圖形。如何將現(xiàn)實中的實體抽象成可以量化的圖或網(wǎng)絡、如何對圖或網(wǎng)絡進行設計以及如何對圖或網(wǎng)絡進行分析等就是應用比較廣泛的一個數(shù)學分支——圖論。本章所介紹的圖及網(wǎng)絡是圖論的有關知識，它的理論和方法在許多領域得到廣泛的應用。17十一月2025第6頁第9章圖與網(wǎng)絡

圖及網(wǎng)絡對實際問題描述具有直觀性，可以將一些復雜的問題用圖或網(wǎng)絡的形式刻畫出來，所以前面章節(jié)介紹的一般線性規(guī)劃問題、運輸問題、整數(shù)規(guī)劃以及動態(tài)規(guī)劃等有時可以用圖論或網(wǎng)絡的方法來解決。圖論內容十分豐富，涉及面也比較廣。在圖基礎上產生的網(wǎng)絡規(guī)劃也是數(shù)學規(guī)劃理論的重要分支，網(wǎng)絡規(guī)劃是尋求系統(tǒng)最優(yōu)的決策，即對網(wǎng)絡模型尋求最優(yōu)解。本章介紹的圖與網(wǎng)絡的理論和算法，是實際生活、生產和科研工作中經常用到的。首先學習一些有關圖的相關知識以及網(wǎng)絡的基本概念，在此基礎上，主要學習網(wǎng)絡圖的應用問題，即研究網(wǎng)絡規(guī)劃問題。主要包括：最短路問題最小生成樹問題中國郵路問題最大流問題最小費用流問題最小費用最大流問題17十一月2025第7頁第9章圖與網(wǎng)絡

數(shù)學分支，可以解決線性規(guī)劃等問題圖的基本概念鏈、路、路徑、回路、連通性等圖圖的矩陣表示圖的相關運算

樹及生成樹有向圖無向圖關聯(lián)矩陣鄰接矩陣§9.1圖的相關知識17十一月2025第8頁第9章圖與網(wǎng)絡

§9.1.1圖的基本概念

引例1:格尼斯堡七橋問題一個人能否從某地點出發(fā)，一次把七座橋不重復的都走過一遍，最后又回到原地？CADBCADBAB17十一月2025第9頁第9章圖與網(wǎng)絡

引例2:

某大學創(chuàng)新協(xié)會共有7名同學，這7名同學中有的已經認識，有的還不認識，為了明確表明這7名同學之間的認識關系，現(xiàn)在用下圖描述，其中用v1、v2、v3、v4、v5、v6、v7分別表示七名同學，用邊表示他們是否認識v2v6v5v4v7v1v3例如，通過圖可知：v1和v2之間的邊就表示這兩個點代表的兩名同學是認識的，而v3和v4之間沒有邊，則說明這兩個點代表的同學是不認識的。17十一月2025第10頁第9章圖與網(wǎng)絡

引例3:假設下圖是我國某地區(qū)幾座城市之間的高速公路交通示意圖，它反映了這幾座城市之間高速公路的連接情況，其中點代表城市，點與點之間的邊代表兩座城市之間的高速公路。v2v3v4v5v1由以上三個例子可以看出，一般的圖都具有兩個要素，即點和邊。把現(xiàn)實問題抽象為圖的方法是，用點表示現(xiàn)實中的對象。用邊表示對象和對象之間的關系，若對象和對象之間有關系，就用邊把表示對象的點連接起來，直觀的描述如右圖所示。關系對象對象17十一月2025第11頁第9章圖與網(wǎng)絡

自然語言的描述就是：圖是由表示具體事物的對象（頂點）集合和表示事物之間的關系（邊）集合組成。例如針對鐵路網(wǎng)，邊表示區(qū)段，頂點表示區(qū)段間的車站；針對城市道路網(wǎng)，邊表示道路，頂點表示交叉口。如果用G表示圖，用vi表示點，用V表示所有點的集合，用ei表示邊，用E表示所有邊的集合，則圖的數(shù)學語言描述就是G=(V,E)，其中V=(v1,v2,…,vn)，E=(e1,e2,…,em)。另外圖G的頂點集合與邊集合也可分別用V(G)和E(G)表示。根據(jù)邊有無方向，將圖分為無向圖、有向圖和混合圖，所有邊都是無向邊的圖稱為無向圖；所有邊都是有向邊的圖稱為有向圖；既有有向邊又有無向邊的圖一般稱為混合圖。鑒于混合圖的復雜現(xiàn)象，本教材不考慮混合圖的相關問題。17十一月2025第12頁第9章圖與網(wǎng)絡

無向圖定義：存在圖G=(V,E)，其中V是一個有n個頂點的非空集合，即V=(v1,v2,,…,vn)，E是一個有m條邊的非空集合，即E=(e1,e2,…,em)，若E中任意一條邊e是V的無序元素對(vi,vj)，其中i≠j，即可以有(vi,vj)=(vj,vi)，則稱圖G為無向圖，見右圖。v1v2v3v4v5如果把無向邊用元素對表示，那么邊(vi,vj)和邊(vj,vi)是同一條邊，vi和vj稱為該無向邊的端點，其中無向邊與端點（頂點）vi和vj相關聯(lián)，頂點vi和vj相鄰，如上圖中的邊（v2,v4）和(v4,v2)屬于同一條邊，頂點v2和v4為該無向邊的端點。17十一月2025第13頁第9章圖與網(wǎng)絡

有向圖定義：存在圖G=(V,E)，其中V是一個有n個頂點的非空集合，即V=(v1,v2,…,vn)，E是一個有m條邊的非空集合，即E=(e1,e2,…,em)，若E中任意一條邊e是V的有序元素對(vi,vj)

，其中i≠j，即(vi,vj)≠(vj,vi)，稱圖G為有向圖，見右圖v1v2v3v4v5如果把有向邊用元素對表示，那么邊(vi,vj)和邊(vj,vi)就不是同一條邊，針對邊(vi,vj)來說，頂點vi稱為該有向邊的起點，頂點vj稱為該有向邊的終點；但針對邊(vj,vi)來說，頂點vj為該有向邊的起點，頂點vi為該有向邊的終點，如上圖中有向邊(v2,v4)和(v4,v2)就不是同一條邊，頂點v2和v4為邊(v2,v4)的起點和終點，但為邊(v4,v2)的終點和起點。17十一月2025第14頁第9章圖與網(wǎng)絡

§9.1.2圖的相關術語

圖既然分為無向圖和有向圖，所以將分別介紹無向圖和有向圖的有關術語，需要注意的是，針對無向圖和有向圖，盡管有一些術語的名稱和表述相同，但要注意本質上會有一些差別。一無向圖相關術語

平行邊：無向圖G中有相同端點的邊稱為平行邊，如無向圖

v2和v4中間的兩條邊簡單圖：如果無向圖G中無平行邊，圖G也稱為簡單圖，如右圖即為簡單圖v2v3v4v5v1v1v2v3v4v517十一月2025第15頁完備圖：在無向圖G中，若任意兩個端點之間有且僅有一條邊，圖G也稱為完備圖。如下左圖即為完備圖：v1v2v3v4鏈：無向圖G中，兩個端點之間的連接路徑稱為鏈，如上右圖中，v1和v5之間的連接路徑v1v2v4v3v5即為鏈；一條鏈的起始端點和終止端點不為同一個端點的鏈稱為開鏈，否則稱為閉鏈，在上右圖中，鏈v1v2v4v3為開鏈，鏈v1v2v4v3v1為閉鏈v1v2v3v4v5第9章圖與網(wǎng)絡

17十一月2025第16頁初等鏈：在無向圖G中，如果一條鏈中沒有重復的頂點，則此鏈稱

為初等鏈。v1v2v3v4v5如在下面兩個相同的圖中，鏈v1v3v4v2v3v5不是初等鏈，因為有重復的頂點v3，而鏈v1v2v4v3是初等鏈。v1v2v3v4v5第9章圖與網(wǎng)絡

17十一月2025第17頁路：針對無向圖G的一條鏈，若鏈中的每個點都不相同，則稱這條鏈為連接鏈的起點和終點的路，如下圖中鏈v1v2v4v3v5也稱為路。回路：在一個無向圖的閉鏈中，如果除了起始端點和終止端點相同外，沒有相同的頂點和相同的邊，則此閉鏈也稱為回路。如上圖中，閉鏈v1v2v4v3v1是回路，而閉鏈v1v2v4v3v2v1就不是回路，因為有相同的頂點v2和相同的邊(v1,v2)v1v2v3v4v5v1v2v3v4v5第9章圖與網(wǎng)絡

17十一月2025第18頁連通圖：若無向圖G中任意兩點都能連通，則稱無向圖G為連通圖，否則稱為分割圖。連通圖中不存在任何孤立的頂點，即一個圖中任意兩點之間至少存在一條鏈。同構圖：把結構相同一樣，頂點的標識、位置及連接線的長短曲直可能不同的兩個的圖互稱為同構圖，如下圖互為同構圖。v1v2v3v4v1v4v2v3另外，假設Q為連通的無向圖G的一條鏈，若圖G中每一條邊在鏈Q中恰好出現(xiàn)一次，則稱鏈Q為歐拉鏈；若歐拉鏈是閉鏈，則該歐拉鏈也稱為歐拉環(huán)游；若連通的無向圖G中含有一條歐拉環(huán)游，則把圖G也稱為歐拉圖。第9章圖與網(wǎng)絡

17十一月2025第19頁第9章圖與網(wǎng)絡

二有向圖相關術語

平行邊：在有向圖G中，起點和終點都相同的邊稱為平行邊，如下左圖中，頂點v2和v4之間的兩條邊即為平行邊。v1v2v3v4v5簡單圖：若有向圖G中無平行邊，圖G也稱為簡單圖。完備圖：若有向圖G中，任意兩個頂點之間恰好有兩條非平行的有向邊，則圖G稱為完備圖，如上右圖即為完備圖。v1v4v2v317十一月2025第20頁基本圖：去掉有向圖G中所有有向邊的方向，就能得到一個無向圖G*，此無向圖G*稱為有向圖G的基本圖。同構圖：若有向圖之間的頂點和邊相互都能一一對應，則這些圖互為同構圖。初等鏈：有向圖G的基本圖G*中的初等鏈也稱為有向圖G的初等鏈。路：針對有向圖G的一條鏈，若鏈中每個點都不相同，則稱這條鏈為連接該鏈起點和終點的路，如右圖中鏈v1v3v4v2稱為路。回路：起點和終點重合的路稱為回路，如右圖路v1v3v4v2v1稱為回路第9章圖與網(wǎng)絡

v1v2v3v4v517十一月2025第21頁第9章圖與網(wǎng)絡

§9.1.3圖的相關運算設圖G=(V,E)、G1=(V1,E1)，若V1

V，E1

E，則稱G1為G的子圖，記為G1

G；當G1

G且G1≠G時，稱G1為G的真子圖，記為G1

G；當G1

G并且V1=V時，稱G1為G的生成子圖。如下中圖就是下左圖的真子圖，下右圖就是下左圖的生成子圖。v1v2v3v4v1v2v3v1v2v3v4對圖通?？梢赃M行并、交、差的相關運算17十一月2025第22頁設圖G1=(V1,E1)、圖G2=(V2,E2)和圖G=(V,E)，下面給出相關運算：并運算：針對G1∪G2=G，有V(G)=V(G1∪G2)=V1∪V2，E(G)=E(G1∪G2)=E1∪E2。如下圖體現(xiàn)了圖的并運算v1v2v3圖G1v2v3v4圖G2v1v2v3v4圖G1∪G2第9章圖與網(wǎng)絡

17十一月2025第23頁交運算：針對G1∩G2=G，則有E(G)=E(G1∩G2)=E1∩E2，而V(G)=V(G1∩G2)則為圖G1和圖G2的E1∩E2中邊的全體端點。如下圖體現(xiàn)了圖的交運算。v1v2v3v4圖G1v1v2v3圖G1∩G2圖G2v1v2v3v4第9章圖與網(wǎng)絡

17十一月2025第24頁差運算：針對G1-G2=G，則有E(G)=E(G1-G2)=E1-E2，而V(G)=V(G1-G2)則為圖G1和圖G2的E1-E2中邊的全體端點，如下圖體現(xiàn)了圖的差運算。v2v3v4圖G2圖G1v1v2v3v4v1v2v3圖G1-G2第9章圖與網(wǎng)絡

17十一月2025第25頁第9章圖與網(wǎng)絡

§9.1.4樹及生成樹

無回路并且能連通的無向圖G稱為樹，記為T=(V,E)，樹中的邊稱為枝；若圖T是無向圖G的生成子圖，并且T又是樹，則稱圖T是無向圖G的生成樹。樹T滿足V(T)=V(G)，E(T)

E(G)，也就是說生成樹是把原圖上的頂點以最少的邊而連接起來的樹。由于邊的取法不同，同一個圖可以有很多生成樹，如下中圖和下右圖就是下左圖的部分生成樹

17十一月2025第26頁第9章圖與網(wǎng)絡

針對一個圖如何尋找生成樹有一定的方法，這里介紹兩種方法即破圈法和避圈法。尋找圖的生成樹方法如下：（1）破圈法（Kruskal算法，也稱去邊法）破圈法就是在圖G中任取一個回路，從所取的回路中去掉一條邊，如此反復進行，直到圖G中無回路為止，余下的子圖即為原圖G的生成樹。（2）避圈法（也稱著色法或重繪法）在圖G中任取一邊ei，找不與邊ei構成回路的邊ej，再找不與邊ei和邊ej構成回路的邊ek，如此反復進行，直到不能進行為止。17十一月2025第27頁第9章圖與網(wǎng)絡

§9.1.5圖的矩陣表示圖可以用幾何的形式存儲到計算機系統(tǒng)中，但計算機針對圖的運用、決策等需要時，就面臨著數(shù)據(jù)計算的問題，這就涉及到數(shù)據(jù)和圖互相轉換的處理方法。即把圖轉換為數(shù)據(jù)的形式，然后存儲到計算機系統(tǒng)中，反之，可以把計算機系統(tǒng)中的數(shù)據(jù)轉換成幾何形式的圖形，而矩陣就是數(shù)據(jù)和圖互換時比較可用的方式。無論無向圖還是有向圖，都可以用關聯(lián)矩陣或鄰接矩陣的形式表示出來。有了關聯(lián)矩陣和鄰接矩陣，就可以把圖以數(shù)據(jù)的形式存儲在計算機系統(tǒng)中，反過來，可以根據(jù)計算機系統(tǒng)中的數(shù)據(jù)矩陣，按照一定的方法把圖繪制出來。本節(jié)分別介紹無向圖和有向圖的關聯(lián)矩陣和鄰接矩陣的表示方法。17十一月2025第28頁第9章圖與網(wǎng)絡

一無向圖的矩陣表示1無向圖的關聯(lián)矩陣

e1…ej

…em矩陣數(shù)值aij規(guī)則：aij=0，頂點vi與邊eij不關聯(lián)1，頂點vi與邊eij關聯(lián)17十一月2025第29頁示例：寫出右圖的關聯(lián)矩陣v1v2v3v4v5e1e2e3e4e5e6e7特點：（1）第i行中1的個數(shù)就是與頂點vi相連接的邊的數(shù)量。（2）第j列中1的個數(shù)恒為2，因為每條邊只有2個端點。第9章圖與網(wǎng)絡

e1

e2

e3

e4

e5

e6

e717十一月2025第30頁2無向圖的鄰接矩陣v1…

vj

…

vn矩陣數(shù)值aij規(guī)則：aij表示頂點vi和vj之間邊的數(shù)量鄰接矩陣刻畫了無向圖G的頂點之間邊的連接數(shù)量情況。第9章圖與網(wǎng)絡

17十一月2025第31頁示例：寫出右圖的鄰接矩陣v1v2v3v4v5e1e2e3e4e5e6e7v1

v2

v3

v4

v5

特點：（1）對角線上的元素均為0，同時鄰接矩陣也是對稱矩陣。（2）每行或每列上的數(shù)據(jù)之和就是對應頂點上邊的數(shù)量。（3）一般來說鄰接矩陣比關聯(lián)矩陣小。第9章圖與網(wǎng)絡

e1

e2

e3

e4

e5

e6

e7e8

17十一月2025第32頁第9章圖與網(wǎng)絡

一有向圖的矩陣表示1有向圖的關聯(lián)矩陣與無向圖的關聯(lián)矩陣形式一樣，但數(shù)值aij規(guī)則為：e5v1v2v3v4v5e1e2e3e4e7e8e6特點：（1）第i行中1的個數(shù)就是以頂點vi為起點的邊的數(shù)量，-1的

個數(shù)就是以頂點vi為終點的邊的數(shù)量。（2）第j列中的元素之和恒為0。17十一月2025第33頁2有向圖的鄰接矩陣有向圖的鄰接矩陣與無向圖鄰接矩陣唯一不同的是：aij的值是以頂點vi為起點，以頂點vj為終點的邊的數(shù)量e5v1v2v3v4v5e1e2e3e4e7e8e6v1

v2

v3

v4

v5

特點：（1）對角線上的元素均為0。（2）第i行中的元素之和就是以頂點vi為起點的有向邊的數(shù)量。（3）第j列中的元素之和就是以頂點vj為終點的有向邊的數(shù)量。（4）同樣鄰接矩陣比關聯(lián)矩陣小。第9章圖與網(wǎng)絡

17十一月2025第34頁第9章圖與網(wǎng)絡

§9.2網(wǎng)絡的相關知識

通過圖G=(V,E)的概念可知，圖是由點和邊組成，點表示現(xiàn)實世界中的對象，邊表示對象之間的關系，但在圖的定義中，對所謂的關系沒有進行量化，即對象之間的關系是何種關系、關系的程度又如何等等都沒有系統(tǒng)的涉及。為了更深入地利用圖解決現(xiàn)實中的問題，就需要對圖中的邊甚至圖中的點進行量化，也就是說，只要現(xiàn)實中的問題具有可描述的對象，而且這些對象之間有著一種關系，那么對這種關系就可以進行量化，即把現(xiàn)實中的對象和關系描繪成圖以后，在圖的基礎上，把圖中的邊或點賦上表示一定意義的數(shù)量指標，這個數(shù)量指標稱為權，這樣就可以把現(xiàn)實的問題通過圖轉化成網(wǎng)絡。17十一月2025第35頁第9章圖與網(wǎng)絡

對于網(wǎng)絡，人們在現(xiàn)實生活中并不陌生，比如常說的交通網(wǎng)、公交網(wǎng)、水網(wǎng)、管網(wǎng)、電網(wǎng)、信息網(wǎng)等等，在理論上所謂的網(wǎng)絡即是賦有權的圖，有時人們不加區(qū)別地統(tǒng)稱圖、網(wǎng)絡、網(wǎng)絡圖或賦權圖。網(wǎng)絡和圖最大的區(qū)別在于網(wǎng)絡具有表示權的數(shù)值。針對不同的現(xiàn)實問題，權就有不同的意義，權可以表示現(xiàn)實中的距離、費用、時間、成本、交通流量、水流量、電流量、公交乘客流、運輸物資流等等。研究網(wǎng)絡的目的就是如何利用網(wǎng)絡解決現(xiàn)實的問題，根據(jù)賦權的不同，網(wǎng)絡就有不同的應用。在后面的網(wǎng)絡理論中，主要講解網(wǎng)絡極值問題和網(wǎng)絡流問題，其中網(wǎng)絡極值問題主要包括最短路徑問題、最小生成樹問題以及中國郵路問題等；網(wǎng)絡流問題主要包括最大流問題、最小費用流問題以及最小費用最大流問題。另外，為了解決現(xiàn)實中的復雜問題，最后針對性地介紹一些網(wǎng)絡的靈活運用問題。17十一月2025第36頁第9章圖與網(wǎng)絡

網(wǎng)絡極值網(wǎng)絡理論網(wǎng)絡流問題網(wǎng)絡的靈活運用問題最短路徑問題最小生成樹問題中國郵路問題最大流問題最小費用流問題最小費用最大流問題17十一月2025第37頁第9章圖與網(wǎng)絡

§9.3網(wǎng)絡極值問題在實際的工作或生活中，往往會遇到需要解決網(wǎng)絡極值問題，如貨物的布局、公交網(wǎng)站點規(guī)劃、城市自來水網(wǎng)鋪設、安全巡游等一系列的網(wǎng)絡極值問題，為了利用網(wǎng)絡把這些問題更好的刻畫出來，下面給出網(wǎng)絡極值的數(shù)學定義。給定圖G=(V,E)，其中V=(v1,v2,…,vn)，E=(e1,e2,…,em)，現(xiàn)在把圖G的每條邊都賦予一個非負的實數(shù)，即wi=w(ei)或wij=w(vi,vj)，這個非負的實數(shù)稱為權。在圖G的基礎上，就有了關于極值的網(wǎng)絡定義G=(V,E,W)，其中W=(w1,w2,…,wm)，根據(jù)此定義，具有極值的網(wǎng)絡圖中的邊就有了如下的形式：vivjwij無向網(wǎng)絡中的邊vivjwij有向網(wǎng)絡中的邊17十一月2025第38頁第9章圖與網(wǎng)絡

下面的圖分別為無向網(wǎng)絡和有向網(wǎng)絡。4v1v2v3v4v5342523v1v2v3v4v5532314有了關于極值的網(wǎng)絡定義，就可以研究和解決現(xiàn)實中的最短路徑問題、最長路徑問題、最小生成樹問題及中國郵路問題等。17十一月2025第39頁第9章圖與網(wǎng)絡§9.3.1最短路徑問題實際問題中，經常會遇到運輸管理、管道鋪設、交通網(wǎng)優(yōu)化、物流調配、費用（成本）核算、工程進度等問題，這就需要解決出行距離最小、花費成本最低、距離最短、最優(yōu)路徑等一系列網(wǎng)絡圖尋優(yōu)問題，對這些類似問題可以用“最短路徑”來表述，有時簡稱為最短路。最短路問題是圖論的核心問題之一，也是網(wǎng)絡規(guī)劃的一個基本問題，無向網(wǎng)絡和有向網(wǎng)絡都有對應的最短路徑問題。所謂最短路就是從網(wǎng)絡中一點尋求到其它點的最短的路，具體什么是最短路，簡言之最短路就是從網(wǎng)絡中某一點到另外一點的所有路中，所有邊的權之和最小的路，把路中所有邊的權代數(shù)和稱為路長。如果用P來表示網(wǎng)絡中從點vs到點vt的一條路，用W(P)來表示該路的路長，若P*也為網(wǎng)絡中從點vs到點vt的路，并且滿足W(P*)=min{W(P)|P為網(wǎng)絡中從點vs到點vt的路}，則P*即是點vs到點vt路的最短路。17十一月2025第40頁第9章圖與網(wǎng)絡

為了對最短路有更具體和更形象的認識，下面給出一個例題。例假設下圖為規(guī)劃論證的某一城市區(qū)域內可以開通公交的公交線網(wǎng)，頂點表示?？空荆叡硎镜缆?，邊旁數(shù)據(jù)表示道路長度，某公交公司準備在起始站v1和終點站v8之間開通一條距離最短的公交線路，現(xiàn)在需要確定這條公交線路的走向。4v1v2v3v4v515v7v6v83516273722117十一月2025第41頁第9章圖與網(wǎng)絡

針對此問題最容易想到的求解思路就是，設法把從v1到v8的所有路都找出來，然后再計算每條路中關于邊的權的代數(shù)和即路長，最后取路長最小的路作為所求的最短路，即有如下過程：路v1→v2→v5→v6→v8，其長度為1+5+7+1=14；路v1→v2→v4→v6→v8，其長度為1+3+3+1=8；路v1→v2→v5→v4→v6→v8，其長度為1+5+6+3+1=16；……………………路v1→v3→v7→v8，其長度為4+2+2=8；路v1→v3→v7→v6→v8，其長度為4+2+2+1=9。通過比較可以知道最短路為v1→v2→v4→v6→v8和v1→v3→v7→v8，路長為8。即可以按照v1→v2→v4→v6→v8或v1→v3→v7→v8的走向開通一條距離最短的公交線路。17十一月2025第42頁第9章圖與網(wǎng)絡

上面例子的求解過程采用的是全枚舉法，這種方法雖然很明了，但是過程繁瑣，而且容易出錯，尤其是對一些稍微復雜的網(wǎng)絡，這樣的算法幾乎很難實現(xiàn)，因為點或邊很多的網(wǎng)絡，網(wǎng)絡中的路就會很多，而且在現(xiàn)實中遇到的網(wǎng)路幾乎都是相對復雜的網(wǎng)路，所以就需要有更方便、簡潔的算法求最短路問題。最短路的求解算法很多，主要有Dijkstra算法、Bellman-Ford算法以及SPFA算法等等，這些算法是許多更深層算法的基礎。在目前使用比較普遍而且得到公認的經典算法就是E.W.Dijkstra在1959年提出的最短路求解算法，簡稱為Dijkstra算法。這個算法另外一個特點就是，不僅能求出某點到另外一點的最短路，也能求出某點到網(wǎng)絡中其它各個點的最短路。下面對Dijkstra算法的相關內容進行介紹。一Dijkstra算法思想在網(wǎng)絡圖G中，假設從頂點v1到頂點vn的最短路徑P為v1…vi…vn，那么從v1沿著路徑P到vi的路徑P1也是v1到vi的最短路，也就是說，P不僅是起點v1到終點vn的最短路，而且由v1到路徑P上任意一個中間點vi的最短路P1也在路徑P上。

17十一月2025第43頁第9章圖與網(wǎng)絡

設從vi沿著路徑P到vn的路徑為P2，那么就有W(P)=W(P1)+W(P2)；利用反證法，反設從v1到vi的最短路不是路徑P1，而是另外一條路徑P'，即有W(P')＜W(P1)，這也就有W(P')+W(P2)＜W(P1)+W(P2)，此時出現(xiàn)了W(P′)+W(P2)＜W(P)，這就說明從v1到vn的最短路不是路徑P，而是P′與P2組成的路徑，這就與從v1到vn的最短路徑是P的前提相矛盾。由以上性質可以想到，為了求由v1到vn的最短路徑，可以先求出v1到網(wǎng)絡中間點的最短路，然后再逐步擴展到終點vn，由此，Dijkstra算法的思想如下：路徑P路徑P′vnv1vi路徑P1路徑P2論證：17十一月2025第44頁第9章圖與網(wǎng)絡

在最短路的計算過程中，為了將已經求出最短路的點與尚未求的點分開，為此針對頂點給出兩個子集合S和T，已經求出最短路的點置于集合S中，其它點置于集合T中。開始時把起點v1置于集合S中，把其它點置于集合T中，隨著最短路計算過程的推移，集合S中的點逐漸增多，集合T中的點逐漸減少，當終點vn也被納入到集合S中時，計算結束。為了便于計算和區(qū)分各個頂點是否已進入集合S中，需要對已求出最短路的點vj賦以標號，這個標號由兩部分組成，記為(d(v1,vj),vi），其中d(v1,vj)是從起點v1到vj的最短路的路長，vi是起點v1到vj的最短路中vj的前一個頂點。因為Dijkstra算法需要標號，所以也稱為標號法，又因為標號中包含兩部分，所以也稱為雙標號法。二Dijkstra算法步驟給定一個網(wǎng)絡G=(V,E)，這里用wij表示網(wǎng)絡中邊(vi,vj)的權，v1是網(wǎng)絡的起點，vn是終點，vi、vj等是網(wǎng)絡的中間節(jié)點，其中i，j=2,3,…,n-1且i≠j，設子集合S和T，S=

，T=V={v1,…,vn}。17十一月2025第45頁第9章圖與網(wǎng)絡

再設L(v1,vi)表示起點v1到點vi的當前最短路的路長，可以把L(v1,vi)簡寫為L(vi)；同樣，L(v1,vj)表示起點v1到點vj的當前最短路的路長，也把L(v1,vj)簡寫為L(vj)；L(vi)+wij是從起點v1出發(fā)，沿著起點v1到點vi的最短路，經由vi后到點vj的路長。那么L(vj)=min{L(vi)+wij

；L(vj)}就是從起點v1到點vj的兩條路徑中，選擇最短的一條作為起點v1到點vj新的最短路的路長。v1到vj當前最短路，路長L(vj)L(vj)=min{L(vi)+wij；L(vj)}表示從v1到vj的兩條路徑中選擇最短的一條作為v1到vj的新的最短路。v1到vi當前最短路，路長L(vi)wijviv1vj17十一月2025第46頁第9章圖與網(wǎng)絡

由Dijkstra算法思想及前面的相關界定，求v1到vn最短路的Dijkstra算法步驟如下：第一步：設L(v1)=0，L(vi)=+∞，其中i=2,…,n。在網(wǎng)絡圖中，把起點v1賦以標號（L(v1),v1），即（0,v1），其余各點均標為（+∞,v1）。第二步：檢查起點v1，即將網(wǎng)絡中v1的標號變?yōu)?0*,v1），表示v1已被檢查，同時設集合S={v1}，T={v2,…,vn}。

第四步：計算L(vi)*=min{L(vi),其中vi

T}，將L(vi)*對應點vi的第一個標號L(vi)標上*，即變?yōu)長(vi)*，表示vi已被檢查，同時設集合S={v1,vi}，此時vi

T。

第三步：針對其它點vi，若v1與vi沒有直接連線，vi的標號就保持不變；若v1與vi有直接連線，則點vi的標號就變?yōu)?L(vi),v1)，其中：

L(vi)=min{L(v1)+W1i；L(vi)}=min{0+W1i；+∞}=W1i17十一月2025第47頁第9章圖與網(wǎng)絡

第六步：計算L(vj)*=min{L(vj),其中vj

T}，將L(vj)*對應點vj的第一個標號L(vj)標上*，即變?yōu)長(vj)*，表示vj已被檢查，同時設集合S={v1,vi,vj}，而vj

T。第七步：返回第五步，直到所有的點都被檢查，而且終點vn進入到集合S中為止。第八步：在網(wǎng)絡中，從終點vn的第二個標號開始反向追蹤，從而找出最短路徑；同時從終點vn的第一個標號可以讀出起點v1到終點vn最短路的路長。另外，從各個點的第一個標號也可以讀出從起點v1到該點的最短路的路長。第五步：再依次求vj，若vi與vj沒有直接連線，vj的標號就保持不變；若vi與vj有直接連線，則計算L(vj)=min{L(vi)+wij；L(vj)}。若L(vj)值來源L(vi)+wij，則把vj的標號修改為(L(vi)+wij,vi），否則點vj的標號保持不變。17十一月2025第48頁第9章圖與網(wǎng)絡

三最短路算法應用示例用dijkstra算法求下面網(wǎng)絡圖中點v1到點v8的最短路4v1v2v3v4v515v7v6v835162737221具體解題步驟如下：

第一步：設L(v1)=0,L(vi)=+∞,其中i=2,…,8.在網(wǎng)絡中,把起點v1賦以標號(L(v1),v1),即(0,v1),其余各點均標為(+∞,v1),檢查起點v1,并將網(wǎng)絡中v1的標號變?yōu)?0*,v1),同時設集合S={v1},T={v2,…,v8},如下圖：17十一月2025第49頁第9章圖與網(wǎng)絡

710*,v14v1v2v3v4v55v7v6v83516273221+∞,v1+∞,v1+∞,v1+∞,v1+∞,v1+∞,v1+∞,v1第一步計算結果：L(vi)kv1v2v3v4v5v6v7v81

0*+∞+∞+∞+∞+∞+∞+∞vi17十一月2025第50頁第二步:v1與v2、v3有直接連線，則L(v2)=min{L(v1)+W12;L(v2)}=min{0+1;+∞}=1，點v2的標號變?yōu)?1,v1)。同理L(v3)=min{L(v1)+W13;L(v3)}=min{0+4;+∞}=4，點v3的標號就變?yōu)?4,v1），其余點的標號保持不變。再計算：L(vi)*=min{L(vi)}=min{L(v2),L(v3),L(v4),…,L(v8)}=min{1,4,+∞,…,+∞}=1=L(v2),將網(wǎng)絡中v2的標號變?yōu)?1*,v1),同時設集合S={v1,v2},此時v2

T，如下圖70*,v14v1v2v3v4v515v7v6v835162732211*,v1+∞,v14,v1+∞,v1+∞,v1+∞,v1+∞,v1第9章圖與網(wǎng)絡

17十一月2025第51頁第二步計算結果：L(vi)vikv1v2v3v4v5v6v7v810*+∞+∞+∞+∞+∞+∞+∞2

11*41+∞+∞+∞+∞+∞第三步：從v2開始繼續(xù)檢查，v2與v3、v4、v5有直接連線，L(v3)=min{L(v2)+W23;L(v3)}=min{1+5;4}=4,點v3的標號保持不變；L(v4)=min{L(v2)+W24;L(v4)}=min{1+3;+∞}=4,點v4的標號變?yōu)?4,v2);L(v5)=min{L(v2)+W25;L(v5)}=min{1+5;+∞}=6,點v5的標號變?yōu)?6,v2),其余點的標號保持不變。再計算：L(vi)*=min{L(vi)}=min{L(v3),L(v4),L(v5),…,L(v8)}=min{4,4,6,…,+∞}=4=L(v3)=L(v4)對最小值L(v3)和L(v4)可以任意取一個,這里取L(v3)作為最小值，將網(wǎng)絡中v3的標號修改為（4*,v1）,同時設集合S={v1,v2,v3}，此時v3

T，第9章圖與網(wǎng)絡

17十一月2025第52頁70*,v14v1v2v3v4v515v7v6v835162732211*,v16,v24*,v14,v2+∞,v1+∞,v1+∞,v1+∞+∞+∞6242

41*3+∞+∞+∞+∞+∞41

11*2+∞+∞+∞+∞+∞+∞+∞0*1v8v7v6v5v4v3v2v1L(vi)vik第三步計算結果：如下圖所示。同時將上表格擴展為下表第9章圖與網(wǎng)絡

17十一月2025第53頁第四步：從v3開始繼續(xù)檢查，v3與v7有直接連線，L(v7)=min{L(v3)+W37；L(v7)}=min{4+2；+∞}=6，點v7的標號變?yōu)椋?,v3），其余點的標號保持不變。再計算：L(vi)*=min{L(vi)}=min{L(v4),L(v5),L(v6),L(v7),L(v8)}=min{4,6,+∞,6,+∞}=4=L(v4)將網(wǎng)絡中v4標號改為(4*,v2），設集合S={v1,v2,v3,v4}，此時v4

T，70*,v14v1v2v3v4v515v7v6v835162732211*,v16,v24*,v14*,v26,v3+∞,v1+∞,v1第9章圖與網(wǎng)絡

17十一月2025第54頁第四步計算結果：L(vi)vikv1v2v3v4v5v6v7v81

0*+∞+∞+∞+∞+∞+∞+∞2

11*41+∞+∞+∞+∞+∞3

41*4262+∞+∞+∞4

42*62+∞63+∞第五步：從v4開始繼續(xù)檢查,v4與v3、v6、v7有直接連線，L(v3)=min{L(v4)+W43;L(v3)}=min{4+1;4}=4,點v3的標號保持不變；L(v6)=min{L(v4)+W46;L(v6)}=min{4+3;+∞}=7,點v6的標號變?yōu)?7,v4);L(v7)=min{L(v4)+W47;L(v7)}=min{4+7;6}=6,點v7的標號保持不變,其余點的標號保持不變。再計算：L(vi)*=min{L(vi)}=min{L(v5),L(v6),L(v7),L(v8)}=min{6,7,6,+∞}=6=L(v5)=L(v7).這里取L(v7)作為最小值，就將網(wǎng)絡中v7的標號修改為(6*,v3），同時設集合S={v1,v2,v3,v4,v7}，此時v7

T第9章圖與網(wǎng)絡

17十一月2025第55頁70*,v14v1v2v3v4v515v7v6v835162732211*,v16,v24*,v14*,v26*,v37,v4+∞,v1第五步計算結果：L(vi)vikv1v2v3v4v5v6v7v81

0*+∞+∞+∞+∞+∞+∞+∞2

11*41+∞+∞+∞+∞+∞3

41*4262+∞+∞+∞4

42*62+∞63+∞56274

63*+∞第9章圖與網(wǎng)絡

17十一月2025第56頁第六步：從v7開始繼續(xù)檢查，v7與v6、v8有直接連線，L(v6)=min{L(v7)+W76；L(v6)}=min{6+2；7}=7，點v6的標號保持不變；L(v8)=min{L(v7)+W78；L(v8)}=min{6+2；+∞}=8，點v8的標號變?yōu)?8,v7），再計算：L(vi)*=min{L(v5),L(v6),L(v8)}=min{6,7,8}=6=L(v5)將網(wǎng)絡中v5的標號修改為(6*,v2），同時設集合S={v1,v2,v3,v4,v7,v5}，此時v5

T

0*,v14v1v2v3v4v515v7v6v8351627372211*,v1

6*,v24*,v14*,v26*,v37,v48,v7第9章圖與網(wǎng)絡

17十一月2025第57頁L(vi)vikv1v2v3v4v5v6v7v81

0*+∞+∞+∞+∞+∞+∞+∞2

11*41+∞+∞+∞+∞+∞3

41*4262+∞+∞+∞4

42*62+∞63+∞56274

63*+∞6

62*7487第六步計算結果：第七步：再從v5開始繼續(xù)檢查，v5與v6有直接連線，L(v6)=min{L(v5)+W56；L(v6)}=min{6+7；7}=7，點v6的標號保持不變。再計算：L(vi)*=min{L(v6),L(v8)}=min{7,8}=7=L(v6)將網(wǎng)絡中v6的標號變?yōu)?7*,v4），同時設集合S={v1,v2,v3,v4,v7,v5,v6}，此時v6

T

第9章圖與網(wǎng)絡

17十一月2025第58頁0*,v14v1v2v3v4v515v7v6v8351627372211*,v1

6*,v24*,v14*,v26*,v37*,v48,v7L(vi)vikv1v2v3v4v5v6v7v81

0*+∞+∞+∞+∞+∞+∞+∞2

11*41+∞+∞+∞+∞+∞3

41*4262+∞+∞+∞4

42*62+∞63+∞56274

63*+∞6

62*74877

74*87第七步計算結果：第9章圖與網(wǎng)絡

17十一月2025第59頁第八步：從v6開始繼續(xù)檢查,v6與v8有直接連線，L(v8)=min{L(v6)+W68;L(v8)}=min{7+1;8}=8。最小值8來自兩處，點v8的標號應該為(8,v6)和(8,v7),點v8的標號寫為(8,v6v7).再計算：L(vi)*=min{L(vi)}=min{L(v8)}=min{8}=8=L(v8)將網(wǎng)絡中v8標號變?yōu)?8*,v6v7),同時設集合S={v1,v2,v3,v4,v7,v5,v6,v8},此時v8

T70*,v14v1v2v3v4v515v7v6v835162732211*,v1

6*,v24*,v14*,v26*,v37*,v48*,v6v7第9章圖與網(wǎng)絡

17十一月2025第60頁第八步計算結果：L(vi)vikv1v2v3v4v5v6v7v810*+∞+∞+∞+∞+∞+∞+∞2

11*41+∞+∞+∞+∞+∞3

41*4262+∞+∞+∞4

42*62+∞63+∞56274

63*+∞6

62*74877

74*878

867*此時終點v8已經被標識和檢查，算法結束。從終點v8的第一個標號可以讀出起點v1到終點v8最短路的路長為8，同時從終點v8的第二個號開始反向追蹤，找出最短路徑為v1→v2→v4→v6→v8和v1→v3→v7→v8，此網(wǎng)絡有兩條最短路。第9章圖與網(wǎng)絡

17十一月2025第61頁特別提示：（1）網(wǎng)絡中的最短路不止一條時，要注意進行多點標號，如上例的第八步。另外，上例是利用dijkstra算法對有向網(wǎng)絡進行尋找最短路，dijkstra算法對無向網(wǎng)絡的使用原理一樣。（2）dijkstra算法只適用于網(wǎng)絡中所有邊的權Wij≥0的情況，當網(wǎng)絡中出現(xiàn)負權邊的時候，dijkstra算法就不能保證得到正確的結果。（3）另外，同樣也可以讀出從起點v1到該網(wǎng)絡中任意一點的最短路及路長。（4）針對含有負權邊求最短路的算法很多，但因這類問題算法的復雜性較高，本教材不作介紹。第9章圖與網(wǎng)絡

17十一月2025第62頁第9章圖與網(wǎng)絡

§9.3.2最小生成樹問題在第9.1.4節(jié)中，介紹了基于圖的樹以及生成樹問題，針對具有權的網(wǎng)絡，常常需要尋找基于權之和最小的生成樹，這就是最小生成樹問題。具有一定的實用意義，如常常需要以最研究最小生成樹問題短線路連接網(wǎng)絡中若干個固定點，例如城市水網(wǎng)鋪設、交通網(wǎng)規(guī)劃、煤氣管網(wǎng)建設等等，為了便于維護、管理等目的，這些都涉及到線網(wǎng)中總長度最短的問題。這些問題需要在線網(wǎng)中找出一棵最小生成樹，類似的問題還有，如何設計總長度最小的公交網(wǎng)或公路網(wǎng)把若干城鎮(zhèn)連接起來等等，也就是說，許多網(wǎng)絡問題會派生出最小生成樹問題，因此，最小生成樹問題也是網(wǎng)絡極值的基本問題之一。下面的示例就是在網(wǎng)絡圖中找出一棵最小生成樹問題。17十一月2025第63頁引例：圖中表示10個居住小區(qū)間道路連接以及距離情況，問如何開通公交線路使公交車運行路程最短？對于給定的網(wǎng)絡圖，常常含有許多不同的樹，如何找出具有某種最小性質的樹？第9章圖與網(wǎng)絡

4563v1v2v3v4v5v7v6v8v9v104454335265178217十一月2025第64頁給定無向網(wǎng)絡圖G=(V,E)，其中V=(v1,v2,…,vn)，E=(e1,e2,…,em)，針對邊ei的實數(shù)權為w(ei)，令T是G的生成樹，則生成樹T的權之和為：第9章圖與網(wǎng)絡

一最小生成樹的數(shù)學描述若T*也是G的生成樹，且有W(T*)=min{W(T)|T是G的一個生成樹}，則稱T*是無向網(wǎng)絡圖G的最小生成樹。二尋找最小生成樹的方法在第9.1.4節(jié)中，已經介紹了針對圖尋找生成樹的兩種方法，即破圈法和避圈法。針對具有權的網(wǎng)絡圖，尋找最小生成樹的方法仍然是基于破圈法和避圈法的思路，但需要考慮權的大小問題。17十一月2025第65頁第9章圖與網(wǎng)絡

下面給出網(wǎng)絡中尋找最小生成樹的破圈法和避圈法的思路（1）避圈法在連通的無向網(wǎng)絡圖G中，從所有邊中選出一條權最小的邊，并把它納入樹中，在G中余下的邊中再選擇一條權最小且與選進樹中的邊不構成回路的邊，同樣將其納入樹中，如此反復，直到找不出這樣的邊為止。（2）破圈法在連通的無向圖G中，任取一個回路，將該回路中權最大的邊去掉，如果回路中含有兩條及兩條以上權最大的邊，則任取一條，再在余下的回路中重復這一步驟，直到圖G中不含有回路為止。17十一月2025第66頁“一個郵遞員每次送信，從郵局出發(fā)，必須至少一次地走過他負責投遞范圍的每一條街道，完成投遞任務后仍然回到郵局，問他如何選擇一條投遞路線，使他所走的路程最短？”，這個問題是我國管梅谷在1962年首先提出，所以稱為中國郵路問題。3410v16v2v3v7v6v5v4v8v9例：郵遞員需從v1出發(fā)，走遍每條街道遞送郵件，最后再回到v1，他應選擇什么路線才能使總的路程長度最短第9章圖與網(wǎng)絡

§9.3.3中國郵路問題17十一月2025第67頁給定一個連通的無向網(wǎng)絡圖G=(V,E,W)，所有邊(vi,vj)的權wij>0，現(xiàn)在要求每條邊至少通過一次的閉鏈Q，使得總權最小。如果圖G恰好是歐拉圖，那么從郵局出發(fā)，恰好每邊走一次可回到郵局，這時總權必定最小；如果圖G不是歐拉圖，則某些邊必然要重復走，當然要求重復走過邊的總長度最小。第一步：若網(wǎng)絡圖G是一個歐拉圖，即沒有奇階點（奇階點指與點連接的邊的數(shù)量為奇數(shù)），則該圖可以一筆畫出全部的邊而無重復，此時，郵遞員的最優(yōu)路線就是一個歐拉環(huán)游，其總的走行長度為全部邊長之和，但一般而言，街道圖并非歐拉圖，那么可以采用以下辦法消除奇階點，從而將非歐拉圖變?yōu)闅W拉圖：第9章圖與網(wǎng)絡

一中國郵路問題的數(shù)學描述二中國郵路問題的一個算法17十一月2025第68頁（1）找出全部奇階點(全部奇階點的頂點個數(shù)一定是偶數(shù)個);（2）將2m個奇階點構成m個奇階點對，使每點都在一個點對中，找出每個點對中兩個奇階點之間一條鏈，對應于鏈上的每條邊都添加一條長度和該邊相等的邊，經過添加邊的兩點間的街道，郵遞員需要兩次經過。第二步：解奇階點匹配問題最優(yōu)解的分枝定界算法。設au,v為奇階點u至奇階點v的最短路長度，將全部2m個奇階點的最短路長度構成一個2m×2m的矩陣：第9章圖與網(wǎng)絡

17十一月2025第69頁將A視為一個指派問題的費用矩陣，并令主對角線各元素等于∞，現(xiàn)在，對這個指派問題求解，最優(yōu)解用2m個表中位置表示。如果最優(yōu)解在表中是關于主對角線對稱（稱為對稱解），則這個表右上角即為奇階點匹配問題的最優(yōu)解；如果指派問題最優(yōu)解不是對稱解，則解中必然存在由n個表位（n>2）構成的下標回路，如：(1,3）、(3,5）、(5,1），為了尋求對稱解，這個回路必然打破，因此，可分別令表中這n個位置上的元素等于∞，將指派問題分枝成n個子問題，繼續(xù)用指派問題的算法，計算出各子問題的目標值，做為該子問題以后分枝的目標下界，這樣不斷分枝下去，直至沒有任何一個子問題需要再分枝，即可確定奇階點匹配問題的最優(yōu)解。任一子問題停止分枝的條件是：（1）該子問題的解為對稱解；第9章圖與網(wǎng)絡

17十一月2025第70頁（2）其目標下界大于等于某一具有對稱解的子問題的目標值。計算步驟如下：1.找出全部奇階點，用最短路算法計算全部奇階點任一點對間的最短路長度。

2.將奇階點最短路長度矩陣A視為指派問題的費用矩陣，構成一個指派問題，形成初始子問題矩陣后，將某些不可能進入奇階點匹配問題最優(yōu)解的表位排除掉：（1）如果點i至點j的最短路由三個以上奇階點組成，那么令ai,j=∞，aj,i=∞；（2）檢查所有三奇階點最短路，設為i—j—k，如果其中間點j與任何其他奇階點構成的最短路都包含一個端點i或k，則令它們在初始子問題表中的元素ai,k=∞，將該問題置入待分枝子問題集合B，令奇階點匹配問題的候選最優(yōu)解目標T=∞。第9章圖與網(wǎng)絡

17十一月2025第71頁

3.如果B為空，則停止計算，候選最優(yōu)解S即為最優(yōu)解；如果B非空，則從B中取出一個子問題k，用指派問題算法解子問題k。其目標值為Tk，解為Sk（以分配的表位集合表示）。4.若Tk＞T則停止分枝，轉第3步取另一子問題，否則轉第5步。6.在Sk中找出一個點數(shù)為n的下標回路(i1,j1)、(i2,j2)、…、(in,jn），其中i2=j1,i3=j2…,in=jn-1，而且n>2，分別令子問題k的矩陣Ak中的，構成n個子問題，并置入待分枝子問題集合B，然后轉第3步。第9章圖與網(wǎng)絡

5.若Sk關于主軸對稱，停止分枝，令候選最優(yōu)解等于子問題k的解，令S=Sk，T=Tk，然后轉三取另一個子問題；若Sk為非對稱解，轉第六步。17十一月2025第72頁求上面示例中的最短郵遞路線解：圖14有6個奇階點，其對應的奇階點之間的最短路矩陣如左下：

針對上述A矩陣，按照指派問題求解思路求對應的最優(yōu)解，最優(yōu)解矩陣如右上所示：

指派問題的解不對稱,從而相對應的中國郵路問題的解不可行,解中存在如下下標環(huán)(1,4)、(4,5)、(5,1),現(xiàn)在分別將A矩陣中下標環(huán)中三個位置及其對稱位置的數(shù)值置為∞,從而構造出以下三個子問題:第9章圖與網(wǎng)絡

17十一月2025第73頁子問題1：將A矩陣中(1,4）和(4,1）處的元素置為∞，構造出如左下指派問題：最優(yōu)解不對稱，子問題1的解不可行，最優(yōu)目標函數(shù)值為36。子問題1最優(yōu)解矩陣

子問題2：將A矩陣中(4,5）和(5,4）處的元素置為∞，構造出如左下指派問題：子問題2最優(yōu)解矩陣第9章圖與網(wǎng)絡

17十一月2025第74頁最優(yōu)解對稱，子問題2可行，最優(yōu)目標函數(shù)值為36，添加邊方案：7-8、2-9、5-1，添加邊總長18

子問題3：將A矩陣中(5,1）和(1,5）處的元素置為∞，構造出如左下指派問題：子問題3最優(yōu)解矩陣

最優(yōu)解對稱，子問題3可行，最優(yōu)目標函數(shù)值為36，添加邊方案：5-6-7、8-9、2-9-10，添加邊總長18。由停止分枝的條件，子問題都不再往下分枝，已得到此中國郵路問題的最優(yōu)解，子問題2或子問題3都是該問題的最優(yōu)解。第9章圖與網(wǎng)絡

17十一月2025第75頁第9章圖與網(wǎng)絡

§9.4網(wǎng)絡流問題在上一節(jié)中，把圖中的邊賦予權的數(shù)量指標后，研究了網(wǎng)絡的極值問題，如果把圖中的邊賦予其它意義的數(shù)量指標，就可以產生網(wǎng)絡流的問題。研究網(wǎng)絡流的問題有一定的現(xiàn)實意義，例如交通系統(tǒng)中的車流、金融系統(tǒng)中的現(xiàn)金流、控制系統(tǒng)中的信息流、供水系統(tǒng)中的水流等等，針對這些系統(tǒng)，有時需要考慮在既定的網(wǎng)絡中能通過網(wǎng)絡的最大流量是多少，這就產生了網(wǎng)絡的最大流問題；有時需要考慮在滿足成本最低的前提下，使網(wǎng)絡承載一定的流量，這就產生了網(wǎng)絡的最小費用流問題；有時也需要考慮在滿足成本最低的前提下，使網(wǎng)絡通過的流量達到最大，這就產生了網(wǎng)絡的最小費用最大流問題。這些問題可以說是線性規(guī)劃問題，用線性規(guī)劃的方法也可以解決，但依據(jù)現(xiàn)實問題抽象出來的網(wǎng)絡模型具有特殊的結構，而且網(wǎng)絡模型也具有直觀性，所以基于網(wǎng)絡模型可以設計出比單純形法更為有效的的算法來解決這類問題。17十一月2025第76頁第9章圖與網(wǎng)絡

§9.4.1網(wǎng)絡流的相關知識在上一節(jié)中，把圖中的邊賦予權的數(shù)量指標后，研究了網(wǎng)絡的極值問題，如果把圖中的邊賦予其它意義的數(shù)量指標，就可以產生網(wǎng)絡流的問題。研究網(wǎng)絡流的問題有一定的現(xiàn)實意義，例如交通系統(tǒng)中的車流、金融系統(tǒng)中的現(xiàn)金流、控制系統(tǒng)中的信息流、供水系統(tǒng)中的水流等等，針對這些系統(tǒng)，有時需要考慮在既定的網(wǎng)絡中能通過網(wǎng)絡的最大流量是多少，這就產生了網(wǎng)絡的最大流問題；有時需要考慮在滿足成本最低的前提下，使網(wǎng)絡承載一定的流量，這就產生了網(wǎng)絡的最小費用流問題；有時也需要考慮在滿足成本最低的前提下，使網(wǎng)絡通過的流量達到最大，這就產生了網(wǎng)絡的最小費用最大流問題。這些問題可以說是線性規(guī)劃問題，用線性規(guī)劃的方法也可以解決，但依據(jù)現(xiàn)實問題抽象出來的網(wǎng)絡模型具有特殊的結構，而且網(wǎng)絡模型也具有直觀性，所以基于網(wǎng)絡模型可以設計出比單純形法更為有效的的算法來解決這類問題。17十一月2025第77頁第9章圖與網(wǎng)絡

為了更形象地的學習網(wǎng)絡流的相關知識，下面給出一個引例：某運輸企業(yè)