(畢業(yè)設(shè)計論文)最大流問題及應(yīng)用

1、山東科技大學(xué)本科畢業(yè)設(shè)計（論文）題目最大流問題以及應(yīng)用學(xué)院名稱 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院專業(yè)班 級 信息與計算科學(xué)2011級2班學(xué)生姓名呂永強(qiáng)學(xué)號摘要網(wǎng)絡(luò)流問題是運(yùn)籌學(xué)的重要研究課題。最大流問題是網(wǎng)絡(luò)流問題的一 個重要的內(nèi)容，應(yīng)用極為廣泛。研究最大流問題并將其應(yīng)用到工業(yè)、工程 商業(yè)、農(nóng)業(yè)，運(yùn)輸業(yè)等領(lǐng)域可給我們的生活帶來很大方便。本論文討論最大流問題，綜述圖論的歷史背景、基本概念和基本知識； 闡述網(wǎng)絡(luò)的基本概念；介紹最大流問題的核心依據(jù)Ford-Fulkerson最大流最小割定理；綜述解決最大流問題的 幾種算法 Ford-Fulkerson 標(biāo)號法、 Edmonds-Karp修正算法、Dinic算法，

2、并比較各算法在解決不同問題中的 優(yōu)劣。為了更加明確的展現(xiàn)最大流問題在生產(chǎn)生活中的應(yīng)用，本文例舉了一 個實際生活中的問題鐵路貨運(yùn)列車的最優(yōu)調(diào)度來突出研究最大流問題 的重要意義，此實例需要求解的是在一定的限制條件下，設(shè)計出一個在一 晝夜間能通過某段鐵路的最多的貨運(yùn)列車數(shù)量并列出每 輛列車開出的時 刻表。在此實例中，通過從實際問題中抽象出網(wǎng)絡(luò)圖，將實際問題轉(zhuǎn)化為 最大流問題并應(yīng)用圖的性質(zhì)和 Ford-Fulkerson 標(biāo)號法的算法依據(jù)，最終解 決了問題。本文采用理論與 實例相結(jié)合，重在應(yīng)用理論依據(jù)解決實際問題，具有 較強(qiáng)的實踐性，突出的是應(yīng)用。AbstractThe network flow pr

3、oblem is an important operational research subject. The maximum flow problem is an important content of network flow problem, which has widely applications. The research of maximum flow problem and its applications to industry, engineering，commerce, agriculture, transportation and other areas can br

4、ing us great convenience.The paper discusses the maximum flow problem, and summarizes the historical background of graph theory, basic concepts, basic knowledge and describes the basic concept of the network. The core basis of the maximum flow problem - Ford-Fulkerson maximum flow minimum cut theore

5、m is introduced. Several algorithms for solving maximal-flow problem like Ford-Fulkerson labeling algorithm, Edmonds-Karp correct algorithm, Dinic algorithm are summarized in this paper. It also compares various algorithms to solve different problems in the pros and cons.In order to more clearly sho

6、w the application of the maximum flow problem in the production life, the paper illustrates a real-life problem - -The optimal scheduling of railway freight train to highlight the importance of maximum flow. This instance is to be solved under certain constraints , to design the most freight train n

7、umbers through the railway in a day and night and to list out the schedules for each train. In this instance, by abstracting the network diagram from the real problems, transform the actual problem into the maximum flow problem, and use the properties of graph and Ford-Fulkerson labeling algorithm,

8、and ultimately solve the problem.In this paper, the combination of theory and examples focus on solving practical problems by applying theoretical basis. It has strong practicality andhighlights the applications.Maximum flowKeywords ： Graph Network flowMaximum flow目錄 TOC o 1-5 h z HYPERLINK l bookma

9、rk6 o Current Document 第一章 緒論 1 HYPERLINK l bookmark8 o Current Document 最大流問題的研究內(nèi)容及背景 1 HYPERLINK l bookmark10 o Current Document 最大流問題的發(fā)展?fàn)顩r 1 HYPERLINK l bookmark12 o Current Document 選題的意義 2 HYPERLINK l bookmark20 o Current Document 第二章 預(yù)備知識 4 HYPERLINK l bookmark22 o Current Document 2.1 圖論 4 HY

10、PERLINK l bookmark24 o Current Document 2.2 網(wǎng)絡(luò)的基本概念 5 HYPERLINK l bookmark36 o Current Document 2.3最大流問題核心依據(jù)Ford-Fulkerson最大流最小割定理7 HYPERLINK l bookmark52 o Current Document 第三章 最大流問題的幾種算法 9 HYPERLINK l bookmark54 o Current Document 標(biāo)號法（Ford-Fulkerson 算法）9 HYPERLINK l bookmark66 o Current Document E

11、dmonds-Karp 修正算法 12 HYPERLINK l bookmark68 o Current Document Dinic 算法15 HYPERLINK l bookmark72 o Current Document 第四章 最大流問題的應(yīng)用 19 HYPERLINK l bookmark74 o Current Document 4.1 鐵路貨運(yùn)列車的最優(yōu)調(diào)度19 HYPERLINK l bookmark126 o Current Document 第五章 結(jié)論 30參 考 文 獻(xiàn) 31 HYPERLINK l bookmark132 o Current Document 致謝辭

12、 32 HYPERLINK l bookmark134 o Current Document 附錄 1英文原文 33 HYPERLINK l bookmark136 o Current Document 附錄 2中文譯文 37第一章 緒論最大流問題的研究內(nèi)容及背景最大流問題也就是是指網(wǎng)絡(luò)分析問題的一類，它是在指定的條件下,要 求通過網(wǎng)絡(luò)的物流、能量流、信息流等流量為最大的問題。比如交通運(yùn)輸 網(wǎng)絡(luò)中的人流、車流、物流,供水網(wǎng)絡(luò)中的水流、金融系統(tǒng)中的現(xiàn)金流通信 系統(tǒng)中的信息流等等，都屬于最大流問題。圖論是組合數(shù) 學(xué)的個分支與其他的數(shù)學(xué)分支如群論、矩陣論、概 率論、拓?fù)鋵W(xué)、數(shù)值分析有著密切的聯(lián)系而且

13、其應(yīng)用十分廣泛，是近年來 較為活躍的數(shù)學(xué)分支之一。它的產(chǎn)生和 發(fā)展歷經(jīng)了二百多年的歷史，瑞士 數(shù)學(xué)家歐拉(L. Euler)在1736年解決了當(dāng)時頗為有名的一個數(shù)學(xué)難題，即 哥尼斯城堡七橋問題，從而使他成了圖論和拓?fù)鋵W(xué)的創(chuàng)始人。早期的圖論 與數(shù)學(xué)游戲有密切的聯(lián)系，如哈密爾頓 的周游世界問題、迷宮問題、博奕 問題以及棋盤上馬的行走路線之類的難題等吸引了許多學(xué)者。20世紀(jì)后， 圖論的應(yīng)用滲透到許多其他學(xué)科領(lǐng)域，如物理、化學(xué)、信息學(xué)、運(yùn)籌學(xué)、 博奕論、計算機(jī)網(wǎng)絡(luò)、社會學(xué)以及集合論、矩陣論等。從 20 世紀(jì)50 年代 以后，由于計算機(jī)的迅速發(fā)展，有力地推動了圖論的發(fā)展，使圖論成為數(shù) 學(xué)領(lǐng)域中發(fā)展最快的

14、分支之一，也成為現(xiàn)代研究最大流問題的一個重要工 具。最大流問題的發(fā)展?fàn)顩r最大流問題是早期的線性網(wǎng)絡(luò)最優(yōu)化的一個例子。最早研究這類問題 的是美國學(xué)者希奇柯克(H itchcock), 1941年他在研究生產(chǎn)組織和鐵路運(yùn) 輸方 面 的 線性 規(guī) 劃 問題 時 提 出運(yùn) 輸 問 題的 基 本 模 型 ； 后來 柯 普 曼(Koopmans)在1947年獨(dú)立地提出運(yùn)輸問題并詳細(xì)地對此問題加以討論； 從上世紀(jì)40年代早期開始，康脫洛維奇(Kantorovich)圍繞著運(yùn)輸問題作 了大量的研究，因此運(yùn)輸問題又稱為希奇柯克問題或康脫洛維奇問題。與 一般線性規(guī)劃問題不同，它的約束方程組的系數(shù)矩陣具有特殊的結(jié)構(gòu)

15、，這 就需要采用不同的甚至更為簡便的求解方法來解決這種在實際工作中經(jīng)常 遇到的問題。運(yùn)輸問題不僅代表了物資合理調(diào)運(yùn)、車輛合理調(diào)度等問題， 有些其他類型的問題經(jīng)過適當(dāng)變換后也可以歸結(jié)為運(yùn)輸問題。后來把這種 解決線性網(wǎng)絡(luò)最優(yōu)化的方法與最大流問題相結(jié)合，同時推動了最大流問題 的發(fā)展。最大流問題就是就是在一個有向連通圖中，指定一點(diǎn)為發(fā)點(diǎn)，另一點(diǎn) 為收點(diǎn)，其余的點(diǎn)為中間點(diǎn)，在所有的點(diǎn) 都能承載的情況下能通過此網(wǎng)絡(luò) 圖的最大可行流，即發(fā)點(diǎn)發(fā)往收點(diǎn)的最大可行流。本課題的意義在于掌握 最大流問題的基本理論和算法來解決實際應(yīng)用問題，提高生產(chǎn)的有效性和 生產(chǎn)設(shè)備的有效利用率。最大流問題應(yīng)用極為廣泛，很多生活中的問

16、題都可轉(zhuǎn)化為最大流問題， 其難點(diǎn)是從實際中抽象出最大流模型，即轉(zhuǎn)化問題，且實踐性較強(qiáng)，通過 實例分析，更有利于對最大流問題的了解與應(yīng)用。1.3 選題的意義在日常生活和生產(chǎn)中我們時常遇到一些網(wǎng)絡(luò)圖。如交通圖、旅游線路 圖、管道系統(tǒng)圖等。在優(yōu)化理論 中所謂圖就是上述各類圖的抽象和概括， 用圖來描述我們的研究對象，以及這些對象之間的相互聯(lián)系。例如旅游管 理、網(wǎng)絡(luò)通信、交通運(yùn)輸、金融系統(tǒng)等問題都可以用網(wǎng)絡(luò)圖來描述。最大流問題就是就是在一個有向連通圖中，指定一點(diǎn)為發(fā)點(diǎn)，另一點(diǎn) 為收點(diǎn)，其余的點(diǎn)為中間點(diǎn)，在所有的點(diǎn) 都能承載的情況下能通過此網(wǎng)絡(luò) 圖的最大可行流，即發(fā)點(diǎn)發(fā)往收點(diǎn)的最大可行流。本課題的意義在于

17、掌握 最大流問題的基本理論和算法來解決實際應(yīng)用問題，提高生產(chǎn)的有效性和 生產(chǎn)設(shè)備的有效利用率。最大流問題應(yīng)用極為廣泛，很多生活中的問題都可轉(zhuǎn)化為最大流問題， 其難點(diǎn)是從實際中抽象出最大流模型，即轉(zhuǎn)化問題，且實踐性較強(qiáng)，通過 實例分析，更有利于對最大流問題的了解與應(yīng)用。第二章 預(yù)備知識2.1 圖論所謂“圖論”，顧名思義也就是是研究“圖”的理論。圖論中的“圖”是由 許多實際問題經(jīng)過抽象而得到，由點(diǎn)及點(diǎn)與點(diǎn)之間的連線構(gòu)成，它可以反 映一些對象之間的關(guān)系。圖形中的點(diǎn)表示對象(如工序、選手、通訊站等)， 兩點(diǎn)之間的有向或無向連線表示對象之間具有某種特定的關(guān)系 (如先后關(guān) 系、勝負(fù)關(guān)系、傳遞關(guān)系、連接關(guān)系

18、等)。物質(zhì)結(jié)構(gòu)、電路網(wǎng)絡(luò)、城市規(guī)劃、交通運(yùn)輸、信息傳遞、物資調(diào)配等 都可以用點(diǎn)和線連 接起來的圖進(jìn)行模擬。這里所研究的圖與平面幾何中的 圖不同，這里只關(guān)心圖中有多少個點(diǎn)，點(diǎn)與點(diǎn)之間有無連線，至于連線的 方式是直線還是曲線，點(diǎn)與點(diǎn)的 v ,v 相對位置如何，都是無關(guān)緊要的。ij定義 1：兩點(diǎn)之間不帶箭頭的連線稱為邊，一條連接 v ,v 的邊記為 v (或i j sv , v )，表示邊的集合。ij定義2：兩點(diǎn)之間帶箭頭的連線稱為E = e ,e,e 弧,一條以v .為始點(diǎn)v.1 2 m i j為終點(diǎn)的弧記為a = (v , v ), A = a ,a，a 表示弧的集合。i i j 1 2 m定義

19、3：由點(diǎn)和邊構(gòu)成的圖為無向圖，記為G二(V,E)；由點(diǎn)和弧構(gòu)成的圖為有向圖，記為D二(V,A).定 義 4 ： 在 無 向 圖 G 中 ， 若 存 在 一 個 點(diǎn) 邊 交 錯 序 列(v , e , v , e , v , e , v ) ，滿足e = v , v (t = 1,2,. k -1),則稱之為一條聯(lián)結(jié)v和v的鏈記為 TOC o 1-5 h z +1Z1ik(v ,v ,v ),若v = v ,貝y稱之為圈。i1 i2iki1 ik定義 5：在有向圖 D 中， 若 存在一 個點(diǎn)弧交錯序列(v ,a ,v ,a ,. v ,a ) ， 弧 a 的始點(diǎn)為 v ， 終點(diǎn)為 v ， 記為i

20、1 i1 i2 i2ik-1 ik -1ititit+1a = (v , v ),則稱這條點(diǎn)弧的交錯序列為從 v到v的一條路，記為itit it +1i1ik(v ,v ,. ,v )。若路的第一點(diǎn)和最后一點(diǎn)相同，則稱之為回路。鏈與路中i1 i2ik的點(diǎn)互不相同，則為初等鏈(路)，以后說到的鏈與路，均指初等鏈(路)。定義6：如果對于一個無向圖G的每一條邊，相應(yīng)有一個權(quán)數(shù)w，則稱這ij樣的圖為賦權(quán)圖，記為G二(V,E,C)。定義7：如果對于一個有向圖D的每一條弧，相應(yīng)有一個權(quán)數(shù)c，稱這樣ij的圖為網(wǎng)絡(luò)，記為D = (V, A,C)。一般在網(wǎng)絡(luò)圖中，每條弧的權(quán)，不是表示弧的長度、而是表示弧的寬度，

21、即代表距離、費(fèi)用、通過能力(容量)等等。例如，公路運(yùn)輸網(wǎng)絡(luò)中路 面的寬度或管道輸送網(wǎng)絡(luò)中管道的直徑，它是單位時間內(nèi)允許通過實體的 數(shù)量。所以將弧權(quán)稱為弧的容量，網(wǎng)絡(luò)稱為容量網(wǎng)絡(luò)(參見文獻(xiàn)17)。定義8：在圖G中，若任何兩個點(diǎn)之間至少有一條鏈(或一條路)，則稱G 是連通圖，否則，稱為不連通圖。2.2 網(wǎng)絡(luò)的基本概念假設(shè)要把起點(diǎn)的一批流轉(zhuǎn)物運(yùn)送到終點(diǎn)去，在每一弧上通過流轉(zhuǎn)物的 總量不能超過這條弧上的容量，問題是應(yīng)該怎樣安排運(yùn)送，才能使從起點(diǎn)運(yùn)送至終點(diǎn)的總量達(dá)到最大，這樣的問題就稱為網(wǎng)絡(luò)上最大流問題，最大流問題是網(wǎng)絡(luò)流問題中的一個非常重要的研究內(nèi)容(參見文獻(xiàn)15)，以下討論的網(wǎng)絡(luò)均為只有一個發(fā)點(diǎn)v和

22、一個收點(diǎn)v的容量網(wǎng)絡(luò)D = (V,A,C)。 st定義9：對任意容量網(wǎng)絡(luò)D = (V,A,C)中的弧(v ,v )有流量f ,稱集合i j ijf二 f 為網(wǎng)絡(luò)D上的一個流，稱滿足下列條件的流f為可行流：ij容量限制條件：對D中每條弧(v , v )，有0 f C ；i j ij ij平衡條件：對中間點(diǎn)v，有工f =Sf (即中間點(diǎn)v的物資的輸入量與輸出i ij ki ijk量相等)。對收、發(fā)點(diǎn)v , v 有工f.=S f. =W (即從v點(diǎn)發(fā)出的物資總量t s si jt sij等于v點(diǎn)入的量)，W為網(wǎng)絡(luò)流的總流量。t在容量網(wǎng)絡(luò)D二(V, A, C)中c表示弧(v , v )的容量，令x為通

23、過弧 ij i j ij(v ,v )的流量，顯然有0 x c，流x 應(yīng)遵守點(diǎn)守恒規(guī)則，即: i j ij ij iji = si 豐 si = si 豐 s, ti=t工x _工x = 0ij ji_W稱為守恒方程。定義10：對任意容量網(wǎng)絡(luò)D = (V, A, C)，尋求一可行流f使得流量W取得極大值，這個可行流 f 便稱為最大流。定義11：在容量網(wǎng)絡(luò)D = (V, A,C)中，若卩為網(wǎng)絡(luò)中從發(fā)點(diǎn)v到收點(diǎn)v的 st一條路，給卩定向為從v到v，卩上的弧凡與卩同向稱為前向弧。凡與卩反 st向稱為后向弧，其集合分別用卩+和卩-表示，f是一個可行流，如果滿足0 f f 0(v , v ) up-ij

24、 iji j則稱p為從v到v的(關(guān)于f的)增廣鏈。st定義12：在容量網(wǎng)絡(luò)G二(V, A, C)中，若有弧集A為A的子集，將D分為兩個子圖D ,D，其頂點(diǎn)集合分別記S,S，SUS = V,SflS = 0，v ,v分別12st屬于S, S，滿足：D(V, A - A)不連通;A為A的真子集，而D(V, A - A)仍連通，則稱A為D的割集，記A = (S, S)。害I集(S, S)中所有始點(diǎn)在S，終點(diǎn)在S的邊的容量之和，稱為(S, S)的割集容量，記為C(S, S)。2.3最大流問題核心依據(jù)Ford-Fulkerson最大流最小割定理Ford-Fulkerson 最大流最小割定理是由 Ford

25、 和 Fulkerson 在 1956 年提 出的，是圖論的核心定理。定理1： (Ford-Fulkerson最大流最小割定理)任一容量網(wǎng)絡(luò)D中，從v到v st的最大流f 的流量等于分離v ,v的最小割的容量。ijs t證明：設(shè)在D中從v到v的任一可行流x 的流量為W，最小割集為s tij(S,S)，最小割集的容量為C(S,S)。這個定理的證明分兩步：我們先證明W - C(S,S):由守恒方程可得：W =工(工x -工x ) TOC o 1-5 h z ijjiieSjj=乙乙(x - x ) +乙乙(x - x )ij ji一 j jiieS jeSieS jeS=ZZ (x -x )(3.

26、1)ij jiieS jeS因此有： W -工工(x - x ) f時，即流出未飽i j j ij ij和弧，給v以標(biāo)號0 , v ；j j i而且 f 0時，即流入非零ji對每一弧 （v ,而且 f 0時，即流入非零jij i j流弧，給v以標(biāo)號0，-v ；j j i 步驟3 重復(fù)步驟2直到收點(diǎn)v被標(biāo)號，或不再有頂點(diǎn)可以標(biāo)號為止。其中：0j二min其中：0j二min0 ,a,a 二ic fij ij若（v , v ）為流出未飽和弧ij若（v , v ）為流入非零流弧 jit如果點(diǎn)給了標(biāo)號說明存在一條增廣路徑，故轉(zhuǎn)向增廣過程B。如若點(diǎn)vt 不能獲得標(biāo)號，而且不存在其它可標(biāo)號的頂點(diǎn)時，算法結(jié)束，

27、所得到的流 便是最大流。B：增廣過程由終點(diǎn)v開始，使用標(biāo)號的第二個元素構(gòu)造一條增廣路徑卩（點(diǎn)v的標(biāo)tt 號的第二個元素表示在路中倒數(shù)第二個點(diǎn)的下標(biāo)，而這第二個點(diǎn)的標(biāo)號的 第二個元素表示倒數(shù)第三個點(diǎn)的下標(biāo)等等），在卩上作調(diào)整得新的可行流 f ，（標(biāo)號的第二個元素的正負(fù)號表示通過增加或減少弧流來增大流值）。 ij令0為v標(biāo)號的第一個元素的值，作tf +0（v ,v ）是卩上前向弧_iji jf = f -0（v , v ）是卩上后向弧ijijj if 其它ij以新的可行流f代替原來的可行流，去掉所有標(biāo)號，轉(zhuǎn)標(biāo)號過程的步驟ij1。采用 Ford-Fulkerson 標(biāo)號算法求解最大流問題，同時得到一

28、個最小割 集。最小割集的意義是：網(wǎng)絡(luò)從發(fā)點(diǎn)到收點(diǎn)的各個通路中，由容量決定其 通過能力，通常我們將最小割集形象地稱為這些通路的咽喉部分，或叫做 “瓶頸”，它決定了整個網(wǎng)絡(luò)的通過能力，即最小割集的容量的大小影響總 的流量的提高。因此，為提高總的流量，必須首先考慮改善最小割集中各 小弧的流量，提高它們的通過能力（參見文獻(xiàn)14）。3.2 Edmonds-Karp 修正算法Ford-Fulkerson 標(biāo)號算法理論上存在著嚴(yán)重的弱點(diǎn)，以下圖 3.2.1 為例 各邊上的權(quán)是它們的容量，其最大流流量為 2m ，若增廣路徑選擇得不好, 即交替地采用sabeft和Sdebct作為增廣路徑，則每次增廣只能使總的流

29、量增 加1,當(dāng)初始流選為零流，無疑需作2m 1次的增加流量才能使之達(dá)到最大, 可見 Ford-Fulkerson 算法的時間復(fù)雜度不僅依賴于網(wǎng)絡(luò)的規(guī)模（即依賴于網(wǎng) 絡(luò)點(diǎn)數(shù)和邊數(shù)），還和各邊的容量有關(guān),而容量可以是任意的正整數(shù)。如圖 3.2.1 中，當(dāng) sabeft 和 sdebct 交替作為增廣路徑時， be 弧交替地以前向弧和 后向弧出現(xiàn)。利用 Ford-Fulkerson 算法求解就很麻煩了（參見文獻(xiàn)8）。對于 Ford-Fulkerson 算法,由于增廣路徑選取的任意性造成了該算法不 是好算法， Edmonds 和 Karp 對 Ford-Fulkerson 算法作修正，可概括為一句 話

30、：“先給標(biāo)號的先掃描”。它的意思是對已給標(biāo)號的頂點(diǎn)v進(jìn)行掃描時， 先對所有和v鄰接的未給標(biāo)號的頂點(diǎn)給予標(biāo)號。具體的說圖321的例子， 頂點(diǎn)s先標(biāo)記，所以應(yīng)該先掃描，因此避免了 Ford-Fulkerson算法那樣交替 地出現(xiàn)sabeft,sdebct的情況，也就避免了 be弧交替地以前向弧和后向弧來 回?fù)u擺的局面。所以Edmonds-Karp的修正實質(zhì)是對頂點(diǎn)給標(biāo)記過程采用了 “寬度優(yōu)先”策略。使得流量增加總是沿著一條長度最短的路徑從s流向t的 （參見文獻(xiàn)3）?，F(xiàn)在我 們?nèi)钥紤] 只有一個 發(fā)點(diǎn) v 和一個收 點(diǎn) v 的 網(wǎng)絡(luò)圖，stEdmonds-Karp 修正算法的主要步驟是：確定一初始可行

31、流f ，其流量W（f）。ij檢驗當(dāng)前所確定可行流是否是網(wǎng)絡(luò)中的最大流，若不是，需進(jìn)一步調(diào)整 （檢驗一個可行流是否為最大流。只要檢查一下當(dāng)前可行流是否還存在 增廣路徑，若存在，則說明當(dāng)前可行流還不是最大流，否則是最大流）。將當(dāng)前的可行流調(diào)整成一個流量更大的新可行流，再由檢驗。同樣地，我們通常用觀察法確定網(wǎng)絡(luò)的個初始可行流。對于較為復(fù) 雜的網(wǎng)絡(luò)，至少能把初始可行流取為零流。通過在網(wǎng)絡(luò)上標(biāo)號的方法能系 統(tǒng)地尋找出當(dāng)前可行流的增廣路徑，它的基本思想是：從起點(diǎn) v 起，逐步 s尋找V至各點(diǎn)v間的增廣路徑，若能找到v至v的一條增廣路徑，則給點(diǎn)vs i s i i標(biāo)號0 Q （其中第一個標(biāo)號0即為v至v這條

32、增廣路徑上的最大可調(diào)整i i i s i量，第二個標(biāo)號a則表示這條可行流上點(diǎn)v的前一點(diǎn)是a點(diǎn)）。根據(jù)標(biāo)號可i i i反向追蹤而寫出這條增廣路徑。在逐步擴(kuò)大已標(biāo)號的過程中，一旦終點(diǎn)v標(biāo)t上號，表示已找到一條由v至v的增廣路徑。反之，如果標(biāo)號過程進(jìn)行至st某一步中止了，而v尚未標(biāo)號，則表明對當(dāng)前的可行流，網(wǎng)絡(luò)中不存在任t何增廣路徑。當(dāng)前可行流即為最大流。 Edmonds-Karp 修正算法的具體步驟 如下： 給發(fā)點(diǎn)v標(biāo)號g,v ，含義為v至v的增廣路徑已找到，前一點(diǎn)為v，s s s s s這條增廣路徑上的調(diào)整量為-。選與v關(guān)聯(lián)的從v流出的未飽和弧(v ,v ) 或流入 v 的非零流弧 (v ,v

33、) ，給 v 標(biāo)號9 ,v (對于流出弧 )或 s i s i s i i9 , -v (對于流入弧)。is|c -f若(v ,v )為流出未飽和弧其中：9 = si sis ii I f若(v , v )為流入非零弧sii s將頂點(diǎn)集分為互補(bǔ)的二個點(diǎn)集s、S，其中S為已標(biāo)號點(diǎn)集，S為未標(biāo)號點(diǎn)集；考慮所有這樣的弧(v ,v )或(v ,v )，其中v e S,v e S。若弧(v ,v )為 i j j i i j i j從v流出的未飽和弧，則給v標(biāo)號9 ,v 。其中9 = min9 ,c - f ；i j j i j i ij ij若弧(v , v )為流入v的非零流弧，則給v標(biāo)號9 ,-v

34、 。其中j i i j j i9 = min9 , f 。依此進(jìn)行，得到的結(jié)果是： j i ij(a)S =0，說明網(wǎng)絡(luò)中存在增廣路徑卩，則由標(biāo)號點(diǎn)反向追蹤找出卩，轉(zhuǎn)第步；(b)S工0，標(biāo)號已進(jìn)行不下去，說明對于當(dāng)前可行流。網(wǎng)絡(luò)中已無新的增廣路徑，當(dāng)前可行流即為最大流，同時得到最小割集(S,S)。f +9(v ,v )是卩上前向弧調(diào)整過程：取9 調(diào)整過程：取9 = min9 ，令f =vyef -9(v ,v )是卩上后向弧ijj if 其它ij得到新可行流f ，流量W(/) = W(/) +9，即比原可行流流量增加了9， ij再轉(zhuǎn)步。用 Edmonds-Karp 修正算法求解最大流問題時，也

35、可以得到一個最小 割集。最小割集的意義同 Ford-Fulkerson 算法得到的最小割集的意義相同。3.3 Dinic 算法Dinic于1970年提出了 Ford-Fulkerson算法的改進(jìn)算法，Dinic算法的 特點(diǎn)是將頂點(diǎn)按其與發(fā)點(diǎn)的最短距離分層。Edmonds-Karp修正算法的實質(zhì) 也是一種分層，如果說 Ford-Fulkerson 算法是采用了深度優(yōu)先策略。 Edmonds-Karp 修正算法則是用寬度優(yōu)先取代了深度優(yōu)先， Dinic 算法則是 兼取這兩種方法。在分層時用的寬度優(yōu)先法，而尋求增廣路徑時則采用深 度優(yōu)先策略(參見文獻(xiàn)3)。3.3.1 增量網(wǎng)絡(luò)與分層增量網(wǎng)絡(luò)定義13：

36、給定一個帶發(fā)點(diǎn)v和收點(diǎn)v的容量網(wǎng)絡(luò)D二(V, A,C)及D上的st可行流f 后，我們定義ij，因為D中任A+ (f) = (v , v )|(v , 可行流f 后，我們定義 0i j j i ji何一對頂點(diǎn)之間至多有一條弧，所以A+ (f)n A- (f) = 0，記A(f) = A+ (f)U A- (f)， 并且 對一切 (v , v ) e A(f) 令i jc 一 f , 若(v , v ) e A+ (f)c = j ji j，于是得一個帶發(fā)點(diǎn)v和收點(diǎn)v的容量網(wǎng)絡(luò)ij f，若(v, v ) e A- (f)stjii jD(f) = (V, A(f),C)，稱之為D的關(guān)于可行流f 的

37、增量網(wǎng)絡(luò)。ij為了介紹分層增量網(wǎng)絡(luò)，我們先來介紹關(guān)于網(wǎng)絡(luò)的一個算法 分層算法，它的基本思想是：步驟0：把發(fā)點(diǎn)v標(biāo)為“已標(biāo)號未檢查”，v的層數(shù)h(s) = 0。ss步驟1：在已標(biāo)號未檢查頂點(diǎn)中選取最早得到標(biāo)號的頂點(diǎn)v，轉(zhuǎn)步驟2；如i果所有標(biāo)號頂點(diǎn)都已檢查，轉(zhuǎn)步驟 3。步驟2：考察頂點(diǎn)v的一切出弧(v ,v )，若v已標(biāo)號，什么也不做；否則將ii jjv標(biāo)為“已標(biāo)號未檢查”，并令h(j)二h(i) +1。當(dāng)v的所有出弧都考察完畢， ji把v改為已檢查，轉(zhuǎn)步驟1。i步驟3：如果有一些頂點(diǎn)沒有標(biāo)號，則從v到這些頂點(diǎn)不存在路；否則v為 siD的根，h(i)為D中最短(v , v )路的長。si在增量網(wǎng)絡(luò)

38、D(f)中應(yīng)用分層算法，可以求出從發(fā)點(diǎn)v到其余各頂點(diǎn)v si的最短路的長h(i)，h(i)就是頂點(diǎn)v (關(guān)于發(fā)點(diǎn)v )的層數(shù)。即v就是D(f)isi的第h(i)層頂點(diǎn)。D(f)的第0層只有一個頂點(diǎn)，把頂點(diǎn)分層后，D(f)中的弧又可以分為三類：第一類為從第i層頂點(diǎn)到第i +1層頂點(diǎn)的弧；第二類為從第i層頂點(diǎn)到同一層頂點(diǎn)的?。坏谌悶閺牡趇層頂點(diǎn)到第j層頂點(diǎn)的弧(j i)(參見文獻(xiàn)5)。定義14：對于帶發(fā)點(diǎn)v和收點(diǎn)v的容量網(wǎng)絡(luò)D二(V, A,C)，設(shè)關(guān)于可行流 stf 的增量網(wǎng)絡(luò)D(f)二(V, A(f), C)，我們定義D(f)的子網(wǎng)絡(luò) ijAD(f)二(V(f), A(f), C)如下：V(f

39、)二v Uv I h(i) h(t)tiA( f)二(v , v )I h( j)二 h(i) +1 h(t),(v , v ) e A( f) U(v , v )I h(i)二 h(t) - 1,(v , v ) e A( f)i ji ji ti t則AD(f)稱為D的關(guān)于可行流f 的分層增量網(wǎng)絡(luò)。其中第0層和第h(t) ij層分別只有一個頂點(diǎn)v和v，AD(f)的所有弧都是由第i層頂點(diǎn)指向第i +1 st層頂點(diǎn) i T及T T，則在第k站與第k+1k k+1k k +1k kk+1k +1站必發(fā)生客車追上貨車情況。否則在第k站與第k+1站之間不發(fā)生客車追上 貨車情況。（4）繪制網(wǎng)絡(luò)圖用（k

40、, T）表示第k站處于時刻T的狀態(tài)，如在T =2.3在（k, 2.6）,kkk（k, 6.6）狀態(tài)開出的貨車不會再途中被客車追上，則在圖中表現(xiàn)為（k, 2.6）及（k, 6.6）兩節(jié)點(diǎn)為起點(diǎn)的兩條水平方向的直線弧，而在（k, 4.6） 狀態(tài)下開出的貨車會在途中被客車追上，則不能從該點(diǎn)引出水平方向的直 線?。▓D4.1.2），垂直方向的直線弧并聯(lián)著同一車站的相鄰狀態(tài)。圖 4.1.2上圖中各弧旁的數(shù)字為容量，因鐵路線是單向單軌的，故水平方向的 弧容量為1,垂直方向的弧的容量為各站的岔道數(shù)量，在列出全部狀態(tài)的網(wǎng) 絡(luò)圖中求最大流，此最大流即為允許開出的最多貨運(yùn)列車數(shù)。4.1.3問題求解以貨運(yùn)列車的運(yùn)行時

41、間為基礎(chǔ)繪制網(wǎng)絡(luò)圖。（1）令T ,T ,T ,T為火車從某站開出或到達(dá)某站的時刻。依題意，若不A B C D受客車干擾則:t =0:00,2:00,4:00.At =5:00,7:00,9:00.Bt =9:00,11:00,13:00.Ct =16:00,18:00,20:00D于是貨車在相鄰兩站的運(yùn)行時間為（若不受客車干擾）：t =16:00,18:00,20:00D于是貨車在相鄰兩站的運(yùn)行時間為（若不受客車干擾）：（25點(diǎn)即翌日1點(diǎn)，余類推）T ,t ： ）5,9 7,1111,15 113,17 115,19 117,21E923?, 21,25 23,27 25,29 27,31B

42、CXXT ,t ：鬧山罰丘刼血卻扁品128!/。/ 27,34卜9,363C DXX（2）令T ,T ,T ,T 為客車從某站開出或到達(dá)某站的時刻，依題意:ABCDT =2：00,7：00,12：00,17：00,22：00AT =5：00,10：00,15：00,20：00,25：00（即1：00）BT =7：00,12：00,17：00,22：00,27：00（即3：00）CT =12：00,17：00,22：00,27：00（即3：00）， 32：00（即8：00）D于是客車在相鄰兩站之間的運(yùn)行時間為:T ,T ： 2：00,5：00, 7 ： 00,10 ： 00, 12 ： 00,1

43、5 ： 00, 17 ： 00,20 ： 00, 22：00,25：00 ABT , TBC： 5 ： 00,7 ： 00, 10 ： 00,12 ： 00, 15 ： 00,17 ： 00, 20 ： 00,22 ： 00T , TBC,.C D:b : 00,12 : oo 112: 00,17 : oo 117 : 00,22 : Oo卜2 : 00,27 : Oo卜7 : 00,32 : 00BCDA11.1,a 9OC(13 15:00：1.D . 7io匚,11 04l?:00lfl013:t0：1Q+ 】3:00+ 17:C05：00-LU 19：C0:U) I4?：m11： .

44、 19:00f71H：l：00GJ)+ 21:C0C5.D23:C09,r匚 25：C0詔：00：5:00:7:00匚嘰27X0匚嘰29:C0Elg 25:00123:001132:00 (Ul,oA-一22:001： g I*- 一24:0011.1t門幾 34:00(.門r.35:00Erill 31:t0Cl t 3?:00圖 4.1.3(3)比較(3)比較t ,T 及II ,T 我們發(fā)現(xiàn)bABAB:00,10: oo 在 k: oo,11: oo之內(nèi);17 : 00,20: 00在16 : 00,21: 00之內(nèi)。這說明若A站在6:00及16:00開出兩列貨車，則該兩列貨車在到達(dá)B站前

45、，必會被客車撞上。故這兩次貨運(yùn)列車 是不可行的。這表示在以貨運(yùn)列車的運(yùn)行時刻為基礎(chǔ)的網(wǎng)絡(luò)圖（圖4.1.3） 中為（A,6:00）及（A，16:00）兩節(jié)點(diǎn)前未引出水平方向的直線弧。該圖 的各個節(jié)點(diǎn)中僅注明貨運(yùn)列車從該站開出或到達(dá)該站的時刻，站名省略了 比較 I J 及 L ,t ,我們發(fā)現(xiàn) b:00,12：00 在（9: 00,13:00之內(nèi)；B C B C20: 00,22: 00在119 : 00,23 : 00之內(nèi)，其在圖4.1.3中的表示同前。比較說與L ,1,我們發(fā)現(xiàn) 112: 00,17: 00在 11:00,18: 00之內(nèi)；C D C D22:00,27:00在 21:00,2

46、8:00之內(nèi)，其在圖3中的表示同前。（4）圖4.1.3中各水平方向的直線弧的容量均為1。如前所述，它表示在該 時間內(nèi)，貨車在相鄰兩站的行程中不會被客車追上，故可順利地到達(dá)前方 車站。垂直方向的直線弧的通量表示各站的岔道數(shù)。（5）做網(wǎng)絡(luò)的發(fā)點(diǎn)v，并從v向A站的各狀態(tài)節(jié)點(diǎn)作輔助弧，輔助弧的容ss量等于以A站的各狀態(tài)節(jié)點(diǎn)為起點(diǎn)的各弧的容量的總和。作網(wǎng)絡(luò)的收點(diǎn)v，t并從D站的各狀態(tài)節(jié)點(diǎn)向v作輔助弧。輔助弧的容量等于以D站個狀態(tài)節(jié)點(diǎn)t為終點(diǎn)的各弧的容量總和。（6）求圖4.1.3所示容量網(wǎng)絡(luò)的最大流I）以零流f=0,0,0為初始流，但圖4.1.3的各弧旁省略了零流量。II）以v表示圖3中第i行第j列的節(jié)點(diǎn)

47、。用Ford-Fulkerson標(biāo)號法求得以ij下增廣鏈并按0值進(jìn)行調(diào)整。 v (0, g *)sv (v ,6) v (v ,1)1,1 s 1,2 1,1v(v,1) v (v ,1)1,3 1,21,4 1,3v ( v ,1)1 1,4v (Oo)sv( v ,1)3,4 3,3v (Oo)sv( v ,1)4,4 4,3v (Oo)sv ( v ,1)t 5,4v (Oo)sv ( v ,1)6,4 6,3v ( v,1)t6, 4v (Oo)sv ( v,1)8,3 7,3v( v ,1)8,4 8,3v (Oo)sv ( v,1)9,3 9,2v( v ,1)9,4 9,2v (

48、Oo)sv( v,1)1O,4 1O,3v ( v,1)t 1O,4v ( v ,6)2,1 1v ( v ,1)1 3,4v ( v ,6)3,1 sv ( v ,1)1 4,4v ( v ,6)5,1 sv6,1(vs,6)v7,1(vs,6)v ( v ,1)t 8,4v ( v ,6)8,1 sv2,2(v2,1,1)v2,3(v2,2,1)v3,2(v3,1,1)v5,2(v5,1,1)v6,2(v6,1,1)v7,2(v7,1,1)v4,2(v3,2,1)v5,3(v5,2,1)v6,3(v6,2,1)v7,3(v7,2,1)v( v ,1)9,4 9,3v( v ,6)1O,1

49、sv ( v ,1)3,3 2,39 = 1v ( v ,1)4,3 4,29 = 1v ( v ,1)5,4 5,39 = 19 = 19 = 1v ( v ,1) v (v ,1)8,2 8,1 8,2 8,2v (v ,1)9 = 1t 9,4v(v,1) v (v ,1)1O, 21O,11O,3 1O,2 v (Oo)sv11,1(vs,6) v11,2(v11,1,1) v11,3(v11,2,1)v11,4(v11,3,1)vt(v11,4,1) v (Oo)s v (Oo)sv12,1(vs,1,6)v12,2(v12,1,1)v12,3(v12,2,1)v12,4(v12,3

50、,1)v ( v,1)t 12,4=1。用它對初始流(零流)進(jìn)行調(diào)整以上10條增廣鏈的調(diào)整量均為9 后，結(jié)果如圖4.1.3所示。若對現(xiàn)行流繼續(xù)標(biāo)號，則只有A站的=1。用它對初始流(零流)進(jìn)行調(diào)整點(diǎn)獲得標(biāo)號，即標(biāo)號中斷，不能延伸達(dá) v 。故現(xiàn)行流即為最大流，其流量 tv( f) = f+ f + f + f + f + f + f + fs ,(1,1s ,( 2,1s,(3,1s ,(5,1s,(6,1s,(7,1 s ,(8,1s,(10,1+ f + f = 1 +1 +1 +1 +1 +1 +1 +1 +1 +1 = 10s,(11,1s,(12,1結(jié)論 在本問題所給條件下各車站一晝夜中

51、能開出的最多貨運(yùn)列車數(shù) 位10列?，F(xiàn)由圖4.1.3將A站以晝夜中能開出的10列貨車的運(yùn)行時刻及調(diào)度情況 闡述如(貨車一晝夜中在其他各站點(diǎn)的運(yùn)行及調(diào)度情況可由同圖作類似闡 述)在0:00,8:00,10:00,18:00,20:00,22:00時刻所開出的貨車在各站點(diǎn)均暢 通。在2:00開出的貨車，11:00到達(dá)C站時須在岔道內(nèi)停留到13:00方可繼 續(xù)前行。在4:00開出的貨車，9:00到達(dá)B站時，須在岔道內(nèi)停留到11:00方可繼 續(xù)前行。在12:00開出的貨車，21:00到達(dá)C站時，須在岔道內(nèi)停留到23:00方可 繼續(xù)前行。在14:00開出的貨車，19:00到達(dá)B站時，須在岔道內(nèi)停留到21:

52、00方可繼續(xù)前行。至此已求得一晝夜中從A站開出的10次貨運(yùn)列車的最優(yōu)調(diào)度及最優(yōu)運(yùn) 行時刻表。仿此，由圖4.1.3可求得從其他各站點(diǎn)開出貨車的最優(yōu)調(diào)度及最優(yōu)運(yùn)行時刻 表。4.1.4 問題總結(jié)本問題看似簡單，是個追趕問題，只要計算出貨車與客車在兩站之間 的運(yùn)行時間即可控制貨車的開出時間，其實不然，此問題是在追趕問題的 基礎(chǔ)上求最多可開出的貨車輛數(shù)，我們把該問題轉(zhuǎn)化成為最大流問題，應(yīng) 用Ford-Fulkerson標(biāo)號法解決了這一問題。通過對算法的分析求解制定出了 貨車運(yùn)行的最大數(shù)量并列出貨車運(yùn)行時間表，可見最大流算法的有效性和 實用性。第五章 結(jié)論本課題主要以圖論的知識為理論基礎(chǔ)，來討論最大流問題

53、。最大流問 題是一類應(yīng)用極為廣泛的問題，20世紀(jì)50年代福特(Ford)、富克遜 (Fulkerson )建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。最大流問題的核心依據(jù)是Ford-Fulkerson最大流最小割定理，在這個 定理的基礎(chǔ)上，解決最大流問題的幾種算法有Ford-Fulkerson標(biāo)號法、 Edmonds-Karp 修正算法、 Dinic 算法等本論文分別介紹了這幾種算法，并 舉實例說明各個算法具體的解題過程，各算法的優(yōu)劣各不相同， Ford-Fulkerson標(biāo)號法是最原始的算法，由Ford和Fulkerson提出,Edmonds 和 Karp 針對該算法增廣路徑選取的任意性

54、這一缺點(diǎn)對它做了修正算法產(chǎn) 生了 Edmonds-Karp修正算法，而Dinic算法則兼取前兩種算法的優(yōu)點(diǎn)，是 這三種算法中最有效的算法。最大流問題是網(wǎng)絡(luò)流問題的一個重要的內(nèi)容，研究最大流問題并將其 應(yīng)用到工業(yè)、工程、商業(yè)、農(nóng)業(yè)，運(yùn)輸業(yè)等領(lǐng)域可給我們的生活帶來很大 方便。在很多情況下，實際遇到的問題可能是很復(fù)雜的，甚至是無從下手， 不過通過分析建立模型，如果可以建立成一個網(wǎng)絡(luò)圖，轉(zhuǎn)化成為最大流問 題，就會找到相應(yīng)的解決方法。由此，最大流問題在現(xiàn)實生活中是非常重 要的。參考文獻(xiàn)熊義杰運(yùn)籌學(xué)教程天津：國防工業(yè)出版社，2004徐俊明. 圖論及其應(yīng)用. 合肥：中國科學(xué)技術(shù)大學(xué)出版社，2005盧開澄.

55、圖論及其應(yīng)用. 北京：清華大學(xué)出版社，1984吳育華，杜綱管理科學(xué)基礎(chǔ)天津：天津大學(xué)出版社，2001謝政，李建平. 網(wǎng)絡(luò)算法與復(fù)雜性理論. 北京：國防科技大學(xué)出版社， 1995刁在筠，鄭漢鼎，劉家壯，劉桂真. 運(yùn)籌學(xué). 第 2 版. 北京：高等教育 出版社，2001田豐，馬仲蕃. 圖與網(wǎng)絡(luò)流理論. 北京：科學(xué)出版社，1987卜月華，吳建專. 圖論及其應(yīng)用. 南京：東南大學(xué)出版社， 2000Bondy JA, Mutry USR. Graph Theory with Applications. London and Basingstoke: MacMillan Press, 1976王樹禾. 圖

56、論及其算法. 合肥：中國科學(xué)技術(shù)大學(xué)出版社，1990戴一奇. 圖論及其應(yīng)用. 北京：水利電力出版社，1988展丙軍運(yùn)籌學(xué)哈爾濱：哈爾濱地圖出版社，2005運(yùn)籌學(xué)教材編寫組. 運(yùn)籌學(xué). 第 3 版. 北京: 清華大學(xué)出版社，2004胡運(yùn)權(quán)運(yùn)籌學(xué)教程北京：清華大學(xué)出版社，2007謝金星，邢文順. 網(wǎng)絡(luò)優(yōu)化. 北京：清華大學(xué)出版社，2000李向東. 運(yùn)籌學(xué)：管理科學(xué)基礎(chǔ). 北京：北京理工大學(xué)出版社，1990李建中, 駱吉洲（譯）. 圖論導(dǎo)引. 北京：機(jī)械工業(yè)出版社，2006王朝瑞. 圖論. 北京：北京工業(yè)學(xué)院出版社，1987致謝辭本科畢業(yè)論文即將完成，回顧我大學(xué)四年的學(xué)習(xí)生涯，我得到了眾多 老師的教

57、誨，同學(xué)的支持和幫助，再次對他們表示中心的感謝。首先感謝我的導(dǎo)師王朝陽老師，他生活中待人十分熱情誠懇，給予我 無微不至的關(guān)懷和照顧；工作中他治學(xué)嚴(yán)謹(jǐn)，思維活躍，在研究課題閱讀 文獻(xiàn)、論文寫作上給予我許多指導(dǎo)和幫助，使我對數(shù)學(xué)的認(rèn)識有了很大的 提高，我將銘記恩師的教誨、關(guān)心和幫助。還要感謝大學(xué)四年來所有的老師，為我們打下堅實的數(shù)學(xué)專業(yè)知識基 礎(chǔ)，在論文的寫作過程中，還要感謝班內(nèi)同學(xué)的幫助，他們在我完成論文 的過程中，給我提了許多寶貴的建議，正是因為有了你們的支持和鼓勵。 此次畢業(yè)設(shè)計才能夠順利的完成。感謝所有給予我?guī)椭湾憻挼娜?。最后，衷心感謝所有老師對我的栽培、支持和鼓勵，感謝所有朋友的 關(guān)心

58、和幫助。向在百忙中抽出時間對此論文進(jìn)行評審并提出寶貴意見的各 位專家表示衷心地感謝！衷心祝愿母校山東科技大學(xué)明天更加美好！附錄 1英文原文Maximum flow problem in the introduction, we listed one of the largest flow of goods delivery. If this issue also includes the known conditions of delivery of each unit while the cost of goods, then how to transport, to get the mos

59、t traffic, and transportation costs to a minimum? This is the so-called maximum flow problem minimum cost. The maximum flow based on the definition, if each side of a first-priority claim to the number of c(e) (that the edge capacity) but also have another weights w(e) (that the unit cost flow), and

60、 has been seeking a maximum flow of the network value of F, then the minimum cost maximum flow problem, it is clear the following linear programming model can be used to describe:min Y w(e) f (e) e e ESatisfy 0 f (e) 0, then G in the building edge (u, v), to empower the w (u, v) = -w(u, v).The estab