表上作業法

出自 MBA智库百科(https://wiki.mbalib.com/)

　　表上作業法是指用列表的方法求解線性規劃問題中運輸模型的計算方法。是線性規劃一種求解方法。當某些線性規劃問題採用圖上作業法難以進行直觀求解時，就可以將各元素列成相關表，作為初始方案，然後採用檢驗數來驗證這個方案，否則就要採用閉合迴路法、位勢法等方法進行調整，直至得到滿意的結果。這種列表求解方法就是表上作業法。

　　1、找出初始基本可行解（初始調運方案，一般m+n-1個數字格），用西北角法、最小元素法；

　　（1）西北角法：

　　從西北角（左上角）格開始，在格內的右下角標上允許取得的最大數。然後按行（列）標下一格的數。若某行（列）的產量（銷量）已滿足，則把該行（列）的其他格划去。如此進行下去，直至得到一個基本可行解。

　　（2）最小元素法：

　　從運價最小的格開始，在格內的右下角標上允許取得的最大數。然後按運價從小到大順序填數。若某行（列）的產量（銷量）已滿足，則把該行（列）的其他格划去。如此進行下去，直至得到一個基本可行解。

　　註:應用西北角法和最小元素法，每次填完數，都只划去一行或一列，只有最後一個元例外（同時划去一行和一列）。當填上一個數後行、列同時飽和時，也應任意划去一行（列），在保留的列（行）中沒被划去的格內標一個0。

　　2、求出各非基變數的檢驗數，判別是否達到最優解。如果是停止計算，否則轉入下一步，用位勢法計算；

　　運輸問題的約束條件共有m+n個，其中：m是產地產量的限制；n是銷地銷量的限制。其對偶問題也應有m+n個變數，據此：

　　σ_ij = c_ij − (u_i + v_j) ,其中前m個計為,前n個計為

　　由單純形法可知，基變數的σ_ij = 0

　　c_ij − (u_i + v_j) = 0因此u_i,v_j可以求出。

　　3、改進當前的基本可行解（確定換入、換出變數），用閉合迴路法調整；

　　（因為目標函數要求最小化）

　　表格中有調運量的地方為基變數，空格處為非基變數。基變數的檢驗數σ_ij = 0，非基變數的檢驗數。σ_ij < 0表示運費減少,σ_ij > 0表示運費增加。

　　4、重覆②，③，直到找到最優解為止。

　　1、無窮多最優解

　　產銷平衡的運輸問題必定存最優解。如果非基變數的σ_ij = 0，則該問題有無窮多最優解。

　　2、退化

　　表格中一般要有(m+n-1)個數字格。但有時，在分配運量時則需要同時划去一行和一列，這時需要補一個0，以保證有(m+n-1)個數字格。一般可在划去的行和列的任意空格處加一個0即可。

　　配送是物流系統的一項十分重要的功能。隨著物流行業的發展，物流公司迅速增加，各個物流公司之間的競爭日趨激烈。如何加強管理以減少成本問題成為各物流公司非常關註的話題。一般來說，配送中心數量減少，配送中心距離客戶的距離就會越長，配送成本就越高;配送中心數量增多，配送中心距離客戶的距離就會縮短，配送成本就越少，但是配送中心的管理成本隨之增加。本文討論利用現有的配送中心向客戶的配送問題，尋求最小的配送成本。

　　一、配送模型的建立與求解

　　 1.配送模型的建立。物流公司常常在某個地區有多個配送中心來供應貨物，每個物流中心都有一定的供應量。物流中心配送貨物的客戶也往往不止一個，多個客戶更為常見。a_i(i=1，2，3，…，m)表示不同的配送中心貨物供應量，m表示配送中心的數量。b_j(j=1，2，3,…n)表示不同客戶需求的貨物量，n表示量客戶的數量。從配送中心到客戶的單位配送價格用c_{ij}表示。這些數據可用表1來表示。

　　若用x_ij表示從a_i到b_j的實際供應量，那麼在供需平衡的條件下，要求得總運費最小的配送方案，可求解以下數學模型:

　　 2.表上作業法對模型的求解。利用一般的求解方法很難求得上述數學模型的解，但是根據運籌學的相關內容來求解就相當容易了。求解的步驟分三步:首先用最小元素法求出初始可行解，再採用閉合迴路法判斷是否最優，最後採用閉合迴路調整法調整變數直至最優解。

以最小單位配送價格運價開始配送，從單位配送價格最小到最大順序逐一使供需量平衡，配送中供需達到規定量的可以從表上劃掉。根據表上求得的結果可以得到最小的配送成本。最小元素法的缺點是:為了節省某一配送中心的費用，可能造成其他配送中心幾倍的配送成本，所以必須對上述的結果進行檢驗。

　　檢驗的方法採用閉合迴路法，即從表上任一個空格出發，沿水平或垂直方向前進，每遇到一個適當數字(有利於回到原空格)轉90°,繼續前進直到回到原空格。當所有檢驗數，則就是最優解，否則還需要繼續改進。 當有的空格檢驗數小於0時，說明此空格應當使用。改進的方法採用閉合迴路調整法，從檢驗數是負數的空格開始，沿閉迴路前進取數字的最小值，使用閉迴路轉角的數加減這個數。然後再次使用閉合迴路法檢驗所有空格的檢驗數，所有檢驗數大於0則就是最優解，否則再繼續改進，直至最優。

　　二、物流公司配送實例

　　 某物流公司給四個客戶甲、乙、丙和丁配送貨物，配送量分別為3噸、6噸、5噸和6噸。物流公司在該地區有三個配送中心，每個配送中心的貨物供應量分別為7噸、4噸和9噸。由於各個配送中心距離客戶的距離不一樣，所以配送貨物的單位價格也不同。需求量和供應量及價格數據如表2所示。其中價格單位為萬元/噸。

　　 1.最小元素法求出初始可行解。物流公司在配送貨物時，除了考慮準時、安全送達貨物以外，儘可能減少配送成本。首先以最小單位價格開始配送，從單位價格最小到最大順序逐一使供需平衡，配送中供需達到規定量的劃掉。從上表中找到最低配送單位價格為2.1萬元/噸，由於甲客戶需求量為3噸，物流中心2的供應量為4噸，取min{3 4}=3填入表中，甲客戶一欄需求量達到規定量，把甲客戶一欄划去，如表3所示。

　　再從表中未划去的價格中找到最小價格開始配送，這時最小的單位價格為2.2萬元/噸。由於丙客戶需求量為5噸，而物流中心2的供應量僅為4噸且已經配給甲客戶3噸，故配給丙客戶只能1噸，取min{5 1}=1填入表中，物流中心2一行供應量達到規定量，把物流中心2一行划去，如表4所示。

　　同理:按照上面的做法一直划下去，最後的結果如下表5所示。

　　最後可得到最小配送成本為:

　　Z_min=4×2.3+3×3.0+3×2.1+1×2.2＋6×2.4＋3×2.5 (萬元)。

　　2.閉合迴路法判斷最優解。上表中未填入數字的稱之為空格，需要計算所有空格的檢驗數，若檢驗數全部大於等於0，則上述填入的數字為最優解，否則不是最優解，需要進一步計算。 圖中的空格(11)閉合迴路，可採取空格(11)——空格(13)——空格(23)——空格(21)——空格(11)組成迴路。如下表6所示。

　　檢驗數：

　　同理,空格(12)、空格(22)、空格(24)、空格(31)和空格(33)的檢驗數分別為:K₁₂ = 0.2,K₂₂ = 0.1,K₂₄ = − 0.1,K₃₁ = 1和K₃₃ = 1.2。 空格檢驗數K₂₄ = − 0.1為負數，所以上述不是最優解。

　　3.閉合迴路調整法對上述變數進行調整。由於K₂₄ = − 0.1，故空格(24)必須要使用，先對(24)轉角進行調整。取轉角最小值min{1，3，4}=1填入空格(24)中，其空格(24)轉角值相應做出如下調整，如表7所示。

　　調整後的空格檢驗數如下：

　　 K₁₁ = 0,K₁₂ = 0.2,K₂₂ = 0.2,K₂₃ = 0.1,K₃₁ = 0.9,K₃₃ = 1.2

　　所有空格檢驗數均為正數，說明上表中的解為最優解。即，物流中心1給丙客戶配送5噸貨物，給丁客戶配送2噸貨物；物流公司2給甲客戶配送3噸貨物，給丁客戶配送1噸貨物。物流中心3給乙客戶配送6噸貨物，給丁客戶配送3噸貨物。此時物流公司的配送總成本最小。

　　Z_min=5×2.3＋2×3.0+3×2.1＋1×2.8＋6×2.4＋3×2.5(萬元)。

　　從計算結果可以看出，最優解比初始可行解總成本又降低了0.1萬元。

　　 通過建立物流配送模型，利用表上作業法解出最小配送成本，解決了降低配送中心的配送成本問題，提升了物流公司的市場競爭力。

• 圖上作業法