運(yùn)籌學(xué)最短路徑實(shí)驗(yàn)

1、實(shí)驗(yàn)項(xiàng)目：最短路徑問(wèn)題實(shí)驗(yàn)學(xué)時(shí)： 4實(shí)驗(yàn)日期： 2012 年 11 月 30 日 實(shí)驗(yàn)要求：案例 模型 分析 實(shí)驗(yàn)內(nèi)容：用最短路徑模型解決具體問(wèn)題前言 運(yùn)輸是物流過(guò)程的主要職能之一，也是物流過(guò)程各項(xiàng)業(yè)務(wù)的中心活動(dòng)。物流過(guò)程中 的其它各項(xiàng)活動(dòng)， 如包裝、裝卸搬運(yùn)、物流信息等， 都是圍繞著運(yùn)輸而進(jìn)行的。 可以說(shuō)， 在科學(xué)技術(shù)不斷進(jìn)步、 生產(chǎn)的社會(huì)化和專(zhuān)業(yè)化程度不斷提高的今天， 一切物質(zhì)產(chǎn)品的生 產(chǎn)和消費(fèi)都離不開(kāi)運(yùn)輸。物流合理化，在很大程度上取決于運(yùn)輸合理化。所以，在物流 過(guò)程的各項(xiàng)業(yè)務(wù)活動(dòng)中，運(yùn)輸是關(guān)鍵，起著舉足輕重的作用。而有效的縮減路徑可以使 得運(yùn)輸費(fèi)用降低。本文運(yùn)用 Dijkstra 算法求

2、出最短路徑，以最大限度地節(jié)約運(yùn)輸費(fèi)用降 低物流成本， Dijkstra 算法用于求解最短路徑問(wèn)題最常用的方法之一。Dijkstra 算法的基本步驟如下 ：（1）給起點(diǎn)v 1以P標(biāo)號(hào)p v 1 0 ,其余各點(diǎn)均給以 T標(biāo)號(hào)，TVi 。（2）若vi 點(diǎn)為剛得到的標(biāo)號(hào)的點(diǎn)，考慮這樣的點(diǎn)為 v j ，考慮 vi ,vj 這條邊，且 vj 為T(mén)標(biāo)號(hào)，對(duì)vj 的T標(biāo)號(hào)進(jìn)行如下更改T v jminT v j , Pv i l ij（3）比較所有具有標(biāo)號(hào)的點(diǎn)，把最小者改為標(biāo)號(hào)，即 PVimin vi ，當(dāng)存在兩個(gè)以上最小者時(shí)， 可同時(shí)改為標(biāo)號(hào)， 若全部點(diǎn)均為標(biāo)號(hào)， 則停止，否則v i 代v i 改為第二步重做

3、。案例分析下圖所示是某地區(qū)交通運(yùn)輸?shù)氖疽鈭D，試問(wèn)從 v1 出發(fā)，經(jīng)哪條路線達(dá)到v8才能使總行程最短使用Dijkstra 求解。步驟：v81.首先給 v1以P標(biāo)號(hào)， P V1 0 ,給其余所有的點(diǎn)以 T標(biāo)號(hào)，T Vii 1,2,82.1）考察點(diǎn) V1 ，邊 V1,V2 , V1,V3T V2T V3min T V2 ,P V1 min T V3 ,PV1l12 minl13 min,0 4,0 62）比較所有 T 標(biāo)號(hào)T V2 ,T V3 ，T V24 最小，所以給 V2以P 標(biāo)號(hào)，PV2 4 ,記錄路徑 V1,V23. （1） V2 為剛得到 P標(biāo)號(hào)的點(diǎn)，考察邊V2,V4 , V2,V5T V

4、4min T V4 ,P V2l24 min,459T V5 min T V5 ,P V2l25 min,4482）比較所有 T 標(biāo)號(hào)，T V3 ,T V4 ,T V5,T V3 6最小，給 V3以 P標(biāo)號(hào)，P V3 6 ,記錄路徑 V1,V34. （1）V3 為剛得到 P標(biāo)號(hào)的點(diǎn)，考察 V3,V4 , V3,V5T V4 min T V4 ,P V3l34min 9,6 4 9T V5min T V5 ,PV3l35min 8,6 7 82）比較所有 T 標(biāo)號(hào)，TV4 ,TV5 ,TV5 8最小，給V5以 P標(biāo)號(hào)，令P V5 8 ,記錄路徑 V2,V55. （1） V5為剛得到 P標(biāo)號(hào)的點(diǎn)，

5、考察 V5,V6 , V5,V7T V6min T V6 ,P V5l56min,8 513T V7min T V7 ,P V5l57min,8 614（2）比較所有 T 標(biāo)號(hào)， TV4 ,TV6,T V7 ,TV4 9最小,給V4以 P 標(biāo)號(hào),令 P V4 9 ，記錄路徑 V2,V46. （1）V4為剛得到 P標(biāo)號(hào)的點(diǎn)，考察 V4,V6 , V4,V7T V6 min T V6 ,PV4 l46 min 13,9 9 13T V7 min T V7 ,P V4 l 47 min 14,9 7 14（2） 比較所有 T標(biāo)號(hào),T V6 ,T V7 ,T V6 13最小,給V6以P標(biāo)號(hào),令P V6

6、 13,記 錄路徑 V5,V67. （1） V6為剛得到 P標(biāo)號(hào)的點(diǎn)，考察 V6,V7 , V6,V8T V7 min T V7 ,P V6 l67 min 14,13 4 14T V8 min T V8 ,P V6 l 68 min ,13 4 17（2）比較所有 T標(biāo)號(hào)，T V7 ,TV8 ,T V7 14最小,給V7以P標(biāo)號(hào),令PV7 14, 記錄路徑 V5,V78. （1）V7 為剛得到 P標(biāo)號(hào)的點(diǎn)，考察 V7,V8T V8 min T V8 ,PV7 l78 min 17,14 1 15（2）比較所有 T標(biāo)號(hào)， T V8 15最小，給 V8以 P標(biāo)號(hào),令P V8 15 ,記錄路 徑 V7 ,V8至此可以得到最短路徑為 V1 V2 V5 V7 V8 ,最短行程為 15實(shí)驗(yàn)總結(jié)科學(xué)合理的運(yùn)輸路線對(duì)物流的成本的大小影響很大。 Dijkstra 算法就是通過(guò)一種 方法，使運(yùn)輸路線最短，運(yùn)費(fèi)最少，盡可能的降低物流成本， 提高產(chǎn)品的競(jìng)爭(zhēng)力， Dijkstra， 根據(jù)距 V1從近到遠(yuǎn)的順序， 依次求得 V1到V