【文章內(nèi)容簡介】 境、需求等因素，修建鐵路的預(yù)定方案如下：（1）鐵路的運行方式為客車與貨運兼營的雙軌鐵路（單向單軌），在其運行的列車有旅客快車和貨運列車，由于客車的運行時間是國家鐵路部門早已排定的，不可更改，且規(guī)定客運優(yōu)于貨運，即貨車在每站開出前應(yīng)先明確在其到達(dá)前方車站前不會被客車趕上，否則在該站等候不能開車。又若貨車的前方到達(dá)站如無停車岔道，則貨車從本站開出前應(yīng)明確在其前面兩站的行程中不會被客車趕上否則在本站等候不能開車，余類推。（2）鐵路線內(nèi)有A、B、C、D四個站，各站的岔道數(shù)為.這些岔道可供調(diào)車用，亦可供停車卸貨及洗刷車輛用。（3）按早已排定的旅客快車時刻表，客車每天凌晨2:00從A站開出，以后每隔5小時開出一列，一晝夜共開出5列，當(dāng)天最后一列的開車時間與翌晨第一列的開車時間相隔4小時。客車的行車時間在A、B站之間為3小時；在B、C站之間為2小時；在C、D站之間為5小時。（4）在不干擾客車運行的條件下，關(guān)于貨運列車的初步安排為：每天0:00從A站發(fā)出一列，以后每隔2小時發(fā)出一列，貨車的行車時間在A、B站之間為5小時；在B、C站之間為4小時；在C、D站之間為7小時。為了充分發(fā)揮該鐵路線的貨運能力，需要排定一張最優(yōu)的貨車運行時刻表，即要求每天發(fā)出最多的貨運列車且不干擾已排定的客運列車。 問題分析 求解這個問題較為復(fù)雜，但可將其轉(zhuǎn)化為網(wǎng)絡(luò)最大流問題。（1）設(shè)A、B兩市及其間的車站共P個。每個車站有nk條岔道（k=1,2,3…P）,可停放nk列列車。從第k站到第k+1站的行車時間貨車為tk個小時，客車為tk 個小時。設(shè)為火車到達(dá)第k站并從第k站開出的時刻設(shè)為客車到達(dá)第k站并從第k站開出的時刻設(shè)為貨車到達(dá)第k+1站并從第k+1站開出的時刻設(shè)為客車到達(dá)第k+1站并從第k+1站開出的時刻于是顯然有 （2）若有公共部分，則稱是相交的，否則成為不相交的。顯然有當(dāng)只相交情況下客車才有可能（并非必然）在第k站與地k+1站間追上貨車。（3）在相交情況下，，：情況Ⅵ為途中貨車追上了客車故不符合題意。情況Ⅰ與情況Ⅱ中在第k站與第k+1站間不發(fā)生在途中追上貨車。而在情況Ⅲ中必發(fā)生在第k站與第k+1站間客車在途中追上貨車。 于是有下列結(jié)論：若內(nèi)，即，則在第k站與第k+1站必發(fā)生客車追上貨車情況。否則在第k站與第k+1站之間不發(fā)生客車追上貨車情況。（4）繪制網(wǎng)絡(luò)圖用（k，）表示第k站處于時刻的狀態(tài)，如在=（k，），（k，）狀態(tài)開出的貨車不會再途中被客車追上，則在圖中表現(xiàn)為（k，）及（k，）兩節(jié)點為起點的兩條水平方向的直線弧，而在（k，）狀態(tài)下開出的貨車會在途中被客車追上，則不能從該點引出水平方向的直線?。ǎ?，垂直方向的直線弧并聯(lián)著同一車站的相鄰狀態(tài)。 上圖中各弧旁的數(shù)字為容量，因鐵路線是單向單軌的，故水平方向的弧容量為1，垂直方向的弧的容量為各站的岔道數(shù)量，在列出全部狀態(tài)的網(wǎng)絡(luò)圖中求最大流，此最大流即為允許開出的最多貨運列車數(shù)。 問題求解以貨運列車的運行時間為基礎(chǔ)繪制網(wǎng)絡(luò)圖。（1）令為火車從某站開出或到達(dá)某站的時刻。依題意，若不受客車干擾則：=0:00,2:00,4:00……=5:00,7:00,9:00……=9:00,11:00,13:00……=16:00,18:00,20:00……于是貨車在相鄰兩站的運行時間為（若不受客車干擾）：(25點即翌日1點，余類推)(2)令為客車從某站開出或到達(dá)某站的時刻，依題意：=2:00,7:00,12:00,17:00,22:00=5:00,10:00,15:00,20:00,25:00(即1:00)=7:00,12:00,17:00,22:00,27:00（即3:00）=12:00,17:00,22:00,27:00（即3:00），32:00（即8:00）于是客車在相鄰兩站之間的運行時間為： （3）比較之內(nèi)。這說明若A站在6:00及16:00開出兩列貨車，則該兩列貨車在到達(dá)B站前，必會被客車撞上。故這兩次貨運列車是不可行的。這表示在以貨運列車的運行時刻為基礎(chǔ)的網(wǎng)絡(luò)圖（）中為（A,6:00）及（A，16:00）兩節(jié)點前未引出水平方向的直線弧。該圖的各個節(jié)點中僅注明貨運列車從該站開出或到達(dá)該站的時刻，站名省略了。比較,我們發(fā)現(xiàn)之內(nèi)；之內(nèi)。比較,我們發(fā)現(xiàn)之內(nèi)；之內(nèi)，其在圖3中的表示同前。（4）。如前所述，它表示在該時間內(nèi)，貨車在相鄰兩站的行程中不會被客車追上，故可順利地到達(dá)前方車站。垂直方向的直線弧的通量表示各站的岔道數(shù)。（5）做網(wǎng)絡(luò)的發(fā)點，并從向A站的各狀態(tài)節(jié)點作輔助弧，輔助弧的容量等于以A站的各狀態(tài)節(jié)點為起點的各弧的容量的總和。作網(wǎng)絡(luò)的收點，并從D站的各狀態(tài)節(jié)點向作輔助弧。輔助弧的容量等于以D站個狀態(tài)節(jié)點為終點的各弧的容量總和。（6）Ⅰ）以零流f={0,0,…………0}為初始流。Ⅱ）以表示圖3中第i行第j列的節(jié)點。用FordFulkerson標(biāo)號法求得以下增廣鏈并按值進(jìn)行調(diào)整。① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ 以上10條增廣鏈的調(diào)整量均為。用它對初始流（零流）進(jìn)行調(diào)整后。若對現(xiàn)行流繼續(xù)標(biāo)號，則只有A站的12個狀態(tài)節(jié)點獲得標(biāo)號，即標(biāo)號中斷，不能延伸達(dá)。故現(xiàn)行流即為最大流，其流量結(jié)論 在本問題所給條件下各車站一晝夜中能開出的最多貨運列車數(shù)位10列。（貨車一晝夜中在其他各站點的運行及調(diào)度情況可由同圖作類似闡述）①在0:00,8:00,10:00,18:00,20:00,22:00時刻所開出的貨車在各站點均暢通。②在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:00方可繼續(xù)前行。至此已求得一晝夜中從A站開出的10次貨運列車的最優(yōu)調(diào)度及最優(yōu)運行時刻表。仿此。 問題總結(jié)本問題看似簡單，是個追趕問題，只要計算出貨車與客車在兩站之間的運行時間即可控制貨車的開出時間，其實不然，此問題是在追趕問題的基礎(chǔ)上求最多可開出的貨車輛數(shù)，我們把該問題轉(zhuǎn)化成為最大流問題，應(yīng)用FordFulkerson標(biāo)號法解決了這一問題。通過對算法的分析求解制定出了貨車運行的最大數(shù)量并列出貨車運行時間表，可見最大流算法的有效性和實用性。第五章 結(jié)論本課題主要以圖論的知識為理論基礎(chǔ)，來討論最大流問題。最大流問題是一類應(yīng)用極為廣泛的問題，20世紀(jì)50年代福特(Ford)、富克遜(Fulkerson)建立的“網(wǎng)絡(luò)流理論”，是網(wǎng)絡(luò)應(yīng)用的重要組成部分。最大流問題的核心依據(jù)是FordFulkerson最大流最小割定理，在這個定理的基礎(chǔ)上，解決最大流問題的幾種算法有FordFulkerson標(biāo)號法、EdmondsKarp修正算法、Dinic算法等本論文分別介紹了這幾種算法，并舉實例說明各個算法具體的解題過程，各算法的優(yōu)劣各不相同，F(xiàn)ordFulkerson標(biāo)號法是最原始的算法，由Ford和Fulkerson提出，Edmonds和Karp針對該算法增廣路徑選取的任意性這一缺點對它做了修正算法產(chǎn)生了EdmondsKarp修正算法，而Dinic算法則兼取前兩種算法的優(yōu)點，是這三種算法中最有效的算法。最大流問題是網(wǎng)絡(luò)流問題的一個重要的內(nèi)容，研究最大流問題并將其應(yīng)用到工業(yè)、工程、商業(yè)、農(nóng)業(yè)，運輸業(yè)等領(lǐng)域可給我們的生活帶來很大方便。在很多情況下，實際遇到的問題可能是很復(fù)雜的，甚至是無從下手，不過通過分析建立模型，如果可以建立成一個網(wǎng)絡(luò)圖，轉(zhuǎn)化成為最大流問題，就會找到相應(yīng)的解決方法。由此，最大流問題在現(xiàn)實生活中是非常重要的。參 考 文 獻(xiàn)[1] 熊義杰．運籌學(xué)教程．天津：國防工業(yè)出版社，2004[2] 徐俊明. 圖論及其應(yīng)用. 合肥：中國科學(xué)技術(shù)大學(xué)出版社，2005[3] 盧開澄. 圖論及其應(yīng)用. 北京：清華大學(xué)出版社，1984