《物流運籌方法與工具》第3版 課件 模塊六單元三 運輸網(wǎng)流量分布的最大流法

物流運籌方法與工具（第3版）目錄

CONTENTS物流運籌方法與工具概述物流決策分析物流資源配置規(guī)劃物流任務(wù)指派運輸方案優(yōu)化運輸路徑規(guī)劃物流項目計劃物流需求預(yù)測庫存水平控制模塊六模塊二模塊三模塊四模塊五模塊七模塊八模塊九模塊一模塊六運輸路徑規(guī)劃運輸路徑規(guī)劃概述應(yīng)用舉例線路選擇的最短路法運輸網(wǎng)流量分布的最大流法線路網(wǎng)布局的最小樹法車輛配送路線的安排單元四單元三單元二單元一單元六單元五本章知識點1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義。3．掌握求解最短路問題的Dijkstra算法步驟。4．理解可行流、最大流、增廣鏈的概念。5．掌握求解最大流問題的標(biāo)號算法步驟。6．理解最小樹、圖的中心和重心的含義。7．掌握最小樹問題的逐步生長法步驟。8．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。9．掌握單回路路線優(yōu)化的最近鄰點法和最近插入法的求解步驟。10．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。本節(jié)知識點知識點1．理解圖、網(wǎng)絡(luò)、鏈、連通圖、圖模型的概念。2．理解最短路問題的含義；掌握求解最短路問題的Dijkstra算法步驟。3．理解可行流、最大流、增廣鏈的概念；掌握求解最大流問題的標(biāo)號算法步驟。4．理解最小樹、圖的中心和重心的含義；掌握最小樹問題的逐步生長法步驟。5．理解單、多車輛配送路線安排問題及啟發(fā)式算法的含義。6．掌握單回路路線優(yōu)化的最近鄰點法和最近插入法的求解步驟。7．掌握多回路路線優(yōu)化的掃描法、節(jié)約法的求解步驟。本單元知識點能力點、素質(zhì)點能力點：1．能夠把相應(yīng)的實際問題歸結(jié)為最短路問題，并能夠熟練運用Dijkstra算法求解。2．能夠把相應(yīng)的實際問題歸結(jié)為最大流問題，并能熟練運用標(biāo)號算法求解。3．能夠把相應(yīng)的實際問題歸結(jié)為最小樹問題，并能熟練運用逐步生長法求解。4．能夠把相應(yīng)的實際問題歸結(jié)為回路運輸路線優(yōu)化問題，并能熟練運用最近鄰點法和最近插入法、掃描法、節(jié)約法求解。素質(zhì)點：1．提高對大數(shù)據(jù)及云計算、物聯(lián)網(wǎng)、人工智能等新科技的應(yīng)用興趣，勇于實踐創(chuàng)新。2．加強“互聯(lián)網(wǎng)+高效物流”和“降本增效”理念。單元三

運輸網(wǎng)流量分布的最大流法一、最大流的含義二、最大流的標(biāo)號算法三、最大流的圖解算法運輸網(wǎng)最大流量分布問題：最大流問題的一般提法：一、最大流的含義在已知的物流網(wǎng)絡(luò)（各段線路的通過能力、運輸費用或運輸時間為已知）中，有一貨物發(fā)點（供應(yīng)點）和一貨物收點（客戶），在這種情況下找出最佳流量安排（線路流量分配）方案，使通過網(wǎng)絡(luò)的流量達到最大（或運輸費用最省、或運輸時間最?。Ｔ谟幸粋€起點和一個終點的網(wǎng)絡(luò)中，最大流問題是企圖找出，在一定時期內(nèi)，能在起點進入，并通過這個網(wǎng)絡(luò)，在終點輸出的最大流量（不管它是物資、卡車、飛機、液體或電流）。即最大流問題，就是在一定條件下，要求流過網(wǎng)絡(luò)的流量為最大的問題。一、最大流的含義（一）網(wǎng)絡(luò)流量在一定條件下流過一個網(wǎng)絡(luò)的總流量，它等于起點的總發(fā)量或終點的總收量。網(wǎng)絡(luò)流量記作

，網(wǎng)絡(luò)邊上的實際流量記作fij。一、最大流的含義（二）可行

流滿足以下條件的流叫可行流（記為可行流f）：一、最大流的含義（三）最大

流在一個網(wǎng)絡(luò)中，流量達到最大值的可行流。求網(wǎng)絡(luò)的最大流，就是指在滿足上述（二）中條件1、2、3的前提下，使的值達到最大。一、最大流的含義（四）增廣

鏈如果從網(wǎng)絡(luò)的發(fā)點s到收點t能找出一條鏈，在這條鏈上，所有指向為s→t的邊（稱為前向邊），其上的流量都小于容量，而所有指向為t→s的邊（稱為后向邊），其上的流量都大于0，則稱這樣的鏈為增廣鏈，如圖6-8所示。f45>0f23>0f34<c34v5v3fs2<cs2sv2v4tf5t<c5t圖6-8網(wǎng)絡(luò)中的一條增廣鏈一、最大流的含義（四）增廣

鏈如果從網(wǎng)絡(luò)的發(fā)點s到收點t能找出一條鏈，在這條鏈上，所有指向為s→t的邊（稱為前向邊），其上的流量都小于容量，而所有指向為t→s的邊（稱為后向邊），其上的流量都大于0，則稱這樣的鏈為增廣鏈，如圖6-8所示。f45>0f23>0f34<c34v5v3fs2<cs2sv2v4tf5t<c5t圖6-8網(wǎng)絡(luò)中的一條增廣鏈二、最大流的標(biāo)號算法1先給發(fā)點s標(biāo)號

，其中s是發(fā)點，此前還沒有已標(biāo)號點，所以給s標(biāo)的第一個記號是0，第二個記號

可取∞。2找出和已標(biāo)號點i相鄰的所有未標(biāo)號點，比如j。二、最大流的標(biāo)號算法3重復(fù)步驟2，可能出現(xiàn)兩種結(jié)局：（1）標(biāo)號過程中斷，即t得不到標(biāo)號，這表明該網(wǎng)絡(luò)中不存在增廣鏈，此時的可行流已是最大流，計算即告結(jié)束。（2）t得到標(biāo)號，這時可用反向追蹤法在網(wǎng)絡(luò)中找出一條從s→t的由標(biāo)號點及相應(yīng)的邊連接而成的增廣鏈，接下去轉(zhuǎn)入步驟4。二、最大流的標(biāo)號算法5抹掉圖上所有標(biāo)號，重復(fù)第1到第4步，直到圖中找不出任何增廣鏈，即出現(xiàn)第3步的結(jié)局（1）為止，這時，網(wǎng)絡(luò)中的可行流就是最大流。4調(diào)整網(wǎng)絡(luò)中的可行流f的流量：對增廣鏈上的前向邊，其流量增加

，對增廣鏈上的后向邊，其流量減少

，增廣鏈以外的邊上的流量不變。這樣得到一個新的可行流f`。二、最大流的標(biāo)號算法例6-2

用標(biāo)號算法求圖6-7中s→t的最大流，圖中邊旁數(shù)字為。9(4)2(0)9(9)6(1)5(5)10(8)5(4)7(5)8(8)sv1v2v3v4t圖6-7二、最大流的標(biāo)號算法解：1．先給發(fā)點s標(biāo)號：（0，∞），見圖6-9；圖6-9v4v1(v4，1)(v1，2)v2(s，2)(v3-，1)(v2-，2)(0，∞)s9(4)2(0)9(9)6(1)5(5)10(8)5(4)7(5)8(8)v3t二、最大流的標(biāo)號算法解：二、最大流的標(biāo)號算法解：二、最大流的標(biāo)號算法解：非增廣鏈上所有邊的流量都不變，這樣便得到網(wǎng)絡(luò)的一個新的可行流，其流量分布情況見圖6-10所示。二、最大流的標(biāo)號算法圖6-10新可行流的流量分布方案s9(5)2(0)9(9)6(0)5(5)10(9)5(3)7(6)8(8)v1v2v3v4t解：三、最大流的圖解算法圖解算法就是根據(jù)最大流問題的網(wǎng)絡(luò)圖來尋找從

到

所允許流過的最大流量。其具體步驟是：01020304任意選擇從

到

的通路，一般從最外層開始。接著找出該通路中允許通過的最小流量，并給該通路中各邊上安排這個最小流量。將上述具有最小流量的邊刪去，余下的重新畫出網(wǎng)絡(luò)圖。重復(fù)上述步驟，直到從

到

已無通路時為止。05將以上所得的通路最小流量值相加，即得該網(wǎng)絡(luò)的最大流量。例6-3某地區(qū)從北到南的交通，平時是利用高速公路通行的?，F(xiàn)在，將有一個月的時間因為高速公路要進行路面修理，車輛不能行駛，因此該地區(qū)公路管理部門的工程技術(shù)人員需要查明，穿過該地區(qū)的其它幾條道路，是不是有把握每小時通過6000輛汽車，這些汽車在正常情況下，是走高速公路通行的。圖6-11所示是穿過該地區(qū)的道路通行情況，每條道路的通行能力用每小時千輛汽車為單位來表示。各支線每小時流量能力為：1——2線：6000輛；1——3線：5000輛；1——4線：3000輛；2——5線：4000輛；2——3線：7000輛；3——5線：5000輛；3——4線：3000輛；4——6線：7000輛；5——6線：2000輛；試計算該地區(qū)的道路通行能力有多大？三、最大流的圖解算法三、最大流的圖解算法3（3）5（0）7（0）3（3）5（3）7（3+3）6（2）1234564（2）2（2）圖6-11該地區(qū)汽車通過能力的計算解：該問題實質(zhì)就是求解圖6-11的最大流問題。計算過程如下：1．任意選擇從起點到終點的第一條路線（即增廣鏈）。這里，選擇路線1-2-5-6。該路線上支線5-6的流量能力最小，為每小時2000輛，用2表示。因此該路線的每小時的最大流量是2000輛。給該路線上每條支線安排流量2000輛，圖中線路旁的數(shù)字為

，見圖6-11所示。支線5-6已無剩余能力，從圖中劃掉。三、最大流的圖解算法解：

2．另選第二條從起點到終點的路線，如1-4-6。該路線上支線1-4的流量能力最小，其最小流量能力為3。因此第二條路線的最大流量是3。給該路線上每條支線安排流量3，見圖6-11所示。支線1-4已無剩余能力，從圖中劃掉。3．另選第三條從起點到終點的路線，如1-3-4-6。該路線上支線3-4的流量能力最小，其最小流量能力為3。因此第三條路線的最大流量是3。給該路線上每條支線安排流量3，見圖6-11所示。支線3-4已無剩余能力，從圖中劃掉。三、最大流的圖解算法解：