《物流運(yùn)籌方法與工具》第3版 課件 模塊六單元四 線路網(wǎng)布局的最小樹法

物流運(yùn)籌方法與工具（第3版）目錄

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

一、最小樹的含義

二、最小樹的逐步生長法

三、最小樹的破圈法1．樹所謂樹（樹圖），就是沒有圈的連通圖。一、最小樹的含義2．部分樹如果樹T是圖G的一個部分圖，則稱樹T是圖G的部分樹。v2v1v3(a)925v2v1v3(b)95v2v1v3(c)25圖6-12連通圖a與部分樹b、c3．最小樹在賦權(quán)圖中，構(gòu)成其部分樹各邊權(quán)的總和稱為部分樹的權(quán)，如圖6-12（b）對應(yīng)的部分樹的權(quán)為14，6-12（c）為7。具有最小權(quán)的部分樹，稱為最小部分樹，簡稱最小樹。一、最小樹的含義二、最小樹的逐步生長法例6-4

某天然氣公司計劃在如圖6-13(a)所示的網(wǎng)絡(luò)中鋪設(shè)天然氣管道，向五個居民小區(qū)v1、v2、v3、v4、v5

供氣，網(wǎng)絡(luò)中各邊的權(quán)代表相應(yīng)小區(qū)之間所鋪設(shè)天然氣管道的實(shí)際長度（公里）。試問：應(yīng)如何鋪設(shè)管道，既能保證向五個居民小區(qū)供應(yīng)天然氣，又能使管道的總長度最短從而使費(fèi)用最省？v1v2v3v5v45613849109圖6－13(a)二、最小樹的逐步生長法解：1．先將圖6-13所示網(wǎng)絡(luò)圖列出相應(yīng)的矩陣。二、最小樹的逐步生長法2．從v1出發(fā)，于是除去D中的v1列，保留v1

行做圖表F（1），如圖6-14所示。956V4V3V5V3V4V5∞994V2V3V4V4V5F(1)V1V1V1V1∞85F(2)V1V2V198V5F(3)V2V39V5F(4)V22行V4V51063行V5134行圖6-14逐步生長法求解過程圖6-14逐步生長法求解過程二、最小樹的逐步生長法3．在F（1）左部上面一行中，填寫v1行的元素值；而下面一行中全部填寫v1

，表示上面一行的數(shù)值全部來自v1

行。然后，在F（1）左部上面一行找出最小值4，即由v1點(diǎn)

到v2點(diǎn)

的距離d12=4為最小，因此把4圈起來，說明可以從v1點(diǎn)

到v2點(diǎn)

鋪設(shè)一條管道，記作

。接著，除去D的第二列（v2列）元素，保留第二行余下的元素做F（1）右面部分的副表。二、最小樹的逐步生長法二、最小樹的逐步生長法最后，可按最小樹鋪設(shè)管道，其距離總長為：4+5+6+9=24為最短，圖6-13（b）所示為最小樹示意圖。圖6-14（b）三、最小樹的破圈法破圈法在連通圖G中任意選取一個回路，從該回路中去掉一條權(quán)數(shù)最大的邊（如果權(quán)數(shù)最大的邊不唯一，則任意選取其中一條）。在余下的圖中，重復(fù)這一步驟，直到得到一個不含回路的連通圖（有n個頂點(diǎn)、n-1條邊），該連通圖便是最小部分樹。三、最小樹的破圈法例6-5如圖6-15所示，A、B、C、D、E、F、G代表某集團(tuán)公司及下屬的工廠，它們之間的連線代表彼此之間的道路交通情況，連線旁的數(shù)字代表相應(yīng)道路的長度。現(xiàn)在要沿道路鋪設(shè)通訊電纜，使公司、各工廠彼此之間都能通上電話，問應(yīng)如何鋪設(shè)才能使線路總長度最短。ABEDCG7564F5289783圖6-16三、最小樹的破圈法解：用破圈法求解該問題的過程和結(jié)果分別見圖6-16，6-17，6-18所示，鋪設(shè)線路的最短長度是8+2+5+4+3+7=29，其中，打