高羽佳，葉　勇

(安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院, 安徽 合肥 230036)

?

Dijkstra和關(guān)鍵路徑AOE在農(nóng)業(yè)經(jīng)濟(jì)管理中的應(yīng)用研究

高羽佳，葉勇

(安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院, 安徽 合肥 230036)

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

Dijkstra; AOE; 運(yùn)籌學(xué); 農(nóng)業(yè); 優(yōu)化

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

1　Dijkstra和AOE方法在農(nóng)業(yè)經(jīng)濟(jì)管理活動(dòng)中的運(yùn)用

1.1農(nóng)產(chǎn)品物流體系中的運(yùn)輸問題

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

(1)

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

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

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

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

(2)

(3)從Vsk點(diǎn)出發(fā)，來對(duì)與Vsk點(diǎn)相鄰的點(diǎn)進(jìn)行考慮，可將其記為Vsk,i(i=1,2,......skm)，其中，skm是與Vsk臨近點(diǎn)的個(gè)數(shù).

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

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

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

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

1.2農(nóng)業(yè)生產(chǎn)計(jì)劃中的網(wǎng)絡(luò)制定

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

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

(3)

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

(4)

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

(3)對(duì)最晚開始時(shí)間和最早開始時(shí)間進(jìn)行確定，計(jì)算公式為：

(5)

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

圖2　工序前后順序的表達(dá)

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

2　實(shí)證分析

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

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

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

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

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

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

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

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

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

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

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

圖5AOE關(guān)鍵路徑圖

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

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)最遲時(shí)間tl(i) 可計(jì)算得出，計(jì)算方式為從右到左：

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)各工序的最早開工時(shí)間tes和最遲開工時(shí)間tls可用公式(5)計(jì)算得出，

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)對(duì)各工序的總時(shí)差r(i,j)進(jìn)行計(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.

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

3　結(jié)語

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

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

[2]牛凱.中國農(nóng)業(yè)結(jié)構(gòu)調(diào)整的多目標(biāo)線性規(guī)劃模型研究[J].浙江農(nóng)業(yè)學(xué)報(bào), 2011,(4):108-113.

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

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

[5]葛莉.基于最短路徑Dijkstra算法多尺度道路網(wǎng)中優(yōu)化路徑規(guī)劃方法的研究[J].湖北民族學(xué)院學(xué)報(bào)(自然科學(xué)版),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.

(責(zé)任編校：晴川)

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— )，女，安徽滁州人，安徽農(nóng)業(yè)大學(xué)信息與計(jì)算機(jī)學(xué)院講師, 碩士.研究方向：物流信息化.

F322;O22

A

1008-4681(2016)05-0106-04