畢業(yè)設(shè)計(jì)---最大流問(wèn)題及應(yīng)用

1、<p>　　本科畢業(yè)設(shè)計(jì)（論文）</p><p>　　題 目 最大流問(wèn)題以及應(yīng)用 </p><p>　　學(xué) 院 名 稱(chēng) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院 </p><p>　　專(zhuān)業(yè)班級(jí) </p><p>　　學(xué)生姓名 <

2、;/p><p>　　學(xué) 號(hào) </p><p><b>　　摘要</b></p><p>　　網(wǎng)絡(luò)流問(wèn)題是運(yùn)籌學(xué)的重要研究課題。最大流問(wèn)題是網(wǎng)絡(luò)流問(wèn)題的一個(gè)重要的內(nèi)容，應(yīng)用極為廣泛。研究最大流問(wèn)題并將其應(yīng)用到工業(yè)、工程、商業(yè)、農(nóng)業(yè)，運(yùn)輸業(yè)等領(lǐng)域可給我們的生活帶來(lái)很大方便。 </p>

3、<p>　　本論文討論最大流問(wèn)題，綜述圖論的歷史背景、基本概念和基本知識(shí)；闡述網(wǎng)絡(luò)的基本概念；介紹最大流問(wèn)題的核心依據(jù)——Ford-Fulkerson最大流最小割定理；綜述解決最大流問(wèn)題的 幾種算法Ford-Fulkerson標(biāo)號(hào)法、Edmonds-Karp修正算法、Dinic算法，并比較各算法在解決不同問(wèn)題中的優(yōu)劣。</p><p>　　為了更加明確的展現(xiàn)最大流問(wèn)題在生產(chǎn)生活中的應(yīng)用，本文例舉了一個(gè)實(shí)

4、際生活中的問(wèn)題——鐵路貨運(yùn)列車(chē)的最優(yōu)調(diào)度來(lái)突出研究最大流問(wèn)題的重要意義，此實(shí)例需要求解的是在一定的限制條件下，設(shè)計(jì)出一個(gè)在一晝夜間能通過(guò)某段鐵路的最多的貨運(yùn)列車(chē)數(shù)量并列出每 輛列車(chē)開(kāi)出的時(shí)刻表。在此實(shí)例中，通過(guò)從實(shí)際問(wèn)題中抽象出網(wǎng)絡(luò)圖，將實(shí)際問(wèn)題轉(zhuǎn)化為最大流問(wèn)題并應(yīng)用圖的性質(zhì)和Ford-Fulkerson標(biāo)號(hào)法的算法依據(jù)，最終解決了問(wèn)題。</p><p>　　本文采用理論與 實(shí)例相結(jié)合，重在應(yīng)用理論依據(jù)解決實(shí)際問(wèn)

5、題，具有較強(qiáng)的實(shí)踐性，突出的是應(yīng)用。</p><p><b>　　Abstract</b></p><p>　　The network flow problem is an important operational research subject. The maximum flow problem is an important content of networ

6、k 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 bring us great convenience. <

7、/p><p>　　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

8、 the maximum flow problem -- Ford-Fulkerson maximum flow minimum cut theorem is introduced. Several algorithms for solving maximal-flow problem like Ford-Fulkerson labeling algorithm, Edmonds-Karp correct algorithm, Dini

9、c algorithm are summarized in this paper. It also compares various algorithms t</p><p>　　In order to more clearly show the application of the maximum flow problem in the production life, the paper illustrate

10、s 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 numbers thr

11、ough 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, tra</p><p>　　In this paper, the combination of t

12、heory and examples focus on solving practical problems by applying theoretical basis. It has strong practicality and highlights the applications. 字典</p><p>　　Keywords： Graph Network flow Maximum flow <

13、;/p><p><b>　　目錄</b></p><p><b>　　第一章 緒論1</b></p><p>　　1.1 最大流問(wèn)題的研究?jī)?nèi)容及背景1</p><p>　　1.2 最大流問(wèn)題的發(fā)展?fàn)顩r1</p><p>　　1.3 選題的意義2</p>&l

14、t;p>　　第二章 預(yù)備知識(shí)4</p><p><b>　　2.1 圖論4</b></p><p>　　2.2 網(wǎng)絡(luò)的基本概念6</p><p>　　2.3 最大流問(wèn)題核心依據(jù)——Ford-Fulkerson最大流最小割定理7</p><p>　　第三章 最大流問(wèn)題的幾種算法9</p>

15、<p>　　3.1 標(biāo)號(hào)法(Ford-Fulkerson算法)9</p><p>　　3.2 Edmonds-Karp修正算法11</p><p>　　3.3 Dinic算法15</p><p>　　第四章 最大流問(wèn)題的應(yīng)用19</p><p>　　4.1 鐵路貨運(yùn)列車(chē)的最優(yōu)調(diào)度19</p><

16、p>　　第五章 結(jié)論30</p><p>　　參 考 文 獻(xiàn)31</p><p><b>　　致謝辭32</b></p><p>　　附錄1英文原文33</p><p>　　附錄2中文譯文37</p><p><b>　　第一章 緒論 </b></p

17、><p>　　1.1 最大流問(wèn)題的研究?jī)?nèi)容及背景</p><p>　　最大流問(wèn)題也就是是指網(wǎng)絡(luò)分析問(wèn)題的一類(lèi)，它是在指定的條件下,要求通過(guò)網(wǎng)絡(luò)的物流、能量流、信息流等流量為最大的問(wèn)題。比如交通運(yùn)輸網(wǎng)絡(luò)中的人流、車(chē)流、物流,供水網(wǎng)絡(luò)中的水流、金融系統(tǒng)中的現(xiàn)金流通信系統(tǒng)中的信息流等等，都屬于最大流問(wèn)題。</p><p>　　圖論是組合數(shù) 學(xué)的—個(gè)分支與其他的數(shù)學(xué)分支如群論、

18、矩陣論、概率論、拓?fù)鋵W(xué)、數(shù)值分析有著密切的聯(lián)系而且其應(yīng)用十分廣泛，是近年來(lái)較為活躍的數(shù)學(xué)分支之一。它的產(chǎn)生和 發(fā)展歷經(jīng)了二百多年的歷史，瑞士數(shù)學(xué)家歐拉(L．Euler)在1736年解決了當(dāng)時(shí)頗為有名的一個(gè)數(shù)學(xué)難題，即哥尼斯城堡七橋問(wèn)題，從而使他成了圖論和拓?fù)鋵W(xué)的創(chuàng)始人。早期的圖論與數(shù)學(xué)游戲有密切的聯(lián)系，如哈密爾頓 的周游世界問(wèn)題、迷宮問(wèn)題、博奕問(wèn)題以及棋盤(pán)上馬的行走路線之類(lèi)的難題等吸引了許多學(xué)者。20世紀(jì)后，圖論的應(yīng)用滲透到許多其他學(xué)科

19、領(lǐng)域，如物理、化學(xué)、信息學(xué)、運(yùn)籌學(xué)、博奕論、計(jì)算機(jī)網(wǎng)絡(luò)、社會(huì)學(xué)以及集合論、矩陣論等。從20世紀(jì)50年代以后，由于計(jì)算機(jī)的迅速發(fā)展，有力地推動(dòng)了圖論的發(fā)展，使圖論成為數(shù)學(xué)領(lǐng)域中發(fā)展最快的分支之一，也成為現(xiàn)代研究最大流問(wèn)題的一個(gè)重要工具。</p><p>　　1.2 最大流問(wèn)題的發(fā)展?fàn)顩r</p><p>　　最大流問(wèn)題是早期的線性網(wǎng)絡(luò)最優(yōu)化的一個(gè)例子。最早研究這類(lèi)問(wèn)題的是美國(guó)學(xué)者希奇柯克（Hi

20、tchcock），1941年他在研究生產(chǎn)組織和鐵路運(yùn)輸方面的線性規(guī)劃問(wèn)題時(shí)提出運(yùn)輸問(wèn)題的基本模 型；后來(lái)柯普曼（Koopmans）在1947年獨(dú)立地提出運(yùn)輸問(wèn)題并詳細(xì)地對(duì)此問(wèn)題加以討論；從上世紀(jì)40年代早期開(kāi)始，康脫洛維奇（Kantorovich）圍繞著運(yùn)輸問(wèn)題作了大量的研究，因此運(yùn)輸問(wèn)題又稱(chēng)為希奇柯克問(wèn)題或康脫洛維奇問(wèn)題。與 一般線性規(guī)劃問(wèn)題不同，它的約束方程組的系數(shù)矩陣具有特殊的結(jié)構(gòu)，這就需要采用不同的甚至更為簡(jiǎn)便的求解方法來(lái)解決這

21、種在實(shí)際工作中經(jīng)常遇到的問(wèn)題。運(yùn)輸問(wèn)題不僅代表了物資合理調(diào)運(yùn)、車(chē)輛合理調(diào)度等問(wèn)題，有些其他類(lèi)型的問(wèn)題經(jīng)過(guò)適當(dāng)變換后也可以歸結(jié)為運(yùn)輸問(wèn)題。后來(lái)把這種解決線性網(wǎng)絡(luò)最優(yōu)化的方法與最大流問(wèn)題相結(jié)合，同時(shí)推動(dòng)了最大流問(wèn)題的發(fā)展。</p><p>　　最大流問(wèn)題就是就是在一個(gè)有向連通圖中，指定一點(diǎn)為發(fā)點(diǎn)，另一點(diǎn)</p><p>　　為收點(diǎn)，其余的點(diǎn)為中間點(diǎn)，在所有的點(diǎn) 都能承載的情況下能通過(guò)此網(wǎng)絡(luò)圖的

22、最大可行流，即發(fā)點(diǎn)發(fā)往收點(diǎn)的最大可行流。本課題的意義在于掌握最大流問(wèn)題的基本理論和算法來(lái)解決實(shí)際應(yīng)用問(wèn)題，提高生產(chǎn)的有效性和生產(chǎn)設(shè)備的有效利用率。</p><p>　　最大流問(wèn)題應(yīng)用極為廣泛，很多生活中的問(wèn)題都可轉(zhuǎn)化為最大流問(wèn)題，其難點(diǎn)是從實(shí)際中抽象出最大流模型，即轉(zhuǎn)化問(wèn)題，且實(shí)踐性較強(qiáng)，通過(guò)實(shí)例分析，更有利于對(duì)最大流問(wèn)題的了解與應(yīng)用。</p><p><b>　　1.3 選題的

23、意義</b></p><p>　　在日常生活和生產(chǎn)中我們時(shí)常遇到一些網(wǎng)絡(luò)圖。如交通圖、旅游線路圖、管道系統(tǒng)圖等。在優(yōu)化理論 中所謂圖就是上述各類(lèi)圖的抽象和概括，用圖來(lái)描述我們的研究對(duì)象，以及這些對(duì)象之間的相互聯(lián)系。例如旅游管理、網(wǎng)絡(luò)通信、交通運(yùn)輸、金融系統(tǒng)等問(wèn)題都可以用網(wǎng)絡(luò)圖來(lái)描述。</p><p>　　最大流問(wèn)題就是就是在一個(gè)有向連通圖中，指定一點(diǎn)為發(fā)點(diǎn)，另一點(diǎn)為收點(diǎn)，其余的

24、點(diǎn)為中間點(diǎn)，在所有的點(diǎn) 都能承載的情況下能通過(guò)此網(wǎng)絡(luò)圖的最大可行流，即發(fā)點(diǎn)發(fā)往收點(diǎn)的最大可行流。本課題的意義在于掌握最大流問(wèn)題的基本理論和算法來(lái)解決實(shí)際應(yīng)用問(wèn)題，提高生產(chǎn)的有效性和生產(chǎn)設(shè)備的有效利用率。</p><p>　　最大流問(wèn)題應(yīng)用極為廣泛，很多生活中的問(wèn)題都可轉(zhuǎn)化為最大流問(wèn)題，其難點(diǎn)是從實(shí)際中抽象出最大流模型，即轉(zhuǎn)化問(wèn)題，且實(shí)踐性較強(qiáng)，通過(guò)實(shí)例分析，更有利于對(duì)最大流問(wèn)題的了解與應(yīng)用。</p>

25、<p><b>　　第二章 預(yù)備知識(shí)</b></p><p><b>　　2.1 圖論</b></p><p>　　所謂“圖論”，顧名思義也就是是研究“圖”的理論。圖論中的“圖”是由許多實(shí)際問(wèn)題經(jīng)過(guò)抽象而得到，由點(diǎn)及點(diǎn)與點(diǎn)之間的連線構(gòu)成，它可以反映一些對(duì)象之間的關(guān)系。圖形中的點(diǎn)表示對(duì)象(如工序、選手、通訊站等)，兩點(diǎn)之間的有向或無(wú)向連

26、線表示對(duì)象之間具有某種特定的關(guān)系(如先后關(guān)系、勝負(fù)關(guān)系、傳遞關(guān)系、連接關(guān)系等)。</p><p>　　物質(zhì)結(jié)構(gòu)、電路網(wǎng)絡(luò)、城市規(guī)劃、交通運(yùn)輸、信息傳遞、物資調(diào)配等都可以用點(diǎn)和線連 接起來(lái)的圖進(jìn)行模擬。這里所研究的圖與平面幾何中的圖不同，這里只關(guān)心圖中有多少個(gè)點(diǎn)，點(diǎn)與點(diǎn)之間有無(wú)連線，至于連線的方式是直線還是曲線，點(diǎn)與點(diǎn)的相對(duì)位置如何，都是無(wú)關(guān)緊要的。</p><p>　　定義1：兩點(diǎn)之間不帶

27、箭頭的連線稱(chēng)為邊，一條連接的邊記為 (或)，表示邊的集合。</p><p>　　定義2：兩點(diǎn)之間帶箭頭的連線稱(chēng)為弧，一條以為始點(diǎn)</p><p>　　為終點(diǎn)的弧記為表示弧的集合。</p><p>　　定義3：由點(diǎn)和邊構(gòu)成的圖為無(wú)向圖，記為；由點(diǎn)和弧構(gòu)成的圖為有向圖，記為.</p><p>　　定義4：在無(wú)向圖中，若存在一個(gè)點(diǎn)邊交錯(cuò)序列，滿(mǎn)足&

28、lt;/p><p>　　，則稱(chēng)之為一條聯(lián)結(jié)和的鏈，記為,若，則稱(chēng)之為圈。</p><p>　　定義5：在有向圖中，若存在一個(gè)點(diǎn)弧交錯(cuò)序列，弧的始點(diǎn)為，終點(diǎn)為，記為，則稱(chēng)這條點(diǎn)弧的交錯(cuò)序列為從到的一條路，記為。若路的第一點(diǎn)和最后一點(diǎn)相同，則稱(chēng)之為回路。鏈與路中的點(diǎn)互不相同，則為初等鏈(路)，以后說(shuō)到的鏈與路，均指初等鏈(路)。</p><p>　　定義6：如果對(duì)于一個(gè)無(wú)向

29、圖的每一條邊，相應(yīng)有一個(gè)權(quán)數(shù)，則稱(chēng)這樣的圖為賦權(quán)圖，記為。</p><p>　　定義7：如果對(duì)于一個(gè)有向圖的每一條弧，相應(yīng)有一個(gè)權(quán)數(shù)，稱(chēng)這樣的圖為網(wǎng)絡(luò),記為。</p><p>　　一般在網(wǎng)絡(luò)圖中，每條弧的權(quán)，不是表示弧的長(zhǎng)度、而是表示弧的寬度，即代表距離、費(fèi)用、通過(guò)能力(容量)等等。例如，公路運(yùn)輸網(wǎng)絡(luò)中路面的寬度或管道輸送網(wǎng)絡(luò)中管道的直徑，它是單位時(shí)間內(nèi)允許通過(guò)實(shí)體的數(shù)量。所以將弧權(quán)稱(chēng)為弧

30、的容量，網(wǎng)絡(luò)稱(chēng)為容量網(wǎng)絡(luò)（參見(jiàn)文獻(xiàn)[17]）。</p><p>　　定義8：在圖中，若任何兩個(gè)點(diǎn)之間至少有一條鏈（或一條路），則稱(chēng)是連通圖，否則，稱(chēng)為不連通圖。</p><p>　　2.2 網(wǎng)絡(luò)的基本概念</p><p>　　假設(shè)要把起點(diǎn)的一批流轉(zhuǎn)物運(yùn)送到終點(diǎn)去，在每一弧上通過(guò)流轉(zhuǎn)物的總量不能超過(guò)這條弧上的容量，問(wèn)題是應(yīng)該怎樣安排運(yùn)送，才能使從起點(diǎn)運(yùn)送至終點(diǎn)的總量達(dá)

31、到最大，這樣的問(wèn)題就稱(chēng)為網(wǎng)絡(luò)上最大流問(wèn)題，最大流問(wèn)題是網(wǎng)絡(luò)流問(wèn)題中的一個(gè)非常重要的研究?jī)?nèi)容（參見(jiàn)文獻(xiàn)[15]），以下討論的網(wǎng)絡(luò)均為只有一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)的容量網(wǎng)絡(luò)。</p><p>　　定義9：對(duì)任意容量網(wǎng)絡(luò)中的弧有流量，稱(chēng)集合為網(wǎng)絡(luò)上的一個(gè)流，稱(chēng)滿(mǎn)足下列條件的流為可行流：</p><p>　　(1)容量限制條件：對(duì)中每條弧，有；</p><p><b>

32、　　(2)平衡條件：</b></p><p>　?、賹?duì)中間點(diǎn)，有(即中間點(diǎn)的物資的輸入量與輸出量相等)。</p><p>　?、趯?duì)收、發(fā)點(diǎn)有(即從點(diǎn)發(fā)出的物資總量等于點(diǎn)入的量) ，為網(wǎng)絡(luò)流的總流量。</p><p>　　在容量網(wǎng)絡(luò)中表示弧的容量，令為通過(guò)弧的流量，顯然有，流應(yīng)遵守點(diǎn)守恒規(guī)則，即：</p><p><b>

33、　　稱(chēng)為守恒方程。</b></p><p>　　定義10：對(duì)任意容量網(wǎng)絡(luò)，尋求一可行流使得流量取得</p><p>　　極大值，這個(gè)可行流便稱(chēng)為最大流。</p><p>　　定義11：在容量網(wǎng)絡(luò)中，若為網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)的一條路，給定向?yàn)閺牡?，上的弧凡與同向稱(chēng)為前向弧。凡與反向稱(chēng)為后向弧，其集合分別用和表示，是一個(gè)可行流，如果滿(mǎn)足</p>

34、<p>　　則稱(chēng)為從到的(關(guān)于的)增廣鏈。</p><p>　　定義12：在容量網(wǎng)絡(luò)中，若有弧集為的子集，將分為兩個(gè)子圖，其頂點(diǎn)集合分別記，，分別屬于，滿(mǎn)足：①不連通；②為的真子集，而仍連通，則稱(chēng)為的割集，記。</p><p>　　割集中所有始點(diǎn)在，終點(diǎn)在的邊的容量之和，稱(chēng)為的割集容量，記為。</p><p>　　2.3 最大流問(wèn)題核心依據(jù)——Ford-

35、Fulkerson最大流最小割定理</p><p>　　Ford-Fulkerson最大流最小割定理是由Ford和Fulkerson在1956年提出的，是圖論的核心定理。</p><p>　　定理1：（Ford-Fulkerson最大流最小割定理）任一容量網(wǎng)絡(luò)中，從到</p><p>　　的最大流的流量等于分離的最小割的容量。</p><p>

36、;　　證明：設(shè)在中從到的任一可行流的流量為，最小割集為</p><p>　　，最小割集的容量為。這個(gè)定理的證明分兩步：</p><p><b>　　⑴ 我們先證明：</b></p><p><b>　　由守恒方程可得：</b></p><p><b>　　因此有：。</b>&l

37、t;/p><p>　?、?下面我們證明一個(gè)可行流是最大流，當(dāng)且僅當(dāng)不存在關(guān)于它的從到的增廣路徑：</p><p>　　必然性：顯然，因?yàn)槿绻嬖谠鰪V路徑，還可以繼續(xù)增廣，流就不是最大流。</p><p>　　充分性：假設(shè)可行流是一個(gè)不存在關(guān)于它的增廣路徑的流，對(duì)于最小割集，有對(duì)任意，存在從到的增廣路徑，而對(duì)任意，不存在從到的增廣路徑，由定義可知對(duì)任意有：</p&g

38、t;<p><b>　　由公式可知：。</b></p><p>　　即流的值等于割集的容量，定理得證。</p><p>　　第三章 最大流問(wèn)題的幾種算法</p><p>　　最大流問(wèn)題是社會(huì)經(jīng)濟(jì)生活和軍事活動(dòng)中經(jīng)常出現(xiàn)的優(yōu)化問(wèn)題。如在經(jīng)濟(jì)建設(shè)和國(guó)防建設(shè)中，經(jīng)常遇到一些物資調(diào)運(yùn)的問(wèn)題。如何制定調(diào)運(yùn)方案，將物資盡快運(yùn)到指定點(diǎn)，而且不

39、影響費(fèi)用的計(jì)劃開(kāi)銷(xiāo)，即為最大流問(wèn)題。下面用數(shù)學(xué)語(yǔ)言來(lái)說(shuō)明最大流問(wèn)題：</p><p>　　1.設(shè)有一個(gè)有向連通圖G(V,A)，在V中指定一點(diǎn)稱(chēng)為發(fā)點(diǎn)s,和另外一點(diǎn)為收點(diǎn)t，其余的稱(chēng)為中間點(diǎn)，?。╝rc）集A中每條弧（i，j）上有非負(fù)數(shù)稱(chēng)為這弧的容量，記容量集為c={}，稱(chēng)這樣的圖為一個(gè)網(wǎng)絡(luò)，記為G(V,A,c)（注：當(dāng)（i，j）不是弧時(shí)=0）。</p><p>　　2.在弧集A上的?。╥

40、，j）定義一非負(fù)數(shù)，稱(chēng)為弧（i，j）上的流量，流量的集合f={}稱(chēng)為網(wǎng)絡(luò)的一個(gè)流，滿(mǎn)足下列條件的稱(chēng)為可行流：</p><p>　　1）容量限制條件，所有的弧的流量不大于弧的容量；</p><p>　　2）平衡條件，對(duì)所有的中間點(diǎn)，流入的流量和等于流出的流量和，發(fā)點(diǎn)流出的流量F等于流進(jìn)收點(diǎn)的總流量F.</p><p>　　最大流問(wèn)題就是求總流量最大達(dá)可行流。</

41、p><p>　　求解最大流問(wèn)題存在許多算法，這一節(jié)將介紹幾種常用算法。</p><p>　　3.1 標(biāo)號(hào)法(Ford-Fulkerson算法)</p><p>　　3.1.1標(biāo)號(hào)法(Ford-Fulkerson算法)思想</p><p>　　Ford-Fulkerson標(biāo)號(hào)法是一種找最大流的算法。它是由Ford和Fulkerson于1957年最

42、早提出的，其基本思想是從任意一個(gè)可行流出發(fā)尋</p><p>　　找—條增廣路徑，并在這條增廣路徑上增加流量，于是便得到一個(gè)新的可行流，然后在這新的可行流的基礎(chǔ)上再找一條新的增廣路徑，再增加流量……，繼續(xù)這個(gè)過(guò)程，一直到找不到新的增廣路徑為止（參見(jiàn)文獻(xiàn)[2]）。</p><p>　　采用Ford-Fulkerson標(biāo)號(hào)法求解最大流問(wèn)題時(shí)，在標(biāo)號(hào)過(guò)程中，一個(gè)點(diǎn)僅有下列三種狀態(tài)之一：標(biāo)號(hào)已檢查

43、(有標(biāo)號(hào)且所有相鄰點(diǎn)都標(biāo)號(hào)了)；標(biāo)號(hào)未檢查(有標(biāo)號(hào)，但某些相鄰點(diǎn)未標(biāo)號(hào))；未標(biāo)號(hào)（參見(jiàn)文獻(xiàn)[6]）。</p><p>　　Ford-Fulkerson標(biāo)號(hào)算法分為兩個(gè)過(guò)程：一是標(biāo)號(hào)過(guò)程，通過(guò)標(biāo)號(hào)過(guò)程找到一條增廣路徑；二是增廣過(guò)程，沿著增廣路徑增加網(wǎng)絡(luò)流流量的過(guò)程（參見(jiàn)文獻(xiàn)[18]）。現(xiàn)在我們考慮只有一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)的容量網(wǎng)絡(luò)，應(yīng)用Ford-Fulkerson標(biāo)號(hào)算法求解它的最大流</p><

44、p>　　3.1.2 Ford-Fulkerson標(biāo)號(hào)法的具體步驟</p><p><b>　　A:標(biāo)號(hào)過(guò)程</b></p><p>　　步驟0 確定一初始可行流，可以是零流。</p><p>　　步驟1 給發(fā)點(diǎn)以標(biāo)號(hào)。</p><p>　　步驟2 選擇一個(gè)已標(biāo)號(hào)但未檢查的點(diǎn)，并作如下檢查：</p

45、><p>　　對(duì)每一弧，若未給標(biāo)號(hào)，而且時(shí)，即流出未飽和弧,給以標(biāo)號(hào)；</p><p>　　對(duì)每一弧，若未給標(biāo)號(hào)，而且時(shí)，即流入非零流弧，給以標(biāo)號(hào)；</p><p><b>　　其中：</b></p><p>　　步驟3 重復(fù)步驟2直到收點(diǎn)被標(biāo)號(hào)，或不再有頂點(diǎn)可以標(biāo)號(hào)為止。</p><p>　　如

46、果點(diǎn)給了標(biāo)號(hào)說(shuō)明存在一條增廣路徑，故轉(zhuǎn)向增廣過(guò)程B。如若點(diǎn)不能獲得標(biāo)號(hào)，而且不存在其它可標(biāo)號(hào)的頂點(diǎn)時(shí)，算法結(jié)束，所得到的流便是最大流。</p><p><b>　　B：增廣過(guò)程</b></p><p>　　由終點(diǎn)開(kāi)始，使用標(biāo)號(hào)的第二個(gè)元素構(gòu)造一條增廣路徑(點(diǎn)的標(biāo)號(hào)的第二個(gè)元素表示在路中倒數(shù)第二個(gè)點(diǎn)的下標(biāo)，而這第二個(gè)點(diǎn)的標(biāo)號(hào)的第二個(gè)元素表示倒數(shù)第三個(gè)點(diǎn)的下標(biāo)等等)，在上

47、作調(diào)整得新的可行流，(標(biāo)號(hào)的第二個(gè)元素的正負(fù)號(hào)表示通過(guò)增加或減少弧流來(lái)增大流值)。令為標(biāo)號(hào)的第一個(gè)元素的值，作</p><p>　　以新的可行流代替原來(lái)的可行流，去掉所有標(biāo)號(hào)，轉(zhuǎn)標(biāo)號(hào)過(guò)程的步驟1。</p><p>　　采用Ford-Fulkerson標(biāo)號(hào)算法求解最大流問(wèn)題，同時(shí)得到一個(gè)最小割集。最小割集的意義是：網(wǎng)絡(luò)從發(fā)點(diǎn)到收點(diǎn)的各個(gè)通路中，由容量決定其通過(guò)能力，通常我們將最小割集形象地稱(chēng)

48、為這些通路的咽喉部分，或叫做“瓶頸”，它決定了整個(gè)網(wǎng)絡(luò)的通過(guò)能力，即最小割集的容量的大小影響總的流量的提高。因此，為提高總的流量，必須首先考慮改善最小割集中各小弧的流量，提高它們的通過(guò)能力（參見(jiàn)文獻(xiàn)[14]）。</p><p>　　3.2 Edmonds-Karp修正算法</p><p>　　Ford-Fulkerson標(biāo)號(hào)算法理論上存在著嚴(yán)重的弱點(diǎn)，以下圖3.2.1為例各邊上的權(quán)是它們

49、的容量，其最大流流量為，若增廣路徑選擇得不好,即交替地采用和作為增廣路徑，則每次增廣只能使總的流量增加1,當(dāng)初始流選為零流，無(wú)疑需作次的增加流量才能使之達(dá)到最大，可見(jiàn)Ford-Fulkerson算法的時(shí)間復(fù)雜度不僅依賴(lài)于網(wǎng)絡(luò)的規(guī)模(即依賴(lài)于網(wǎng)絡(luò)點(diǎn)數(shù)和邊數(shù))，還和各邊的容量有關(guān),而容量可以是任意的正整數(shù)。如圖3.2.1中，當(dāng)和交替作為增廣路徑時(shí)，弧交替地以前向弧和后向弧出現(xiàn)。利用Ford-Fulkerson算法求解就很麻煩了（參見(jiàn)文獻(xiàn)[8

50、]）。</p><p>　　對(duì)于Ford-Fulkerson算法,由于增廣路徑選取的任意性造成了該算法不是好算法，Edmonds和Karp對(duì)Ford-Fulkerson算法作修正，可概括為一句話：“先給標(biāo)號(hào)的先掃描”。它的意思是對(duì)已給標(biāo)號(hào)的頂點(diǎn)進(jìn)行掃描時(shí)，先對(duì)所有和鄰接的未給標(biāo)號(hào)的頂點(diǎn)給予標(biāo)號(hào)。具體的說(shuō)圖3.2.1的例子，頂點(diǎn)先標(biāo)記，所以應(yīng)該先掃描，因此避免了Ford-Fulkerson算法那樣交替地出現(xiàn)的情況，

51、也就避免了弧交替地以前向弧和后向弧來(lái)回?fù)u擺的局面。所以Edmonds-Karp的修正實(shí)質(zhì)是對(duì)頂點(diǎn)給標(biāo)記過(guò)程采用了“寬度優(yōu)先”策略。使得流量增加總是沿著一條長(zhǎng)度最短的路徑從流向的（參見(jiàn)文獻(xiàn)[3]）。</p><p>　　現(xiàn)在我們?nèi)钥紤]只有一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)的網(wǎng)絡(luò)圖，Edmonds-Karp修正算法的主要步驟是：</p><p>　　確定一初始可行流，其流量。</p><p

52、>　　檢驗(yàn)當(dāng)前所確定可行流是否是網(wǎng)絡(luò)中的最大流，若不是，需進(jìn)一步調(diào)整(檢驗(yàn)一個(gè)可行流是否為最大流。只要檢查一下當(dāng)前可行流是否還存在增廣路徑，若存在，則說(shuō)明當(dāng)前可行流還不是最大流，否則是最大流)。</p><p>　　將當(dāng)前的可行流調(diào)整成一個(gè)流量更大的新可行流，再由②檢驗(yàn)。</p><p>　　同樣地，我們通常用觀察法確定網(wǎng)絡(luò)的—個(gè)初始可行流。對(duì)于較為復(fù)雜的網(wǎng)絡(luò)，至少能把初始可行流取為

53、零流。通過(guò)在網(wǎng)絡(luò)上標(biāo)號(hào)的方法能系統(tǒng)地尋找出當(dāng)前可行流的增廣路徑，它的基本思想是：從起點(diǎn)起，逐步尋找至各點(diǎn)間的增廣路徑，若能找到至的一條增廣路徑，則給點(diǎn)標(biāo)號(hào)（其中第一個(gè)標(biāo)號(hào)即為至這條增廣路徑上的最大可調(diào)整量，第二個(gè)標(biāo)號(hào)則表示這條可行流上點(diǎn)的前一點(diǎn)是點(diǎn)）。根據(jù)標(biāo)號(hào)可反向追蹤而寫(xiě)出這條增廣路徑。在逐步擴(kuò)大已標(biāo)號(hào)的過(guò)程中，一旦終點(diǎn)標(biāo)上號(hào)，表示已找到一條由至的增廣路徑。反之，如果標(biāo)號(hào)過(guò)程進(jìn)行至某一步中止了，而尚未標(biāo)號(hào)，則表明對(duì)當(dāng)前的可行流，網(wǎng)絡(luò)中

54、不存在任何增廣路徑。當(dāng)前可行流即為最大流。Edmonds-Karp修正算法的具體步驟如下：</p><p>　　給發(fā)點(diǎn)標(biāo)號(hào)，含義為至的增廣路徑已找到，前一點(diǎn)為，這條增廣路徑上的調(diào)整量為。選與關(guān)聯(lián)的從流出的未飽和弧或流入的非零流弧，給標(biāo)號(hào) (對(duì)于流出弧)或 (對(duì)于流入弧)。</p><p><b>　　其中：</b></p><p>　　將頂點(diǎn)集

55、分為互補(bǔ)的二個(gè)點(diǎn)集、，其中為已標(biāo)號(hào)點(diǎn)集，為未標(biāo)號(hào)點(diǎn)集；</p><p>　　考慮所有這樣的弧或，其中。若弧為從流出的未飽和弧，則給標(biāo)號(hào)。其中；若弧為流入的非零流弧，則給標(biāo)號(hào)。其中。依此進(jìn)行，得到的結(jié)果是： </p><p>　　(a)，說(shuō)明網(wǎng)絡(luò)中存在增廣路徑，則由標(biāo)號(hào)點(diǎn)反向追蹤找出，轉(zhuǎn)第④步；</p><p>　　(b)，標(biāo)號(hào)已進(jìn)行不下去，說(shuō)明對(duì)于當(dāng)前可行流。網(wǎng)絡(luò)中

56、已無(wú)新的增廣路徑，當(dāng)前可行流即為最大流，同時(shí)得到最小割集。</p><p><b>　　調(diào)整過(guò)程：取，令</b></p><p>　　得到新可行流，流量，即比原可行流流量增加了，再轉(zhuǎn)①步。</p><p>　　用Edmonds-Karp修正算法求解最大流問(wèn)題時(shí)，也可以得到一個(gè)最小割集。最小割集的意義同F(xiàn)ord-Fulkerson算法得到的最小割

57、集的意義相同。</p><p>　　3.3 Dinic算法</p><p>　　Dinic于1970年提出了Ford-Fulkerson算法的改進(jìn)算法，Dinic算法的特點(diǎn)是將頂點(diǎn)按其與發(fā)點(diǎn)的最短距離分層。Edmonds-Karp修正算法的實(shí)質(zhì)也是一種分層，如果說(shuō)Ford-Fulkerson算法是采用了深度優(yōu)先策略。Edmonds-Karp修正算法則是用寬度優(yōu)先取代了深度優(yōu)先，Dinic

58、算法則是兼取這兩種方法。在分層時(shí)用的寬度優(yōu)先法，而尋求增廣路徑時(shí)則采用深度優(yōu)先策略（參見(jiàn)文獻(xiàn)[3]）。</p><p>　　3.3.1 增量網(wǎng)絡(luò)與分層增量網(wǎng)絡(luò)</p><p>　　定義13：給定一個(gè)帶發(fā)點(diǎn)和收點(diǎn)的容量網(wǎng)絡(luò)及上的可行流后，我們定義，因?yàn)橹腥魏我粚?duì)頂點(diǎn)之間至多有一條弧，所以，記，并且對(duì)一切令，于是得一個(gè)帶發(fā)點(diǎn)和收點(diǎn)的容量網(wǎng)絡(luò)，稱(chēng)之為的關(guān)于可行流的增量網(wǎng)絡(luò)。</p>

59、<p>　　為了介紹分層增量網(wǎng)絡(luò)，我們先來(lái)介紹關(guān)于網(wǎng)絡(luò)的一個(gè)算法——分層算法，它的基本思想是：</p><p>　　步驟0：把發(fā)點(diǎn)標(biāo)為“已標(biāo)號(hào)未檢查”，的層數(shù)。</p><p>　　步驟1：在已標(biāo)號(hào)未檢查頂點(diǎn)中選取最早得到標(biāo)號(hào)的頂點(diǎn)，轉(zhuǎn)步驟2；如果所有標(biāo)號(hào)頂點(diǎn)都已檢查，轉(zhuǎn)步驟3。</p><p>　　步驟2：考察頂點(diǎn)的一切出弧，若已標(biāo)號(hào)，什么也不做；否

60、則將</p><p>　　標(biāo)為“已標(biāo)號(hào)未檢查”，并令。當(dāng)?shù)乃谐龌《伎疾焱戤叄?lt;/p><p>　　把改為已檢查，轉(zhuǎn)步驟1。</p><p>　　步驟3：如果有—些頂點(diǎn)沒(méi)有標(biāo)號(hào)，則從到這些頂點(diǎn)不存在路；否則為</p><p>　　的根，為中最短路的長(zhǎng)。</p><p>　　在增量網(wǎng)絡(luò)中應(yīng)用分層算法，可以求出從發(fā)點(diǎn)到其余

61、各頂點(diǎn)的最短路的長(zhǎng)，就是頂點(diǎn)（關(guān)于發(fā)點(diǎn)）的層數(shù)。即就是的第層頂點(diǎn)。的第0層只有一個(gè)頂點(diǎn)，把頂點(diǎn)分層后，中</p><p>　　的弧又可以分為三類(lèi)：</p><p>　　第一類(lèi)為從第層頂點(diǎn)到第層頂點(diǎn)的?。?lt;/p><p>　　第二類(lèi)為從第層頂點(diǎn)到同一層頂點(diǎn)的?。?lt;/p><p>　　第三類(lèi)為從第層頂點(diǎn)到第層頂點(diǎn)的?。▍⒁?jiàn)文獻(xiàn)[5]）。</

62、p><p>　　定義14：對(duì)于帶發(fā)點(diǎn)和收點(diǎn)的容量網(wǎng)絡(luò)，設(shè)關(guān)于可行流的增量網(wǎng)絡(luò)，我們定義的子網(wǎng)絡(luò)如下：</p><p>　　則稱(chēng)為的關(guān)于可行流的分層增量網(wǎng)絡(luò)。其中第0層和第層分別只有一個(gè)頂點(diǎn)和，的所有弧都是由第層頂點(diǎn)指向第層頂點(diǎn)。</p><p>　　3.2 Dinic算法的基本思想及具體步驟</p><p>　　Dinic算法的基本思想是：從帶

63、發(fā)點(diǎn)和收點(diǎn)的容量網(wǎng)絡(luò)的任一可行流 (例如零流)開(kāi)始，構(gòu)造的關(guān)于的分層增量網(wǎng)絡(luò)，在中找一條從到的增廣路徑，對(duì)沿進(jìn)行增廣得到可行流，在中刪去上容量最小的弧，并相應(yīng)修改上弧的容量，得到網(wǎng)絡(luò)，然后可以在中再找一條從到的增廣路徑，對(duì)沿進(jìn)行增廣得到可行流，重復(fù)上述步驟依次得到的可行流，因?yàn)橹挥杏邢迼l弧，每次至少刪去一條弧，所以在有限步后必然使余下的網(wǎng)絡(luò)不再存在增廣路徑，在中的層數(shù)一定大于它在中的層數(shù)；針對(duì)重復(fù)上面的做法，在有限次增廣后一定會(huì)得到的可

64、行流，使在中的層數(shù)更大。由于的層數(shù)最多為（是網(wǎng)絡(luò)的頂點(diǎn)數(shù)）。因此經(jīng)過(guò)有限步后得到的可行流，中不再有的增廣鏈，這時(shí)就是的最大流。Dinic算法的具體步驟如下：</p><p>　　步驟0：在網(wǎng)絡(luò)中任意取—個(gè)可行流作為初始可行流，令。</p><p>　　步驟1：(作分層增量網(wǎng)絡(luò))根據(jù)作的增量網(wǎng)絡(luò)，再利用分層算</p><p>　　法構(gòu)造分層增量網(wǎng)絡(luò)，如果在作分層增量網(wǎng)

65、絡(luò)時(shí)得不到標(biāo)號(hào)，則</p><p>　　算法結(jié)束，就是的最大流；否則轉(zhuǎn)步驟2。</p><p>　　步驟2：(尋找增廣路徑)</p><p>　?、俳o發(fā)點(diǎn)標(biāo)號(hào)為，令。</p><p>　?、谌缭跊](méi)有出弧，轉(zhuǎn)⑤；否則在中任取的一條出弧，轉(zhuǎn)③。</p><p>　　③設(shè)的標(biāo)號(hào)為，其中為前面的節(jié)點(diǎn)，令，獲得標(biāo)號(hào) 。<

66、/p><p>　　④如果，轉(zhuǎn)步驟3；否則令，轉(zhuǎn)②。</p><p>　?、菰O(shè)的標(biāo)號(hào)為，如果，在中刪去的所有入弧，所</p><p>　　得的網(wǎng)絡(luò)仍記為，轉(zhuǎn)②；否則置，轉(zhuǎn)步驟1。</p><p>　　步驟3：（增廣）從頂點(diǎn)的標(biāo)號(hào)中的第二個(gè)元素反向追蹤，求出的增廣路徑，在中把上的每條弧的容量改為，刪去容量為0的弧，同時(shí)把流增廣為流，把中修改容量和刪去

67、弧后的網(wǎng)絡(luò)記為，置，去掉網(wǎng)絡(luò)中所有頂點(diǎn)的標(biāo)號(hào)，轉(zhuǎn)步驟2。</p><p>　　第四章 最大流問(wèn)題的應(yīng)用</p><p>　　4.1 鐵路貨運(yùn)列車(chē)的最優(yōu)調(diào)度</p><p>　　4.1.1 問(wèn)題敘述</p><p>　　某地區(qū)A、B兩市之間要修建一鐵路，依據(jù)地勢(shì)、環(huán)境、需求等因素，修建鐵路的預(yù)定方案如下：</p><p&g

68、t;　　（1）鐵路的運(yùn)行方式為客車(chē)與貨運(yùn)兼營(yíng)的雙軌鐵路（單向單軌），在其運(yùn)行的列車(chē)有旅客快車(chē)和貨運(yùn)列車(chē)，由于客車(chē)的運(yùn)行時(shí)間是國(guó)家鐵路部門(mén)早已排定的，不可更改，且規(guī)定客運(yùn)優(yōu)于貨運(yùn)，即貨車(chē)在每站開(kāi)出前應(yīng)先明確在其到達(dá)前方車(chē)站前不會(huì)被客車(chē)趕上，否則在該站等候不能開(kāi)車(chē)。又若貨車(chē)的前方到達(dá)站如無(wú)停車(chē)岔道，則貨車(chē)從本站開(kāi)出前應(yīng)明確在其前面兩站的行程中不會(huì)被客車(chē)趕上否則在本站等候不能開(kāi)車(chē)，余類(lèi)推。</p><p>　　（2）鐵

69、路線內(nèi)有A、B、C、D四個(gè)站，各站的岔道數(shù)為.</p><p>　　這些岔道可供調(diào)車(chē)用，亦可供停車(chē)卸貨及洗刷車(chē)輛用。</p><p>　?。?）按早已排定的旅客快車(chē)時(shí)刻表，客車(chē)每天凌晨2:00從A站開(kāi)出，以后每隔5小時(shí)開(kāi)出一列，一晝夜共開(kāi)出5列，當(dāng)天最后一列的開(kāi)車(chē)時(shí)間與翌晨第一列的開(kāi)車(chē)時(shí)間相隔4小時(shí)?？蛙?chē)的行車(chē)時(shí)間在A、B站之間為3小時(shí)；在B、C站之間為2小時(shí)；在C、D站之間為5小時(shí)。&l

70、t;/p><p>　?。?）在不干擾客車(chē)運(yùn)行的條件下，關(guān)于貨運(yùn)列車(chē)的初步安排為：每天0:00從A站發(fā)出一列，以后每隔2小時(shí)發(fā)出一列，貨車(chē)的行車(chē)時(shí)間在A、B站之間為5小時(shí)；</p><p>　　在B、C站之間為4小時(shí)；在C、D站之間為7小時(shí)。</p><p>　　為了充分發(fā)揮該鐵路線的貨運(yùn)能力，需要排定一張最優(yōu)的貨車(chē)運(yùn)行時(shí)刻表，即要求每天發(fā)出最多的貨運(yùn)列車(chē)且不干擾已排定的

71、客運(yùn)列車(chē)。</p><p>　　4.1.2 問(wèn)題分析</p><p>　　求解這個(gè)問(wèn)題較為復(fù)雜，但可將其轉(zhuǎn)化為網(wǎng)絡(luò)最大流問(wèn)題。</p><p>　　（1）設(shè)A、B兩市及其間的車(chē)站共P個(gè)。每個(gè)車(chē)站有nk條岔道（k=1,2,3…P）,可停放nk列列車(chē)。從第k站到第k+1站的行車(chē)時(shí)間貨車(chē)為tk個(gè)小時(shí)，客車(chē)為tk 個(gè)小時(shí)。</p><p>　　設(shè)為火

72、車(chē)到達(dá)第k站并從第k站開(kāi)出的時(shí)刻</p><p>　　設(shè)為客車(chē)到達(dá)第k站并從第k站開(kāi)出的時(shí)刻</p><p>　　設(shè)為貨車(chē)到達(dá)第k+1站并從第k+1站開(kāi)出的時(shí)刻</p><p>　　設(shè)為客車(chē)到達(dá)第k+1站并從第k+1站開(kāi)出的時(shí)刻</p><p><b>　　于是顯然有 </b></p><p&g

73、t;　　（2）若有公共部分，則稱(chēng)是相交的，否則成為不相交的。顯然有當(dāng)只相交情況下客車(chē)才有可能（并非必然）在第k站與地k+1站間追上貨車(chē)。</p><p>　?。?）在相交情況下，，，，間的相交關(guān)系可由圖4.1.1所示：</p><p><b>　　圖4.11</b></p><p>　　情況Ⅵ為途中貨車(chē)追上了客車(chē)故不符合題意。情況Ⅰ與情況Ⅱ中在

74、第k站與第k+1站間不發(fā)生在途中追上貨車(chē)。而在情況Ⅲ中必發(fā)生在第k站與第k+1站間客車(chē)在途中追上貨車(chē)。</p><p><b>　　于是有下列結(jié)論：</b></p><p>　　若內(nèi)，即，則在第k站與第k+1站必發(fā)生客車(chē)追上貨車(chē)情況。否則在第k站與第k+1站之間不發(fā)生客車(chē)追上貨車(chē)情況。</p><p><b>　?。?）繪制網(wǎng)絡(luò)圖&l

75、t;/b></p><p>　　用（k，）表示第k站處于時(shí)刻的狀態(tài)，如在=2.3在（k，2.6），（k，6.6）狀態(tài)開(kāi)出的貨車(chē)不會(huì)再途中被客車(chē)追上，則在圖中表現(xiàn)為（k，2.6）及（k，6.6）兩節(jié)點(diǎn)為起點(diǎn)的兩條水平方向的直線弧，而在（k，4.6）狀態(tài)下開(kāi)出的貨車(chē)會(huì)在途中被客車(chē)追上，則不能從該點(diǎn)引出水平方向的直線?。▓D4.1.2），垂直方向的直線弧并聯(lián)著同一車(chē)站的相鄰狀態(tài)。</p><p&

76、gt;<b>　　圖4.1.2</b></p><p>　　上圖中各弧旁的數(shù)字為容量，因鐵路線是單向單軌的，故水平方向的弧容量為1，垂直方向的弧的容量為各站的岔道數(shù)量，在列出全部狀態(tài)的網(wǎng)絡(luò)圖中求最大流，此最大流即為允許開(kāi)出的最多貨運(yùn)列車(chē)數(shù)。</p><p>　　4.1.3 問(wèn)題求解</p><p>　　以貨運(yùn)列車(chē)的運(yùn)行時(shí)間為基礎(chǔ)繪制網(wǎng)絡(luò)圖。&l

77、t;/p><p>　　（1）令為火車(chē)從某站開(kāi)出或到達(dá)某站的時(shí)刻。依題意，若不受客車(chē)干擾則：</p><p>　　=0:00,2:00,4:00……</p><p>　　=5:00,7:00,9:00……</p><p>　　=9:00,11:00,13:00……</p><p>　　=16:00,18:00,20:00……

78、</p><p>　　于是貨車(chē)在相鄰兩站的運(yùn)行時(shí)間為（若不受客車(chē)干擾）：</p><p>　　(25點(diǎn)即翌日1點(diǎn)，余類(lèi)推)</p><p>　　(2)令為客車(chē)從某站開(kāi)出或到達(dá)某站的時(shí)刻，依題意：</p><p>　　=2:00,7:00,12:00,17:00,22:00</p><p>　　=5:00,10:00,1

79、5:00,20:00,25:00(即1:00)</p><p>　　=7:00,12:00,17:00,22:00,27:00（即3:00）</p><p>　　=12:00,17:00,22:00,27:00（即3:00），32:00（即8:00）</p><p>　　于是客車(chē)在相鄰兩站之間的運(yùn)行時(shí)間為：</p><p><b>

80、　　圖4.1.3</b></p><p><b>　?。?）比較</b></p><p>　　之內(nèi)。這說(shuō)明若A站在6:00及16:00開(kāi)出兩列貨車(chē)，則該兩列貨車(chē)在到達(dá)B站前，必會(huì)被客車(chē)撞上。故這兩次貨運(yùn)列車(chē)是不可行的。這表示在以貨運(yùn)列車(chē)的運(yùn)行時(shí)刻為基礎(chǔ)的網(wǎng)絡(luò)圖（圖4.1.3）中為（A,6:00）及（A，16:00）兩節(jié)點(diǎn)前未引出水平方向的直線弧。該圖的各個(gè)

81、節(jié)點(diǎn)中僅注明貨運(yùn)列車(chē)從該站開(kāi)出或到達(dá)該站的時(shí)刻，站名省略了。</p><p>　　比較,我們發(fā)現(xiàn)之內(nèi)；之內(nèi)，其在圖4.1.3中的表示同前。</p><p>　　比較,我們發(fā)現(xiàn)之內(nèi)；</p><p>　　之內(nèi)，其在圖3中的表示同前。</p><p>　?。?）圖4.1.3中各水平方向的直線弧的容量均為1。如前所述，它表示在該時(shí)間內(nèi)，貨車(chē)在相鄰兩

82、站的行程中不會(huì)被客車(chē)追上，故可順利地到達(dá)前方車(chē)站。垂直方向的直線弧的通量表示各站的岔道數(shù)。</p><p>　?。?）做網(wǎng)絡(luò)的發(fā)點(diǎn)，并從向A站的各狀態(tài)節(jié)點(diǎn)作輔助弧，輔助弧的容量等于以A站的各狀態(tài)節(jié)點(diǎn)為起點(diǎn)的各弧的容量的總和。作網(wǎng)絡(luò)的收點(diǎn)，并從D站的各狀態(tài)節(jié)點(diǎn)向作輔助弧。輔助弧的容量等于以D站個(gè)狀態(tài)節(jié)點(diǎn)為終點(diǎn)的各弧的容量總和。</p><p>　?。?）求圖4.1.3所示容量網(wǎng)絡(luò)的最大流&l

83、t;/p><p>　?、瘢┮粤懔鱢={0,0,…………0}為初始流，但圖4.1.3的各弧旁省略了零流量。</p><p>　　Ⅱ）以表示圖3中第i行第j列的節(jié)點(diǎn)。用Ford-Fulkerson標(biāo)號(hào)法求得以下增廣鏈并按值進(jìn)行調(diào)整。</p><p>　?、?</p><p>　　② <

84、/p><p>　　③ </p><p>　?、?</p><p>　　⑤ </p><p>　?、?</p><p>　?、?</p>

85、<p>　　⑧ </p><p>　?、?</p><p>　　⑩ </p><p>　　以上10條增廣鏈的調(diào)整量均為。用它對(duì)初始流（零流）進(jìn)行調(diào)整后，結(jié)果如圖4.1.3所示。若對(duì)現(xiàn)行流繼續(xù)標(biāo)號(hào)，則只有A站的12個(gè)狀態(tài)節(jié)點(diǎn)獲得標(biāo)號(hào)，即標(biāo)號(hào)中斷，不能延伸達(dá)。故現(xiàn)行流即為最大流

86、，其流量</p><p>　　結(jié)論 在本問(wèn)題所給條件下各車(chē)站一晝夜中能開(kāi)出的最多貨運(yùn)列車(chē)數(shù)位10列。</p><p>　　現(xiàn)由圖4.1.3將A站以晝夜中能開(kāi)出的10列貨車(chē)的運(yùn)行時(shí)刻及調(diào)度情況闡述如（貨車(chē)一晝夜中在其他各站點(diǎn)的運(yùn)行及調(diào)度情況可由同圖作類(lèi)似闡述）</p><p>　　①在0:00,8:00,10:00,18:00,20:00,22:00時(shí)刻所開(kāi)出的貨車(chē)

87、在各站點(diǎn)均暢通。</p><p>　?、谠?:00開(kāi)出的貨車(chē)，11:00到達(dá)C站時(shí)須在岔道內(nèi)停留到13:00方可繼續(xù)前行。</p><p>　　③在4:00開(kāi)出的貨車(chē)，9:00到達(dá)B站時(shí)，須在岔道內(nèi)停留到11:00方可繼續(xù)前行。</p><p>　　④在12:00開(kāi)出的貨車(chē)，21:00到達(dá)C站時(shí)，須在岔道內(nèi)停留到23:00方可繼續(xù)前行。</p><

88、;p>　?、菰?4:00開(kāi)出的貨車(chē)，19:00到達(dá)B站時(shí)，須在岔道內(nèi)停留到21:00方可繼續(xù)前行。</p><p>　　至此已求得一晝夜中從A站開(kāi)出的10次貨運(yùn)列車(chē)的最優(yōu)調(diào)度及最優(yōu)運(yùn)行時(shí)刻表。</p><p>　　仿此，由圖4.1.3可求得從其他各站點(diǎn)開(kāi)出貨車(chē)的最優(yōu)調(diào)度及最優(yōu)運(yùn)行時(shí)刻表。</p><p>　　4.1.4 問(wèn)題總結(jié)</p><

89、p>　　本問(wèn)題看似簡(jiǎn)單，是個(gè)追趕問(wèn)題，只要計(jì)算出貨車(chē)與客車(chē)在兩站之間的運(yùn)行時(shí)間即可控制貨車(chē)的開(kāi)出時(shí)間，其實(shí)不然，此問(wèn)題是在追趕問(wèn)題的基礎(chǔ)上求最多可開(kāi)出的貨車(chē)輛數(shù)，我們把該問(wèn)題轉(zhuǎn)化成為最大流問(wèn)題，應(yīng)用Ford-Fulkerson標(biāo)號(hào)法解決了這一問(wèn)題。通過(guò)對(duì)算法的分析求解制定出了貨車(chē)運(yùn)行的最大數(shù)量并列出貨車(chē)運(yùn)行時(shí)間表，可見(jiàn)最大流算法的有效性和實(shí)用性。</p><p><b>　　第五章 結(jié)論<

90、/b></p><p>　　本課題主要以圖論的知識(shí)為理論基礎(chǔ)，來(lái)討論最大流問(wèn)題。最大流問(wèn)題是一類(lèi)應(yīng)用極為廣泛的問(wèn)題，20世紀(jì)50年代福特(Ford)、富克遜(Fulkerson)建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。</p><p>　　最大流問(wèn)題的核心依據(jù)是Ford-Fulkerson最大流最小割定理，在這個(gè)定理的基礎(chǔ)上，解決最大流問(wèn)題的幾種算法有Ford-Fulkers

91、on標(biāo)號(hào)法、Edmonds-Karp修正算法、Dinic算法等本論文分別介紹了這幾種算法，并舉實(shí)例說(shuō)明各個(gè)算法具體的解題過(guò)程，各算法的優(yōu)劣各不相同，F(xiàn)ord-Fulkerson標(biāo)號(hào)法是最原始的算法，由Ford和Fulkerson提出，Edmonds和Karp針對(duì)該算法增廣路徑選取的任意性這一缺點(diǎn)對(duì)它做了修正算法產(chǎn)生了Edmonds-Karp修正算法，而Dinic算法則兼取前兩種算法的優(yōu)點(diǎn)，是這三種算法中最有效的算法。</p>

92、<p>　　最大流問(wèn)題是網(wǎng)絡(luò)流問(wèn)題的一個(gè)重要的內(nèi)容，研究最大流問(wèn)題并將其應(yīng)用到工業(yè)、工程、商業(yè)、農(nóng)業(yè)，運(yùn)輸業(yè)等領(lǐng)域可給我們的生活帶來(lái)很大方便。</p><p>　　在很多情況下，實(shí)際遇到的問(wèn)題可能是很復(fù)雜的，甚至是無(wú)從下手，不過(guò)通過(guò)分析建立模型，如果可以建立成一個(gè)網(wǎng)絡(luò)圖，轉(zhuǎn)化成為最大流問(wèn)題，就會(huì)找到相應(yīng)的解決方法。由此，最大流問(wèn)題在現(xiàn)實(shí)生活中是非常重要的。</p><p>&

93、lt;b>　　參 考 文 獻(xiàn)</b></p><p>　　[1] 熊義杰．運(yùn)籌學(xué)教程．天津：國(guó)防工業(yè)出版社，2004</p><p>　　[2] 徐俊明. 圖論及其應(yīng)用. 合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，2005</p><p>　　[3] 盧開(kāi)澄. 圖論及其應(yīng)用. 北京：清華大學(xué)出版社，1984</p><p>　　[

94、4] 吳育華，杜綱．管理科學(xué)基礎(chǔ)．天津：天津大學(xué)出版社，2001</p><p>　　[5] 謝政，李建平. 網(wǎng)絡(luò)算法與復(fù)雜性理論. 北京：國(guó)防科技大學(xué)出版社，1995</p><p>　　[6] 刁在筠，鄭漢鼎，劉家壯，劉桂真. 運(yùn)籌學(xué). 第2版. 北京：高等教育出版社，2001</p><p>　　[7] 田豐，馬仲蕃. 圖與網(wǎng)絡(luò)流理論. 北京：科學(xué)出版

95、社，1987</p><p>　　[8] 卜月華，吳建專(zhuān). 圖論及其應(yīng)用. 南京：東南大學(xué)出版社， 2000</p><p>　　[9] Bondy JA, Mutry USR. Graph Theory with Applications. London and Basingstoke: MacMillan Press, 1976</p><p>　　[10]

96、 王樹(shù)禾. 圖論及其算法. 合肥：中國(guó)科學(xué)技術(shù)大學(xué)出版社，1990</p><p>　　[11] 戴一奇. 圖論及其應(yīng)用. 北京：水利電力出版社，1988</p><p>　　[12] 展丙軍．運(yùn)籌學(xué)．哈爾濱：哈爾濱地圖出版社，2005</p><p>　　[13] 《運(yùn)籌學(xué)》教材編寫(xiě)組. 運(yùn)籌學(xué). 第3版. 北京: 清華大學(xué)出版社，2004</p>

97、;<p>　　[14] 胡運(yùn)權(quán)．運(yùn)籌學(xué)教程．北京：清華大學(xué)出版社，2007</p><p>　　[15] 謝金星，邢文順. 網(wǎng)絡(luò)優(yōu)化. 北京：清華大學(xué)出版社，2000</p><p>　　[16] 李向東. 運(yùn)籌學(xué)：管理科學(xué)基礎(chǔ). 北京：北京理工大學(xué)出版社，1990</p><p>　　[17] 李建中, 駱吉洲(譯). 圖論導(dǎo)引. 北京：機(jī)械

98、工業(yè)出版社，2006</p><p>　　[18] 王朝瑞. 圖論. 北京：北京工業(yè)學(xué)院出版社，1987</p><p><b>　　致謝辭</b></p><p>　　本科畢業(yè)論文即將完成，回顧我大學(xué)四年的學(xué)習(xí)生涯，我得到了眾多老師的教誨，同學(xué)的支持和幫助，再次對(duì)他們表示中心的感謝。</p><p>　　首先感謝我的

99、導(dǎo)師**老師，他生活中待人十分熱情誠(chéng)懇，給予我無(wú)微不至的關(guān)懷和照顧；工作中他治學(xué)嚴(yán)謹(jǐn)，思維活躍，在研究課題閱讀文獻(xiàn)、論文寫(xiě)作上給予我許多指導(dǎo)和幫助，使我對(duì)數(shù)學(xué)的認(rèn)識(shí)有了很大的提高，我將銘記恩師的教誨、關(guān)心和幫助。</p><p>　　還要感謝大學(xué)四年來(lái)所有的老師，為我們打下堅(jiān)實(shí)的數(shù)學(xué)專(zhuān)業(yè)知識(shí)基礎(chǔ)，在論文的寫(xiě)作過(guò)程中，還要感謝班內(nèi)同學(xué)的幫助，他們?cè)谖彝瓿烧撐牡倪^(guò)程中，給我提了許多寶貴的建議，正是因?yàn)橛辛四銈兊闹С趾?/p>

100、鼓勵(lì)。此次畢業(yè)設(shè)計(jì)才能夠順利的完成。</p><p>　　感謝所有給予我?guī)椭湾憻挼娜恕?lt;/p><p>　　最后，衷心感謝所有老師對(duì)我的栽培、支持和鼓勵(lì)，感謝所有朋友的關(guān)心和幫助。向在百忙中抽出時(shí)間對(duì)此論文進(jìn)行評(píng)審并提出寶貴意見(jiàn)的各位專(zhuān)家表示衷心地感謝！</p><p>　　衷心祝愿母校**大學(xué)明天更加美好！</p><p><b&g

101、t;　　附錄1英文原文</b></p><p>　　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 t

102、he cost of goods, then how to transport, to get the most 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

103、a first-priority claim to the number of (that the edge capacity) but also have another weights (that th</p><p>　　Satisfy for all </p><p>　　for all (maximum flow constraints)(Or)</p>&

104、lt;p>　　Algorithm ideas Solve the minimum cost maximum flow problem, there are two general ways. Way is to use a maximum flow algorithm to calculate the maximum flow, and then based on the cost side, check whether it i

105、s possible to balance the flow by adjusting the flow side, so that to reduce the total cost? As long as there is a possibility, on such adjustments. After adjusting for a new </p><p>　　maximum flow. Then, on

106、 the basis of the new flow to continue to check and adjust. This iteration continues until no adjustment may be, they will have the minimum cost maximum flow. The characteristics of this line of thought is to maintain th

107、e feasibility of the problem (always maintain maximum flow), to promote optimal. Solution to another and in front of the maximum flow algorithm, introduced a similar line of thought, first of all, given the general flow

108、as the initial flow of zero. The cost </p><p>　　If G in the edge is not enough traffic, that is, , then G 'in the building edge , Empowering; edge of G if has been the flow, that is, , then G' in t

109、he building edge , to empower the .</p><p>　　The establishment of the network by streaming, you can seek in this network to the Meeting Point source shortest path, as decided by flow path, and then in the or

110、iginal network by flow in this path. Here, the use of maximum flow algorithm is still the principle of increasing flow, but the cost must be selected by the smallest chain by stream flow. Calculation, there is a need to