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

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

2、，Dijkstra算法用于求解最短路徑問題最常用的方法之一。Dijkstra算法的基本步驟如下：(1)給起點(diǎn)Vi以P標(biāo)號(hào)pvi0,其余各點(diǎn)均給以T標(biāo)號(hào)，TVi=。(2)若Vi點(diǎn)為剛得到的p標(biāo)號(hào)的點(diǎn)，考慮這樣的點(diǎn)為Vj,考慮Vi,Vj這條邊，且Vj為T標(biāo)號(hào)，對(duì)Vj的T標(biāo)號(hào)進(jìn)行如下更改TVjminTVj,PVilj(3)比較所有具有T標(biāo)號(hào)的點(diǎn)，把最小者改為P標(biāo)號(hào)，即PViminVi,當(dāng)存在兩個(gè)以上最小者時(shí)，可同時(shí)改為P標(biāo)號(hào)，若全部點(diǎn)均為P標(biāo)號(hào)，則停止，否則Vi代Vi改為第二步重做。案例分析下圖所示是某地區(qū)交通運(yùn)輸?shù)氖疽鈭D，試問從V1出發(fā)，經(jīng)哪條路線達(dá)到V8才能使總行程最短使用Dijkstra求解。

3、步驟:V81.首先給Vi以P標(biāo)號(hào)，PVi0,給其余所有的點(diǎn)以T標(biāo)號(hào)，TV1i1,2,82.(1)考察點(diǎn)Vi,邊Vi,V2,Vi,V3TV2TV3minTV2,PV1minTV3,PV11213minmin,04,06(2)比較所有T標(biāo)號(hào)TV2,TV3TV24最小，所以給V2以P標(biāo)號(hào),PV24,記錄路徑V1,V23.(1)V2為剛得到P標(biāo)號(hào)的點(diǎn)，考察邊V2,V4,V2,V5TV4minTV4,PV2l24min,4TV5minTV5,PV2l25min,4(2)比較所有T標(biāo)號(hào),TV3,TV4,TV5,TV36最小，給V3以P標(biāo)號(hào),PV36，記錄路徑Vi,V34.(1)V3為剛得到P標(biāo)號(hào)的點(diǎn),考察

4、V3,V4,V3,V5TV4minTV4,PV3134min9,649TV5minTV5,PV3l35min8,678(2)比較所有T標(biāo)號(hào),TV4,TV5,TV58最小，給V5以P標(biāo)號(hào)，令PV58，記錄路徑V2V5. (1)V5為剛得到P標(biāo)號(hào)的點(diǎn),考察V5,V6,V5,V7TV6minTV6,PV5l56min,8513TV7minTV7,PV5I57min,8614(2)比較所有T標(biāo)號(hào)，TV4,TV6,TV7,TV49最小，給V4以P標(biāo)號(hào)，令PV49,記錄路徑V2,V46. (1)V4為剛得到P標(biāo)號(hào)的點(diǎn),考察V4,V6,V4,V7TV6minTV6,PV4l46min13,9913TV7mi

5、nTV7,PV4I47min14,9714(2)比較所有T標(biāo)號(hào)，TV6,TV7,TV613最小，給V6以P標(biāo)號(hào)，令PV613,記錄路徑V5,V67. (1)V6為剛得到P標(biāo)號(hào)的點(diǎn)，考察V6,V7,V6,V8TV7minTV7,PV6l67min14,13414TV8minTV8,PV6&min,13417(2)比較所有T標(biāo)號(hào)，TV7,TV8,TV714最小，給V7以P標(biāo)號(hào),令PV714,記錄路徑V5,V78. (1)V7為剛得到P標(biāo)號(hào)的點(diǎn)，考察V7,V8TV8minTV8,PV7l78min17,14115(2)比較所有T標(biāo)號(hào)，TV815最小，給V8以P標(biāo)號(hào)，令PV815,記錄路徑V7,V8實(shí)驗(yàn)總結(jié)科學(xué)合理的運(yùn)輸路線對(duì)物流白成本的大小影響很大。Dijkstra算法就是通過一種方法，使運(yùn)輸路線最短，運(yùn)費(fèi)最少，盡可能的降低物流成本，提高產(chǎn)品的競爭力，Dijkstra,根據(jù)距V1從近到遠(yuǎn)的順序，依次求得Vi到V8