模塊六 運輸與配送網(wǎng)絡(luò)優(yōu)化課件講解

港口物流優(yōu)化模塊六目錄

CONTENTS模塊三模塊四模塊五物流決策優(yōu)化認(rèn)知物流管理決策分析物流資源配置優(yōu)化物流任務(wù)指派優(yōu)化模塊二模塊七模塊一物資調(diào)運方案優(yōu)化運輸與配送網(wǎng)絡(luò)優(yōu)化物流項目計劃優(yōu)化模塊六運輸與配送網(wǎng)絡(luò)優(yōu)化任務(wù)1網(wǎng)絡(luò)圖認(rèn)知任務(wù)2最小費用流問題任務(wù)3最大流問題任務(wù)4最小費用最大流問題任務(wù)5最短路問題任務(wù)6最小支撐樹問題任務(wù)7節(jié)約里程法模塊知識點了解網(wǎng)絡(luò)圖的相關(guān)基本概念及含義了解節(jié)約里程法的基本原理和求解步驟掌握節(jié)約里程法的求解方法掌握最小費用流、最大流、最小費用最大流、最短路、最小支撐樹、貨郎擔(dān)、中國郵路等問題的基本描述、數(shù)學(xué)模型特點及應(yīng)用情境模塊能力點掌握最小費用流、最大流、最小費用最大流、最短路、最小支撐樹、貨郎擔(dān)、中國郵路等問題的表格模型建模及求解節(jié)約里程法求解配送問題任務(wù)1網(wǎng)絡(luò)圖認(rèn)知許多研究問題可以用網(wǎng)絡(luò)圖來表示，研究的目的歸結(jié)為網(wǎng)絡(luò)圖的最優(yōu)化問題。網(wǎng)絡(luò)圖點權(quán)弧或邊網(wǎng)絡(luò)圖具有下列特征：(1)點（圓圈）——研究對象，連線（無方向的不帶箭頭的邊或有方向的帶箭頭的弧）——對象之間的某種關(guān)系。(2)強(qiáng)調(diào)點之間的關(guān)聯(lián)關(guān)系，不講究圖的比例大小與形狀（曲直）。(3)每條邊（或?。┒假x有一個權(quán)，其圖稱為網(wǎng)絡(luò)圖或賦權(quán)圖。實際中，權(quán)可以表示兩點之間的距離、費用、利潤、時間、容量等不同的含義；(4)建立一個網(wǎng)絡(luò)模型，求最大值或最小值。任務(wù)1網(wǎng)絡(luò)圖認(rèn)知研究對象之間的關(guān)系可能具有對稱性和非對稱性，因此將圖劃分為無向圖和有向圖。點邊無向圖點弧有向圖3947326141287110823546668v1v4v2v3v5v6鏈：無向網(wǎng)絡(luò)中，前后相繼點和邊的交替序列稱為一條鏈。圈：閉合的鏈稱為一個圈。路：有向網(wǎng)絡(luò)圖中，前后相繼并且方向一致的點弧序列稱為一條路徑。回路：閉合的路徑稱為一個回路。任務(wù)2最小費用流問題①節(jié)點：包括供應(yīng)點、需求點和轉(zhuǎn)運點。②弧：可行的運輸線路（節(jié)點i->節(jié)點j）。③有最大運輸能力（容量）的限制。最小費用流問題的構(gòu)成（網(wǎng)絡(luò)表示）最小費用流問題的數(shù)學(xué)模型為：（1）決策變量：設(shè)fi

j為?。ü?jié)點i->節(jié)點j）的流量。（2）目標(biāo)：通過網(wǎng)絡(luò)的流量總成本最小。（3）約束條件（凈流量=總流出-總流入） ①供應(yīng)點：凈流量為正（已知，總流入=0）； ②轉(zhuǎn)運點：凈流量為零（總流出=總流入）； ③需求點：凈流量為負(fù)（已知，總流出=0）； ④弧流量fi

j受到弧的容量限制； ⑤弧流量fi

j非負(fù)。任務(wù)2最小費用流問題①至少有一個供應(yīng)點和一個需求點，可有轉(zhuǎn)運點。②通過弧的最大流量取決于該弧的容量。③網(wǎng)絡(luò)中有足夠的弧提供足夠容量，使得所有在供應(yīng)點中產(chǎn)生的流，都能夠到達(dá)需求點（有可行解）。

⑤目標(biāo)是在滿足給定需求的條件下，使得通過配送網(wǎng)絡(luò)的總成本最小（或總利潤最大）。⑥具有可行解：在以上假設(shè)下，當(dāng)且僅當(dāng)供應(yīng)點所提供的供應(yīng)量總和等于需求點所需要的需求量總和時（即平衡條件）。⑦整數(shù)解特征：只要所有的供應(yīng)量、需求量和弧的容量都是整數(shù)最小費用流問題的特點任務(wù)2最小費用流問題例1某公司有兩個工廠（F1,F2）生產(chǎn)產(chǎn)品，這些產(chǎn)品需要運送到兩個倉庫（W1,W2）中。其配送網(wǎng)絡(luò)圖如圖所示（DC為配送中心，（c,b）表示（弧容量，單位運費））。目標(biāo)是確定一個運輸方案（即每條線路上運送多少單位的產(chǎn)品），使得通過配送網(wǎng)絡(luò)的總運輸成本最小。（50，400）（50，200）（50，400）（50，300）F1F2DCW2W180706090（無限制，700）（無限制，900）任務(wù)2最小費用流問題解：

該問題的要考察從工廠W1、W2經(jīng)配送中心運輸貨物到倉庫W1、W2的運費最優(yōu)化問題，在線路上有容量限制的情況下，求線路上流量（貨運量）。因此，屬于最小費用流問題。最小費用流問題的數(shù)學(xué)模型為：（1）決策變量：設(shè)fi

j為弧（節(jié)點i->節(jié)點j）的流量。（2）目標(biāo)函數(shù)本問題的目標(biāo)是使通過配送網(wǎng)絡(luò)的總運輸成本最小任務(wù)2最小費用流問題（3）約束條件(節(jié)點凈流量、弧的容量限制、非負(fù)）①供應(yīng)點F1:

供應(yīng)點F2: ②轉(zhuǎn)運點DC: ③需求點W1:

需求點W2: ④弧容量限制：⑤非負(fù)：任務(wù)2最小費用流問題結(jié)果解釋：從F1運往W1和DC分別為30和50單位，從F2運往W2和DC分別為40和30單位，DC分別運往W1和W2為30和50單位，這樣安排配送，成本最小為110000元。1、下圖表示了企業(yè)所處的供應(yīng)市場（v1和v2）、配送中心（v3和v4）、以及銷售市場（v5、v6和v7）組成的網(wǎng)絡(luò)?；∨缘臄?shù)字為(bijcij),分別表示弧的費用和容量。試求這個供應(yīng)-銷售網(wǎng)絡(luò)流的最小費用流（v1和v2供應(yīng)能力分別為30和35，v5、v6和V7的需求均為1）.練一練V1V2V3V4V5V6V7(10,5)(15,4)(4,6)(4,10)(5,10)(6,8)(6,3)任務(wù)3最大流問題問題描述：在有一個起點和一個終點的網(wǎng)絡(luò)中，最大流問題是企圖找出，在一定時期內(nèi)，能在起點進(jìn)入，并通過這個網(wǎng)絡(luò)，在終點輸出的最大流量（不管它是物資、卡車、飛機(jī)、液體或電流）。最大流問題，就是在一定條件下，要求流過網(wǎng)絡(luò)的流量為最大的問題。如：交通網(wǎng)絡(luò)中要研究車輛的最大通行能力；生產(chǎn)流水線上產(chǎn)品的最大加工能力；供水網(wǎng)絡(luò)中通過的水流量；信息網(wǎng)絡(luò)中的信息傳送能力等。708060403050407050VSV1V2V3V5V4VT任務(wù)3最大流問題①節(jié)點：包括供應(yīng)點、需求點和轉(zhuǎn)運點。②?。嚎尚械倪\輸線路（節(jié)點i->節(jié)點j）。③有最大運輸能力（容量）的限制。最大流問題的構(gòu)成（網(wǎng)絡(luò)表示）最大流問題的數(shù)學(xué)模型為：（1）決策變量：設(shè)fi

j為?。ü?jié)點i->節(jié)點j）的流量。（2）目標(biāo)：通過網(wǎng)絡(luò)流量最大（區(qū)別于最小費用流問題）。（3）約束條件 ①供應(yīng)點：凈流量為正（但未知，區(qū)別于最小費用流）； ②轉(zhuǎn)運點：凈流量為零； ③需求點：凈流量為負(fù)（但未知，區(qū)別于最小費用流）； ④弧流量fi

j受到弧的容量限制； ⑤弧流量fi

j非負(fù)。任務(wù)3最大流問題例2某公司要從起始點VS（供應(yīng)點）運送貨物到目的地VT（需求點），其網(wǎng)絡(luò)圖如圖所示。圖中每條?。ü?jié)點i->節(jié)點j）旁的權(quán)ci

j表示這段運輸線路的最大運輸能力（容量）。要求制訂一個運輸方案，使得從VS到VT的貨運量達(dá)到最大，這個問題就是尋求網(wǎng)絡(luò)系統(tǒng)的最大流問題。708060403050407050VSV1V2V3V5V4VT任務(wù)3最大流問題例2最大流問題的線性規(guī)劃數(shù)學(xué)模型：（1）決策變量設(shè)fi

j為弧（節(jié)點i->節(jié)點j）的流量。（2）目標(biāo)函數(shù)從供應(yīng)點VS流出的總流量最大。（3）約束條件轉(zhuǎn)運點的凈流量為0

弧的容量限制

決策變量非負(fù)任務(wù)3最大流問題例2最大流問題的電子表格模型任務(wù)3最大流問題最大流問題的變形主要在于：有多個供應(yīng)點和（或）多個需求點。例3

在例2的基礎(chǔ)上，增加了一個供應(yīng)點PS、一個需求點PT、兩個轉(zhuǎn)運點P1和P2以及與之相連的7條弧，如圖所示。目標(biāo)是從2個供應(yīng)點VS和PS運出的貨物量最大。本問題是一個有2個供應(yīng)點和2個需求點的最大流問題。70804010203050406030404070502060V1V2V3V5V4VTP1PSPTP2VS任務(wù)3最大流問題例3的線性規(guī)劃模型任務(wù)3最大流問題例3的電子表格模型2、某第三方物流企業(yè)從配送中心VS向客戶倉庫VT送貨，運輸網(wǎng)路如圖所示，線路上的數(shù)字表示該線路的最大運量通過能力（單位：t），各線路均為單行線。試計算通過該運輸網(wǎng)絡(luò)VS向VT的最大送貨量。練一練VSVTV1V2V31085107243、如圖所示是5個城市之間公路所能承受的最大流量(輛/小時)，求1-5之間的最大流量及安排。練一練2356000400020002000700042000300030001任務(wù)4最小費用最大流問題在實際的網(wǎng)絡(luò)應(yīng)用中，當(dāng)有時考慮的不只是流量，還要考慮費用問題。尤其是需兼顧流量和費用問題，于是就出現(xiàn)了最小費用最大流問題。所謂的“最小費用最大流問題”，就是保證網(wǎng)絡(luò)在最大流的情況下，如果有多個最大流量運輸方案，則尋求其中費用最小的方案。最小費用最大流問題，是最小費用流問題的特殊情況。如果問題明確提出求最小費用最大流問題，則問題可以分成兩步求解：第一步：求出問題不考慮成本時的最大流量；第二步：將確定的最大流量作為新的約束條件，添加到求最小費用的模型中去。任務(wù)4最小費用最大流問題例4

某公司有一個管道網(wǎng)絡(luò)（如圖所示），使用這個網(wǎng)絡(luò)可以把石油從采地V1運送到銷地V7。由于輸油管道長短不一，每段管道除了有不同的容量cij限制外，還有不同的單位流量的費用bij。每段管道旁括號內(nèi)的數(shù)字為（cij，bij）。如果使用這個管道網(wǎng)絡(luò)，從采地V1向銷地V7輸送石油，怎樣才能輸送最多的石油并使得總的輸送費用最??？(3,2)(6,3)(2,8)(1,3)(4,4)(2,3)(5,7)(2,4)（2,5）(3,4)(6,6)V1V7V6V5V4V3V2(容量cij,費用bij)任務(wù)4最小費用最大流問題解：用線性規(guī)劃來求解此問題，分為兩步：第一步：先求出此管道網(wǎng)絡(luò)的最大流量F（最大流問題）。設(shè)通過弧（Vi,Vj）的流量為fij，最大流問題的線性規(guī)劃模型為：任務(wù)4最小費用最大流問題第一步：先求出此管道網(wǎng)絡(luò)的最大流量F（最大流問題）。石油網(wǎng)絡(luò)最大流問題的電子表格模型：求得的最大流量F＝10任務(wù)4最小費用最大流問題第二步：在最大流量F的所有解中，找出一個最小費用的解（最小費用流問題）。設(shè)通過弧（Vi,Vj）的流量為fij，則例4最小費用最大流問題的線性規(guī)劃模型為：任務(wù)4最小費用最大流問題第二步：在最大流量F=10的所有解中，找出一個最小費用的解（最小費用流問題）石油網(wǎng)絡(luò)最小費用最大流問題的電子表格模型：求得的最小費用為1454、求下圖中網(wǎng)絡(luò)從Vs到Vt的最小費用最大流，圖中弧上的數(shù)字為（弧容量，單位費用）。練一練任務(wù)5最短路問題最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一。許多優(yōu)化問題可以使用這個模型，如設(shè)備更新、管道鋪設(shè)、路線安排、廠區(qū)布局等。最短路問題最普遍的應(yīng)用是在兩個點之間尋找最短路線，是最小費用流問題的一種特殊類型：出發(fā)地（供應(yīng)點）的供應(yīng)量為1、目的地（需求點）的需求量為1、轉(zhuǎn)運點的凈流量為0、沒有弧的容量限制，目標(biāo)是使通過網(wǎng)絡(luò)到目的地的總距離最短。在已知的物流網(wǎng)絡(luò)（通過各段線路所需的時間、距離或費用為已知）中，有一貨物發(fā)點（供應(yīng)點）對一貨物收點（客戶）專門送貨，在這種直送情況下找出貨物運送所需的最少時間、最短距離或最少費用的路徑問題。任務(wù)5最短路問題例5

某人每天從V1開車到V7送貨，圖中各弧旁的數(shù)字表示道路的長度（單位：公里），試問他從V1出發(fā)到V7，應(yīng)選擇哪條路線，才能使路上行駛的總距離最短。V1V2V3V4V5V6V729683.51452.53任務(wù)5最短路問題解：這是一個最短路問題。其數(shù)學(xué)模型為：（1）決策變量：設(shè)xij為弧(節(jié)點Vi->節(jié)點Vj)是否走（1表示走，0表示不走）。（2）目標(biāo)函數(shù)：目標(biāo)是總距離最短（3）約束條件(節(jié)點凈流量、非負(fù)）任務(wù)5最短路問題例5最短路問題的電子表格模型求解結(jié)果：某人從V1出發(fā)到V7，他開車應(yīng)行駛的路線為：V1－>V2－>V3－>V5－>V7，此時路上行駛的總距離最短，為13.5公里。任務(wù)5最短路問題例6應(yīng)用于設(shè)備更新問題。某工廠的某臺機(jī)器可連續(xù)工作4年，決策者每年年初都要決定機(jī)器是否需要更新。若購置新機(jī)器，就要支付購置費用；若繼續(xù)使用舊機(jī)器，則需要支付一定的維修與運行費用。試制訂今后4年的機(jī)器更新計劃，使得總的支付費用最少。估計該種設(shè)備計劃期（4年）內(nèi)各年年初的購置費用和使用不同年限的設(shè)備所需要的維修與運行費用。年份第1年第2年第3年第4年購置費用2.52.62.83.1維修費用11.524任務(wù)5最短路問題解：可以把設(shè)備更新問題看作最短路問題。

用節(jié)點i代表“第i年年初購買一臺新設(shè)備”這種狀態(tài)（增加一個節(jié)點5，可以理解為第4年年末），節(jié)點1和節(jié)點5表示計劃期的始點和終點。從節(jié)點i到i＋1，?，5各畫一條弧，弧（i，j）表示在第i年年初購進(jìn)的機(jī)器使用到j(luò)年年初（第j-1年年底）。任務(wù)5最短路問題每條弧的權(quán)（弧旁的數(shù)字）可以根據(jù)表中的數(shù)據(jù)計算得到。

弧長＝購置費用＋使用多年的維修與運行總費用如，考慮從節(jié)點1到節(jié)點3的?。?,3），這條弧對應(yīng)的是在第1年年初購進(jìn)一臺新機(jī)器（支付購置費2.5），一直使用到第3年年初（第2年年末，即使用了2年，支付維修與運行總費用1＋1.5＝2.5），所以

從①到③的弧長＝2.5＋1+1.5=5這樣一來，制訂一個最優(yōu)的設(shè)備更新計劃問題就等價于尋求從節(jié)點1到節(jié)點5的最短路問題。年份第1年第2年第3年第4年購置費用2.52.62.83.1維修費用11.524任務(wù)5最短路問題例6的電子表格模型求解結(jié)果為：①

③

⑤，即計劃期內(nèi)機(jī)器更新最優(yōu)計劃為：第1年年初、第3年年初各購置一臺新機(jī)器，4年總的支付費用為10.3。任務(wù)5最短路問題如果已知不同役齡機(jī)器的處理價格，那么在計劃期（4年）內(nèi)機(jī)器的最優(yōu)更新計劃又會怎樣？這還是一個最短路問題，網(wǎng)絡(luò)模型仍然如圖5-22所示，只是弧長有所不同。

弧長＝購置費用＋使用多年的維修與運行總費用

－使用多年后的處理價格使用年數(shù)1年2年3年4年處理價格21.61.31.1任務(wù)5最短路問題有處理價格的設(shè)備更新問題的電子表格模型求解結(jié)果為：①－>②－>③－>⑤，即計劃期內(nèi)機(jī)器更新最優(yōu)計劃為：第1年年初、第2年年初、第3年年初各購置一臺新機(jī)器，同時在第2年年初（第1年年末）、第3年年初（第2年年末）、第5年年初（第4年年末）將舊的機(jī)器處理掉，4年總的支付費用為6.8。5、某車隊要從甲市運送一批物資到乙市，中間可穿行的市鎮(zhèn)與行車網(wǎng)絡(luò)道路如圖所示，圖中表明的數(shù)字為里程數(shù)，試著找出甲市到乙市的最短路線。練一練甲市12345乙市3340275212437023202033任務(wù)6最小支撐樹問題點邊無向圖鏈：無向網(wǎng)絡(luò)中，前后相繼點和邊的交替序列稱為一條鏈。圈：閉合的鏈稱為一個圈。無向圖中任意兩點之間，至少有一條鏈，則為連通圖，否則為不連通圖。樹（針對無向圖）：無圈的連通圖支撐樹：與圖G頂點相同，邊是圖的一部分的樹。支撐樹的權(quán)：在賦權(quán)圖中，構(gòu)成其支撐樹各邊權(quán)的總和。最小支撐樹：具有最小權(quán)的支撐樹，簡稱最小樹。v2v1v3(a)925v2v1v3(b)95v2v1v3(c)25圖

連通圖a與部分樹b、c注：樹的邊數(shù)=圖的頂點數(shù)-1任務(wù)6最小支撐樹問題v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)v1v2v3v4v5v6v7e1e6e7e9e10e11(c)任務(wù)6最小支撐樹問題許多網(wǎng)絡(luò)問題可以歸結(jié)為最小支撐樹問題。例如，設(shè)計長度最短的公路網(wǎng)，把若干城市（鄉(xiāng)村）聯(lián)系起來；設(shè)計用料最省的電話線網(wǎng)（光纖），把有關(guān)單位聯(lián)系起來；等等。這種問題的目標(biāo)是設(shè)計網(wǎng)絡(luò)。雖然節(jié)點已經(jīng)給出，但必須決定在網(wǎng)絡(luò)中要加入哪些邊。特別要指出的是，向網(wǎng)絡(luò)中插入的每一條可能的邊都有成本。為了使每兩個節(jié)點之間有連接，需要提供足夠的邊。目標(biāo)就是以某種方法完成網(wǎng)絡(luò)設(shè)計，使得邊的總成本最小。這種問題稱為最小支撐樹問題。任務(wù)6最小支撐樹問題例7某六個城市之間的道路網(wǎng)如圖所示，要求沿著已知長度的道路聯(lián)結(jié)六個城市的電話線網(wǎng)，使電話線的總長度最短。v1v2v3v4v5v6651572344任務(wù)6最小支撐樹問題5v1v2v3v4v5v612344避圈法：每步從圖中未選的邊中選取邊e,使它與已選邊中的最小權(quán)邊不構(gòu)成圈,直到選夠n-1（n為頂點數(shù)）條邊為止.破圈法：在圖G中任意取一個圈，從圈上任意舍棄一條邊（通常選權(quán)最大者）,將此圈破掉。重復(fù)此步驟直到圖G中沒有圈為止。v1v2v3v4v5v6651572344v1v2v3v4v5v6651572344電話線鋪設(shè)線路最短為最小支撐樹的權(quán)，即5+1+2+3+4=15.，鋪設(shè)方法如圖所示。任務(wù)6最小支撐樹問題v1v2v3v4v5v6651572344電子表格模型如下:可知，鋪設(shè)方法為(v1,v2),(v2,v3),(v2,v4),(v4,v5),(v5,v6),費用最省為15.任務(wù)6最小支撐樹問題解：使用Excel軟件求解最小生成樹的基本步驟如下：（1）輸入網(wǎng)絡(luò)圖到Excel工作表中。表中左上角是一個6×6的對稱權(quán)矩陣。例如單元格C2位置的“5”代表從v1點到v2點的距離；同樣，單元格B3位置的“5”代表的是從v2點到點v1的距離。矩陣中“1000”代表距離是無窮大，意味著相應(yīng)兩點間沒有路。（2）輸入6×6的變量矩陣。矩陣中的元素只能取“0”和“1”，“0”代表沒有選中，“1”代表被選中。（3）輸入約束條件：1）變量矩陣的每行的行和大于等于1。這意味著一個節(jié)點至少與其它一個節(jié)點相連。

2）變量矩陣的每列的列和=相應(yīng)的行和（對稱矩陣）。3）總邊數(shù)等于頂點數(shù)減1，這是樹的定義。總邊數(shù)就是B10：G15的所有元素和除以“2”（因為每條邊有兩個節(jié)點重復(fù)計算了一次，所有要除以“2”）。（4）輸入目標(biāo)函數(shù)：總鋪設(shè)費用最小?？備佋O(shè)費用等于選中路徑的權(quán)重之和，即SUMPRODUCT(B2:G7，B10:G15)/2。（5）求解：目標(biāo)函數(shù)：Min（總建設(shè)費用最?。?約束條件：變量矩陣=bin;總邊數(shù)=頂點個數(shù)-1=5;行和大于等于1;行和等于列和6、如圖所示，A、B、C、D、E、F、G代表某集團(tuán)公司及下屬的工廠，它們之間的連線代表彼此之間的道路交通情況，連線旁的數(shù)字代表相應(yīng)道路的長度?，F(xiàn)在要