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

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

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

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

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

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