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

【實(shí)施步驟】1.建立數(shù)學(xué)模型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ù)組間對(duì)應(yīng)的元素相乘，并返回乘積之和。其語(yǔ)法形式為“=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)如圖所示的對(duì)話框，設(shè)置目標(biāo)為單元格C18到“最小值”，通過(guò)可更改單元格設(shè)置為“E4:E15”，如圖所示。點(diǎn)擊遵守約束右側(cè)的“添加”按鈕，彈出添加約束對(duì)話框，單元格引用選擇輸入“$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)擊“確定”，如圖所示。勾選使無(wú)約束變量為非負(fù)數(shù)，點(diǎn)擊選擇求解方法右側(cè)箭頭，在下拉菜單中選擇“單純線性規(guī)劃”，如圖所示。點(diǎn)擊“求解”，彈出規(guī)劃求解結(jié)果對(duì)話框，如圖所示。保留默認(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é)】最短路徑問(wèn)題廣泛應(yīng)用于交通、電路、通訊等實(shí)際領(lǐng)域。它的目標(biāo)是從起點(diǎn)到終點(diǎn)尋找一條總長(zhǎng)度最短的路。在一些實(shí)際應(yīng)用中，長(zhǎng)度指的是距離，所以最短路的目標(biāo)就是總行進(jìn)距離最短。但是，另一些最短路徑的應(yīng)用的目標(biāo)則是使得一系列活動(dòng)的總成本或總時(shí)間最短。最短路徑問(wèn)題是一類特殊的線性規(guī)劃問(wèn)題，在Excel中可以利用Solver求解器解決最短路徑問(wèn)題的關(guān)鍵是將如何將問(wèn)題描述為線性規(guī)劃模型，難點(diǎn)是約束條件中關(guān)于節(jié)點(diǎn)凈流量計(jì)算公式“=SUMIF(從,**,是否選擇)-SUMIF(至,**,是否選擇)”的理解?！緦?shí)踐訓(xùn)練】迅達(dá)物流公司需要將一批重要物資從中央倉(cāng)庫(kù)（O）緊急配送到市中心的目的地（T）?，F(xiàn)有的公路運(yùn)輸網(wǎng)絡(luò)如下圖所示，每條公路上的數(shù)字表示運(yùn)輸該路段所需支付的成本（單位：元）。由于時(shí)間緊迫，公司希望找到一條總成本最低的運(yùn)輸路線。起點(diǎn)：

O終點(diǎn)：

T中間節(jié)點(diǎn)：

A,B,C,D可行路線及成本：O→A=80元