第10章 地理網(wǎng)絡(luò)分析

第十章地理網(wǎng)絡(luò)分析

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院對(duì)于許多現(xiàn)實(shí)的地理問(wèn)題，譬如，城鎮(zhèn)體系問(wèn)題、城市地域結(jié)構(gòu)問(wèn)題、交通問(wèn)題、商業(yè)網(wǎng)點(diǎn)布局問(wèn)題、物流問(wèn)題、管道運(yùn)輸問(wèn)題、供電與通訊線路問(wèn)題等等，都可以運(yùn)用網(wǎng)絡(luò)分析方法進(jìn)行研究。

網(wǎng)絡(luò)分析，主要是運(yùn)用圖論方法研究各類網(wǎng)絡(luò)的結(jié)構(gòu)及其優(yōu)化問(wèn)題。網(wǎng)絡(luò)分析方法是計(jì)量地理學(xué)必不可少的重要方法之一。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院?jiǎn)栴}1(哈密爾頓環(huán)球旅行問(wèn)題,1859年愛爾蘭數(shù)學(xué)家哈密爾頓提出):

十二面體的20個(gè)頂點(diǎn)代表世界上20個(gè)城市，能否從某個(gè)城市出發(fā)在十二面體上依次經(jīng)過(guò)每個(gè)城市恰好一次最后回到出發(fā)點(diǎn)？哈密頓圈（環(huán)球旅行游戲）甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院?jiǎn)栴}2(四色問(wèn)題,1852年，摩爾根):

對(duì)任何一張地圖進(jìn)行著色，兩個(gè)共同邊界的國(guó)家染不同的顏色，則只需要四種顏色就夠了.問(wèn)題3(關(guān)鍵路徑問(wèn)題):

一項(xiàng)工程任務(wù),大到建造一座大壩,一座體育中心,小至組裝一臺(tái)機(jī)床,一架電視機(jī),都要包括許多工序.這些工序相互約束,只有在某些工序完成之后,一個(gè)工序才能開始.即它們之間存在完成的先后次序關(guān)系,一般認(rèn)為這些關(guān)系是預(yù)知的,而且也能夠預(yù)計(jì)完成每個(gè)工序所需要的時(shí)間.

這時(shí)工程領(lǐng)導(dǎo)人員迫切希望了解最少需要多少時(shí)間才能夠完成整個(gè)工程項(xiàng)目,影響工程進(jìn)度的要害工序是哪幾個(gè)？甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院列昂納德·歐拉——7橋問(wèn)題

東普魯士的哥尼斯堡城（現(xiàn)在的加里寧格勒）是建在兩條河流的匯合處以及河中的兩個(gè)小島上的，共有7座小橋?qū)蓚€(gè)小島及小島與城市的其他部分連接起來(lái)，那么，哥尼斯堡人從其住所出發(fā)，能否恰好只經(jīng)過(guò)每座小橋一次而返回原處？圖論研究結(jié)果告訴我們，其答案是否定的。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院內(nèi)容地理網(wǎng)絡(luò)的圖論描述

最短路徑與選址問(wèn)題

最大流與最小費(fèi)用流甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院第1節(jié)地理網(wǎng)絡(luò)的圖論描述地理網(wǎng)絡(luò)的圖論描述地理網(wǎng)絡(luò)的測(cè)度（LeonhardPaulEuler，1707年－1783年)甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院通俗意義上的“圖”，主要是指各種各樣的地圖、遙感影像圖，或者是由各種符號(hào)、文字代表的示意圖，或者是由各種地理數(shù)據(jù)繪制而成的曲線圖、直方圖等等。

圖論中的“圖”，是一個(gè)數(shù)學(xué)概念，這種“圖”能從數(shù)學(xué)本質(zhì)上揭示地理實(shí)體與地理事物空間分布格局，地理要素之間的相互聯(lián)系以及它們?cè)诘赜蚩臻g上的運(yùn)動(dòng)形式、地理事件發(fā)生的先后順序等。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（1）圖：設(shè)V是一個(gè)由n個(gè)點(diǎn)vi(i=1，2，…，n)所組成的集合，即V={v1，v2，…，vn}，E是一個(gè)由m條線ei（i=1，2，…，m）所組成的集合，即E={e1，e2，…，em}，而且E中任意一條線，都是以V中的點(diǎn)為端點(diǎn)；任意兩條線除了端點(diǎn)外沒(méi)有其他的公共點(diǎn)。一、地理網(wǎng)絡(luò)的圖論描述（一）圖的定義那么，把V與E結(jié)合在一起就構(gòu)成了一個(gè)圖G，記作G＝（V，E）。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（3）邊：E中每一條線稱為圖G的邊（或?。?；若一條邊e連接u，v兩個(gè)頂點(diǎn)，則記為e＝（u，v）。

（2）頂點(diǎn)：V中的每一個(gè)點(diǎn)vi（i=1，2，…，n）稱為圖G的頂點(diǎn)。（4）在圖G＝（V，E）中，V不允許是空集，但E可以是空集。（5）從以上定義可以看出，圖包含兩個(gè)方面的基本要素：點(diǎn)集（或稱頂點(diǎn)集）；邊集（或稱弧集）。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院例：在如圖10.1.1所示的圖中，頂點(diǎn)集為

V＝｛v1，v2，v3，v4，v5，v6，v7，v8｝，邊集為E＝{e1，e2，e3，e4，e5，e6，e7，e8，e9，e10，e11}。圖10.1.1甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（6）在現(xiàn)實(shí)地理系統(tǒng)中，對(duì)于地理位置、地理實(shí)體、地理區(qū)域以及它們之間的相互聯(lián)系，可以經(jīng)過(guò)一定的簡(jiǎn)化與抽象，將它們描述為圖論意義下的地理網(wǎng)絡(luò)，即圖。

地理位置、地理實(shí)體、地理區(qū)域，譬如，山頂、河流匯聚點(diǎn)、車站、碼頭、村莊、城鎮(zhèn)等——點(diǎn)。它們之間的相互聯(lián)系，譬如，構(gòu)造線、河流、交通線、供電與通訊線路、人口流、物質(zhì)流、資金流、信息流、技術(shù)流等——點(diǎn)與點(diǎn)的連線。一個(gè)由基本流域單元組成的復(fù)雜的流域地貌系統(tǒng)，如果舍棄各種復(fù)雜的地貌形態(tài)，各條河流——線，河流分岔或匯聚處——點(diǎn)，流域地貌系統(tǒng)——水系的基本結(jié)局（樹）。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（7）需要說(shuō)明的是：圖的定義只關(guān)注點(diǎn)之間是否連通，而不關(guān)注點(diǎn)之間的連結(jié)方式。對(duì)于任何一個(gè)圖，他的畫法并不唯一。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院圖與網(wǎng)絡(luò)優(yōu)化的一些基本問(wèn)題例1最短路問(wèn)題（SPP－shortestpathproblem）一名貨柜車司機(jī)奉命在最短的時(shí)間內(nèi)將一車貨物從甲地運(yùn)往乙地。從甲地到乙地的公路網(wǎng)縱橫交錯(cuò)，因此有多種行車路線，這名司機(jī)應(yīng)選擇哪條線路呢？假設(shè)貨柜車的運(yùn)行速度是恒定的，那么這一問(wèn)題相當(dāng)于需要找到一條從甲地到乙地的最短路。例2公路連接問(wèn)題某一地區(qū)有若干個(gè)主要城市，現(xiàn)準(zhǔn)備修建高速公路把這些城市連接起來(lái)，使得從其中任何一個(gè)城市都可以經(jīng)高速公路直接或間接到達(dá)另一個(gè)城市。假定已經(jīng)知道了任意兩個(gè)城市之間修建高速公路的成本，那么應(yīng)如何決定在哪些城市間修建高速公路，使得總成本最?。扛拭C農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院例3指派問(wèn)題（assignmentproblem）一家公司經(jīng)理準(zhǔn)備安排名員工去完成項(xiàng)任務(wù)，每人一項(xiàng)。由于各員工的特點(diǎn)不同，不同的員工去完成同一項(xiàng)任務(wù)時(shí)所獲得的回報(bào)是不同的。如何分配工作方案可以使總回報(bào)最大？例4中國(guó)郵遞員問(wèn)題（CPP－Chinesepostmanproblem）一名郵遞員負(fù)責(zé)投遞某個(gè)街區(qū)的郵件。如何為他（她）設(shè)計(jì)一條最短的投遞路線（從郵局出發(fā)，經(jīng)過(guò)投遞區(qū)內(nèi)每條街道至少一次，最后返回郵局）？由于這一問(wèn)題是我國(guó)管梅谷教授1960年首先提出的，所以國(guó)際上稱之為中國(guó)郵遞員問(wèn)題。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院例5旅行商問(wèn)題（TSP－travelingsalesmanproblem）一名推銷員準(zhǔn)備前往若干城市推銷產(chǎn)品。如何為他（她）設(shè)計(jì)一條最短的旅行路線（從駐地出發(fā)，經(jīng)過(guò)每個(gè)城市恰好一次，最后返回駐地）？這一問(wèn)題的研究歷史十分悠久，通常稱之為旅行商問(wèn)題。例6運(yùn)輸問(wèn)題（transportationproblem）某種原材料有個(gè)產(chǎn)地，現(xiàn)在需要將原材料從產(chǎn)地運(yùn)往個(gè)使用這些原材料的工廠。假定每個(gè)產(chǎn)地的產(chǎn)量和家工廠的需要量已知，單位產(chǎn)品從任一產(chǎn)地到任一工廠的運(yùn)費(fèi)已知，那么如何安排運(yùn)輸方案可以使總運(yùn)輸成本最低？甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院上述問(wèn)題有兩個(gè)共同的特點(diǎn)：一是它們的目的都是從若干可能的安排或方案中尋求某種意義下的最優(yōu)安排或方案，數(shù)學(xué)上把這種問(wèn)題稱為最優(yōu)化或優(yōu)化（optimization）問(wèn)題；二是它們都易于用圖形的形式直觀地描述和表達(dá)，數(shù)學(xué)上把這種與圖相關(guān)的結(jié)構(gòu)稱為網(wǎng)絡(luò)（network）。與圖和網(wǎng)絡(luò)相關(guān)的最優(yōu)化問(wèn)題就是網(wǎng)絡(luò)最優(yōu)化或稱網(wǎng)絡(luò)優(yōu)化（netwokoptimization）問(wèn)題。所以上面例子中介紹的問(wèn)題都是網(wǎng)絡(luò)優(yōu)化問(wèn)題。由于多數(shù)網(wǎng)絡(luò)優(yōu)化問(wèn)題是以網(wǎng)絡(luò)上的流（flow）為研究的對(duì)象，因此網(wǎng)絡(luò)優(yōu)化又常常被稱為網(wǎng)絡(luò)流（networkflows）或網(wǎng)絡(luò)流規(guī)劃等。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（二）圖的一些相關(guān)概念

（1）無(wú)向圖與有向圖：無(wú)向圖——圖的每條邊都沒(méi)有給定方向，即（u，v）＝（v，u）；有向圖——圖的每條邊都給定了方向，即（u，v）≠（v，u）。

一般將有向圖的邊集記為A，無(wú)向圖的邊集記為E。這樣，G=（V，A）就表示有向圖，而G=（V，E）則表示無(wú)向圖。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

（2）賦權(quán)圖：如果圖G＝（V，E）中的每一條邊（vi，vj）都相應(yīng)地賦有一個(gè)數(shù)值wij，則稱G為賦權(quán)圖，其中wij稱為邊（vi，vj）的權(quán)值。除了可以給圖的邊賦權(quán)外，也可以給圖的頂點(diǎn)賦權(quán)。這就是說(shuō)，對(duì)于圖G中的每一頂點(diǎn)vj，也可以賦予一個(gè)載荷a(vj)。

（3）關(guān)聯(lián)邊：若e＝（u，v），則稱u和v是邊e的端點(diǎn)，e是u和v的關(guān)聯(lián)邊。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（4）環(huán)：若e的兩個(gè)端點(diǎn)相同，即u＝v，則稱為環(huán)。（5）多重邊：若連接兩個(gè)端點(diǎn)的邊多于一條以上，則稱為多重邊。（6）多重圖：含有多重邊的圖，稱為多重圖。（7）簡(jiǎn)單圖：無(wú)環(huán)、無(wú)多重邊的圖，稱為簡(jiǎn)單圖。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（8）點(diǎn)與次。以點(diǎn)v為端點(diǎn)的邊的個(gè)數(shù)稱為點(diǎn)v的次，記為d(v)。次等于1的點(diǎn)稱為懸掛點(diǎn)；與懸掛點(diǎn)關(guān)聯(lián)的邊稱為懸掛邊。次為零的點(diǎn)稱為孤立點(diǎn)。次為奇數(shù)的點(diǎn)稱為奇點(diǎn)；次為偶數(shù)的點(diǎn)稱為偶點(diǎn)。（9）連通圖。在圖G中，若任何兩點(diǎn)之間至少存在一條路（對(duì)于有向圖，則不考慮邊的方向），則稱G為連通圖，否則稱為不連通圖。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（10）路（鏈）：若圖G＝（V，E）中，若頂點(diǎn)與邊交替出現(xiàn)的序列（對(duì)于有向圖來(lái)說(shuō)，要求排在每一條邊之前和之后的頂點(diǎn)分別是這條邊的起點(diǎn)和終點(diǎn)）

P＝{vi1，ei1，vi2，ei2，…，eik-1，vik}

滿足

eit

=(vit，vi，t+1)(t=1,2,…,k-1)

則稱P為一條從vi1到vik的路（或鏈），簡(jiǎn)記為

P＝{vi1，vi2，…，vik}。（11）回路：若一條路的起點(diǎn)與終點(diǎn)相同，即vi1=vik，則稱它為回路。（12）樹：不含回路的連通的無(wú)向圖稱為樹。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（13）基礎(chǔ)圖：從一個(gè)有向圖D＝（V，A）中去掉所有邊上的箭頭所得到的無(wú)向圖，就稱為D的基礎(chǔ)圖，記之為G（D）。（14）截：如果從圖中移去邊的一個(gè)集合將增加亞圖的數(shù)目時(shí)，被移去的邊的集合就稱為截。（15）子圖：設(shè)G＝（V，E）是一個(gè)無(wú)向圖，V1與E1分別是V與E的子集，即V1V，

E1E。如果對(duì)于任意ei∈E1，其兩個(gè)端點(diǎn)都屬于V1，則稱G1＝（V1，E1）是圖G的一個(gè)子圖。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（16）支撐子圖：設(shè)G1＝（V1，E1）是圖G＝（V，E）的一個(gè)子圖，如果V1＝V，則稱G1是G的支撐子圖。（17）支撐樹：設(shè)G＝（V，E）是一個(gè)無(wú)向圖，如果T＝（V1，E1）是G的支撐子圖，并且T是樹，則稱T是G

的一個(gè)支撐樹。（18）樹的重量：一個(gè)樹的所有邊的權(quán)值之和稱為該樹的重量。（19）最小支撐樹：在一個(gè)圖的所有支撐樹中，重量最小的那個(gè)叫做該圖的最小支撐樹。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子圖v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撐子圖甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院二、地理網(wǎng)絡(luò)的測(cè)度

許多現(xiàn)實(shí)的地理問(wèn)題，只要經(jīng)過(guò)一定的簡(jiǎn)化和抽象，就可以將它們描述為圖論意義下的地理網(wǎng)絡(luò)，點(diǎn)和線的排布格局，并可以進(jìn)一步定量化地測(cè)度它們的拓?fù)浣Y(jié)構(gòu)，以及連通性和復(fù)雜性。

樹狀型地理網(wǎng)絡(luò)平面網(wǎng)絡(luò)（二維的）非平面網(wǎng)絡(luò)（非二維的）道路型環(huán)狀型細(xì)胞型圖10.1.5地理網(wǎng)絡(luò)的拓?fù)浞诸?/p>

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

目前關(guān)于地理網(wǎng)絡(luò)的拓?fù)溲芯浚疃?、最常見的是基于平面圖描述的二維平面網(wǎng)絡(luò)。

所謂平面圖，被規(guī)定為：各連線之間不能交叉，而且每一條連線除頂點(diǎn)以外，不能再有其他的公共點(diǎn)（牛文元，1987）。

以下的討論，除非特別申明外，都限于二維平面網(wǎng)絡(luò)。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（一）關(guān)聯(lián)矩陣與鄰接矩陣

關(guān)聯(lián)矩陣（incidencematrix）測(cè)度網(wǎng)絡(luò)圖中頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系。

假設(shè)網(wǎng)絡(luò)圖G＝（V，E）的頂點(diǎn)集為V={v1，v2，…，vn}，邊集為E={e1，e2，…，em}，則該網(wǎng)絡(luò)圖的關(guān)聯(lián)矩陣就是一個(gè)n×m矩陣，可表示為

式中：gij為頂點(diǎn)vi與邊ej相關(guān)聯(lián)的次數(shù)。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院v3v1v2v4v5e1e2e3e4e5e6e7該圖的關(guān)聯(lián)矩陣為

例：

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院鄰接矩陣（adjacencymatrix）測(cè)度網(wǎng)絡(luò)圖中各頂點(diǎn)之間的連通性程度。

假設(shè)圖G＝（V，E）的頂點(diǎn)集為V={v1，v2，…，vn}，則鄰接矩陣是一個(gè)n階方陣，可表示為式中：aij表示連接頂點(diǎn)vi與vj的邊的數(shù)目。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院該圖的鄰接矩陣為

v3v1v2v4v5e1e2e3e4e5e6e7例：

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（二）有關(guān)測(cè)度指標(biāo)對(duì)于任何一個(gè)網(wǎng)絡(luò)圖，都存在著3種共同的基礎(chǔ)指標(biāo)：

①連線（邊或弧）數(shù)目m；

②結(jié)點(diǎn)（頂點(diǎn)）數(shù)目n；

③

網(wǎng)絡(luò)中亞圖的數(shù)目p。由它們可以產(chǎn)生如下幾個(gè)更為一般性的測(cè)度指標(biāo)：β指數(shù)、回路數(shù)k、α指數(shù)、γ指數(shù)。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

也稱為線點(diǎn)率，是網(wǎng)絡(luò)內(nèi)每一個(gè)結(jié)點(diǎn)的平均連線數(shù)目

β=0，表示無(wú)網(wǎng)絡(luò)存在；網(wǎng)絡(luò)的復(fù)雜性增加，則β值也增大。

沒(méi)有孤立點(diǎn)存在的網(wǎng)絡(luò)，連線數(shù)目為n-p,則β指數(shù)為β指數(shù)如果地理網(wǎng)絡(luò)不包含次級(jí)亞圖，即P＝1，則其最低限度連接的指數(shù)值為。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院回路數(shù)k

回路是一種閉合路徑,它的始點(diǎn)同時(shí)也是終點(diǎn)。

若網(wǎng)絡(luò)內(nèi)存在回路，則連線的數(shù)目就必須超過(guò)n-p（最低限度連接網(wǎng)絡(luò)的連接數(shù)目）。

回路數(shù)k為實(shí)際連線數(shù)目減去最低限度連接的連線數(shù)目，即

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院指數(shù)指數(shù)指實(shí)際回路數(shù)與網(wǎng)絡(luò)內(nèi)可能存在的最大回路數(shù)之間的比率。網(wǎng)絡(luò)內(nèi)可能存在的最大回路數(shù)目為連線的最大可能數(shù)目減去最低限度連接的連線數(shù)目，即所以，

指數(shù)為

指數(shù)也可以用百分率表示甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院對(duì)于非平面網(wǎng)絡(luò)，其指數(shù)為指數(shù)的變化范圍，一般介于[0，1]區(qū)間，＝0意味著網(wǎng)絡(luò)中不存在回路；＝1，說(shuō)明網(wǎng)絡(luò)中已達(dá)到最大限度的回路數(shù)目。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院γ指數(shù)

γ指數(shù)指網(wǎng)絡(luò)內(nèi)連線的實(shí)際數(shù)目與連線可能存在的最大數(shù)目之間的比率，對(duì)于平面網(wǎng)絡(luò)，其計(jì)算公式為γ指數(shù)也可以用百分比表示γ指數(shù)是測(cè)度網(wǎng)絡(luò)連通性的一種指標(biāo)，其數(shù)值變化范圍為[0，1]。γ＝0，表示網(wǎng)絡(luò)內(nèi)無(wú)連線，只有孤立點(diǎn)存在；γ＝1，則表示網(wǎng)絡(luò)內(nèi)每一個(gè)結(jié)點(diǎn)都存在與其他它所有結(jié)點(diǎn)相連的連線。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

對(duì)于非平面網(wǎng)絡(luò)，指數(shù)的計(jì)算公式為

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院表10.1.1幾種簡(jiǎn)單網(wǎng)絡(luò)圖的有關(guān)測(cè)度指標(biāo)

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院第2節(jié)最短路徑與選址問(wèn)題

最短路徑問(wèn)題選址問(wèn)題甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院對(duì)于許多地理問(wèn)題，當(dāng)它們被抽象為圖論意義下的網(wǎng)絡(luò)圖時(shí)，問(wèn)題的核心就變成了網(wǎng)絡(luò)圖上的優(yōu)化計(jì)算問(wèn)題。其中，最為常見的是關(guān)于路徑和頂點(diǎn)的優(yōu)選計(jì)算問(wèn)題。在路徑的優(yōu)選計(jì)算問(wèn)題中，最常見的是最短路徑問(wèn)題；而在頂點(diǎn)的優(yōu)選計(jì)算問(wèn)題中，最為常見的是中心點(diǎn)和中位點(diǎn)選址問(wèn)題。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院“純距離”意義上的最短路徑例如，需要運(yùn)送一批物資從一個(gè)城市到另一個(gè)城市，選擇什么樣的運(yùn)輸路線距離最短？“經(jīng)濟(jì)距離”意義上的最短路徑

例如，某公司在10大港口C1，C2，…，C10設(shè)有貨棧，從Ci到Cj之間的直接航運(yùn)價(jià)格，是由市場(chǎng)動(dòng)態(tài)決定的。如果兩個(gè)港口之間無(wú)直接通航路線，則通過(guò)第三個(gè)港口轉(zhuǎn)運(yùn)。那么，各個(gè)港口之間最廉價(jià)的貨運(yùn)線路是什么？一、最短路徑問(wèn)題（一）最短路徑的含義甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院“時(shí)間”意義上的最短路徑

例如，某家經(jīng)營(yíng)公司有一批貨物急需從一個(gè)城市運(yùn)往另一個(gè)城市，那么，在由公路、鐵路、河流航運(yùn)、航空運(yùn)輸?shù)?種運(yùn)輸方式和各個(gè)運(yùn)輸線路所構(gòu)成的交通網(wǎng)絡(luò)中，究竟選擇怎樣的運(yùn)輸路線最節(jié)省時(shí)間？

以上3類問(wèn)題，都可以抽象為同一類問(wèn)題，即賦權(quán)圖上的最短路徑問(wèn)題。

不同意義下的距離都可以被抽象為網(wǎng)絡(luò)圖中邊的權(quán)值。

權(quán)——這種權(quán)值既可以代表“純距離

”，又可以代表“經(jīng)濟(jì)距離

”，也可以代表“時(shí)間距離

”。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（二）最短路徑的算法標(biāo)號(hào)法（狄克斯屈拉算法）

1959年E.W.Dijkstar

提出的標(biāo)號(hào)法是最短路徑問(wèn)題最好的求解方法。

標(biāo)號(hào)法優(yōu)點(diǎn)

不僅可以求出起點(diǎn)到終點(diǎn)的最短路徑及其長(zhǎng)度，而且可以求出起點(diǎn)到其他任何一個(gè)頂點(diǎn)的最短路徑及其長(zhǎng)度；同時(shí)適用于求解有向圖或無(wú)向圖上的最短路徑問(wèn)題。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院標(biāo)號(hào)法的基本思想設(shè)G是一個(gè)賦權(quán)有向圖，即對(duì)于圖中的每一條邊，都賦予了一個(gè)權(quán)值。在圖G中指定兩個(gè)頂點(diǎn)，確定為起點(diǎn)和終點(diǎn)，不妨設(shè)v1為起點(diǎn)，vk為終點(diǎn)。

首先從v1開始，給每一個(gè)頂點(diǎn)標(biāo)一個(gè)數(shù)，稱為標(biāo)號(hào)。這些標(biāo)號(hào)，又進(jìn)一步區(qū)分為T標(biāo)號(hào)和P標(biāo)號(hào)兩種類型。其中，每一個(gè)頂點(diǎn)的T標(biāo)號(hào)表示從起點(diǎn)v1到該點(diǎn)的最短路徑長(zhǎng)度的上界，這種標(biāo)號(hào)為臨時(shí)標(biāo)號(hào)；P標(biāo)號(hào)表示從v1到該點(diǎn)的最短路長(zhǎng)度，這種標(biāo)號(hào)為固定標(biāo)號(hào)。在最短路徑計(jì)算過(guò)程中，對(duì)于已經(jīng)得到P標(biāo)號(hào)的頂點(diǎn)，不再改變其標(biāo)號(hào)；對(duì)于凡是沒(méi)有標(biāo)上P標(biāo)號(hào)的頂點(diǎn)，先給它一個(gè)T標(biāo)號(hào)；算法的每一步就是把頂點(diǎn)的T標(biāo)號(hào)逐步修改，將其變?yōu)镻標(biāo)號(hào)。那么，最多經(jīng)過(guò)k-1步，就可以求得到從起點(diǎn)v1到每一個(gè)頂點(diǎn)的最短路徑及其長(zhǎng)度。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院標(biāo)號(hào)法具體計(jì)算步驟

①如果剛剛得到P標(biāo)號(hào)的點(diǎn)是vi，那么，對(duì)于所有這樣的點(diǎn)將其T標(biāo)號(hào)修改為：min[T(vj)，P(vi)+wij]。②若G中沒(méi)有T標(biāo)號(hào)，則停止。否則，把點(diǎn)的T標(biāo)號(hào)修改為P標(biāo)號(hào)，然后再轉(zhuǎn)入①。

其中，滿足

開始，先給v1標(biāo)上P標(biāo)號(hào)P(v1)＝0，其余各點(diǎn)標(biāo)上T標(biāo)號(hào)T(vj)＝+∞（j≠1）。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院例1：在圖10.2.1所示的賦權(quán)有向圖中，每一個(gè)頂點(diǎn)vi（i=1，2，…，n）代表一個(gè)城鎮(zhèn)；每一條邊代表相應(yīng)兩個(gè)城鎮(zhèn)之間的交通線，其長(zhǎng)度用邊旁的數(shù)字表示。試求城鎮(zhèn)v1到v7之間的最短路徑。

圖10.2.1賦權(quán)有向交通網(wǎng)絡(luò)圖甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院解：首先給v1標(biāo)上P標(biāo)號(hào)P(v1)=0，表示從v1到v1的最短路徑為零。其他點(diǎn)(v2，v3，…，v7)標(biāo)上T標(biāo)號(hào)T(vj)＝+∞（j＝2，3，…，7）。第1步：①

v1是剛得到P標(biāo)號(hào)的點(diǎn)。因?yàn)?v1，v2)，(v1，v3)，(v1，v4)∈E，而且v2，v3，v4是T標(biāo)號(hào)，所以修改這3個(gè)點(diǎn)的T標(biāo)號(hào)為

T(v2)＝min[T(v2)，P(v1)+w12]＝min[+∞，0+2]＝2

T(v3)＝min[T(v3)，P(v1)+w13]＝min[+∞，0+5]＝5

T(v4)＝min[T(v4)，P(v1)+w14]＝min[+∞，0+3]＝3②

在所有T標(biāo)號(hào)中，T(V2)＝2最小，于是令P(V2)＝2。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院第2步：①v2是剛得到P標(biāo)號(hào)的點(diǎn)。因?yàn)?v2，v3)，(v2，v6)∈E，而且v3,v6是T標(biāo)號(hào)，故修改v3和v6的T標(biāo)號(hào)為T(v3)＝min[T(v3)，P(v2)+w23]＝min[5，2+2]＝4

T(v6)＝min[T(v6)，P(v2)+w26]＝min[+∞，2+7]＝9

②在所有的T標(biāo)號(hào)中，T(v4)＝3最小，于是令P(v4)＝3。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院第3步：①v4是剛得到P標(biāo)號(hào)的點(diǎn)。因?yàn)?v4，v5)∈E，而且v5是T標(biāo)號(hào)，故修改v5的T標(biāo)號(hào)為

T(v5)＝min[T(v5)，P(v4)+w45]＝min[+∞，3+5]＝8

②在所有的T標(biāo)號(hào)中，T(v3)＝4最小，故令P(v3)＝4。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院第4步：①v3是剛得到P標(biāo)號(hào)的點(diǎn)。因?yàn)?v3，v5)，(v3，v6)∈E，而且v5和v6為T標(biāo)號(hào)，故修改v5和v6的T標(biāo)號(hào)為

T(v5)＝min[T(v5)，P(v3)+w35]＝min[8，4+3]＝7

T(v6)＝min[T(v6)，P(v3)+w36]＝min［9，4+5]＝9

②

在所有的T標(biāo)號(hào)中，T(v5)＝7最小，故令P(v5)＝7。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院第5步：①

v5是剛得到P標(biāo)號(hào)的點(diǎn)。因?yàn)?v5，v6)，(v5

，v7)∈E，而且v6和v7都是T標(biāo)號(hào)，故修改它們的T標(biāo)號(hào)為

T(v6)＝min[T(v6)，P(v5)+w56]＝min[9，7+1]=8

T(v7)＝min[T(v7)，P(v5)+w57]＝min[+∞，7+7]=14

②

在所有T標(biāo)號(hào)中，T(v6)＝8最小，于是令：P(v6)＝8。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院第6步：①

v6是剛得到P標(biāo)號(hào)的點(diǎn)。因?yàn)?v6，v7)∈E，而且v7為T標(biāo)號(hào)，故修改它的T標(biāo)號(hào)為

T(v7)＝min[T(v7)，P(v6)+w67]＝min[14，8+5]=13

②目前只有v7是T標(biāo)號(hào)，故令：P(v7)＝13。

從城鎮(zhèn)v1到v7之間的最短路徑為(v1，v2，v3，v5，v6，v7)，最短路徑長(zhǎng)度為13。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院最短路問(wèn)題的應(yīng)用舉例例1、電信公司準(zhǔn)備在甲、乙兩地沿路架設(shè)一條光纜線，問(wèn)如何架設(shè)使其光纜線路最短？v1v2v3v4v5v7v615103176445260151014131930181622v1v3v5v6v7總長(zhǎng)度為22甲地乙地甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院237184566134105275934682求從1到8的最短路徑甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院237184566134105275934682X={1},w1=0min{c12,c14,c16}=min{0+2,0+1,0+3}=min{2,1,3}=1X={1,4},p4=1p4=1p1=0甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院237184566134105275934682X={1,4}min{c12,c16,c42,c47}=min{0+2,0+3,1+10,1+2}=min{2,3,11,3}=2X={1,2,4},p2=2p1=0p4=1p2=2甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院237184566134105275934682X={1,2,4}min{c13,c23,c25,c47}=min{0+3,2+6,2+5,1+2}=min{3,8,7,3}=3X={1,2,4,6},p6=3p2=2p4=1p1=0p6=3甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院237184566134105275934682X={1,2,4,6}min{c23,c25,c47,c67}=min{2+6,2+5,1+2,3+4}=min{8,7,3,7}=3X={1,2,4,6,7},p7=3p2=2p4=1p1=0p6=3p7=3甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院237184566134105275934682X={1,2,4,6,7}min{c23,c25,c75,c78}=min{2+6,2+5,3+3,3+8}=min{8,7,6,11}=6X={1,2,4,5,6,7},p5=6p2=2p4=1p1=0p6=3p7=3p5=6甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院237184566134105275934682X={1,2,4,6,7}min{c23,c53,c58,c78}=min{2+6,6+9,6+4,3+8}=min{8,15,10,11}=8X={1,2,3,4,5,6,7},p3=8p2=2p4=1p1=0p6=3p7=3p5=6p3=8甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院237184566134105275934682X={1,2,3,4,6,7}min{c38,c58,c78}=min{8+6,6+4,3+7}=min{14,10,11}=10X={1,2,3,4,5,6,7,8},p8=10p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院237184566134105275934682X={1,2,3,4,6,7,8}1到8的最短路徑為{1，4，7，5，8}，長(zhǎng)度為10。p2=2p4=1p1=0p6=3p7=3p5=6p3=8p8=10甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院二、選址問(wèn)題

選址問(wèn)題，是現(xiàn)代地理學(xué)研究的主要問(wèn)題之一。選址問(wèn)題涉及人類生產(chǎn)、生活、文化、娛樂(lè)等各個(gè)方面。選址問(wèn)題的數(shù)學(xué)模型取決于兩個(gè)方面的條件：可供選址的范圍、條件；怎樣判定選址的質(zhì)量。本節(jié)的討論僅限于選址的范圍是一個(gè)地理網(wǎng)絡(luò)，而且選址位置位于網(wǎng)絡(luò)圖的某一個(gè)或幾個(gè)頂點(diǎn)上。

對(duì)這樣的選址問(wèn)題，根據(jù)其選址的質(zhì)量判據(jù)，可以將其歸納為求網(wǎng)絡(luò)圖的中心點(diǎn)與中位點(diǎn)兩類問(wèn)題。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（一）中心點(diǎn)選址問(wèn)題

例：某縣要在其所轄的6個(gè)鄉(xiāng)鎮(zhèn)之一修建一個(gè)消防站，為6個(gè)鄉(xiāng)鎮(zhèn)服務(wù)，要求消防站至最遠(yuǎn)鄉(xiāng)鎮(zhèn)的距離達(dá)到最小。

中心點(diǎn)選址問(wèn)題的質(zhì)量判據(jù)

最佳選址位置所在的頂點(diǎn)的最大服務(wù)距離為最小。中心點(diǎn)選址問(wèn)題適宜于醫(yī)院、消防站點(diǎn)等一類服務(wù)設(shè)施的布局問(wèn)題。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

設(shè)G＝（V，E）是一個(gè)無(wú)向簡(jiǎn)單連通賦權(quán)圖，連接兩個(gè)頂點(diǎn)的邊的權(quán)值代表它們之間的距離，對(duì)于每一個(gè)頂點(diǎn)vi，它與各個(gè)頂點(diǎn)之間的最短路徑長(zhǎng)度為di1，di2，…，din。這些距離中的最大數(shù)稱為頂點(diǎn)vi的最大服務(wù)距離，記為e(vi)。

那么，中心點(diǎn)選址問(wèn)題，就是求網(wǎng)絡(luò)圖G的中心點(diǎn)，使得中心點(diǎn)選址問(wèn)題的數(shù)學(xué)描述

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院例2：假設(shè)某縣下屬的6個(gè)鄉(xiāng)鎮(zhèn)及其之間公路聯(lián)系如圖所示。每一頂點(diǎn)代表一個(gè)鄉(xiāng)鎮(zhèn)；每一條邊代表連接兩個(gè)鄉(xiāng)鎮(zhèn)之間的公路，每一條邊旁的數(shù)字代表該條公路的長(zhǎng)度?，F(xiàn)在要設(shè)立一個(gè)消防站，為全縣的6個(gè)鄉(xiāng)鎮(zhèn)服務(wù)。試問(wèn)該消防站應(yīng)該設(shè)在哪一個(gè)鄉(xiāng)鎮(zhèn)（頂點(diǎn)）？

圖10.2.2甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院解：第1步：用標(biāo)號(hào)法求出每一個(gè)頂點(diǎn)vi至其他各個(gè)頂點(diǎn)vj的最短路徑長(zhǎng)度dij（i，j

＝1，2，…，6），并將它們寫成如下的距離矩陣甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

第2步：求每一個(gè)頂點(diǎn)的最大服務(wù)距離。顯然，它們分別是矩陣D中各行的最大值，即：e(v1)＝6，e(v2)＝7，e(v3)＝6，e(v4)＝7，e(v5)＝6，e(v6)＝7。

第3步：判定。因?yàn)閑(v1)＝e(v3)＝e(v5)＝min{e(vi)}＝6，所以v1，v3，v5都是中心點(diǎn)。也就是說(shuō)，消防站設(shè)在v1，v3，v5中任何一個(gè)頂點(diǎn)上都是可行的。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院中位點(diǎn)選址問(wèn)題的質(zhì)量判據(jù)

使最佳選址位置所在的頂點(diǎn)到網(wǎng)絡(luò)圖中其他各個(gè)頂點(diǎn)的最短路徑距離的總和（或者以各個(gè)頂點(diǎn)的載荷加權(quán)求和）達(dá)到最小。（二）中位點(diǎn)選址問(wèn)題甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院中位點(diǎn)選址問(wèn)題的數(shù)學(xué)描述

設(shè)G＝（V，E）是一個(gè)簡(jiǎn)單連通賦權(quán)無(wú)向圖，連接兩個(gè)頂點(diǎn)的邊的權(quán)值為該兩頂點(diǎn)之間的距離；對(duì)于每一個(gè)頂點(diǎn)vi（i＝1，2，…，n），有一個(gè)正的負(fù)荷a(vi)，而且它與其他各頂點(diǎn)之間的最短路徑長(zhǎng)度為di1，di2，…，din。那么，中位點(diǎn)選址問(wèn)題，就是求圖G的中位點(diǎn)，使得甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院例3：某縣下屬7個(gè)鄉(xiāng)鎮(zhèn)，各鄉(xiāng)鎮(zhèn)所擁有的人口數(shù)a(vi)（i=1，2，…，7），以及各鄉(xiāng)鎮(zhèn)之間的距離wij（i，j=1，2，…，7）如圖所示?，F(xiàn)在需要設(shè)立一個(gè)中心郵局，為全縣所轄的7個(gè)鄉(xiāng)鎮(zhèn)共同服務(wù)。問(wèn)該中心郵局應(yīng)該設(shè)在哪一個(gè)鄉(xiāng)鎮(zhèn)（頂點(diǎn)）？

圖10.2.3甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院解：第1步：用標(biāo)號(hào)法求出每一個(gè)頂點(diǎn)vi至其他各個(gè)頂點(diǎn)vj的最短路徑長(zhǎng)度dij（i，j

＝1，2，…，7），并將其寫成如下距離矩陣

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院第2步：以各頂點(diǎn)的載荷（人口數(shù)）加權(quán)，求每一個(gè)頂點(diǎn)至其他各個(gè)頂點(diǎn)的最短路徑長(zhǎng)度的加權(quán)和

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

第3步：判斷。因?yàn)?/p>

所以，v3和v4都是圖10.2.3的中位點(diǎn)。即：中心郵局設(shè)在點(diǎn)v3或點(diǎn)v4都是可行的。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院v6v8v1v7v5v4v2v389363253757例4，某縣要在其所轄的8個(gè)鄉(xiāng)鎮(zhèn)之一修建一個(gè)消防站，為8個(gè)鄉(xiāng)鎮(zhèn)服務(wù)，要求消防站至最遠(yuǎn)鄉(xiāng)鎮(zhèn)的距離達(dá)到最小。假設(shè)該8個(gè)鄉(xiāng)鎮(zhèn)之間的交通網(wǎng)絡(luò)被抽象為無(wú)向賦權(quán)連通圖，權(quán)值為鄉(xiāng)鎮(zhèn)之間的距離。下面求解消防站應(yīng)設(shè)在哪個(gè)鄉(xiāng)鎮(zhèn)，即哪個(gè)頂點(diǎn)？甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院首先，用Dijkstra算法計(jì)算出每一個(gè)頂點(diǎn)vi至其它各頂點(diǎn)vj的最短路徑長(zhǎng)度dij(i,j=1,2,…,6)，寫出距離矩陣：

6061916152565473甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院其次，求距離矩陣中每行的最大值，即各個(gè)頂點(diǎn)的最大服務(wù)距離，得

e(v1)=14,e(v2)=15,e(v3)=20,e(v4)=12,e(v5)=15,e(v6)=17,e(v7)=12,e(v8)=20

最后計(jì)算最大服務(wù)距離的最小值。顯然，e(v4)=e(v7)=min{e(vi)}。所以，消防站應(yīng)建在v4或v7點(diǎn)所在的鄉(xiāng)鎮(zhèn)。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院6061916152565473要求消防站至所有鄉(xiāng)鎮(zhèn)的距離達(dá)到最?。合勒緫?yīng)建在v5點(diǎn)所在的鄉(xiāng)鎮(zhèn)甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院第3節(jié)最大流與最小費(fèi)用流

最大流問(wèn)題及其求解方法最小費(fèi)用流及其求解方法甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院一、最大流問(wèn)題及其求解方法

（一）最大流問(wèn)題最大流問(wèn)題設(shè)有向網(wǎng)絡(luò)N（V，A），在發(fā)點(diǎn)Vs

有一批貨，要通過(guò)網(wǎng)絡(luò)上的弧運(yùn)輸?shù)绞拯c(diǎn)Vt

去，受運(yùn)輸條件限制，每條弧aij在單位時(shí)間內(nèi)通過(guò)的車輛數(shù)不能超過(guò)cij

輛，分析：如何組織運(yùn)輸才能使從Vs到Vt

在單位時(shí)間內(nèi)通過(guò)的車輛達(dá)到最多？上面描述的這類問(wèn)題，稱為最大流問(wèn)題。

最大流問(wèn)題廣泛地應(yīng)用在交通運(yùn)輸、供水、油管供油、郵電通訊，也可以用在生產(chǎn)安排，管理優(yōu)化等實(shí)際問(wèn)題上。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院例：如圖10.3.1中，有一批物資需要用汽車盡快從發(fā)點(diǎn)①運(yùn)到收點(diǎn)⑦，?。╥，j）上所標(biāo)的數(shù)字表示該條道路在單位時(shí)間內(nèi)最多能通過(guò)的車輛數(shù)（單位：百輛），問(wèn)如何調(diào)運(yùn)，才能使單位時(shí)間里有最多的車輛從①調(diào)到⑦。圖10.3.1甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院┍┑線

性

規(guī)

劃

方

法┕┙點(diǎn)①出發(fā)的車輛數(shù)應(yīng)該與點(diǎn)⑦到達(dá)的車輛數(shù)相同，除①和⑦以外的各中間點(diǎn)，進(jìn)的車輛數(shù)應(yīng)該與離去的車輛數(shù)應(yīng)該相同。xij

是通過(guò)弧(i，j)的車輛數(shù)。（10.3.1）（10.3.4）（10.3.5）（10.3.6）（10.3.2）（10.3.3）甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

對(duì)所有?。╥，j），應(yīng)滿足約束

滿足（10.3.1）～（10.3.7）的解稱為從①到⑦的一個(gè)可行流。我們的目的：在所有可行流中求出一個(gè)方案，使得這個(gè)可行流得到的f最大。

若從收點(diǎn)到發(fā)點(diǎn)連接一條假想弧(7，1)，設(shè)它的容量c71=∞，那么

對(duì)點(diǎn)①：

對(duì)點(diǎn)⑦：

最大流問(wèn)題的目標(biāo)為┍┑線

性

規(guī)

劃

方

法┕┙

（10.3.7）（10.3.8）（10.3.9）（10.3.10）甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院所以，對(duì)于發(fā)點(diǎn)為Vs，收點(diǎn)為Vt的網(wǎng)絡(luò)N（V，U），當(dāng)增加一條約束為cts=∞的假想?。╰，s）后，最大流問(wèn)題就成為：

容量約束

平衡條件

目標(biāo)函數(shù)┍┑線

性

規(guī)

劃

方

法┕┙

（10.3.11）（10.3.12）（10.3.13）甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（二）求最大流的方法：弧標(biāo)號(hào)法

盡管最大流問(wèn)題可以用線性規(guī)劃模型描述，但是我們一般并不用求解線性規(guī)劃的方法求最大流，而是用一種更為簡(jiǎn)便明了的圖上作業(yè)法——弧標(biāo)號(hào)法，求解上述最大流問(wèn)題。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

(1)為了便于弧標(biāo)號(hào)法的計(jì)算，首先需要將最大流問(wèn)題（譬如圖10.3.1）重新改畫成為圖10.3.2的形式。

圖10.3.2甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院在圖10.3.2中，每條弧上標(biāo)有兩個(gè)數(shù)字，其中，靠近點(diǎn)i的是，靠近點(diǎn)j的是。如①②表示從①到②的最大通過(guò)量是5（百輛），從②到①的最大通過(guò)量是0；②③表示從②到③和從③到②都可以通過(guò)2（百輛）；等等。

圖10.3.2甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

(2)求最大流的基本步驟：標(biāo)號(hào)法求最大流的過(guò)程，就是對(duì)圖10.3.2反復(fù)地進(jìn)行修改的過(guò)程，其計(jì)算步驟如下：

步驟1.

從發(fā)點(diǎn)s到收點(diǎn)t選定一條路，使這條路通過(guò)的所有弧Vij的前面約束量cij都大于0，如果找不到這樣的路，說(shuō)明已經(jīng)求得最大流，轉(zhuǎn)步驟4。

步驟2.

在選定的路上，找到最小的容許量cij定為P。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

步驟3.

對(duì)選定的路上每條弧的容量作以下修改，對(duì)于與路同向的弧，將cij修改為cij-P，對(duì)于與路反向的弧，將cij修改為cij+P。修改完畢后再轉(zhuǎn)入步驟1。步驟4.用原圖中各條弧上起點(diǎn)與終點(diǎn)數(shù)值減去修改后的圖中對(duì)應(yīng)點(diǎn)的數(shù)值，得到正負(fù)號(hào)相反的兩個(gè)數(shù)，并將從正到負(fù)的方向用箭頭表示。這樣，就得到一個(gè)最大流量圖。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院第1次修改：

①?gòu)陌l(fā)點(diǎn)s到收點(diǎn)t找一條路，使得這條路上的所有弧前面的約束量。從圖10.3.2中可以看出，顯然，①—③—⑥—⑦就是滿足這樣的條件的一條路。

下面，我們用弧標(biāo)號(hào)法求解圖10.3.2中的最大流。

②在路①—③—⑥—⑦中,,,，所以取。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

③在路①—③—⑥—⑦中，修改每一條弧的容量甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院通過(guò)第1次修改，得到圖10.3.3。圖10.3.3返回步驟①，進(jìn)行第2次修改。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

第2次修改：選定①—②—⑤—⑦，在這條路中，由于，所以，將改為2，改為0，改為5，、、改為3。修改后的圖變?yōu)閳D10.3.4。

圖10.3.4返回步驟①繼續(xù)做第3次修改。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院第3次修改：?、佟凇邸荨?，在這條路中，由于所以將改為0，改為5，改為0，改為4，改為1，改為2，改為3,c75改為5。修改后的圖變?yōu)閳D10.3.5。

圖10.3.5返回步驟①，繼續(xù)做第4次修改。，甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

第4次修改：選定①—④—⑥—⑦，在這條路中，由于P=c67=1，所以將c14改為4,c41改為1,c46改為4,c64改為1,c67改為0，c76改為7。修改后的圖為變?yōu)閳D10.3.6。

圖10.3.6返回步驟①，繼續(xù)做第5次修改。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

第5次修改：選定①—④—⑥—⑤—⑦,在這條路中，由于P=c65

=1，所以將c14和c46均改為3，c65改為0，c57改為2，c41、c64、c56均改為2，c75改為6。修改后的圖變?yōu)閳D10.3.7。

圖10.3.7甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院需要注意的是，由圖10.3.7中可以看出，弧本來(lái)在圖10.3.2中是無(wú)容量可通過(guò)的，但經(jīng)過(guò)幾次修改，由③⑥變成③⑥，即此時(shí)從③到⑥還可通過(guò)1（百輛），而從⑥到③，可以通過(guò)6（百輛）的容量，這說(shuō)明，修改過(guò)程實(shí)際上是把計(jì)劃中從③到⑥的通過(guò)車輛數(shù)減少了。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院第6次修改：取①—④—⑥—③—⑤—⑦，在這條路中，由于P=c35=1，所以將c14和c46均改為2，c63改為5,c35改為0，c57改為1，c41、c64、c53均改為3，c36改為2，c75改為7。修改后的圖變?yōu)閳D10.3.8。

圖10.3.8甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院在圖10.3.8中，從發(fā)點(diǎn)①到收點(diǎn)⑦，再也不存在連通的起點(diǎn)容量都大于零的弧了，所以圖10.3.8為最大流圖。

轉(zhuǎn)入步驟④，用原圖中各條弧上發(fā)點(diǎn)與收點(diǎn)數(shù)值減去修改后的圖上各點(diǎn)的數(shù)值，將得到正負(fù)號(hào)相反的兩個(gè)數(shù)，將這個(gè)數(shù)標(biāo)在弧上，并將從正到負(fù)的方向用箭頭表示,這樣就得到最大流量圖。例如原來(lái)弧是③⑥，現(xiàn)在是③⑥，相減為±5，③那邊為正，我們就記作③⑥。這樣，就得到圖10.3.9，即最大流量圖。依這樣的調(diào)度方式，可以從發(fā)點(diǎn)s調(diào)運(yùn)14（百輛）汽車到收點(diǎn)t。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院圖10.3.9最大流量圖

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

(3)最大流算法的討論：

①?gòu)纳厦娴臉?biāo)號(hào)計(jì)算過(guò)程可以看出，一個(gè)圖成為最大流圖的條件是從發(fā)點(diǎn)到收點(diǎn)的每一條路上總存在某個(gè)起點(diǎn)容量為零的弧，我們稱這樣的路為飽和路；如果從s到t有一條路，它上面每條路的起點(diǎn)容量都大于零，則稱為非飽和路。由此可以得到一個(gè)結(jié)論：一個(gè)圖是最大流圖的充分必要條件是不存在從s到t的非飽和路。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

②將網(wǎng)絡(luò)中的點(diǎn)分成兩組，一組包括發(fā)點(diǎn)，稱為發(fā)集，一組包括收點(diǎn)t，稱為收集，連接到的所有弧稱為截集，截集中各弧在旁的容量和稱為截集的容量。

例如，在圖10.3.2中，

圖10.3.2甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院我們?nèi)?，，則截集為{(2,5),(3,5),(1,4),(3,6),(3,4)}，它的容量為3+3+5+7+3=21；若在圖10.3.6中，取，，則截集為{(2,5),(3,5),(6,5),(6,7)}，其容量為0+1+1+0=2等等。在將網(wǎng)絡(luò)分成發(fā)集與收集的所有分法中，容量最小的截集稱為最小截集。可以證明：甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院設(shè)f是網(wǎng)絡(luò)N的一個(gè)可行流，那么，網(wǎng)絡(luò)N的最小截集的容量（μ）等于網(wǎng)絡(luò)最大流與f的差，即（10.3.14）

式中：μ稱為可行流f的余量。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

顯然，當(dāng)μ=0時(shí)，就得到了最大流。因此，進(jìn)一步可以得到：在網(wǎng)絡(luò)N中，設(shè)f是從發(fā)點(diǎn)到收點(diǎn)的一個(gè)可行流，那么，f是最大流的充分必要條件是網(wǎng)絡(luò)N的最小截集的容量為零。

從到的最大流的流量等于分離與的最小截集的容量。

這表明，從到，最小截集的弧是網(wǎng)絡(luò)中的“卡脖子”線路，要獲得最大流量，必須在最小截集的各弧上達(dá)到滿載。甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院圖10.3.10

③最大流fmax的大小是確定的，但最大流的路線可以不唯一。在上例中，如果從不同的路開始來(lái)修改圖，也可能得到另外一個(gè)最大流圖（圖10.3.10）。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院對(duì)于不同的最大流圖（譬如圖10.3.9與圖10.3.10），它們必有以下性質(zhì)：

對(duì)于網(wǎng)絡(luò)的最小截集上的弧，它們的流量是相同的。

對(duì)于由最小截集分開的V1和V2內(nèi)，它們的流量可能不同，但都是相差一個(gè)或幾個(gè)不飽和回路上的量，如圖10.3.9與圖10.3.10，相差的是③—④—⑥—③回路上一個(gè)值為2的流量。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院二、最小費(fèi)用流及其求解方法

（一）最小費(fèi)用流問(wèn)題如果在考慮網(wǎng)絡(luò)上流量的同時(shí)，還要使得所安排流量的費(fèi)用或者代價(jià)達(dá)到最小，就是所謂的最小費(fèi)用流問(wèn)題。

在上例中，如果單位車輛數(shù)通過(guò)某一條弧要付出一定的代價(jià)，其代價(jià)如圖10.3.11。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院現(xiàn)在要從發(fā)點(diǎn)①調(diào)動(dòng)若干車輛到收點(diǎn)⑦去，約束條件為圖10.3.1，代價(jià)條件為圖10.3.11，要使所花費(fèi)的代價(jià)達(dá)到最小，用公式表示，就是要在（10.3.1）～（10.3.7）式的約束條件下，找到一個(gè)可行流f的流量（10.3.15）

使其代價(jià)最小，即

（10.3.16）

式中：指單位車輛數(shù)通過(guò)弧的代價(jià)。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院圖10.3.11代價(jià)條件

圖10.3.1約束條件

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院（二）求解最小費(fèi)用流問(wèn)題求最小費(fèi)用流的步驟和求最大流的步驟幾乎完全一致，只是在步驟（1）中，選一條非飽和路時(shí)，應(yīng)選代價(jià)和最小的路，即最短路。例如，在圖10.3.11中，從①到⑦的最短路是①—③—⑤—⑦，代價(jià)為7，在這條最短非飽和路上取后，③—⑤變成容量為零，在下一次選擇最短路時(shí)應(yīng)將③—⑤視為斷路來(lái)選取最短非飽和路。另外，選?、佟邸荨呗泛?，③—①，⑤—③，⑦—⑤的弧成為容量大于零的弧，可分別標(biāo)上它們的代價(jià)值為-3，-3，-1，是①—③，③—⑤，⑤—⑦的相反數(shù)。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院在求最小費(fèi)用流過(guò)程中，可以依上述方法不斷重復(fù)求最大流的步驟來(lái)進(jìn)行，當(dāng)流量達(dá)到時(shí)就可以停止，這時(shí)求出的是最小費(fèi)用流。當(dāng)然，如果，就需要將步驟進(jìn)行到最后，直到不存在非飽和路存在為止。

按照這種方法，可以將約束條件由圖10.3.1所示，代價(jià)函數(shù)為圖10.3.11所示的最小費(fèi)用流問(wèn)題的求解算法，可以用表10.3.1表示，這里設(shè)。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院表10.3.1最小費(fèi)用流的求解過(guò)程

將各條路的流量相加，就得到最小費(fèi)用流，如圖10.3.12所示。

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院圖10.3.12最小費(fèi)用流

這個(gè)最小費(fèi)用流的總代價(jià)為

甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院練習(xí)：提出下圖的關(guān)聯(lián)矩陣和鄰接矩陣甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院關(guān)聯(lián)矩陣M=鄰接矩陣A=甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院練習(xí)2、用標(biāo)號(hào)法求下圖從v1到v6的最短路。v1v2v3v4v6v5352242421甘肅農(nóng)業(yè)大學(xué)資源與環(huán)境學(xué)院

解（1）首先給v1以P標(biāo)號(hào)，給其余所有點(diǎn)T標(biāo)號(hào)。（2）（3