Dijkstra和AOE圖網絡法在農業運籌管理中的運用

曾 婷，鐘蕓香

（中南林業科技大學經濟學院，湖南 長沙 410004）

0 引言

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

1 Dijkstra和AOE方法在農業活動中的運用

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

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

Dijkstra算法步驟如下：

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

（2）與起點相鄰的點記為：vsk(k=1,2,.....sm)，sm 是與起點相連接的節點個數。那么起點vs→vsk的試探性距離為：

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

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

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

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

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

1.2 農業生產計劃中的網絡制定

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

圖2 工序前后順序的表達

二是對于具有共同先行事件的需求，需要引入“虛工序”，如糧食銷售中必須在加工和訂單簽訂兩者均完成之后才能實施。因為圖3中A和B工序是并行工序，兩者間不存在因果關系，但C的完成依賴于A、B完成，故可以引入一個虛工序4。

圖3 并行先行事件條件的AOE圖規則

繪制網絡圖之后，需要計算工序總時差，具體步驟如下：

（1）計算事件發生最早事件。初始點的時間記為0，由i→j的最早事件為上一節點時間加上i→j花費時間，公式為：

對于虛工序而言，因為其面臨著多個先決條件，故最早發生時間公式為：

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

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

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

2 實例分析

例1：“農超互接”是避免“谷賤傷農”、提高農民收入的重要方式。某一大型超市與某地農民簽訂了固定供貨合同，由該地農民向其供應某一特定蔬菜。在供出地與超市間存在著6個農產品物流集散中心，且它們之間均存在的物流服務。不同地點間的距離在圖4中以權數表明。現尋找一條能夠實現最短距離的蔬菜運送路徑。

圖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

因為minT(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)進行比較，發現T(1)=2最小，故得到：P(1)=2，與1相連的是3、4、5點，計算：

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值，發現T（2)最小，確定p(2)=3。2與4、6點相連，

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點，計算：

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值，發現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

所以本例當中的蔬菜最低運送距離為5.5，最短路解為：s→1→4→e。

圖5 某糧食生產企業運作流程

例2:圖4為一個糧食生產企業的運行流程圖，具體包括檢疫、農機、采購、生產、質量與訂單銷售等各個環節。那么這些活動可以表示為一個先行事件表，表中包括工序代碼、所需要的時間、工序內容與先行工序，這些都會作為繪制AOE網絡圖的關鍵要素，具體為表1。為了便于計算，本文確定的工序時間均按照經驗估算，與現實可能有出入，但這里只側重于算法，具體時間可根據實際進行調整。

表1 先行事件表

圖6 AOE關鍵路徑圖

（1)從左到右邊依次計算最早事件：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)從右到左計算最遲時間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)計算各工序的最早開工時間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)計算工序最遲開工時間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)計算各工序的總時差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,根據定義，總時差為0的為關鍵序列，本例中A（1,2）、C（2,4）、F（4,6）、G（6,7）、H（7,8）、I（8,9）、K（9,10）等7個工序為關鍵工序。而B、D兩個工序為非關鍵工序，說明該糧食企業過程中，農機管理、采購管理和技術準備三個并行工序中，決定生產效率的是糧食原產品的的采購時間，所以可以考慮在其他流程不變的調整下，努力加大物流體系建設，縮短原材料供貨時間，壓縮關鍵工序所需要的時間。值得一提的是，如果路徑C經過效率壓縮后，其自身的關鍵工序地位將被改變，那么需要重新測定并對新的關鍵路徑進行改進，這體現了農業生產企業流程優化的動態性。

3 結論

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

[1]朱春江,古龍高,范郁爾.農業產業線性規劃研究[J].江蘇農業科學，2012，（11）.

[2]牛凱.中國農業結構調整的多目標線性規劃模型研究[J].浙江農業學報，2011，（4）.

[3]丁建國，劉曉媛，蘇武崢，戴健.基于灰色線性規劃法的新疆南疆干旱區農業系統優化研究——以新疆和田縣為例[J].中國農學通報，2012，（23）.

[4]盛秀艷，竇志偉.農業運輸問題的表上作業法與圖上作業法的比較[J].安徽農業科學，2010，（4）.

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