運輸問題表上作業(yè)法改進(jìn)思路研究論述

摘 要：運輸問題的表上作業(yè)法是求解運輸問題的重要方法，實質(zhì)是一種單純形法，其中，運輸問題的基本性質(zhì)對運輸問題表上作業(yè)法的改進(jìn)有著重要的意義。但是，在實際的表上作業(yè)法運作中對運輸問題的性質(zhì)分析不夠，經(jīng)過有關(guān)人員的分析，提出了最小元素法給出的初始方案是解決運輸問題的可行性操作，同時，也解決了運輸問題的退化情況。文章通過對運輸問題表作業(yè)法現(xiàn)狀的分析，對經(jīng)典表上作業(yè)法的闡釋，結(jié)合運輸問題的性質(zhì)，對運輸問題表上作業(yè)法求解初始解方法以及調(diào)運檢驗方案的調(diào)整兩個方面的改進(jìn)思路進(jìn)行研究。

關(guān)鍵詞：運輸問題；表上作業(yè)法；改進(jìn)思路

隨著我國經(jīng)濟(jì)的發(fā)展，物流業(yè)也得到了快速的發(fā)展，在我國經(jīng)濟(jì)活動中發(fā)揮了重要的作用。物流業(yè)的發(fā)展對交通運輸問題提出了更高的要求，在此情況下，運輸問題中引用了一門現(xiàn)代學(xué)科中的運籌學(xué)。運籌學(xué)是指利用數(shù)學(xué)的手段對所需要處理的問題進(jìn)行規(guī)劃和分析，最終實現(xiàn)對問題的最優(yōu)化解決。其中，應(yīng)用到運輸問題中的是運籌學(xué)中線性規(guī)劃方面的表上作業(yè)法。表上作業(yè)法是在一些線性規(guī)劃問題采用圖上作業(yè)難以直觀規(guī)劃的情況下，通過各元素的排列組成表格，并將表格作為一種初始方案，在此基礎(chǔ)上利用閉合回路法、位勢法獲取檢驗數(shù)來對方案檢驗，最終獲得最優(yōu)化的解決辦法。

1 運輸問題性質(zhì)、現(xiàn)狀及表上作業(yè)法現(xiàn)狀

1.1 運輸問題的性質(zhì)

運輸問題中的運輸表中行列、數(shù)列會隨著相異變量的延伸而進(jìn)行改變，變量序列之間形成了一種閉合路。運輸問題的系數(shù)矩陣及其增廣矩陣的秩均為m+n-1。其中，運輸問題中的變量列向的充要條件不包括閉合路。在對運輸問題求解時，主要采用最小元素法的原理，通過對初始方案的確定來實現(xiàn)可行解。

1.2 運輸問題研究現(xiàn)狀

隨著交通運輸事業(yè)的發(fā)展，物資配送問題的求解引起了有關(guān)人員的關(guān)注。運輸問題是一種特殊的線性規(guī)劃形式，在上個世紀(jì)四十年代的時候，蘇聯(lián)數(shù)學(xué)家提出了一種線性的運輸規(guī)劃方法，是一種基于線性約束的基礎(chǔ)上關(guān)于目標(biāo)函數(shù)極大、極小值的數(shù)學(xué)理論，具有非常重要的現(xiàn)實意義。運輸問題的規(guī)劃發(fā)生了由單目標(biāo)運輸向多目標(biāo)運輸?shù)霓D(zhuǎn)變，很多學(xué)者也相繼采取不同的算法來解決多目標(biāo)的優(yōu)化問題。國內(nèi)的運輸問題研究較晚，關(guān)鍵是研究是通過尋找最小讓步值來獲得目標(biāo)沖突的解決和優(yōu)化，將多目標(biāo)運輸問題轉(zhuǎn)為單目標(biāo)運輸問題，主要采用表上作業(yè)法的形式來進(jìn)行求解。

1.3 表上作業(yè)法研究現(xiàn)狀

表上作業(yè)法是指在平衡表中進(jìn)行求解，是一種經(jīng)典的求解單目標(biāo)運輸問題的較為成熟的求解方法，具有簡單、易操作的優(yōu)勢?，F(xiàn)階段的國內(nèi)表上作業(yè)法研究較少，因此，需要有關(guān)人員通過對運輸問題的分析，針對表上作業(yè)法效率的提高和改進(jìn)等方面，進(jìn)行方案的研究，從而提高運輸?shù)男省?/p>

2 經(jīng)典的運輸問題表上作業(yè)法原理

表上作業(yè)法是求解交通運輸問題的經(jīng)典算法，主要的步驟是將問題轉(zhuǎn)化在供求平衡表中來實現(xiàn)求解。首先要先確定初始解，然后按照一定規(guī)則進(jìn)行初始方案的調(diào)整和改進(jìn)得到新解，再對新解進(jìn)行改進(jìn)，直到尋求到最優(yōu)方案。

2.1 初始解

初始解的確定能夠影響后期方案的更迭，其簡單易行能夠減少方案的更迭，具有重要的現(xiàn)實意義。初始解的設(shè)定具體步驟如下：首先，在供需平衡表中選取單元格，令xij=min{ai，bj}使行或列在允許的范圍內(nèi)盡量飽和，即使一個約束方程得以滿足。之后調(diào)整橫列和數(shù)列的供應(yīng)量，當(dāng)ai=0時，刪掉相應(yīng)的行，bj=0時，刪掉相應(yīng)的列，在運輸量選定的時候?qū)崿F(xiàn)行、列的滿足，實現(xiàn)運輸問題的初始基本可行解。

2.2 求解初始解的方法

2.2.1 最小元素法。最小元素法是指在交通運輸?shù)奈锪髋渌椭?，實現(xiàn)每次配送路徑單位運價的最小化。通過找出運價表中的最小元素，在運量表內(nèi)填入允許范圍內(nèi)的最大數(shù)，如果某列的產(chǎn)量或者銷量已經(jīng)滿足，則要將該運價所在的行或者列劃去最小值，從而得到可行解的方法。

2.2.2 西北角法。西北角法是運籌學(xué)中制定運輸問題的求解初始解的基本方法之一，是指從運價表的西北角開始依次安排多個產(chǎn)地和多個銷售地之間的運輸業(yè)務(wù)，從而得到可行解的方法。西北角的運輸應(yīng)用遵循優(yōu)先安排運價表上標(biāo)號最小產(chǎn)地和銷售地之間的運輸原則。

2.2.3 伏格爾法。伏格爾法又叫做差值法，是指在不能按照最小運費供應(yīng)的產(chǎn)地進(jìn)行次小運費的使用，在運費之間的差額最大處進(jìn)行最小運費的調(diào)運。以差值法確定的初始方案作為解決運輸問題的最優(yōu)解，能夠有效減少迭代次數(shù)，從而削減不必要的計算工作量，甚至還會直接實現(xiàn)最優(yōu)解的目標(biāo)，但這種方法會造成為了節(jié)約某處的運費而無形中增大其他運費的弊端。

3 運輸問題表上作業(yè)法中求解初始法的改進(jìn)

求解初始解的方法中差值法是最實用的一種方法，能夠最快速度獲得最優(yōu)解的近似值，減少迭代次數(shù)，提高工作效率。但是差值法由于沒有實現(xiàn)和單位運價的聯(lián)系，不能每次都實現(xiàn)無需調(diào)運方案的調(diào)整直接獲得最優(yōu)解的近似值。因此，需要對運輸問題表上作業(yè)法中最為常用的求解初始法進(jìn)行改進(jìn)。比如在進(jìn)行變量的確定時不僅要考慮變量單位的絕對值，還要考慮變量的可調(diào)運量，在調(diào)配的開始階段要對中次小元素和最小元素之間的運費差進(jìn)行計算，然后在最大差額的行中以最小元素作為基本量，同時，可以不必對豎行進(jìn)行計算。

差值法中求解初始法的改進(jìn)要遵循以下幾方面的原則：首先，當(dāng)行列的元素可調(diào)運量大于等于最小元素的可調(diào)運量時，運費差要等于最小元素的可調(diào)運量和行列的元素以及最小元素運價差相乘的結(jié)果。其次，當(dāng)行列的元素可調(diào)運量小于最小元素的可調(diào)運量時，運費差通常要由兩部分組成。

4 運輸問題表上作業(yè)法中調(diào)運方案的檢驗調(diào)整

調(diào)運方案的檢驗是在運輸問題三種求解初始法可行解的基礎(chǔ)上經(jīng)過最優(yōu)性檢驗來進(jìn)一步對目標(biāo)函數(shù)值的判斷。通過這種檢驗?zāi)軌虬l(fā)現(xiàn)當(dāng)前方案是否實現(xiàn)了最優(yōu)，比如當(dāng)所有的檢驗數(shù)在大于等于零的時候就是獲得了檢驗的最優(yōu)解。常見的判斷最優(yōu)解的方法主要有閉回路法和位勢法兩種。閉回路法是指在平衡表中的一個空格和多個有數(shù)字格的用水平和垂直連線包圍而成的封閉回路。位勢法是將運價分解為行位勢量ui與列位勢量vj，再通過位勢量的計算得出檢驗數(shù)的檢驗方法。

閉回路法和位勢法在實際的運輸問題優(yōu)化調(diào)整中，都需要對空欄的檢驗數(shù)進(jìn)行計算，這種計算過程較為復(fù)雜，影響了實際應(yīng)用效果。因此，借助水往低處流的規(guī)律，提出了流水原理求解的運輸問題。流水原理求解解決了傳統(tǒng)閉回路法和位勢法求解中出現(xiàn)的退化問題，當(dāng)基本可行解的一個或者多個分量出現(xiàn)零時，可以采用加零的方法來解決退化問題。利用流水原理的可行解減少了不必要的檢驗數(shù)的計算，簡化了檢驗方法，優(yōu)化了調(diào)配的運輸問題，具有很重要的實際應(yīng)用價值。

5 結(jié)束語

運輸問題的表上作業(yè)法是一個較為簡便的計算方法，差值法的求解初始法雖然具有一定的現(xiàn)實意義，但是其使用也不能實現(xiàn)對最優(yōu)解的快速獲得，同時，傳統(tǒng)運輸問題的調(diào)運方案的檢驗也存在較為復(fù)雜的問題。因此，有關(guān)人員需要在不斷提升個人技能的基礎(chǔ)上加強(qiáng)對運輸問題表上作業(yè)法求解初始法和調(diào)運方案檢驗等方面的改進(jìn)，從而有效減少運輸問題表上作業(yè)法的工作量，實現(xiàn)運輸問題最優(yōu)解的快速獲得。

參考文獻(xiàn)

[1]李時椿.運輸問題表上作業(yè)法的改進(jìn)研究[J].南京航空航天大學(xué)學(xué)報，2000，3：324-329.

[2]蔣宏峰.運輸問題表上作業(yè)法的改進(jìn)[J].長沙大學(xué)學(xué)報，2002，2：47-48.

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

作者簡介：邢建平（1974，7-），女，出生湖南益陽人，碩士，湖南廣播電視大學(xué)副教授，研究方向：應(yīng)用數(shù)學(xué)。