Dijkstra和AOE圖網(wǎng)絡(luò)法在農(nóng)業(yè)運(yùn)籌管理中的運(yùn)用

曾 婷，鐘蕓香

（中南林業(yè)科技大學(xué)經(jīng)濟(jì)學(xué)院，湖南 長(zhǎng)沙 410004）

0 引言

農(nóng)業(yè)發(fā)展過程中的優(yōu)化問題非常多，但目前的學(xué)術(shù)研究成果過多的探討產(chǎn)業(yè)結(jié)構(gòu)、農(nóng)業(yè)布局等宏觀經(jīng)濟(jì)領(lǐng)域，而在微觀問題上，如農(nóng)業(yè)活動(dòng)的運(yùn)輸問題、農(nóng)業(yè)工程招投標(biāo)中企業(yè)選擇、農(nóng)業(yè)生產(chǎn)管理計(jì)劃控制上，關(guān)注度則相對(duì)不足。通過文獻(xiàn)搜集，發(fā)現(xiàn)朱春江（2012）采用線性規(guī)劃（LP）方法，對(duì)連云港的農(nóng)業(yè)產(chǎn)業(yè)結(jié)構(gòu)優(yōu)化方案進(jìn)行了提出[1]；牛凱（2011）使用多目標(biāo)線性規(guī)劃法，提出了一種農(nóng)作物種類結(jié)構(gòu)優(yōu)化的方案[2]；丁建國(guó)（2012）以新疆干旱區(qū)為研究對(duì)象，對(duì)農(nóng)業(yè)種植結(jié)構(gòu)和產(chǎn)業(yè)布局優(yōu)化提出建議[3]。上述研究將管理運(yùn)籌學(xué)中的規(guī)劃算法引入農(nóng)業(yè)領(lǐng)域，是一個(gè)可喜的現(xiàn)象，說明近些年來學(xué)者們關(guān)注到了運(yùn)籌理論在農(nóng)業(yè)發(fā)展中的重要性。但仍存在著一些缺陷，一是規(guī)劃方法僅為管理運(yùn)籌理論的一小部分，其他的通用優(yōu)化算法如：指派問題、排隊(duì)論、系統(tǒng)模擬、網(wǎng)絡(luò)分析目前被引入的較為稀少，二是研究問題相對(duì)宏觀，農(nóng)業(yè)布局與區(qū)域農(nóng)業(yè)結(jié)構(gòu)論述較多，在微觀主體如農(nóng)戶、農(nóng)業(yè)企業(yè)、政府、農(nóng)業(yè)組織上的優(yōu)化問題上談?wù)摰妮^少，只有盛秀艷（2010）將運(yùn)輸優(yōu)化理論中的表上、圖上作業(yè)法引入農(nóng)業(yè)經(jīng)濟(jì)領(lǐng)域，并舉出實(shí)例進(jìn)行了實(shí)證[4]。綜上所述，運(yùn)籌學(xué)理論在農(nóng)業(yè)經(jīng)濟(jì)領(lǐng)域具有“弱化”特征，基于此本文從微觀角度將兩種圖網(wǎng)絡(luò)工具：Dijkstra最短路算法和AOE關(guān)鍵路徑技術(shù)引入農(nóng)業(yè)經(jīng)濟(jì)領(lǐng)域，并采用“農(nóng)超對(duì)接”和“糧食企業(yè)生產(chǎn)運(yùn)作流程”兩個(gè)案例進(jìn)行論證，以期對(duì)農(nóng)業(yè)經(jīng)濟(jì)管理領(lǐng)域中的運(yùn)籌管理提供借鑒意義。

1 Dijkstra和AOE方法在農(nóng)業(yè)活動(dòng)中的運(yùn)用

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

對(duì)于農(nóng)產(chǎn)品而言，從蔬菜、水果從農(nóng)戶種植場(chǎng)所向農(nóng)貿(mào)市場(chǎng)或其他農(nóng)產(chǎn)品制造基地運(yùn)輸?shù)倪^程中，需要及時(shí)、盡快、成本最小的完成運(yùn)輸目標(biāo)，因?yàn)檗r(nóng)產(chǎn)品易變質(zhì)特征非常明顯,所以在不考慮運(yùn)費(fèi)、時(shí)間與運(yùn)力約束的條件下，尋求一條最短運(yùn)輸距離成為提升農(nóng)產(chǎn)品物流體系運(yùn)行效率的重要手段。Dijkstra算法是尋求物流運(yùn)輸過程中最短路問題的有效辦法，圖1表示對(duì)于某農(nóng)產(chǎn)品需要從vs運(yùn)送到ve地，中間存在著不同的路徑，虛框內(nèi)表示的是一條單路徑(從i→j),這條路的長(zhǎng)度為：lij，那么有必要尋找一條從vs到ve的最短路徑，表示：

Dijkstra算法步驟如下：

（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ù)。那么起點(diǎn)vs→vsk的試探性距離為：

在所有的Tsk(k=1,2,......sm)中尋找最小值Tsk，并將對(duì)應(yīng)的的距離從試探性改為永久性p(sk)。

（3）從vsk點(diǎn)出發(fā)考慮與其相鄰的點(diǎn)，記為：vsk,i(i=1,2,......skm)，skm為與vsk臨近點(diǎn)的個(gè)數(shù)。按照（2）式計(jì)算出Tsk,i，那么在新增的skm個(gè)試探性距離與原有的sk-1個(gè)試探距離（除去（2）步驟中所確定的v(sk)點(diǎn)），尋找最小的試探性距離，假設(shè)該點(diǎn)標(biāo)號(hào)為：vs,k(1)，則形成新1個(gè)確定距離，p(s,k(1))

（4）從（3）確定的新點(diǎn)開始出發(fā)，迭代搜索最小試探距離，將所有路徑上的最小路徑距離進(jìn)行確認(rèn)。值得注意的是，一旦某個(gè)點(diǎn)在一個(gè)迭代過程中被確認(rèn)為最小距離，從該點(diǎn)出發(fā)計(jì)算其他路徑時(shí)的Tsk值就永遠(yuǎn)改為一個(gè)定值，而不是+∞。

（5）最后確定的距離p(ve)就是公認(rèn)的最短距離，然后根據(jù)圖形判定計(jì)算最佳路徑。

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

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

對(duì)于基層政府來說，一定時(shí)期內(nèi)的各項(xiàng)農(nóng)業(yè)決策決定了三農(nóng)目標(biāo)的實(shí)現(xiàn)程度。在農(nóng)民技術(shù)培訓(xùn)、科技推廣、構(gòu)建特色農(nóng)業(yè)體系的過程中面臨著一系列計(jì)劃規(guī)劃，每個(gè)環(huán)節(jié)均需要其他先行步驟的完成與支持，那么實(shí)現(xiàn)最小的精力、時(shí)間、資金投入，以達(dá)到最理想的目的，需要引入關(guān)聯(lián)路徑搜索方法（AOE）。如一個(gè)地區(qū)的農(nóng)業(yè)生產(chǎn)過程如要經(jīng)歷蟲疫測(cè)度、化肥種子采購(gòu)、農(nóng)機(jī)準(zhǔn)備、農(nóng)產(chǎn)品的加工、市場(chǎng)調(diào)研與銷售、回收賬款等各個(gè)過程，那么根據(jù)不同過程的先后順序和需要花費(fèi)的人力、時(shí)間與先行事件，可以構(gòu)建網(wǎng)絡(luò)圖，使用圖的規(guī)則如下：一是先行事件必須在后工序前面。圖2中A成為B的先行工序，如農(nóng)產(chǎn)品加工必須在收割之后進(jìn)行，A(tij)表示收割所需要的時(shí)間，定義為權(quán)數(shù)。

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

二是對(duì)于具有共同先行事件的需求，需要引入“虛工序”，如糧食銷售中必須在加工和訂單簽訂兩者均完成之后才能實(shí)施。因?yàn)閳D3中A和B工序是并行工序，兩者間不存在因果關(guān)系，但C的完成依賴于A、B完成，故可以引入一個(gè)虛工序4。

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

繪制網(wǎng)絡(luò)圖之后，需要計(jì)算工序總時(shí)差，具體步驟如下：

（1）計(jì)算事件發(fā)生最早事件。初始點(diǎn)的時(shí)間記為0，由i→j的最早事件為上一節(jié)點(diǎn)時(shí)間加上i→j花費(fèi)時(shí)間，公式為：

對(duì)于虛工序而言，因?yàn)槠涿媾R著多個(gè)先決條件，故最早發(fā)生時(shí)間公式為：

（2）計(jì)算事件發(fā)生的最遲時(shí)間tl(j)，這個(gè)過程是步驟（1）的逆向步驟。

（3）確定最早和最晚開始時(shí)間，公式為：

（4）將最晚開工與最早開工時(shí)間相減，得到工序時(shí)差R(i→j)，尋找出時(shí)差為0的工序，并將其確定為關(guān)鍵路徑。

2 實(shí)例分析

例1：“農(nóng)超互接”是避免“谷賤傷農(nóng)”、提高農(nóng)民收入的重要方式。某一大型超市與某地農(nóng)民簽訂了固定供貨合同，由該地農(nóng)民向其供應(yīng)某一特定蔬菜。在供出地與超市間存在著6個(gè)農(nóng)產(chǎn)品物流集散中心，且它們之間均存在的物流服務(wù)。不同地點(diǎn)間的距離在圖4中以權(quán)數(shù)表明?，F(xiàn)尋找一條能夠?qū)崿F(xiàn)最短距離的蔬菜運(yùn)送路徑。

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

（1）與供出地S相連的共有3家。集散中心1,2,3的試探性距離：

T(1)=min(T(1),p(s)+ls1)=min(+∞,0+2)=2

T(2)=min(T(2),p(s)+ls2)=min(+∞,0+3)=3

T(3)=min(T(3),p(s)+ls3)=min(+∞,0+1)=1

因?yàn)閙inT(3)=1最小，所以將3的距離確定為：P(3)=1。

(2)與3相連的僅為4。故T(4)=min(T(4),p(3)+l34)=min(+∞,1+2.5)=3.5，那么將所有T(i)進(jìn)行比較，發(fā)現(xiàn)T(1)=2最小，故得到：P(1)=2，與1相連的是3、4、5點(diǎn)，計(jì)算：

T(3)=min(T(3),p(1)+l13)=min(1,2+1.5)=1

T(4)=min(T(4),p(1)+l14)=min(+∞,2+1.5)=3.5

T(5)=min(T(5),p(1)+l15)=min(+∞,2+4)=6

比較T值，發(fā)現(xiàn)T（2)最小，確定p(2)=3。2與4、6點(diǎn)相連，

T(4)=min(T(4),p(2)+l24)=min(3.5,3+2)=3.5

T(6)=min(T(6),p(2)+l26)=min(+∞,3+3)=6

（4）這里確定p(4)=3.5，與4相鄰的有5、6、E點(diǎn)，計(jì)算：

T(5)=min(T(5),p(4)+l45)=min(6,3.5+1.5)=5

T(6)=min(T(6),p(4)+l46)=min(6,3.5+1)=4.5

T(e)=min(T(e),p(4)+l4e)=min(+∞,3.5+2)=5.5

(3)比較T值，發(fā)現(xiàn)T(6)最小為4.5，故確定P(6)=4.5。那么：

T(e)=min(T(e),p(6)+l6e)=min(5.5,4.5+1.5)=5.5

所以本例當(dāng)中的蔬菜最低運(yùn)送距離為5.5，最短路解為：s→1→4→e。

圖5 某糧食生產(chǎn)企業(yè)運(yùn)作流程

例2:圖4為一個(gè)糧食生產(chǎn)企業(yè)的運(yùn)行流程圖，具體包括檢疫、農(nóng)機(jī)、采購(gòu)、生產(chǎn)、質(zhì)量與訂單銷售等各個(gè)環(huán)節(jié)。那么這些活動(dòng)可以表示為一個(gè)先行事件表，表中包括工序代碼、所需要的時(shí)間、工序內(nèi)容與先行工序，這些都會(huì)作為繪制AOE網(wǎng)絡(luò)圖的關(guān)鍵要素，具體為表1。為了便于計(jì)算，本文確定的工序時(shí)間均按照經(jīng)驗(yàn)估算，與現(xiàn)實(shí)可能有出入，但這里只側(cè)重于算法，具體時(shí)間可根據(jù)實(shí)際進(jìn)行調(diào)整。

表1 先行事件表

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

（1)從左到右邊依次計(jì)算最早事件：te(i)

te(1)=0,te(2)=te(1)+t(1,2)=5,te(3)=te(2)+t(1,3)=8,te(4)=te(2)+t(2,4)=7,

te(5)=max(te(3)+t(3,5），te(4)+t(4,5））=8，

te(6)=max(te(3)+t(3,6），te(4)+t(4,6），te(5)+t(5,6））=15

te(7)=te(6)+t(6,7)=21,te(8)=te(7)+t(7,8)=25,te(9)=te(8)+t(8,9)=28,te(10)=te(9)+t(9,10)=33

(2)從右到左計(jì)算最遲時(shí)間tl(i)。

tl(10)=33,tl(9)=tl(10)-t(9,10)=28,tl(8)=tl(9)-t(8,9)=25,tl(7)=tl(8)-t(7,8)=21,

tl(6)=tl(7)-t(6,7)=15,tl(5)=tl(6)-t(5,6)=9,tl(4)=min(tl(6)-t(4,6),tl(5)-t(4,5))=7

tl(3)=min(tl(6)-t(3,6),tl(5)-t(3,5))=9,tl(2)=min(tl(3)-t(2,3),tl(4)-t(2,4))=5,tl(1)=tl(2)-t(1,2)=0

(3)計(jì)算各工序的最早開工時(shí)間tes。

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)計(jì)算工序最遲開工時(shí)間tls。

tls(1,2)=tl(2)-t(1,2)=0,tls(2,3)=tl(3)-t(2,3)=6,tls(2,4)=tl(4)-t(2,4)=5

tls(3,6)=tl(6)-t(3,6)=11,tls(5,6)=tl(6)-t(5,6)=9,tls(4,6)=tl(6)-t(4,6)=7,

tls(6,7)=tl(7)-t(6,7)=15,tls(7,8)=tl(8)-t(7,8)=21,tls(8,9)=tl(9)-t(8,9)=25

tls(9,10)=tl(10)-t(9,10)=28

(5)計(jì)算各工序的總時(shí)差r(i,j)。

R(12)=0,R(23)=1,R(24)=0,R(36)=3,R(56)=1,R(46)=0,R(67)=R(78)=R(89)=R(910)=0,根據(jù)定義，總時(shí)差為0的為關(guān)鍵序列，本例中A（1,2）、C（2,4）、F（4,6）、G（6,7）、H（7,8）、I（8,9）、K（9,10）等7個(gè)工序?yàn)殛P(guān)鍵工序。而B、D兩個(gè)工序?yàn)榉顷P(guān)鍵工序，說明該糧食企業(yè)過程中，農(nóng)機(jī)管理、采購(gòu)管理和技術(shù)準(zhǔn)備三個(gè)并行工序中，決定生產(chǎn)效率的是糧食原產(chǎn)品的的采購(gòu)時(shí)間，所以可以考慮在其他流程不變的調(diào)整下，努力加大物流體系建設(shè)，縮短原材料供貨時(shí)間，壓縮關(guān)鍵工序所需要的時(shí)間。值得一提的是，如果路徑C經(jīng)過效率壓縮后，其自身的關(guān)鍵工序地位將被改變，那么需要重新測(cè)定并對(duì)新的關(guān)鍵路徑進(jìn)行改進(jìn)，這體現(xiàn)了農(nóng)業(yè)生產(chǎn)企業(yè)流程優(yōu)化的動(dòng)態(tài)性。

3 結(jié)論

本文將管理運(yùn)籌學(xué)中的最短路和關(guān)鍵路徑優(yōu)化算法引入農(nóng)業(yè)經(jīng)濟(jì)管理領(lǐng)域，并通過案例展示了其在農(nóng)業(yè)企業(yè)生產(chǎn)、物流運(yùn)輸上的可用行。當(dāng)前關(guān)于農(nóng)業(yè)經(jīng)濟(jì)管理研究太過偏倚于宏觀狀況變動(dòng)及因素分析，在微觀上農(nóng)戶行為調(diào)查研究也比較廣泛，數(shù)理工具上面板數(shù)據(jù)及l(fā)ogit等計(jì)量模型運(yùn)用比較多，但卻在微觀經(jīng)濟(jì)主體的優(yōu)化問題上缺乏足夠的理論探討和實(shí)證分析，所以這些研究成果對(duì)農(nóng)業(yè)企業(yè)、地方農(nóng)業(yè)主管部門特別是農(nóng)戶的指導(dǎo)意義不大。另外，對(duì)于一些常用、通俗易懂的運(yùn)籌算法，各級(jí)地方主管部門應(yīng)當(dāng)組織有關(guān)專家向農(nóng)業(yè)生產(chǎn)企業(yè)和農(nóng)戶進(jìn)行普及，以提高微觀經(jīng)濟(jì)主體的管理水平。

[1]朱春江,古龍高,范郁爾.農(nóng)業(yè)產(chǎn)業(yè)線性規(guī)劃研究[J].江蘇農(nóng)業(yè)科學(xué)，2012，（11）.

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

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

[4]盛秀艷，竇志偉.農(nóng)業(yè)運(yùn)輸問題的表上作業(yè)法與圖上作業(yè)法的比較[J].安徽農(nóng)業(yè)科學(xué)，2010，（4）.

[5]鮑立威，溫日鯤.管理科學(xué)方法[M].杭州：浙江大學(xué)出版社，2008.