運輸問題

現已發現的運輸型問題有以下6類：

如把產地稱為源（發點），銷地稱為匯(收點)，則任務分配問題、生產計劃問題等運輸型問題的模型也可以歸納成類似上述形式。本詞條的運輸問題指的是一般類型的運輸問題。 ^[1] 

運輸問題的典型情況是研究單一品種物質的運輸調度問題：設某種物品有m個產地A₁，A₂，···，A_m，各產地的產量分別是a₁，a₂，···，a_m；有n個銷地B₁，B₂，···，B_n，各個銷地的銷量分別為b₁，b₂，···，b_n。假定從產地Ai(i=1,2,···,m)向銷地Bj(j=1,2,···,n)運輸單位物品的運價為c_ij，問怎麼調運這些物品才能使總運費最小？

產銷平衡運輸問題的數學模型可表示如下：

式中min表示求極小值，因為目標函數表示運輸總費用，要求其極小化，S.T.表示“約束條件為”。約束條件中前m行的意義是由某一個產地A_i運往各個銷地的物品數量x_ij之和等於該產地的產量a_i，後n行的意義是由某一個產地B_j運往各個銷地的物品數量x_ij之和等於該銷地的銷量b_i，最後一行表示變量非負約束，因為物品為負數無意義。

如果運輸問題的總產量等於總銷量，即有

當ɑi，bj滿足此條件時稱為產銷平衡的運輸問題，否則稱為產銷不平衡的運輸問題。產銷不平衡的運輸問題可以通過增加假想產地或假想銷地，化成產銷平衡的運輸問題。

以上模型是一種線性規劃模型，單純形法師求解線性規劃問題十分有效的一般方法，因而單純形法也可以求解運輸問題。但是採用線性規劃的單純形法求解運輸問題時，先得在每個約束條件中引入一個人工變量，即使求解3個產地，4個銷地(m=3,n=4)這樣的簡單運輸問題，在不考慮去掉多餘約束條件的情況下，變量數目也會達到19個之多，因而需要尋求更簡便的解法。

將約束條件的結構加以整理，可知運輸模型約束方程組的係數矩陣具有下述比較鬆散且特殊的形式：

其係數列向量的結構式：A_ij=(0,···,0,1（第i個）,0,···,0,1（第m+j個）,0,···,0)^T，即除第i個和第(m+j)個分量為1外，其他分量全等於0。這是(m+n)×mn的矩陣，每一列的元素中只有2個1，其餘均為0。可以證明A的秩=(m+n－1)，所以運輸問題的任一基本可行解都有(m+n-1)個基變量，這(m+n-1)個基變量的值就對應一個調運方案。

由此可知，運輸問題的約束條件具有下述特點：

對產銷平衡運輸問題，除上述兩個特點外，還有以下特點：

對產銷平衡的運輸問題，可以找到一個可行解：其變量

是運輸問題的一個可行解，其中，

，目標函數有下界0，目標函數值不會趨於

。由此可知，運輸問題必存在有限最優解。

這是有多個產地供應多個銷地的單一品種物資運輸問題。為直觀清楚起見，可列出該問題的運輸表，如下表所示。

表中的變量x_ij(i=1,2,···,m;j=1,2,···,m)為產地A_i運往銷地B_j的物品數量，c_ij為A_i到B_j的單位運價。有時，僅簡單地將單位運價單獨列入另一個表中，稱其為運價表，如下表所示。 ^[2] 

根據運輸問題的數學模型求出的運輸問題的解X=(x_ij)，代表着一個運輸方案，其中每一個變量x_ij的值表示由A_i調運數量為x_ij的物品給B_j。前已指出運輸問題是一種線性規劃問題，可設想用迭代法進行求解，即先找出它的某一個基可行解，在進行解的最優性檢驗，若它不是最優解，就進行迭代調整，以得到一個新的更好的解，繼續檢驗和調整改進，直到得到最優解為止。

為了能按照上述思路求解運輸問題，要求每步得到的解X=(x_ij)都必須是其基可行解，這意味着：

當採用一般單純形法求解運輸問題時，應去掉一個多餘的約束等式，任何一個約束等式均可。但運輸問題是的特殊性，人們將單純性法簡化用表格來處理，採用表上作業法求解時，因為在運輸表上進行，不必寫出上述的數學模型。

運輸問題解的每一個分量，都唯一對應其運輸表中的一個格。得出運輸問題的一個基可行解後，就將即便基變量的值x_ij填入運輸表相應的格子(A_i,B_j)內，並將這種格子稱為填有數字的格，含填數字0的格，這時的解為退化解，退化需要補0；對非基變量對應的格不填入數字，稱為空格。

表上作業法是求解運輸問題的一種簡便而有效的方法，其求解工作在運輸表上進行，它是一種迭代法，可以滿足上述的要求，迭代步驟為：先按照某種規則找出一個初始調運方案；再對現行解做最優性判別；若這個解不是最優解，就在運輸表上對它進行調整改進，得出一個新的解；再判別，再改進；直到得到運輸問題的最優解為止。 ^[3] 

表上作業法的第一步就是找出一個初始解，初始基本可行解的求法介紹三種。

西北角法，它的基本思想是給運輸表中左上角的變量分配運輸量以確定產銷關係。

最小元素法，或最小成本法。它的基本思想是就近供應，即從運輸表中運價最小的格子開始分配運輸量以確定產銷關係。

又稱沃格爾近似法，簡稱VAM法。它是從運輸表中各行和各列的最小元素和次小元素的差額來確定產銷關係。

得到了運輸問題的初始基可行解之後，即對應這個解進行最優性判別，看它是不是最優解。改進初始基本可行解有兩種最常用的方法：閉迴路法和對偶變量法（位勢法）。

這種方法需要對每一個空格尋找一條閉迴路，並根據閉迴路求出每個空格的檢驗數。當運輸問題中m和n較大時，計算檢驗數的工作量很大。

或乘數法。先對初始調運方案求出位勢，然後求各空格的檢驗數。當所有的檢驗數均為非負時，就得到最優方案。如果出現負的檢驗數，則從檢驗數為負的空格出發，作閉迴路，重新計算檢驗數，作進一步調整。用位勢法求檢驗數就是對偶問題的表上作業法。