土方調配和運輸問題的兩種實現方法

張現樂，王月明，歐陽靖雯

(西南科技大學土木工程與建筑學院，四川綿陽 621010)

土方工程中，通過土方調配計算確定施工區(qū)域填挖方區(qū)土方的調配方向和數量，以達到縮短工期和降低成本的目的。本文主要介紹了表上作業(yè)法進行土方調配的缺點和不足，以及常用軟件Excel 的“規(guī)劃求解”功能和LINGO 求解功能在土方調配計算中的應用。這兩種方法避免了繁瑣的求解過程，保證了求解的準確性和可靠性，為工程技術人員提供了簡便的土方調配計算的方法。

1 問題描述及其數學模型

土方調配問題是指從不同的挖方區(qū)向不同的填方區(qū)運送土方，每個填方區(qū)需要特定數量的土方。問題是如何分配每個挖方區(qū)的土方供給，以便在滿足每個填方區(qū)需求的條件下，優(yōu)化某個目標，如最小全部費用或最小總運輸量。設有m個挖方區(qū)Wi(i=1，2，…，m)，設計的待挖土方量分別為si(i=1，2，…，m);有n個填方區(qū)Tj(j=1，2，…，n)，設計需要填方量分別為dj(j=1，2，…，n);從i 到j 平均運輸距離為cij。若用Xij表示從挖方區(qū)i 運往填方區(qū)j 的土方量，則在挖填平衡的條件下，土方的總運輸量最小(若cij為從i 到j 運輸單位土方的單價，則為總運費最小)的調運方案的數學模型為:

其中，式(1)為目標函數，即使土方總運輸量最小;式(2)為挖方區(qū)的供給約束;式(3)為填方區(qū)的需求約束;式(4)為變量非負約束。

上述表達式為挖填平衡時的數學模型。當挖填不平衡時，依據挖、填方量的大小關系，土方調配問題的線性規(guī)劃模型可分別表示如下［1］。

1.1 挖方量大于填方量

1.2 挖方量小于填方量

2 土方調配和運輸問題的傳統(tǒng)方法及其缺陷

2.1 傳統(tǒng)方法的步驟

土方調配問題從實質上講屬于運籌學中的運輸問題，它又分為平衡和不平衡兩類。運輸問題(TP)最早由Hieheoek和Kantorovic 兩位學者提出，我國科學家王元、越民義等人率先開展研究，并于1959年前后獲得了表上作業(yè)法等重要成果。表上作業(yè)法是當前我國解決土方調配問題通用的傳統(tǒng)方法，其基本計算過程為:(1)通過西北角法、最小元素法、元素差額法(Vogel 法)中的一種方法找出初始基可行解。(2)運用閉回路法或位勢法判別基可行解是否最優(yōu)，當全部檢驗數非負時，取得最優(yōu)解。(3)在表上用閉回路調整法進行調整，確定換入變量和換出變量，重復以上步驟直至找出新的基，獲得最優(yōu)方案［2］。

2.2 傳統(tǒng)方法的缺陷

表上作業(yè)法在土方調配應用上的缺陷是由表上作業(yè)法作業(yè)過程和土方工程中土方調配的特點產生的，其缺陷主要表現在以下4個方面:

(1)計算過程比較復雜。表上作業(yè)法不僅要找出初始基可行解，還要反復計算檢驗數，檢核正負值，判斷是否最優(yōu)和進行閉回路調優(yōu)，整個過程比較繁雜。

(2)計算量大，數據處理任務艱巨。假定有m個挖方區(qū)、n個填方區(qū)，則求初始基可行解一般需要m+n－1 次加減運算;用位勢法判優(yōu)，需要經過解m+n－1 次一元一次方程計算位勢和計算(m×n)－(m+n－1)個檢驗數，總計需要計算m×n 次;用閉回路法進行調整，若需要調整k 次，則中間環(huán)節(jié)共需要計算k×(m×n)次得最優(yōu)解時，最優(yōu)解方案的安排需要經過m+n－1 次加減運算得出。故全部過程一共需要經過2×(m+n－1)+k×(m×n)次運算［3］。由于土方工程中挖填區(qū)通常較多，即m 和n 值較大，從而導致表上作業(yè)法的計算量巨大，加之表上作業(yè)法多采用手工計算，因此實現起來比較困難。

(3)計算容易出錯，進行正確性檢核比較困難。由于表上作業(yè)法進行土方調配計算步驟特別多，加之人工計算，很容易出錯，并且難以發(fā)現，逆序檢核、糾錯相當困難。

(4)工作效率低下。表上作業(yè)法步驟多、計算量大，并難以采用電子計算機快速解算，因而要完成大型土方調配方案的確定，通常耗時較長;同時，表上作業(yè)法針對性強，自動化和適應性較差，每遇到一個土方工程都要進行一輪計算，效率低下。

綜上所述，表上作業(yè)法對土方調配區(qū)域較多的工程并非是一種十分有效的方法。實際上，表上作業(yè)法的理論基礎是線性代數中的單純形法，因而可以把土方調配這類運輸問題作為線性規(guī)劃問題來解決。線性規(guī)劃是運籌學的一個重要分支，在數學上用以確定多變量線性函數在變量滿足線性約束條件下的最優(yōu)解，已經成為求解各種優(yōu)化問題的主要方法。線性規(guī)劃不僅理論成熟，而且可以通過計算機來實現。借助線性規(guī)劃模型和Excel 軟件“規(guī)劃求解”功能或運用運籌學中LINGO 求解功能進行土方調配具有操作簡便、計算快速準確的優(yōu)點。

3 線性規(guī)劃模型和Microsoft Excel 在土方調配和運輸問題中的應用

3.1 依據土方工程的設計繪制填挖方平衡及運距表

在土方工程中，可以通過方格網法、橫斷面法和散點法等計算出各挖填區(qū)土方量和之間的平均運輸距離，并繪制各調配區(qū)土方量和平均運距圖。

例:某項目已知各土方調配區(qū)的土方量和相互之間的平均運距(圖1)，求最優(yōu)方案。

為了求解方便，需要在Excel 中建一個填挖方土方量－運距表(見圖2)，將各調配區(qū)土方量和平均運距圖中的數值填入其中，作為土方調配的依據。

圖2 填挖土方量－運距表

3.2 線性規(guī)劃模型表達

在繪制出挖填土方量—運距表后，需要選擇合適的線性規(guī)劃模型，對土方調配問題進行具體數學表達，為利用Microsoft Excel 進行計算提供依據。本文以挖填平衡問題為例，挖填不平衡時土方調配方法與此類似。依據圖2，則所舉案例的線性規(guī)劃數學模型應為:

目標函數:min Z=50×X11+70×X12+100×X13+…+80×X41+100×X42+40×X43

根據約束條件和上述計算式，可以得出未知量有4×3個，獨立方程有4+3－1個，該方程有無窮多組解［4］。而通過Excel 的“規(guī)劃求解”功能可以快速地求出一組最優(yōu)解，使目標函數值為最小。

3.3 借助Excel 快速實現規(guī)劃求解和土方調配

土方調配可以用“單純形法”或“表上作業(yè)法”求解。但用“表上作業(yè)法”求解土方調配最優(yōu)方案須輪流計算，計算量很大;用“單純型法”則更繁瑣。同時，無論是圖解法還是用單純形法，通常采用手工算法，計算起來比較繁瑣，也很容易出錯。

Excel 表具有強大的規(guī)劃求解功能，具體操作步驟如下。

(1)在上述已建好的填挖方平衡及運距Excel 表中，接著建立如圖3 所示單元格。

圖3 目標單元格和可變單元格

其中，單元格B8:D11 與線性規(guī)劃模型中變量Xij相對應，為可變單元格，保持原始值0 空置不填;單元格B12:D12和E8:E11為約束條件的部分表達式，在E8 單元格中輸入公式“= SUM (B8:D8)”(即X11+X12+X13)，在E9 單元格中輸入公式“= SUM (B9:D9)”，在E10 單元格中輸入公式“=SUM (B10:D10)”，在E11 單元格中輸入公式“= SUM(B11:D11)”，在B12 單元格中輸入公式“= SUM (B8:B11)”，在C12 單元格中輸入公式“=SUM (C8:C11)”，在D12 單元格中輸入公式“=SUM (D8:D11)”;單元格F2 與線性規(guī)劃模型中目標函數的表達式相對應，是目標單元格，輸入公式“=SUMPRODUCT (B2:D5，$B$8:$D $11)”，數學含義為“50×X11+70×X12+100×X13+…+80×X41+100×X42+40×X43”，實際含義為“土方總運輸量”。計算式中$ B $8:$D $11為絕對地址，這樣做是為了方便計算式的復制。按上述輸入后，單元格B12:D12、E8:E11 和F2 的值暫時變?yōu)?，見圖3。

(2)加載“規(guī)劃求解”程序。一般情況下，Microsoft Excel軟件中規(guī)劃求解的功能都尚未安裝，需要加載。單擊“工具”菜單，然后點擊“加載宏”，然后在彈出菜單中選中“規(guī)劃求解”項，最后單擊“確定”即可。

(3)設置“規(guī)劃求解參數”。點擊“工具”中的“規(guī)劃求解”選項打開規(guī)劃求解參數設置頁面。在“設置目標單元格中”填入“$F$2”，在“等于”選項中選擇“最小值”，在“可變單元格”選項中填入“$B$8:$D$11”。在“約束”選項中點擊“添加”按紐，添加約束條件“$ B $12:$ D $12=$B$6:$D$6、$ E $8:$ E $11=$ E $2:$ E$5 和$B$8:$D$11 ≥0”。點擊“選項”按鈕出現“規(guī)劃求解選項”對話框，選定“采用線性模型”和“假定非負”復選項，其中的“迭代次數”選項參數可以隨著精度的要求決定。

(4)求解。規(guī)劃求解參數全部設置好之后，即可點擊“求解”按鈕進行計算，彈出“規(guī)劃求解結果”對話框后，點擊“確定”后便得到求解結果(見圖4 所示)。

圖4 土方調配方案

從圖4 中可以看出土方的調配方案為:挖方區(qū)W1 分別運往填方區(qū)T1、T2 土方400 m3和100 m3，挖方區(qū)W2 需要運往填方區(qū)T2 土方500 m3，挖方區(qū)W3 需要分別運往填方區(qū)T1、T3 土方400 m3和100 m3，挖方區(qū)W4 需要運往填方區(qū)T3土方400 m3，土方調配后土方總運輸量為94000 m3。

(5)檢驗結果。為了防止計算出錯，可以通過單元格B12:D12 與B6:D6 以及E8:E11 與E2:E5 對比分析檢驗輸入是否出錯。如果兩者一致說明正確無誤，如果不一致則說明單元格數據輸入或規(guī)劃參數設置出錯，需要檢查糾正。經檢驗，本次計算正確無誤。

(6)繪制土方調配圖。為了方便工程施工需要將得出來的調配方案繪制成土方調配圖，見圖5。

圖5 土方調配圖

4 采用運籌學中LINGO 程序求解

當在Windows 下開始運行LINGO 系統(tǒng)時，會得到類似圖6 的一個窗口。

圖6 Windows 開始運行LINGO 系統(tǒng)時的窗口

其中外層是主框架窗口，包含了所有菜單命令和工具條，其它所有的窗口將被包含在主窗口之下。在主窗口內的標題為LINGO Model－LINGO1 的窗口是LINGO 的默認模型窗口，建立的模型都要在該窗口內編碼實現。

而采用LINGO 求解上面的例題，需要輸入程序:

然后點擊工具條上的求解按鈕即可求得結果。經檢驗，所求得結果與用Excel 求解得到的結果一樣。而運用LINGO的程序求解更方便，它可以用于一切的土方調配和運輸問題。如果是小型土方平整，也可以不輸入程序，直接輸入前面提到的線性規(guī)劃數學模型，即可求得結果。經過筆者檢驗，完全可以實現。

5 Microsoft Excel 規(guī)劃求解功能和LINGO 求解功能的

利用Excel 規(guī)劃求解功能和LINGO 求解功能求解土方調配問題的方法適用范圍較廣，它們不僅適用于挖填平衡條件下的土方調配，而且也適用于挖填不平衡的情況，即可以應用于所有線性運輸問題(LTP)。挖填不平衡時，只需采用相應的線性規(guī)劃模型并改變Excel“規(guī)劃求解參數設置”約束條件即可，而LINGO 只需在模型窗口中改變約束條件即可。Excel 計算表在土方調配中可以重復使用，效率較高。當土地平整工程和土方調配任務發(fā)生變化時，只需根據挖填區(qū)個數在圖4 中刪除或插入相應的單元格即可，而Excel 計算表的公式和規(guī)劃求解參數通常無需修改。此外，如果需要經常性進行土方調配工作，還可設置“清空數據”和“土方調配”等命令按紐以及快捷菜單，方便清除數據，達到優(yōu)化用戶操作界面的目的。而利用LINGO 程序求解則無需這樣。

需要注意的是，運用Excel 規(guī)劃求解功能求解計算出來的結果一定最優(yōu)，但可能并非惟一，所得方案只是最優(yōu)方案中的一種，是否存在惟一解，需通過位勢法求來檢驗。若非基變量的檢驗數全部大于0，則所求解為惟一最優(yōu)解;若存在非基變量的檢驗數等于0，則說明存在非惟一最優(yōu)解。此時，只要把檢驗數為0 的非基變量作為入基變量，調整運輸方案，即可得到另一個最優(yōu)方案。而LINGO 求解計算出來的結果一定最優(yōu)，且可以得到所有的最優(yōu)方案。

8 結束論

本文介紹了借助線性規(guī)劃模型和Microsoft Excel“規(guī)劃求解功能”求解以及LINGO 求解土方工程中土方調配問題的方法，與傳統(tǒng)的表上作業(yè)法相比，這兩種方法具有方便、快捷、準確的優(yōu)點，尤其在挖、填區(qū)較多情況下，這樣的優(yōu)勢將更加明顯。同時，這兩種方法也可推廣應用于所有線性運輸問題(LTP )和最短路徑問題的求解。

［1］劉立群.土方調配優(yōu)化中運籌方法的改進［J］.工業(yè)技術經濟，2001(4):61－63

［2］李時椿.運輸問題表上作業(yè)法的改進研究［J］.南京航空航天大學學報，2000，32 (3):324－329

［3］賈春玉.運輸問題新解法的探討［J］.系統(tǒng)工程學報，2005，19(2):208－217

［4］鄭文魁，徐勝春.“規(guī)劃求解”在土方調配計算中的應用［J］.水利科技與經濟，2006，12 (10):678－686