《物流數(shù)據(jù)分析》課件-任務(wù)6.2 最短路徑問題規(guī)劃求解

任務(wù)6.2最短路徑問題規(guī)劃求解【任務(wù)目的】1.掌握最短路徑規(guī)劃問題的目的和意義；2.掌握SUMIF函數(shù)的應(yīng)用；3.掌握使用規(guī)劃求解工具進(jìn)行最短路徑問題規(guī)劃的操作步驟?！竟ぷ魅蝿?wù)】MY搬家公司接受KE物業(yè)公司的委托，為其把辦公室家具和設(shè)備搬運(yùn)到新總部，道路網(wǎng)絡(luò)圖（單位：公里）如圖6-6所示。假如你是MY搬家公司的調(diào)度員，你會推薦那條線路？SABCDET4108148282101464道路網(wǎng)絡(luò)圖【知識鏈接】1.最短路徑問題的概念最短路徑問題，就是從給定的網(wǎng)絡(luò)圖中找出一點(diǎn)到各點(diǎn)或任意兩點(diǎn)之間距離最短的一條路線。通俗來講，就是在所有的路線中找到一條距離最短的路線。它在生活中有極其重要的意義與運(yùn)用，廣泛應(yīng)用于交通工程、通信工程、計(jì)算機(jī)科學(xué)、系統(tǒng)工程、運(yùn)籌學(xué)、信息論、控制理論等眾多領(lǐng)域。2.最短路徑的問題的數(shù)學(xué)表達(dá)式3.最短路徑的問題的求解從最短路徑問題的數(shù)學(xué)模型可以看出，其本質(zhì)上是一個(gè)線性規(guī)劃模型。因此，可以考慮使用電子表格的規(guī)劃求解工具進(jìn)行求解。4.最短距離問題本質(zhì)是路線最優(yōu)問題通常所講的最短路徑問題不僅包括地理上的距離最短，還包括費(fèi)用最少或者時(shí)間最短等問題。如選址、管道鋪設(shè)時(shí)的選線、設(shè)備更新、投資等問題，都可以歸結(jié)為求最短路的問題。【實(shí)施步驟】1.建立數(shù)學(xué)模型設(shè)決策為s.t.

2.在電子表格中輸入基礎(chǔ)數(shù)據(jù)在B4:E15區(qū)域輸入各段路線及其距離。將B4:B15命名為“從”，將C4:C15命名為“至”，將D4:D15命名為“距離”，將E4:E15命名為“是否選擇”。3.編輯目標(biāo)函數(shù)在C18單元格輸入公式“=SUMPRODUCT(距離,是否選擇)”。思考與點(diǎn)撥：公式“=SUMPRODUCT(距離,是否選擇)”應(yīng)該如何理解？SUMPRODUCT(

)函數(shù)是是在給定的幾組數(shù)組中，將數(shù)組間對應(yīng)的元素相乘，并返回乘積之和。其語法形式為“=SUMPRODUCT(array1,

[array2],

[array3],

...)”，數(shù)組參數(shù)個(gè)數(shù)為2到255個(gè)。在任務(wù)中，公式“=SUMPRODUCT(距離,是否選擇)”與公式“=sum(D4:D15*

E4:E15)”或公式“=D4*E4+D5*E5+D6*E6+……+D15*E15)”

的計(jì)算結(jié)果相同，但使用數(shù)組公式可以為類似于

SUMPRODUCT(

)函數(shù)的計(jì)算提供更通用的解法。需要注意的是：數(shù)組參數(shù)必須具有相同的維數(shù)，否則，函數(shù)SUMPRODUCT(

)將返回錯(cuò)誤值

#VALUE!；函數(shù)SUMPRODUCT(

)將非數(shù)值型的數(shù)組元素作為0處理。4.編輯約束條件式在區(qū)域G4:G10輸入各個(gè)節(jié)點(diǎn)的名稱，在H4單元格輸入公式“=SUMIF(從,G4,是否選擇)-SUMIF(至,G4,是否選擇)”。將該公式向下填充到H10。在J4單元格輸入“1”，在J10單元格輸入“-1”，在J5:J9區(qū)域輸入“0”。5.使用規(guī)劃求解工具求解選中目標(biāo)函數(shù)單元格C18,點(diǎn)擊“數(shù)據(jù)|分析|規(guī)劃求解”，出現(xiàn)如圖所示的對話框，設(shè)置目標(biāo)為單元格C18到“最小值”，通過可更改單元格設(shè)置為“E4:E15”，如圖所示。點(diǎn)擊遵守約束右側(cè)的“添加”按鈕，彈出添加約束對話框，單元格引用選擇輸入“$H$4:$H$10

”，約束輸入“$J$4:$J$10”，點(diǎn)擊約束類型右側(cè)的箭頭，在下拉菜單中選擇“=”，點(diǎn)擊“添加”，繼續(xù)添加新約束條件。單元格引用輸入“E4:E10”，點(diǎn)擊約束類型右側(cè)的箭頭，在下拉菜單中選擇“bin”，即設(shè)置決策變量為“二進(jìn)制”（變量只能取值0或1），點(diǎn)擊“確定”，如圖所示。勾選使無約束變量為非負(fù)數(shù)，點(diǎn)擊選擇求解方法右側(cè)箭頭，在下拉菜單中選擇“單純線性規(guī)劃”，如圖所示。點(diǎn)擊“求解”，彈出規(guī)劃求解結(jié)果對話框，如圖所示。保留默認(rèn)選項(xiàng)“保留規(guī)劃求解的解”，選中“運(yùn)算結(jié)果報(bào)告”，點(diǎn)擊“確定”即可得到規(guī)劃求解的解及運(yùn)算結(jié)果報(bào)告如圖所示。從上圖可以得出，最短路徑為S→A→B→E→D→T,最短距離為26公里。所以，應(yīng)當(dāng)選擇路線S→A→B→E→D→T作為推薦路線?！救蝿?wù)小結(jié)】最短路徑問題廣泛應(yīng)用于交通、電路、通訊等實(shí)際領(lǐng)域。它的目標(biāo)是從起點(diǎn)到終點(diǎn)尋找一條總長度最短的路。在一些實(shí)際應(yīng)用中，長度指的是距離，所以最短路的目標(biāo)就是總行進(jìn)距離最短。但是，另一些最短路徑的應(yīng)用的目標(biāo)則是使得一系列活動(dòng)的總成本或總時(shí)間最短。最短路徑問題是一類特殊的線性規(guī)劃問題，在Excel中可以利用Solver求解器解決最短路徑問題的關(guān)鍵是將如何將問題描述為線性規(guī)劃模型，難點(diǎn)是約束條件中關(guān)于節(jié)點(diǎn)凈流量計(jì)算公式“=SUMIF(從,**,是否選擇)-SUMIF(至,**,是否選擇)”的理解。【實(shí)踐訓(xùn)練】某物流公司計(jì)劃從產(chǎn)地O出發(fā)，將