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

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

CONTENTS模塊三模塊四模塊五物流決策優(yōu)化認(rèn)知物流管理決策分析物流資源配置優(yōu)化物流任務(wù)指派優(yōu)化模塊二模塊七模塊一物資調(diào)運(yùn)方案優(yōu)化運(yùn)輸與配送網(wǎng)絡(luò)優(yōu)化物流項(xiàng)目計(jì)劃優(yōu)化模塊六運(yùn)輸與配送網(wǎng)絡(luò)優(yōu)化任務(wù)1網(wǎng)絡(luò)圖認(rèn)知任務(wù)2最小費(fèi)用流問題任務(wù)3最大流問題任務(wù)4最小費(fèi)用最大流問題任務(wù)5最短路問題任務(wù)6最小支撐樹問題任務(wù)7節(jié)約里程法模塊知識(shí)點(diǎn)了解網(wǎng)絡(luò)圖的相關(guān)基本概念及含義了解節(jié)約里程法的基本原理和求解步驟掌握節(jié)約里程法的求解方法掌握最小費(fèi)用流、最大流、最小費(fèi)用最大流、最短路、最小支撐樹、貨郎擔(dān)、中國郵路等問題的基本描述、數(shù)學(xué)模型特點(diǎn)及應(yīng)用情境模塊能力點(diǎn)掌握最小費(fèi)用流、最大流、最小費(fèi)用最大流、最短路、最小支撐樹、貨郎擔(dān)、中國郵路等問題的表格模型建模及求解節(jié)約里程法求解配送問題任務(wù)5最短路問題最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣泛的問題之一。許多優(yōu)化問題可以使用這個(gè)模型，如設(shè)備更新、管道鋪設(shè)、路線安排、廠區(qū)布局等。最短路問題最普遍的應(yīng)用是在兩個(gè)點(diǎn)之間尋找最短路線，是最小費(fèi)用流問題的一種特殊類型：出發(fā)地（供應(yīng)點(diǎn)）的供應(yīng)量為1、目的地（需求點(diǎn)）的需求量為1、轉(zhuǎn)運(yùn)點(diǎn)的凈流量為0、沒有弧的容量限制，目標(biāo)是使通過網(wǎng)絡(luò)到目的地的總距離最短。在已知的物流網(wǎng)絡(luò)（通過各段線路所需的時(shí)間、距離或費(fèi)用為已知）中，有一貨物發(fā)點(diǎn)（供應(yīng)點(diǎn)）對(duì)一貨物收點(diǎn)（客戶）專門送貨，在這種直送情況下找出貨物運(yùn)送所需的最少時(shí)間、最短距離或最少費(fèi)用的路徑問題。任務(wù)5最短路問題例5

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

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

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

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

③

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

弧長＝購置費(fèi)用＋使用多年的維修與運(yùn)行總費(fèi)用

－使用多年后的處理價(jià)格使用年數(shù)1年2年3年4年處理價(jià)格21.61.31.1任務(wù)5最短路問題有處理價(jià)格的設(shè)備更新問題的電子表格模型求解結(jié)果為：①－>②－>③－>⑤，即計(jì)劃期內(nèi)機(jī)器更新最優(yōu)計(jì)劃為：第1年年初、第2年年初、第3年年初各購置一臺(tái)新機(jī)器，同時(shí)在第2年年初（第1年年末）、第3年年初（第2年年末）、第5年年初（第4年年末）將舊的機(jī)器處理掉，4年總的支付費(fèi)用為6.8。5、某車隊(duì)要