Dijkstra和關鍵路徑AOE在農業(yè)經濟管理中的應用研究

高羽佳，葉　勇

(安徽農業(yè)大學信息與計算機學院, 安徽 合肥 230036)

?

Dijkstra和關鍵路徑AOE在農業(yè)經濟管理中的應用研究

高羽佳，葉勇

(安徽農業(yè)大學信息與計算機學院, 安徽 合肥 230036)

在農業(yè)經濟管理領域中，運籌學理論的應用明顯“弱化”.分析了Dijkstra和AOE方法在農業(yè)經濟管理活動中的運用,并通過兩個例子進行了實證分析.研究發(fā)現(xiàn)，Dijkstra和關鍵路徑AOE在農業(yè)經濟管理中的應用價值較大，能夠促進農業(yè)經濟的快速發(fā)展，值得推廣應用.

Dijkstra; AOE; 運籌學; 農業(yè); 優(yōu)化

隨著我國城鄉(xiāng)一體化進程的日益加快，農業(yè)經濟管理已經成為了社會各界廣泛關注的焦點問題.雖然農業(yè)發(fā)展過程中有較多值得優(yōu)化的問題，但是學術界多注重于農業(yè)布局、農村產業(yè)結構等宏觀經濟領域的優(yōu)化，而對微觀農業(yè)問題的關注度相對較低，在農業(yè)經濟管理領域中，運籌學理論的應用明顯“弱化”[1].Dijkstra算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑.主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止.關鍵路徑是指采用邊表示活動(Activity On Edge)網絡，簡稱AOE網絡，每個頂點代表一個事件，事件說明某些活動或某一項活動的完成，邊表示活動，權表示活動持續(xù)的時間[2].本文從微觀角度入手，在農業(yè)經濟管理領域中引入關鍵路徑AOE技術和Dijkstra最短路算法，以此來為運籌學理論在農業(yè)中的應用打下基礎.

1　Dijkstra和AOE方法在農業(yè)經濟管理活動中的運用

1.1農產品物流體系中的運輸問題

從農戶種植場所中將水果、蔬菜、家畜等農產品運輸到農產品制造基地或農貿市場時，運輸目標往往希望能夠在最小成本、最短時間內完成.由于農產品具有較為明顯的易變質特征，因此，在不對運力約束、時間約束、運費約束進行考慮的情況下，提升農產品物流體系運行效率的主要措施之一就是尋求一條最短運輸距離，而其中最有效的算法就是Dijkstra最短路算法[3].最短路問題的圖形表示如圖1所示，要從Vs地將農產品運輸到Ve地，運輸路徑有多條，虛框內表示的是一條長度為lij的單路徑(從i→j)，那么，需要找出從Vs地將農產品運輸到Ve地的最短路徑，我們用L(u)來表示最短路徑，其計算公式如下：

(1)

Dijkstra最短路算法的具體步驟主要可分為以下5點，分別是：

(1)起點永久性標號P值p(Vs)=0，那么，其他所有點的試探性路徑為：Ti=+∞(i=2,3,......n)；

(2)與起點相鄰的點記為：Vsk(k=1,2,.....sm)，其中，sm是與起點相連接的節(jié)點個數.設定Tsk為Vs地到Vsk地的試探性距離，其計算公式如下：

Tsk=min(Tsk,p(Vs)+ls,sk)

(2)

(3)從Vsk點出發(fā)，來對與Vsk點相鄰的點進行考慮，可將其記為Vsk,i(i=1,2,......skm)，其中，skm是與Vsk臨近點的個數.

基于(2)將Tsk計算出來，那么最小的試探性距離可在原有的(sk-1)個試探距離和新增的skm個試探性距離中尋找.用Vs,k(1)來假設該點標號，則可形成一個全新的確定距離，設定為p(s,k(1)).

(4)初始點選擇為p(s,k(1))，以此為基礎來進行迭代搜索，迭代搜索的目標在于尋找出最小試探距離.一旦某點被迭代搜索確認為最小距離，那么所計算得出的Tsk值就不再是無限值，而是一個定值，且永遠都不能改變[4].

(5)p(Ve)為最后確定的距離，也是被Dijkstra最短路算法公認的最短距離，那么最佳路徑就可以據圖形判定計算而得.

圖1　最短路問題的圖形表示

1.2農業(yè)生產計劃中的網絡制定

對于廣大基層鄉(xiāng)鎮(zhèn)政府而言，“三農目標”在該地區(qū)的實現(xiàn)程度往往是會受到各項農業(yè)決策影響的.無論是農業(yè)技術推廣，還是農民技術培訓，亦或者建立當地特色生態(tài)農業(yè)，都離不開一系列的計劃規(guī)劃，而要實現(xiàn)這些計劃規(guī)劃，那么離不開先行步驟的支持和完成.針對這種情況，就需要引入AOE技術(關聯(lián)路徑搜索技術)，以便能夠用最少的資金投入、最少的時間、最小的精力來達到最理想的效果[5].例如，不管是任何的農業(yè)生產過程，往往都需要經歷回收賬款、銷售農產品、深加工農產品、采購種子化肥等一系列的過程，那么就可基于這些過程所需要耗費的時間、人力、物力、財力，以及先后順序來對網絡圖進行構建[6].使用圖的規(guī)則主要包括2點，第一，只有先發(fā)生了先行事件之后，才可以發(fā)生后續(xù)工序.工序前后順序的表達如圖2所示，工序 A是工序B的先行工序，將A(tij) 定義為權數，表示完成工序 A所需要的時間.第二，適當時可引入“虛工序”，其適用情況為存在著共同先行事件的需求，例如，只有在完成了“糧食訂單簽訂”和“糧食加工”之后，才能夠實施糧食銷售.并行先行事件條件的AOE圖規(guī)則如圖3所示，工序 A、工序B之間沒有因果關系，屬于并行工序，但只有完成了工序 A、工序B之后，才能夠完成工序C，因此，可引入虛工序4.在將網絡圖繪制完畢之后，需要對工序總時差進行計算，具體步驟主要可分為以下4點，分別是：

(1)對最早發(fā)生事件進行計算，用0來標記初始點時間，由i→j的最早事件為上一節(jié)點時間加上i→j花費時間，其計算公式如下：

(3)

由于虛工序所需要面臨的先決條件有若干個，那么最早發(fā)生時間公式為：

(4)

(2)設定tl(j)為事件發(fā)生的最遲時間，對tl(j)進行計算，其計算過程實質上是第(1)步的逆向.

(3)對最晚開始時間和最早開始時間進行確定，計算公式為：

(5)

(4)工序時差R(i→j)可通過“最晚開始時間-最早開始時間”來獲得，然后再對時差為0的工序進行尋找，并將其確定為關鍵路徑[7].

圖2　工序前后順序的表達

圖3　并行先行事件條件的AOE圖規(guī)則

2　實證分析

例1：成都市沃爾瑪超市與蒲江縣碣石鎮(zhèn)農民簽訂了蔬菜固定供貨合同，用S來代表供出地，用E來代表超市所在地，供出地-超市間的物流體系如圖4所示，存在著相互物流服務關系的農產品物流集散中心有6個，以權數表明不同地點間的距離，目前需要找到一條最短路徑來運輸蔬菜.

(1)有3家農產品物流集散中心(分別是農產品物流集散中心1、農產品物流集散中心2、農產品物流集散中心3)與供出地S直接相連.各自的試探性距離為：

由上可知，最小的是T(3)，那么可將3的距離確定為：P(3)=1.

比較全部的T(i)，假定T(1)=2 最小，那么可將1的距離確定為：P(1)=2，與農產品物流集散中心1直接相連的有農產品物流集散中心3、4、5 ，計算：

比較T值，假定T(2)最小，那么可將2的距離確定為：p(2)=3.與農產品物流集散中心2直接相連的有農產品物流集散中心4、6，

再確定p(4)=3.5，與農產品物流集散中心4直接相連的有農產品物流集散中心5、6，以及超市E，計算：

(3)對T值進行比較，發(fā)現(xiàn)T(6)最小為4.5，那么可確定P(6)=4.5.

由此可見，從供出地S到超市所在地E的最短路解為：s→1→4→e，最短運送距離為5.5.

圖4　供出地-超市間的物流體系

例2：某糧食生產企業(yè)在生產運行過程中所涉及到的環(huán)節(jié)如表1所示，并且建立起如圖5所示的AOE關鍵路徑圖.

表1　某糧食生產企業(yè)的涉及環(huán)節(jié)

圖5AOE關鍵路徑圖

(1)te(i)最早事件可用公式(3)計算得出，計算方式為從左到右：

te(1)=0,te(2)= 5,te(3)=8,te(4)=7,te(5)= 8，te(6)= 15，te(7)= 21,te(8)= 25,te(9)= 28,te(10)= 33

(2)最遲時間tl(i) 可計算得出，計算方式為從右到左：

tl(10)=33, tl(9)= tl(10)-t(9,10)=28, tl(8)=25, tl(7)=21, tl(6)=15,tl(5)= 9, tl(4)=min(tl(6)-t(4,6), tl(5)-t(4,5))=7，tl(3)= 9, tl(2)= 5, tl(1)= 0

(3)各工序的最早開工時間tes和最遲開工時間tls可用公式(5)計算得出，

tes(1,2)=te(1)=0,tes(2,3)=te(2)=5,tes(2,4)=te(2)=5,tes(3,6)=te(3)=8,tes(5,6)=te(5)=8,tes(4,6)=te(4)=7,tes(6,7)=te(6)=15,tes(7,8)=te(7)=21,tes(8,9)=te(8)=25,tes(9,10)=te(9)=28

(4)對各工序的總時差r(i,j)進行計算

R(67)=R(78)=R(89)=R(910)=0, R(46)=0,R(12)=0, R(24)=0,R(56)= R(23)=1, R(36)=3.

基于定義來看，關鍵序列的特征為：總時差=0；因此，關鍵工序包括7個，分別是K(9,10)、I(8,9)、A(1,2)、H(7,8)、C(2,4)、G(6,7)、F(4,6).而工序B和工序D屬于非關鍵工序.由此可見，對于技術準備、采購管理和農機管理三個并行工序而言，糧食原產品的采購時間是該企業(yè)生產效率的關鍵.那么可在不調整其他流程的基礎上，對物流體系建設力度進一步加大，以便能夠使采購時間縮短.此外，若效率壓縮路徑C之后，那么有可能會改變路徑C的關鍵工序地位，那么需要對其進行重新測定，并且改進關鍵路徑，這充分說明了優(yōu)化具有動態(tài)性，而不是靜態(tài)的[8].

3　結語

總之，Dijkstra和關鍵路徑AOE在農業(yè)經濟管理中的應用價值較大，能夠促進農業(yè)經濟的快速發(fā)展，值得推廣應用.

[1]丁建國,劉曉媛,蘇武崢,等. 基于灰色線性規(guī)劃法的新疆南疆干旱區(qū)農業(yè)系統(tǒng)優(yōu)化研究——以新疆和田縣為例[J].中國農學通報,2012,(23):130-135.

[2]牛凱.中國農業(yè)結構調整的多目標線性規(guī)劃模型研究[J].浙江農業(yè)學報, 2011,(4):108-113.

[3]盛秀艷,竇志偉.農業(yè)運輸問題的表上作業(yè)法與圖上作業(yè)法的比較[J].安徽農業(yè)科學, 2010,(14):56-60.

[4]楊志丹,李愛平,王懷民.基于Dijkstra算法的多屬性資源搜索的一種實現(xiàn)方法[J].計算機與現(xiàn)代化,2016,(9):191-196.

[5]葛莉.基于最短路徑Dijkstra算法多尺度道路網中優(yōu)化路徑規(guī)劃方法的研究[J].湖北民族學院學報(自然科學版),2012,(3):181-185.

[6]Nachtigall K. Time depending shortest-path problems with applications to railway networks [J]. European Journal of Operational Research,2015,(4):171-178.

[7]Sung K,Bell M G H,Seong M, et al.Shortest paths in a network with time-dependent flow speeds[J]. European Journal of Operational Research,2014,(11):1811-1820.

[8]Xu M, Liu Y, Huang Q,et al. An improved Dijkstra’s shortest path algorithm for sparse network[J]. Applied Mathematics and Computation,2007,(9):2033-2041.

(責任編校：晴川)

Application of Dijkstra and AOE in Agricultural Economic Management

GAO Yujia, YE Yong

(College of Information and Computer, Anhui Agricultural University, Hefei Anhui 230036, China)

In the field of agricultural economic management, the application of operational research theory is obviously weakened. The application of Dijkstra and AOE in agricultural economic management is analyzed, and two examples are given. It is found that the application value of Dijkstra and critical path AOE in agricultural economic management is large, which can promote the rapid development of agricultural economy and is worthy of popularization and application.

Dijkstra; AOE; operational research; agriculture; optimization

2016-06-20

高羽佳(1980— )，女，安徽滁州人，安徽農業(yè)大學信息與計算機學院講師, 碩士.研究方向：物流信息化.

F322;O22

A

1008-4681(2016)05-0106-04