運輸問題最小元素法的一個原則

史書慧

(沈陽工程學(xué)院 基礎(chǔ)部，遼寧 沈陽 110036)

?

運輸問題最小元素法的一個原則

史書慧

(沈陽工程學(xué)院 基礎(chǔ)部，遼寧 沈陽 110036)

表上作業(yè)法是簡單有效的求解運輸問題的算法，而初始方案的確定對表上作業(yè)法尤為重要。對此提出了使用最小元素法的一個原則，利用該原則可以避免可能存在的多余計算過程，從而減少調(diào)整次數(shù)。利用實際算例驗證了所提出方法的正確性和有效性，并得到最小元素法求初始解的兩個結(jié)論。

運輸問題;初始方案;最小元素法

此外，產(chǎn)銷不平衡的運輸問題也可以轉(zhuǎn)化為產(chǎn)銷平衡問題[1-2]。關(guān)于運輸問題，現(xiàn)在廣為使用的方法是表上作業(yè)法[3]，對于表上作業(yè)法的研究和改進已經(jīng)引起了眾多學(xué)者的興趣[4-12]。用表上作業(yè)法求解運輸問題時，需要首先給出一個初始方案，這個初始方案的選取很大程度上決定了后續(xù)檢驗、調(diào)整等循環(huán)步驟的次數(shù)，即而決定了得到最優(yōu)解的時間[4]。因此如何確定初始方案才能盡可能地減少迭代次數(shù)正是需要探討的問題。

1 最小元素法使用原則

常見的初始方案求法有西北角法(或左上角法)、最小元素法和Vogel法。一般地，Vogel法求得的初始基可行解質(zhì)量最好，最小元素法次之，左上角法最差[5]。最小元素法簡便易行，但求得的初始基可行解與最優(yōu)解的接近程度不及Vogel法。Vogel法得到的初始方案最接近最優(yōu)解，但每次均需計算各行各列最小元素與次小元素之差，某種程度上增加了計算工作量。經(jīng)典最小元素法是確定單位運價表中的最小元素，建立供銷關(guān)系(即填上盡可能大的數(shù))，當同時存在兩個或兩個以上的相同最小元素時，任選其中一個最小元素，這樣任意選擇可能使迭代次數(shù)增加，計算繁瑣。綜合分析后，給出了這樣一個處理原則：若相同最小元素存在于一列(行)上，則需要分別計算其所在行(列)中與次小元素的差額，并確定最大的差額，再按最大差額所在行(列)的最小元素建立供銷關(guān)系，劃掉已滿足要求的行或列；若該最小元素所在行或列的產(chǎn)量和銷量相等時，則需要同時劃掉對應(yīng)的一行或一列，這時在對應(yīng)劃掉的一行或一列的一個空格處補0。對未劃去的行或列重復(fù)上述步驟，直到得到一個初始解。

2 實例分析

已知某運輸問題的產(chǎn)銷地供應(yīng)量與單位運價，如表1所示，試用表上作業(yè)法求其最優(yōu)解。

表1 某運輸問題的產(chǎn)銷地供應(yīng)量與單位運價

方法一：用最小元素法求初始可行解可按下述步驟進行：

Step 1：按照最小元素1進行調(diào)運，在初始方案表2中(A1，B3)處填寫4，劃去A1行；

Step 2：未劃去的元素中最小元素為3，分別在(A3，B2)和(A3，B4)處，這時應(yīng)用提出的原則，分別計算第2列和第4列中最小元素與次小元素的差額，按最大差額6所在的第2列的最小元素3調(diào)運，在表2中(A3，B2)處填寫10，劃去B2列；

Step 3：未劃去的元素中最小元素為3，在(A3，B4)處，則A3給B4供應(yīng)，在表2中(A3，B4)處填15，劃去B4列；

Step 4：未劃去的元素中最小元素為4，分別在(A2，B3)和(A3，B3)處，這時應(yīng)用提出的原則，分別計算第2行和第3行中最小元素與次小元素的差額，按最大差額2所在的第2行的最小元素4調(diào)運，在表2中(A2，B3)處填16，劃去B3列；

Step 5：未劃去的元素中最小元素為5，在(A3，B1)處，則A3給B1供應(yīng)，在表2中(A3，B1)處填1，劃去A3行；

Step 6：未劃去的元素中最小元素為6，在(A2，B1)處，則A2給B1供應(yīng)，在表2中(A2，B1)處填9，得到初始可行解，相應(yīng)的總運費 ；

Step 7：用位勢法檢驗，所得結(jié)果如表3所示；

Step 8：表3中括號里的數(shù)即為檢驗數(shù)，因為所有的檢驗數(shù)都大于或等于零，所以表2中給出的初始調(diào)運方案即為最優(yōu)方案，最小運費為202。

表2 按照最小元素1進行調(diào)運的初始方案

表3 位勢法檢驗方法一的結(jié)果

如果在出現(xiàn)兩個或兩個以上相同最小元素時，不采用所提出的準則進行調(diào)運，即按照傳統(tǒng)的最小元素法(任選其一)求解，則會出現(xiàn)以下幾種結(jié)果。

方法二：如果選相同最小元素3時，先選(A3，B2)，再選(A3，B4)；選相同最小元素4時，先選(A3，B3)，再選(A2，B3)，所得到的初始方案如表4所示，總運費z=4×1+10×6+15×4+10×3+1×4+15×3=203。

表4 按方法二所得到的初始方案

表5 位勢法檢驗方法二的結(jié)果

用閉回路法調(diào)整，得新的調(diào)運方案，與表2中的方案相同，則再由方法一得到最優(yōu)方案。

方法三：如果選相同最小元素3時，先選(A3，B4)，再選(A3，B2)；選相同最小元素4時，先選(A3，B3)，再選(A2，B3)，則得到的初始方案與表4中的方案相同，再根據(jù)方法二能得到最優(yōu)方案。

由上述3種方法可知，當選多個相同最小元素之一時，得到的目標函數(shù)值可能不一樣，若按最小差額所在行(或列)的最小元素調(diào)運，則可能使調(diào)整次數(shù)增加。

方法四：如果選相同最小元素3時，先選(A3，B4)，再選(A3，B2)；選相同最小元素4時，先選(A2，B3)，則選不到(A3，B3)，得到初始方案與表2中的方案相同，再根據(jù)方法一能得到最優(yōu)方案。

對比方法一和方法四(或方法二、方法三)可知，若有多個相同最小元素時，無論先選哪一個，其他的都能被選到時，則得到的初始方案一樣。

3 結(jié) 論

最小元素法是求運輸問題初始可行解的一個較為簡便的方法，當同時存在多個相同最小元素時，任選其中一個可能使實際調(diào)整次數(shù)增加。 如果在遵循最小元素法的基本原理基礎(chǔ)上,按所提出的使用原則進行處理,會使迭代次數(shù)明顯減少,從而簡化計算工作量。

[1]運籌學(xué)教材編寫組.運籌學(xué)[M].北京：清華大學(xué)出版社，2005.

[2]胡運權(quán).運籌學(xué)基礎(chǔ)及應(yīng)用[M].第5版.北京：高等教育出版社，2014.

[3]韓偉一,張慶普.運輸問題表上作業(yè)法的一點注記[J].運籌與管理，2009，18(4)：7-9.

[4]劉大為，張方華.運輸問題表上作業(yè)法的改進[J].科技資訊，2008(12):248-249.

[5]劉曉嵐.表上作業(yè)法求解運輸問題的思考[J].山東省農(nóng)業(yè)管理干部學(xué)院學(xué)報,2009，23(6)：155-156.

[6]謝凡榮.產(chǎn)銷平衡運輸問題的表上作業(yè)法解法的一個注記[J].運籌與管理，2005，14(4)：44-46.

[7]郭秀英.論運輸問題表上作業(yè)法[M].科技與管理，2007(3)：33-35.

[8]耿 雪，段川會.改進的最小元素法及其在物資配送問題中的應(yīng)用[J].物流工程與管理，2010，32(6)： 108-111.

[9]王廣民，馬林茂，李蘭蘭.運籌學(xué)中運輸問題求解算法及其擴展研究[J].長江大學(xué)學(xué)報，2011，8(10)： 1-6.

[10]張曉瑾，劉海生.運輸問題的表上作業(yè)法中初始方案的優(yōu)化[J].華北科技學(xué)院學(xué)報，2014，11(6)： 73-79.

[11]段春香.論表上作業(yè)法與單純形法的一致性[J].懷化學(xué)院學(xué)報，2013，32(11)： 78-81.

[12]陳海偉，陶慶玲.表上作業(yè)法在有轉(zhuǎn)運的物資運輸問題中的應(yīng)用[J].河南教育學(xué)院學(xué)報，2012，21(2)： 20-23.

(責任編輯 張 凱 校對 佟金鍇)

A Principle on Minimum Element Method of Transportation Problem

SHI Shu-hui

(Department of Preparatory Course,Shenyang Institute of Engineering,Shenyang 110136,Liaoning Province)

The table-working method is a simple and efficient algorithm for solving transportation problems.The determination of the initial scheme for table-working method is particularly important.In this paper,a principle of minimum element method is presented,which can avoid the possibly existing redundant calculation and reduce the number of adjustments.An example is given to verify the correctness and validity of the proposed method,and two conclusions of the minimum element method are derived.

transportation problem；initial scheme；minimum element method

2015-01-13

史書慧(1983-)，女，遼寧鐵嶺人，講師，博士，主要從事運籌學(xué)與控制論方面的研究。

10.13888/j.cnki.jsie(ns).2015.03.022

O122

A

1673-1603(2015)03-0286-03