曾 強(qiáng) 鄧敬源 袁明明

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

?

利用Excel Vba求解運(yùn)輸問(wèn)題的計(jì)算機(jī)輔助算法

曾 強(qiáng) 鄧敬源 袁明明

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

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

運(yùn)輸問(wèn)題 計(jì)算機(jī)輔助算法 表上作業(yè)法 Excel Vba

0 引 言

運(yùn)輸問(wèn)題是組織運(yùn)營(yíng)中常遇到的重要問(wèn)題，運(yùn)輸優(yōu)化能為組織帶來(lái)經(jīng)濟(jì)或社會(huì)效益。然而，運(yùn)輸問(wèn)題最優(yōu)解的求解過(guò)程卻是一項(xiàng)復(fù)雜而繁瑣的工作，正是這種高度復(fù)雜性限制了運(yùn)輸問(wèn)題在組織運(yùn)營(yíng)中的推廣應(yīng)用。基于此，自從20世紀(jì)40年代運(yùn)輸問(wèn)題提出之日起[1]，學(xué)者對(duì)運(yùn)輸問(wèn)題的求解方法進(jìn)行了大量的研究，取得了較豐富的成果。

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

文獻(xiàn)[1]指出表上作業(yè)法的計(jì)算量大，但因其原理相對(duì)簡(jiǎn)單、計(jì)算過(guò)程相對(duì)形象直觀，因此在現(xiàn)實(shí)中應(yīng)用最為廣泛。本文基于表上作業(yè)原理，將人與計(jì)算機(jī)的特長(zhǎng)相結(jié)合，利用計(jì)算機(jī)擅長(zhǎng)重復(fù)計(jì)算和人擅長(zhǎng)思考的特點(diǎn)，利用Excel Vba開(kāi)發(fā)了一種傳統(tǒng)運(yùn)輸問(wèn)題計(jì)算機(jī)輔助算法。

1 運(yùn)輸問(wèn)題數(shù)學(xué)模型

設(shè)某種物品有m個(gè)產(chǎn)地Ai,i=1,2,…,m，其產(chǎn)量為ai,i=1,2,…,m，有n個(gè)銷(xiāo)地Bj,j=1,2,…,n，其銷(xiāo)量為bj,j=1,2,…,n。從產(chǎn)地Ai向銷(xiāo)地Bj運(yùn)輸單位物品的運(yùn)價(jià)為cij、運(yùn)量為xij。

對(duì)于產(chǎn)銷(xiāo)平衡的運(yùn)輸問(wèn)題有如下數(shù)學(xué)模型：

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

對(duì)于產(chǎn)銷(xiāo)不平衡的運(yùn)輸問(wèn)題可通過(guò)增加虛擬產(chǎn)地或虛擬銷(xiāo)地的方式將其轉(zhuǎn)化為上述標(biāo)準(zhǔn)的運(yùn)輸問(wèn)題。

2 算法原理及流程

本文提出的運(yùn)輸問(wèn)題計(jì)算機(jī)輔助算法依據(jù)的原理是表上作業(yè)原理?；舅悸啡缦拢?1)采用最小元素法獲得初始基可行解；(2)運(yùn)用位勢(shì)法求得非基變量的檢驗(yàn)數(shù)；(3)采用閉回路調(diào)整法對(duì)基可行解進(jìn)行調(diào)整，轉(zhuǎn)(2)，直到所有非基變量的檢驗(yàn)數(shù)非負(fù)，找到一個(gè)最優(yōu)解；若對(duì)最優(yōu)解不滿意(考慮到實(shí)際運(yùn)營(yíng)中某些特定條件的限制，最優(yōu)解可能并不一定適用，導(dǎo)致決策者對(duì)理論上的最優(yōu)解并不一定滿意)，利用算法可快速獲得其他最優(yōu)解以供決策。圖1是本文算法的計(jì)算流程。

圖1 算法計(jì)算流程

3 算法關(guān)鍵技術(shù)

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

為采用最小元素法求初始基可行解，定義了數(shù)組D和E及大正數(shù)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，代表產(chǎn)地i的產(chǎn)量，D的第n+2列元素初值di,n+2=ai，代表產(chǎn)地i的余量，顯然有di,n+1≥di,n+2，當(dāng)產(chǎn)地i未給任何銷(xiāo)地運(yùn)送物品時(shí)取等號(hào)。同理，D的第m+1行元素dm+1,j=bj，代表銷(xiāo)地i的銷(xiāo)量，D的第m+2行元素初值dm+2,j=bj，代表銷(xiāo)地j的欠量，顯然有dm+1,j≥dm+2,j，當(dāng)銷(xiāo)地j未接收任何產(chǎn)地運(yùn)送的物品時(shí)取等。

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

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

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

3.2 用位勢(shì)法求非基變量檢驗(yàn)數(shù)

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

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

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

圖3 用位勢(shì)法求非基變量檢驗(yàn)數(shù)流程

3.3 閉合回路調(diào)整

圖4 尋找閉合回路流程

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

4 案例研究

為驗(yàn)證本文提出的計(jì)算機(jī)輔助算法有效性，以文獻(xiàn)[13]中的一個(gè)案例進(jìn)行了計(jì)算。

某物資供貨系統(tǒng)有3個(gè)資源點(diǎn)、2個(gè)物流網(wǎng)點(diǎn)、6個(gè)需求點(diǎn)，各資源點(diǎn)的資源量、需求點(diǎn)的需求量、網(wǎng)點(diǎn)規(guī)模及各點(diǎn)間的運(yùn)價(jià)分別如表1、表2所示。由于產(chǎn)品質(zhì)量上的原因，要求A廠供給B6的資源數(shù)量不能少于700 t，不允許二次中轉(zhuǎn)，求最優(yōu)運(yùn)輸方案。

表1 各資源點(diǎn)數(shù)量、需求點(diǎn)需求量及運(yùn)價(jià)

表2 網(wǎng)點(diǎn)規(guī)模及運(yùn)價(jià)

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

圖5 參數(shù)設(shè)置

圖6 初始基可行解

圖7 非基變量對(duì)的檢驗(yàn)數(shù)

圖8 “檢驗(yàn)數(shù)”閉合回路

圖9 “基可行解”同步調(diào)整回路

圖11 第一次調(diào)整后非基變量檢驗(yàn)數(shù)

圖12 一個(gè)最優(yōu)解

圖13 最優(yōu)解對(duì)應(yīng)的非基變量檢驗(yàn)數(shù)

圖14 求另一最優(yōu)解的閉合回路

圖15 另一最優(yōu)解

比較圖12和圖15可見(jiàn)，兩個(gè)最優(yōu)解對(duì)應(yīng)的最低成本相同，均為39 390元。整個(gè)計(jì)算過(guò)程形象直觀、簡(jiǎn)便、速度快。一個(gè)10×10運(yùn)輸問(wèn)題，其求解時(shí)間大約在2分鐘之內(nèi)，當(dāng)然這還取決于尋找閉合回路的熟練程度。

5 結(jié) 語(yǔ)

運(yùn)輸問(wèn)題是組織常面臨的決策問(wèn)題，在現(xiàn)實(shí)中具有十分重要的地位。有效降低運(yùn)輸問(wèn)題的求解復(fù)雜度對(duì)于運(yùn)輸問(wèn)題的推廣應(yīng)用具有重要研究意義。借助本文提出的計(jì)算機(jī)輔助求解算法，可幫助現(xiàn)場(chǎng)人員求解運(yùn)輸問(wèn)題的一個(gè)或多個(gè)最優(yōu)解，具有“所見(jiàn)即所得”的可視化效果，計(jì)算速度快，計(jì)算結(jié)果準(zhǔn)確，并可方便地獲得多個(gè)最優(yōu)解供組織決策。

[1] 王有鴻, 費(fèi)威. 運(yùn)輸問(wèn)題國(guó)內(nèi)外研究評(píng)述[J].商業(yè)時(shí)代, 2010(24):31-32.

[2] 甘應(yīng)愛(ài), 田豐. 運(yùn)籌學(xué)(修訂版)[M]. 清華大學(xué)出版社, 2005.

[3] 孫曉燕, 李自良, 彭雄鳳,等. 利用動(dòng)態(tài)規(guī)劃法求解運(yùn)輸問(wèn)題的最短路徑[J]. 機(jī)械設(shè)計(jì)與制造, 2010(2):223-224.

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

[5] 王鳳霞. Excel在物資調(diào)運(yùn)問(wèn)題中的應(yīng)用[J]. 中國(guó)會(huì)計(jì)電算化, 2004(6):51-52.

[6] 李建祥, 唐立新, 吳會(huì)江. 鋼鐵工業(yè)三級(jí)供應(yīng)鏈協(xié)調(diào)生產(chǎn)計(jì)劃研究[J]. 計(jì)算機(jī)集成制造系統(tǒng), 2005,11(3):375-380.

[7] 黃雍檢. Matlab在經(jīng)濟(jì)管理中的應(yīng)用[J]. 湖南大學(xué)學(xué)報(bào)(自然科學(xué)版), 2005,32(2):121-124.

[8] 劉希宋, 孫承華. 基于產(chǎn)銷(xiāo)不平衡運(yùn)輸模型的燃料酒精產(chǎn)業(yè)布局[J]. 哈爾濱工業(yè)大學(xué)學(xué)報(bào),2003,35(1):114-117.

[9] 程國(guó)忠. 運(yùn)輸問(wèn)題的神經(jīng)網(wǎng)絡(luò)解法[J].計(jì)算機(jī)應(yīng)用研究,2001(11):16-18.

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

[11] 俞武揚(yáng). 多式聯(lián)運(yùn)運(yùn)輸問(wèn)題的混合遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用, 2009,45(33):10-12.

[12] 李躍光, 張遠(yuǎn)平. 一種改進(jìn)的蟻群算法在垃圾運(yùn)輸問(wèn)題中的應(yīng)用[J].湖南師范大學(xué)自然科學(xué)學(xué)報(bào),2010,33(2):18-23.

[13] 齊二石. 物流工程[M]. 機(jī)械工業(yè)出版社,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。河南省教育廳科學(xué)技術(shù)研究項(xiàng)目(12B120005)；河南理工大學(xué)博士基金項(xiàng)目(B2011-088)。曾強(qiáng)，副教授，主研領(lǐng)域：工業(yè)工程。鄧敬源，碩士生。袁明明，碩士生。

TP391 C93-03

A

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