利用Excel Vba求解運輸問題的計算機輔助算法

曾 強 鄧敬源 袁明明

(河南理工大學能源科學與工程學院 河南 焦作 454000)

?

利用Excel Vba求解運輸問題的計算機輔助算法

曾 強 鄧敬源 袁明明

(河南理工大學能源科學與工程學院 河南 焦作 454000)

針對運輸問題求解過程的復雜性，基于表上作業原理，提出一種利用Excel Vba求解運輸問題的計算機輔助算法。首先，介紹了輔助算法原理及計算流程；其次，詳細描述了輔助算法的三個關鍵技術，即用最小元素法獲取初始基可行解的技術、用位勢法求取非基變量檢驗數的技術及用程序進行閉合回路自動調整的技術；最后，通過案例分析驗證了該輔助算法的有效性。

運輸問題 計算機輔助算法 表上作業法 Excel Vba

0 引 言

運輸問題是組織運營中常遇到的重要問題，運輸優化能為組織帶來經濟或社會效益。然而，運輸問題最優解的求解過程卻是一項復雜而繁瑣的工作，正是這種高度復雜性限制了運輸問題在組織運營中的推廣應用。基于此，自從20世紀40年代運輸問題提出之日起[1]，學者對運輸問題的求解方法進行了大量的研究，取得了較豐富的成果。

概括而言，運輸問題的主要求解方法有線性規劃法、動態規劃法、表上作業法、圖上作業法、網絡解法和計算機算法[1]。運輸問題是線性規劃問題的特例，故可考慮將運輸問題視為線性規劃問題，利用線性規劃方法求解。但由于運輸問題決策變量多，約束條件多[2]，利用線性規劃方法求解運輸問題需進行大量重復計算，計算很不經濟。動態規劃法[3]將運輸問題轉化為動態規劃問題，采用動態規劃方法求解。但動態規劃法本身比較抽象，不同的動態規劃問題需建立相應的狀態轉移方程，難以被現場人員掌握。表上作業法首先利用最小元素法或其他方法獲得初始基可行解，再利用閉回路法或位勢法求取非基變量的檢驗數，并利用閉回路調整法進行解的調整直到所有非基變量的檢驗數非負[1-2]。表上作業法的計算量大，手工計算易出錯、效率低。圖上作業法需在圖上構造邊、權、邊線，然后在圖上求解，當產地數和銷地數較多時，邊、權、邊線太多，易混淆，不利于實際操作[1]。網絡解法將運輸問題視作一個網絡，采用圖與網絡技術進行求解。它可以更直觀、快速、形象地得到初始解，但當產銷地數量較多時，繪制網絡圖較麻煩[1]。計算機算法是將以上幾種方法用計算機來加以實現，它可提高計算效率和準確性，從而提高運輸問題在組織運營中推廣應用的可能性。目前，在運輸問題的計算機算法方面已有一些研究成果：文獻[4-5]利用EXCEL的規劃求解功能求解運輸問題，在一定程度上提高了計算效率，但由于約束條件隨著產地數m和銷地數n的不同而不同，需手工設置公式及約束條件，操作繁瑣、易出錯，且難以獲得多個最優解。文獻[6-8]利用Matlab的線性規劃工具求解運輸問題，但因運輸問題的變量多(m×n個決策變量)、約束條件多(m+n-1個獨立約束方程)，其系數矩陣的結構松散而龐大[2]，導致設置工作繁雜，不利于現場人員掌握。文獻[9]提出一種神經網絡解法求解運輸問題，雖有一定創新性，但卻問題復雜化，不利于現場人員掌握。文獻[10]提出一種計算機算法求解運輸問題，但僅給出了總體思路，未給出詳細求解步驟。運輸問題的計算機算法還有遺傳算法[11]、蟻群算法[12]等，但這些算法主要用于求解復雜而特殊的運輸問題，不具有普適性。在現實中以傳統運輸問題居多，研究傳統運輸問題的計算機算法更具意義。

文獻[1]指出表上作業法的計算量大，但因其原理相對簡單、計算過程相對形象直觀，因此在現實中應用最為廣泛。本文基于表上作業原理，將人與計算機的特長相結合，利用計算機擅長重復計算和人擅長思考的特點，利用Excel Vba開發了一種傳統運輸問題計算機輔助算法。

1 運輸問題數學模型

設某種物品有m個產地Ai,i=1,2,…,m，其產量為ai,i=1,2,…,m，有n個銷地Bj,j=1,2,…,n，其銷量為bj,j=1,2,…,n。從產地Ai向銷地Bj運輸單位物品的運價為cij、運量為xij。

對于產銷平衡的運輸問題有如下數學模型：

xij≥0i=1，2，…，mj=1，2，…，n

對于產銷不平衡的運輸問題可通過增加虛擬產地或虛擬銷地的方式將其轉化為上述標準的運輸問題。

2 算法原理及流程

本文提出的運輸問題計算機輔助算法依據的原理是表上作業原理。基本思路如下：(1)采用最小元素法獲得初始基可行解；(2)運用位勢法求得非基變量的檢驗數；(3)采用閉回路調整法對基可行解進行調整，轉(2)，直到所有非基變量的檢驗數非負，找到一個最優解；若對最優解不滿意(考慮到實際運營中某些特定條件的限制，最優解可能并不一定適用，導致決策者對理論上的最優解并不一定滿意)，利用算法可快速獲得其他最優解以供決策。圖1是本文算法的計算流程。

圖1 算法計算流程

3 算法關鍵技術

3.1 最小元素法獲取初始基可行解

為采用最小元素法求初始基可行解，定義了數組D和E及大正數M。其中，D=[dij]m+2,n+2，E=[eij]m+1,n+1。

令[dij]m,n中的元素dij=cij，D的第n+1列元素di,n+1=ai，代表產地i的產量，D的第n+2列元素初值di,n+2=ai，代表產地i的余量，顯然有di,n+1≥di,n+2，當產地i未給任何銷地運送物品時取等號。同理，D的第m+1行元素dm+1,j=bj，代表銷地i的銷量，D的第m+2行元素初值dm+2,j=bj，代表銷地j的欠量，顯然有dm+1,j≥dm+2,j，當銷地j未接收任何產地運送的物品時取等。

[eij]m,n中的元素eij用于記錄產地i向銷地j的運量，其值為空表示此運量為0；E的第n+1列元素ei,n+1用于記錄產地i向各銷地運送物品的總量；E的第m+1行元素em+1,j用于記錄銷地j接收各產地運送物品的總量。

在上述變量定義的基礎上，按最小元素法求基可行解的步驟，設計了如圖2所示的初始基可行解計算流程，其中虛線框部分解決了表上作業法的“退化問題”。輸出的初始基可行解存入工作表“基可行解”中。

圖2 用最小元素法求初始基可行解流程

3.2 用位勢法求非基變量檢驗數

用位勢法求非基變量的檢驗數分兩步進行，第一步是計算位勢矩陣F，第二步是根據F和成本矩陣C計算檢驗數矩陣G。F=[fij]m+1,n+1，G=[σij]m+1,n+1。

[fij]m,n中的元素fij=cij(對基變量)，fij=空值(對非基變量)，F的第n+1列元素fi,n+1=ui，F的第m+1行元素fm+1,j=vj，ui、vj是待求的位勢值。[σij]m,n中的元素σij=cij-ui-vj(對非基變量)，σij=空值(對基變量)，Σ的第n+1列元素σi,n+1=ui,Σ的第m+1行元素σm+1,j=vj。

計算非基變量檢驗數的完整流程如圖3所示。輸出的檢驗數矩陣存入工作表“檢驗數”中，為使后續尋找閉合回路的操作更直觀，采用“條件格式”將小于0的單元格置為紅色。

圖3 用位勢法求非基變量檢驗數流程

3.3 閉合回路調整

圖4 尋找閉合回路流程

閉合回路調整包括兩個步驟，第一步是人工尋找閉合回路。在工作表“檢驗數”中找到最小負數檢驗數，以此檢驗數為起點，雙擊該單元格，然后在該單元格橫向或豎向尋找一個空格。找到后雙擊空格，算法自動在起始單元格與空格之間畫一條直線，以此類推，每碰到一個空格，可旋轉90度，直到起始單元格與終點單元格相同，至此找到一個閉合回路。在工作表“檢驗數”中繪制閉合回路的同時，需在工作表“基可行解”中同步繪制閉合回路，并將奇數格背景置為藍色(代表調入格)，偶數格背景置為黃色(代表調出格)。尋找閉合回路的流程如圖4所示，其程序代碼放在該工作表的Worksheet_BeforeDoubleClick事件中。第二步是調整運量。找出工作表“基可行解”中閉合回路中黃色單元格中最小值作為本次運量調整值，將黃色單元格的運量減去此調整值，藍色單元格則加上此調整值，從而實現運量自動調整功能，其對應的代碼放在工作表“基可行解”的“調整”按鈕的Click事件中。

4 案例研究

為驗證本文提出的計算機輔助算法有效性，以文獻[13]中的一個案例進行了計算。

某物資供貨系統有3個資源點、2個物流網點、6個需求點，各資源點的資源量、需求點的需求量、網點規模及各點間的運價分別如表1、表2所示。由于產品質量上的原因，要求A廠供給B6的資源數量不能少于700 t，不允許二次中轉，求最優運輸方案。

表1 各資源點數量、需求點需求量及運價

表2 網點規模及運價

由題意知A1供給B6的物資不少于700 t，可將需求點B6分成B6’和B6”兩部分。其中，B6’需求量為700 t，且這700 t只能由A1供給，故可將A2、A3、D1、D2向B6運輸的運價設為大數M；B6”需求量為800 t，可由A1、A2、A3、D1、D2中的任意資源點或中轉點供給。綜上分析，按如圖5所示進行參數設置。然后利用本文提出的輔助算法求得運輸問題的最優解，求解過程如圖6-圖15。

圖5 參數設置

圖6 初始基可行解

圖7 非基變量對的檢驗數

圖8 “檢驗數”閉合回路

圖9 “基可行解”同步調整回路

圖11 第一次調整后非基變量檢驗數

圖12 一個最優解

圖13 最優解對應的非基變量檢驗數

圖14 求另一最優解的閉合回路

圖15 另一最優解

比較圖12和圖15可見，兩個最優解對應的最低成本相同，均為39 390元。整個計算過程形象直觀、簡便、速度快。一個10×10運輸問題，其求解時間大約在2分鐘之內，當然這還取決于尋找閉合回路的熟練程度。

5 結 語

運輸問題是組織常面臨的決策問題，在現實中具有十分重要的地位。有效降低運輸問題的求解復雜度對于運輸問題的推廣應用具有重要研究意義。借助本文提出的計算機輔助求解算法，可幫助現場人員求解運輸問題的一個或多個最優解，具有“所見即所得”的可視化效果，計算速度快，計算結果準確，并可方便地獲得多個最優解供組織決策。

[1] 王有鴻, 費威. 運輸問題國內外研究評述[J].商業時代, 2010(24):31-32.

[2] 甘應愛, 田豐. 運籌學(修訂版)[M]. 清華大學出版社, 2005.

[3] 孫曉燕, 李自良, 彭雄鳳,等. 利用動態規劃法求解運輸問題的最短路徑[J]. 機械設計與制造, 2010(2):223-224.

[4] 陳雪菱. Excel規劃求解在設施選址中的應用[J]. 工業工程, 2010,13(2):116-118.

[5] 王鳳霞. Excel在物資調運問題中的應用[J]. 中國會計電算化, 2004(6):51-52.

[6] 李建祥, 唐立新, 吳會江. 鋼鐵工業三級供應鏈協調生產計劃研究[J]. 計算機集成制造系統, 2005,11(3):375-380.

[7] 黃雍檢. Matlab在經濟管理中的應用[J]. 湖南大學學報(自然科學版), 2005,32(2):121-124.

[8] 劉希宋, 孫承華. 基于產銷不平衡運輸模型的燃料酒精產業布局[J]. 哈爾濱工業大學學報,2003,35(1):114-117.

[9] 程國忠. 運輸問題的神經網絡解法[J].計算機應用研究,2001(11):16-18.

[10] 司南, 任佳莉. 運輸問題的一種計算機算法[J].計算機應用與軟件,2004,21(7):120-121.

[11] 俞武揚. 多式聯運運輸問題的混合遺傳算法[J].計算機工程與應用, 2009,45(33):10-12.

[12] 李躍光, 張遠平. 一種改進的蟻群算法在垃圾運輸問題中的應用[J].湖南師范大學自然科學學報,2010,33(2):18-23.

[13] 齊二石. 物流工程[M]. 機械工業出版社,2006:182-183.

COMPUTER AIDED ALGORITHM TO SOLVE TRANSPORTATION PROBLEM BY EXCEL VBA

Zeng Qiang Deng Jingyuan Yuan Mingming

(SchoolofEnergyScienceandEngineering,HenanPolytechnicUniversity,Jiaozuo454000,Henan,China)

Aiming at the complexity of solving the transportation problem, a computer-aided algorithm for solving transportation problems using Excel VBA is proposed based on table dispatching method. Firstly, the principle of auxiliary algorithm and the calculation flow are introduced. Secondly, the three key techniques of the auxiliary algorithm are described in detail, namely the technique of obtaining the initial feasible solution by the minimum element method, the technique of calculating the number of non-basic variable by the potential method and the technique of automatically adjusting the closed loop by program. Finally, the effectiveness of the auxiliary algorithm is verified by case study.

Transportation problem Computer-aided algorithm Table dispatching method Excel Vba

2016-07-04。河南省教育廳科學技術研究項目(12B120005)；河南理工大學博士基金項目(B2011-088)。曾強，副教授，主研領域：工業工程。鄧敬源，碩士生。袁明明，碩士生。

TP391 C93-03

A

10.3969/j.issn.1000-386x.2017.07.008