求解運(yùn)輸最短路問(wèn)題

主講教師：孫君楊葉勇無(wú)錫商業(yè)職業(yè)技術(shù)學(xué)院供應(yīng)鏈數(shù)據(jù)分析求解運(yùn)輸最短路問(wèn)題最短路問(wèn)題線性規(guī)劃法建立網(wǎng)絡(luò)最大流問(wèn)題模型0102求解運(yùn)輸最短路問(wèn)題模型03建立運(yùn)輸最短路問(wèn)題模型學(xué)習(xí)目標(biāo)

●了解最短路問(wèn)題的基本涵義●掌握線性規(guī)劃法建立運(yùn)輸最短路問(wèn)題模型●掌握EXCEL工具求解建立運(yùn)輸最短路問(wèn)題模型最短路問(wèn)題最短路問(wèn)題是網(wǎng)絡(luò)分析中的一類優(yōu)化問(wèn)題，它不僅可以直接應(yīng)用于解決生產(chǎn)實(shí)際的許多問(wèn)題，如管道鋪設(shè)、線路安排、廠區(qū)布局等，而且經(jīng)常被作為一個(gè)基本工具，用于解決其它的優(yōu)化問(wèn)題。對(duì)于這類問(wèn)題，圖論中已有解決的方法，如Dijkstra算法、Floyd算法等，但此類算法很繁瑣。最短路問(wèn)題是圖論理論的一個(gè)經(jīng)典問(wèn)題。尋找最短路徑就是在指定網(wǎng)絡(luò)中兩結(jié)點(diǎn)間找一條距離最小的路。最短路不僅僅指一般地理意義上的距離最短,還可以引申到其它的度量,如時(shí)間、費(fèi)用、線路容量等。運(yùn)輸運(yùn)輸最短路問(wèn)題建模求解看例題：Step1

建立運(yùn)輸最短路問(wèn)題模型

Step2

EXCEL工具求解最短路問(wèn)題模型

運(yùn)輸最短路問(wèn)題建模求解

例題求解南洋市東郊城市始點(diǎn)s到終點(diǎn)t的最短路徑及其長(zhǎng)度。圖1南洋市東郊城市交通網(wǎng)絡(luò)圖解決辦法：Step1建立線性規(guī)劃模型Step1.1分析確定目標(biāo)函數(shù)，確定決策變量(整數(shù)規(guī)劃)分析：選擇走哪些相連路段，使得整個(gè)路徑的里程（/時(shí)間/費(fèi)用）最短（最?。?。則目標(biāo)函數(shù)為：里程（/時(shí)間/費(fèi)用）最短（最小）

為路段的里程（/時(shí)間/費(fèi)用）這里，為決策變量，運(yùn)輸最短路問(wèn)題建模求解

Step1.2確定約束條件分析：流量平衡*起點(diǎn)：流出量和=1*終點(diǎn)：流入量和=1*其他節(jié)點(diǎn)的總流入量=總流出量s.t.運(yùn)輸最短路問(wèn)題建模求解

s.t.完整的運(yùn)輸最短路問(wèn)題模型：運(yùn)輸最短路問(wèn)題建模求解

Step2EXCEL工具求解規(guī)劃模型Step2.1向EXCEL表導(dǎo)入數(shù)據(jù)部分Step2.2構(gòu)建模型框架Step2.2.1目標(biāo)函數(shù)單元格中輸入Step2.2.2約束條件關(guān)系構(gòu)建Step2.3運(yùn)用規(guī)劃求解工具求解Step2.3.1工具-加載宏：選擇規(guī)劃求解Step2.3.2輸入目標(biāo)函數(shù)單元格Step2.3.3選擇最大值/最小值Step2.3.4輸入可變（決策）單元格區(qū)域Step2.3.5添加輸入約束條件Step2.3.6確定，保存規(guī)劃求解結(jié)果運(yùn)輸最短路問(wèn)題建模求解

習(xí)題求解圖2始點(diǎn)S到終點(diǎn)T的最短路徑及其長(zhǎng)度。圖2