基于表上作業(yè)法的運(yùn)輸問題研究

文/陳子書，桂林理工大學(xué)

1 產(chǎn)銷平衡問題概述

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

2 問題提出

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

表2-1

3 問題分析

3.1 問題描述

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

根據(jù)題目已知可以得出以下圖論：

圖3-1

3.2 產(chǎn)銷平衡運(yùn)輸問題模型建立

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

設(shè) xij為從產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)輸量，若各產(chǎn)地產(chǎn)量等于各銷地銷量之和，即有：

?

?

則得到下列產(chǎn)銷平衡運(yùn)輸量問題的模型[3]：

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

3.3 求解方法

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

3.3.1 線性規(guī)劃

目標(biāo)（Theobjective）

最少費(fèi)用：

3.3.2 表上作業(yè)法

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

步驟二：對進(jìn)行解作最有判斷，即求個非基變量的檢驗(yàn)數(shù)，是否均大于等于零，若是，則是最優(yōu)解；若否，則不是。如果已經(jīng)是最優(yōu)解，則停止計(jì)算；如果不是最優(yōu)解，則進(jìn)行下一步驟。

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

圖3-2[4]

本題表上作業(yè)法具體求解如下：

表3-3

步驟一：從表4-3中運(yùn)費(fèi)最?。–21=10）的變量開始，給x21盡可能大的數(shù)值，A2產(chǎn)地產(chǎn)量等于B1銷量（400=400），故在表4-3的（A2，B1）交叉格填上400，由于A2產(chǎn)地產(chǎn)量、B1銷地銷量已經(jīng)飽和，故劃去表4-3中的A2行與B1列得表4-4。

表3-4

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

表3-5

步驟三：從表4-5中找出最小運(yùn)價為20，故首先考慮此項(xiàng)，由于A3產(chǎn)地產(chǎn)量大于B3銷量（500＞350），故可以滿足其350噸銷量，故在表2的（A3，B3）交叉格填上350，A3的產(chǎn)量變?yōu)?50，由于B4銷量已經(jīng)飽和，故劃去表4-3中的B3列得表4-6。

表3-6

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

由于此時表中已沒有數(shù)據(jù)可以劃去，因此已完成。經(jīng)以上步驟得到一個總產(chǎn)量等于總銷量，且銷量全部滿足的調(diào)配方案。

表3-7

經(jīng)計(jì)算，最小費(fèi)用為198萬元。

3.3.3 R語言求解模型

3.3.3.1 程序腳本

3.3.3.2 運(yùn)行結(jié)果

圖3-4

由此可看出運(yùn)費(fèi)最少為198萬元。

4 結(jié)果分析

從計(jì)算結(jié)果可以得出（以第一個最優(yōu)解為例），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臺；總費(fèi)用為198萬元。

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

5 總結(jié)

對于平衡問題，首先建立相關(guān)數(shù)學(xué)模型，再運(yùn)用表上作業(yè)法進(jìn)行解決。如果是產(chǎn)銷不平衡運(yùn)輸問題，應(yīng)該先將其轉(zhuǎn)化為平衡問題，再運(yùn)用產(chǎn)銷平衡問題的相關(guān)解決方法進(jìn)行分析。供過于求，為使其轉(zhuǎn)化為產(chǎn)銷平衡，則需虛擬一銷地；若出現(xiàn)供不應(yīng)求，則需要虛擬一產(chǎn)地，將其轉(zhuǎn)化為產(chǎn)銷平衡。

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