石磊昊

(中國人民解放軍陸軍特種作戰(zhàn)學(xué)院 軍政基礎(chǔ)系，廣西 桂林 541002)

0 引言

運輸問題對于提高線性規(guī)劃問題解決實際問題的能力以及軍事運輸問題的實際規(guī)劃都有十分重要的意義[1]。在運輸問題的求解過程中，最優(yōu)性檢驗是實現(xiàn)優(yōu)化的重要依據(jù)，因此，運輸問題最優(yōu)性檢驗的理解對于學(xué)習(xí)和掌握運輸問題至關(guān)重要[2]。

1 運輸問題及其最優(yōu)性檢驗

圖1 運輸問題概念模型 Fig.1 Conceptual model of transportation problem

在軍事運籌學(xué)中，運輸問題泛指在調(diào)撥運輸各類物資(如武器彈藥)的實際活動中，根據(jù)現(xiàn)有交通情況，制訂合理的運輸方案，使總的運輸代價最小的一類問題[3]。一般運輸問題包含多個產(chǎn)地和多個銷售地，其概念模型可用圖1表示。在運輸問題中，根據(jù)產(chǎn)地供應(yīng)量和銷售地需求量之間的關(guān)系，可以分為“供求平衡的運輸問題”(以下簡稱“平衡的運輸問題”)和“供求不平衡的運輸問題”(以下簡稱“不平衡的運輸問題”)。

1.1 運輸問題的數(shù)學(xué)模型

在運輸問題的實際解決過程中，由于不平衡的運輸問題都可以轉(zhuǎn)化為平衡的運輸問題進(jìn)行解決，因此，本文僅以平衡的運輸問題為研究對象。

對于平衡的運輸問題，其數(shù)學(xué)模型可以表示為

(1)

其中，xij表示從產(chǎn)地i至銷售地j的運輸量，cij表示從產(chǎn)地i至銷售地j的運輸單價。

1.2 運輸問題的最優(yōu)性檢驗

一般運輸問題的求解過程也屬于線性規(guī)劃問題，因此其采用的是線性規(guī)劃問題的基本思想：單純形法。但由于平衡運輸問題系數(shù)矩陣的特殊性，對單純形法進(jìn)行了一定程度上的簡化，即表上作業(yè)法[4]，包含的主要過程有[5]：①尋找初始運輸方案。尋找初始運輸方案即根據(jù)實際運輸問題找到一個最初的、可行的運輸方案，根據(jù)單純形法的思想，即尋找該運輸問題的初始可行解。常用的尋找初始運輸方案的方法為最小元素法，這里不再贅述。②最優(yōu)性檢驗。最優(yōu)性檢驗即對上一過程中尋找到的初始運輸方案進(jìn)行檢驗，判斷其是否為該運輸問題的最優(yōu)解。常用的最優(yōu)性檢驗方法有閉合回路法和位勢法，閉合回路法的思想已有學(xué)者進(jìn)行了研究，即對該方案中無運輸量的線路增加運量，如果費用減少，則該方案不是最優(yōu)方案，反之則為最優(yōu)方案；位勢法在現(xiàn)有的文獻(xiàn)中均采用對偶變量的概念進(jìn)行解釋。③運輸方案的改進(jìn)。改進(jìn)運輸方案即根據(jù)最優(yōu)性檢驗的結(jié)果，如果方案為最優(yōu)方案，則無需改進(jìn)，如果非最優(yōu)結(jié)果，則需要對方案進(jìn)行改進(jìn)，以此類推，直至方案最優(yōu)。

以上3個步驟中，尋找初始運輸方案以及運輸方案的改進(jìn)研究較為成熟，而最優(yōu)性檢驗過程中所采用的位勢法在現(xiàn)有的文獻(xiàn)中均采用對偶變量的概念進(jìn)行解釋，沒有類似于閉合回路法中對實際經(jīng)濟(jì)意義原理的闡述，造成了學(xué)習(xí)和理解中的困難。

2 最優(yōu)性檢驗位勢法的剖析及其經(jīng)濟(jì)意義

2.1 運輸問題最優(yōu)性檢驗的位勢法

位勢法又稱為對偶變量法，根據(jù)對偶定理，式(1)的對偶模型可以表示為[6]

(2)

其中，ui和vj為運輸問題的對偶變量[7]。

根據(jù)線性規(guī)劃的單純形法，對上述運輸問題進(jìn)行單純形法的求解時，非基變量的檢驗數(shù)可以表示為

?ij=cij-(ui+vj) 。

(3)

由單純形法的基本思想可知，在求解線性規(guī)劃問題時，對運輸問題中有運量的線路來說，其變量檢驗數(shù)為0，表示為

?ij=cij-(ui+vj)=0，i,j∈N。

(4)

對于非基變量來說，其檢驗數(shù)表示為

?ij=cij-(ui+vj)，i,j∈N。

(5)

根據(jù)運輸問題的模型(1)可知，其目標(biāo)函數(shù)為求最小運費，即求最小值，因而非基變量檢驗數(shù)在取得最優(yōu)值時應(yīng)該大于0，即

?ij=cij-(ui+vj)>0，i,j∈N。

(6)

可以推得

ui+vj

(7)

式(7)的直觀解釋為，當(dāng)運輸問題取得最優(yōu)方案時，在沒有運量的線路上，對偶變量之和應(yīng)小于該線路上的運輸單價。

2.2 對偶變量的經(jīng)濟(jì)意義解釋

在運輸問題的對偶模型中，ui和vj為運輸問題的對偶變量，而在運輸問題的表格法中，ui和vj則分別表示產(chǎn)地i和銷售地j的“位勢”。

“位勢”一詞最早源于物理學(xué)[8]，1687 年牛頓在其巨著《自然哲學(xué)的數(shù)學(xué)原理》一書中的萬有引力定律中提出了位勢的概念，即位勢是一個包含空間概念，隨著測度點距離物體的遠(yuǎn)近而發(fā)生變化的物理量；同時位勢還受物體本身質(zhì)量大小的影響，在相同的距離下，質(zhì)量大的物體其位勢高[9]。 在運輸問題中，位勢可以結(jié)合運輸問題的主要參數(shù)，即“價格”或者“價值”，可以理解為運輸貨物在不同地點的“價值”。因此，本文將“運輸位勢”界定為在運輸問題中，商品在不同產(chǎn)地或銷售地的價值大小。結(jié)合前文對“運輸位勢”的定義，在運輸問題對偶模型中，ui和vj即分別表示產(chǎn)地i和銷售地j的商品價值。由于在金融界，商品價值可以為負(fù)值，因此ui和vj的取值范圍是無約束的，這也與運輸問題對偶模型式(2)中的約束條件是一致的。

2.3 運輸位勢基礎(chǔ)上的最優(yōu)性檢驗原理

前文分析了對偶變量的經(jīng)濟(jì)意義，即運輸位勢。因此，最優(yōu)性檢驗的檢驗數(shù)可以理解為利用兩地之間的價值之差與運輸價格進(jìn)行比較，現(xiàn)舉例說明最優(yōu)性檢驗的原理。

在一個由3個產(chǎn)地和4個銷售地組成的運輸問題中，運輸單價見表1。通過最小元素法進(jìn)行初始方案求解時，可得以下初始方案(表2)，則以位勢法進(jìn)行最優(yōu)性檢驗時，各個產(chǎn)地的位勢ui和各個銷售地的位勢vj分別在表格的最后一列和最后一行表示。

表1 運輸問題運價表 Tab.1 Tariff of transportation problem

表2 初始方案及位勢表 Tab.2 Initial scheme and potential table

以從產(chǎn)地A2到銷售地B2線路為例，該線路所對應(yīng)的非基變量檢驗數(shù)為

?22=c22-(u2+v2)=9-(-1+9)=1。

(8)

式(8)說明，若廠家選擇由A2購買1單位該貨物時，所需支出費用為1個單位，運輸?shù)戒N售地B2所需運費為 9個單位，在B2銷售地進(jìn)行銷售時，所獲得收益為9個單位，因此其運費大于收益，則該線路上沒有運輸量，即其檢驗數(shù)為正。

由于在運輸問題中，非基變量所對應(yīng)的線路上運輸量為0，則若所有非基變量所對應(yīng)的線路檢驗數(shù)均大于0，則說明這些沒有運輸量的線路上的運價均大于收益。若在這些線路上增加運量，則收益將會減小，因此，非基變量檢驗數(shù)均大于0的運輸方案無需調(diào)整，即為最優(yōu)方案。

3 結(jié)論

運輸問題最優(yōu)性檢驗經(jīng)濟(jì)意義的剖析，對于掌握和理解運輸問題的具體方法具有極大的促進(jìn)作用。本文通過對運輸問題對偶模型及對偶變量的分析，創(chuàng)新性地提出了“運輸位勢”的概念，給運輸問題對偶變量賦予了實際的經(jīng)濟(jì)學(xué)含義，對運輸問題的教學(xué)具有重要的促進(jìn)意義。