基于表上作業法的運輸問題研究

文/陳子書，桂林理工大學

1 產銷平衡問題概述

近年來，現代物流在中國發展迅速。據統計，目前，我國已有20多個省市和50多個經濟中心城市制定了物流發展規劃。這些地區通過發展現代物流，促進了增長方式的轉變，提高了企業和區域經濟的競爭力。現代物流在結構調整，產業升級和經濟社會發展中發揮著越來越重要的作用[2]。在社會和經濟生活中，散裝材料從原產地轉移到銷售地點是一個普遍的問題。特殊企業生產的成品交付需要根據現有的交通網絡圖和車輛的具體里程調整費。來自不同生產地點的相同材料被轉移到各個銷售地點，從而使總運輸成本最小化并且效率最高。所謂的生產和銷售余額意味著在不同生產地點生產的產品與每個銷售地點所需的材料總量相同，然后確定從每個原產地到每個銷售地點的運費，以確定總運輸計劃以最小化總成本。這就是產銷平衡的問題。

2 問題提出

某公司在三個地方的分廠A1,A2,A3生產同一種產品,需要把產品運送到四個銷售點B1,B2,B3,B4去銷售。各分廠的產量、各銷地的銷量和各分廠運往各銷地每箱產品的運費(百元)如表1所示。問：問應如何調運,可使得總運輸費最小?

表2-1

3 問題分析

3.1 問題描述

圖表數據顯示銷量的總和為1200噸，產量總和為300+400+500=1200噸，,說明了此問題是一個產量等于總銷量的運輸問題（1200=1200）。該問題一方面要求滿足B1、B2、B3、B4四個銷售地的供貨需求，而另一方面又要考慮A1、A2、A3三個產地的運往銷售地的運輸費用，此外問題不但要求滿足銷售地分配要足，與此同時，我們還必須確保最大限度地降低運輸成本。這里選擇何種分配方案，將涉及不同的運輸費用，所以其是一個典型的線性規劃問題，同時也是一個總產量等于總銷量的產銷平衡運輸問題。

根據題目已知可以得出以下圖論：

圖3-1

3.2 產銷平衡運輸問題模型建立

假設A1、A2、…、Am表示某物品的m個產地，各產地的產量是s1、s2、…、sm； B1、B2、…、Bn表示某物品的n個銷地，各銷售地銷量分別為d1、d2、…、dn；假定從產地Ai（i=1,2，…，m）向銷售地Bj（j=1，2，…，n）運價單位物品的運價是cij，問這樣調運這些物品才能使運費最少？

設 xij為從產地Ai運往銷地Bj的運輸量，若各產地產量等于各銷地銷量之和，即有：

?

?

則得到下列產銷平衡運輸量問題的模型[3]：

其中，約束條件右側常數si和dj，約束條件最多有m+n-1個有效，即最多有m+n-1個基可行解。

3.3 求解方法

針對該運輸問題，為了方便計算，可設B1、B2、B3和B4四個城市銷售量為x11、x12、x13、x14、x21、x22、x23、x24、x31、x32、x33、x34。Cij為從產地Ai（i=1,2，…，m）向銷售地Bj（j=1，2，…，n）運價單位物品的運價，xij為從產地Ai（i=1,2，…，m）運往銷地Bj（j=1，2，…，n）的運輸量。Z即為整個運輸過程涉及的運輸費用。MinZ則為該運輸問題中的最小費用。

3.3.1 線性規劃

目標（Theobjective）

最少費用：

3.3.2 表上作業法

步驟一：按某種規則找出一個初始基可行解。規則主要為西北角法與最小元素法。西北角法：西北角法是從西北角（左上角）格開始，在格內的右下角標上允許取得的最大數，然后按行（列）標下一格的數；若某行（列）的產量（銷量）已滿足，則把該行（列）的其他格劃去，如此進行下去，直至得到一個基本可行解的方法；最小元素法：最小元素法是找出運價表中最小的元素，再重復類似于西北角法一樣的步驟。本文采用的是最小元素法。

步驟二：對進行解作最有判斷，即求個非基變量的檢驗數，是否均大于等于零，若是，則是最優解；若否，則不是。如果已經是最優解，則停止計算；如果不是最優解，則進行下一步驟。

步驟三：在表上對初始方案進行改進，找出新的基可行解，再按照步驟二進行判別，直至找出最優解。

圖3-2[4]

本題表上作業法具體求解如下：

表3-3

步驟一：從表4-3中運費最小（C21=10）的變量開始，給x21盡可能大的數值，A2產地產量等于B1銷量（400=400），故在表4-3的（A2，B1）交叉格填上400，由于A2產地產量、B1銷地銷量已經飽和，故劃去表4-3中的A2行與B1列得表4-4。

表3-4

步驟二：從表4-4中找出最小運價為17，故首先考慮此項，由于A1產地產量大于B2銷量（300＞250），故可以滿足其250噸銷量，在表4-3的（A1，B2）交叉格填上250，A1的產量變成50，并劃去B 2列，得到表4-5。

表3-5

步驟三：從表4-5中找出最小運價為20，故首先考慮此項，由于A3產地產量大于B3銷量（500＞350），故可以滿足其350噸銷量，故在表2的（A3，B3）交叉格填上350，A3的產量變為150，由于B4銷量已經飽和，故劃去表4-3中的B3列得表4-6。

表3-6

步驟四：由于A1與A3的產量相加為200噸（50+150=200）,B4的銷量為200，故可以兩兩對應，在表4-3的（A1，B4）交叉格填上50，在表2的（A3，B4）交叉格填上150，由于A1、A2產地產量已經飽和，故劃去表4-3中的A1、A3行。

由于此時表中已沒有數據可以劃去，因此已完成。經以上步驟得到一個總產量等于總銷量，且銷量全部滿足的調配方案。

表3-7

經計算，最小費用為198萬元。

3.3.3 R語言求解模型

3.3.3.1 程序腳本

3.3.3.2 運行結果

圖3-4

由此可看出運費最少為198萬元。

4 結果分析

從計算結果可以得出（以第一個最優解為例），A1分別銷往B、B2、B3和B4四個地方銷售量為分別為0臺、250臺、0臺、50臺；A2分別銷往B1、B2、廣B3和B4四個地方銷售量為別為40 0臺、0臺、0臺、0臺；A3分別銷往B1、B2、B3和B4四個地方銷售量為分別為0臺、0臺、350臺、150臺；總費用為198萬元。

通過兩個求解法最終得出的結果加以比較分析，無論是表上作業法還是R語言求解法，求解出來的結果都是相同的。

5 總結

對于平衡問題，首先建立相關數學模型，再運用表上作業法進行解決。如果是產銷不平衡運輸問題，應該先將其轉化為平衡問題，再運用產銷平衡問題的相關解決方法進行分析。供過于求，為使其轉化為產銷平衡，則需虛擬一銷地；若出現供不應求，則需要虛擬一產地，將其轉化為產銷平衡。

以運籌學中的表上作業法求初始基可行解，位勢法對最優解進行判定，閉回路調整法對解進行改進為基礎，此方法對實際工作的決策有著重要意義，對以后關于運輸相關方案的解決起到借鑒作用。掌握運輸問題的模型以及求解方法，這對解決諸多問題有非常大的幫助；如：調撥問題，供銷問題，以及合理的造船問題和船舶的調度問題等。我們應加快對運籌學相關知識的研究，更好地發展我國的物流運輸領域。