第六章 物流運籌學——圖與網絡分析.ppt

1、第六章 圖與網絡分析,圖與網絡的概念和模型 最短路徑問題 最大流問題 最小費用流問題 運輸路徑優(yōu)化應用,知識目標 掌握圖與網絡的概念和模型； 掌握求最小路徑兩種算法的計算過程； 掌握最大流算法； 掌握最小費用最大流方法； 了解圖與網絡分析在運輸路徑中的應用。 技能目標 能夠結合實際情況建立圖與網絡模型； 能夠應用本章算法求最優(yōu)運輸路徑。,第一節(jié) 圖與網絡的概念和模型,圖與網絡的概念 樹 圖與網絡分析實例,圖與網絡的概念,圖與網絡的概念,圖與網絡的概念,圖與網絡的概念,圖與網絡的矩陣表示,樹,生成樹和最小生成樹,求最小生成樹的算法,Kruskal算法基本步驟如下： 每步從未選的邊中選取邊e，使它

2、與已選邊不構成圈，且e是位選邊中的最小權邊，直到選夠n-1條邊為止。,圖與網絡分析實例,【例6-5】最短路問題 一名貨柜車司機奉命在最短的時間內將一車貨物從甲地運往乙地。從甲地到乙地的公路網縱橫交錯，因此有多種行車路線，這名司機應選擇哪條線路呢？假設貨柜車的運行速度是恒定的，那么這一問題相當于尋找一條從甲地到乙地的最短路。,【例6-6】公路連接問題 某一地區(qū)有若干個主要城市，現(xiàn)準備 修建高速公路把這些城市連接起來，使得從其中任何一個城市都可以經高速公路直接或間接到達另一個城市。假定已經知道了任意兩個城市之間修建高速公路的成本，那么應如何決定在哪些城市間修建高速公路，使得總成本最??？,【例6-7

3、】指派問題 一家公司經理準備安排n名員工去完成 n項任務，每人一項。由于各員工的特點不同，不同的員工去完成同一項任務時所獲得的回報是不同的。如何分配工作方案可以使總回報最大？,【例6-8】中國郵路問題 一個郵遞員，負責某一地區(qū)的信件投遞。他每天要從郵局出發(fā)，走遍該地區(qū)所有街道再返回郵局，問應如何安排送信的路線可以使所走的總路程最短？用圖論的語言描述：給定一個連通圖，每邊有非負權，要求一條回路過每邊至少一次，且滿足總權最小。,第二節(jié) 最短路徑問題,Dijkstra算法 Floyd算法,Dijkstra算法,Floyd算法,Floyd算法,第三節(jié) 最大流問題,最大流問題是涉及怎樣使得配送網絡中物流

4、量最大的問題,所謂最大流問題就是在容量網絡中，尋找 流量最大的可行流。,求最大流問題的標號法,將所有的點都標上號的過程（即尋找可增廣鏈的過程） 調整過程（將能夠調整的流量進行調整的過程）,第四節(jié) 最小費用最大流問題,第五節(jié) 運輸路徑優(yōu)化的應用,最短路徑算法的應用 最大流算法的應用 最小費用最大流算法的應用,本章小結,本章首先介紹了圖與網絡相關的基本概念及其模型，接著緊密結合物流實際，講述了一些關于圖與網絡問題的重要算法，包括：求解最小支撐樹的Kruskal算法、求解最短路的Dijkstra算法和Floyd算法、求解網絡最大流的標號算法以及求解最小費用流的算法等。最后簡單討論了圖與網絡分析在運輸

5、路徑優(yōu)化中的應用問題。 本章的重點和難點是有關算法的理解和掌握以及如何應用圖與網絡知識分析、解決物流路徑優(yōu)化的實際問題。,案例分析,以超級醫(yī)療設備公司在實際運作工程中，配送中心選址的優(yōu)化，給出圖論模型，說明Floyd算法在實際當中的應用情況。 超級醫(yī)療設備公司在亞利桑那州的菲尼克斯和墨西哥的蒙特雷設有生產廠。需要這些零部件的客戶位于美國和加拿大的某些地方。目前，位于堪薩斯周堪薩斯城的一家倉庫負責接收工廠生產的所有零部件，隨后再分撥給客戶。,公司的管理層考慮倉庫的選址問題?，F(xiàn)有倉庫的租賃期即將屆滿，管理層希望考慮一下是對現(xiàn)有倉庫再續(xù)租約還是另覓租賃地點。倉庫已經許諾如果再續(xù)約租金將及其優(yōu)惠，為每

6、年每平方米29.6美元，倉庫面積為215萬平方米。據(jù)估計在其他任何地點租同樣規(guī)模的倉庫，租金將為34.9美元每平方米。,新租約與續(xù)約的期限均為五年。轉移庫存、主要人員的搬遷費用以及其他選址費用將導致一次性支出30萬美元。各地的倉庫的運營成本基本相同。,該公司根據(jù)最近年份從堪薩斯城倉庫到客戶用2.3噸卡車（第100級貨物）運輸?shù)倪\量、費率、距離等數(shù)據(jù)，以及客戶所在城市之間的運輸距離，數(shù)量及費用等數(shù)據(jù)，建立圖論模型，利用Floyd算法求解，得到新的選址方案，節(jié)約了運輸費用。,思考題 現(xiàn)代配送中心規(guī)劃時需考慮哪些因素？ 案例中建模的過程及模型的涵義？ 圖與網絡規(guī)劃還可以應用在哪些實際問題中？,實訓設計,實訓目標 掌握最小費用最大流在物流運輸路徑優(yōu)化上的應用