陳海偉，陶慶玲

(商丘工學(xué)院管理學(xué)院，河南商丘 476000)

表上作業(yè)法在有轉(zhuǎn)運(yùn)的物資運(yùn)輸問(wèn)題中的應(yīng)用

陳海偉，陶慶玲

(商丘工學(xué)院管理學(xué)院，河南商丘 476000)

討論了產(chǎn)銷平衡運(yùn)輸問(wèn)題的表上作業(yè)法，利用Vogel法求初始方案，位勢(shì)法求檢驗(yàn)數(shù)，閉回路法對(duì)可行解進(jìn)行調(diào)整和改進(jìn).提出了帶有轉(zhuǎn)運(yùn)的物資運(yùn)輸問(wèn)題的求解方法，將所有產(chǎn)地、中間轉(zhuǎn)運(yùn)站、銷地都可以看做產(chǎn)地，又可看做銷地，把整個(gè)問(wèn)題當(dāng)做一個(gè)擴(kuò)大的運(yùn)輸問(wèn)題處理.

表上作業(yè)法;Vogel法;位勢(shì)法;檢驗(yàn)數(shù)

1 運(yùn)輸問(wèn)題的數(shù)學(xué)模型［1］

產(chǎn)銷平衡問(wèn)題的數(shù)學(xué)模型為

這是一個(gè)線性規(guī)劃問(wèn)題，可以用單純形法來(lái)求解運(yùn)輸問(wèn)題.如果用單純形法來(lái)解運(yùn)輸問(wèn)題，就要在每個(gè)約束條件中加入一個(gè)人工變量，即使對(duì)于m=3，n=4這樣如此簡(jiǎn)單的運(yùn)輸問(wèn)題，變量數(shù)目也有19個(gè)，運(yùn)算量非常大，因此一般使用簡(jiǎn)單有效的表上作業(yè)法.

2 表上作業(yè)法在運(yùn)輸問(wèn)題中的應(yīng)用

表上作業(yè)法的求解工作是在運(yùn)輸表上進(jìn)行的一種迭代法，迭代步驟為:先找出一個(gè)初始可行解，然后對(duì)初始可行解做最優(yōu)性檢驗(yàn)，如果不是最優(yōu)解，就在運(yùn)輸表上對(duì)它進(jìn)行調(diào)整和改進(jìn)，得到一個(gè)新的可行解，再進(jìn)行判別和改進(jìn)，直至得到最優(yōu)解為止.

2.1初始可行解的確定［2］

常用的初始可行解的確定方法有3種:西北角法、最小元素法和Vogel法.通常情況下，用Vogel法確定的初始解質(zhì)量最好，最接近最優(yōu)解，最小元素法次之，西北角法最差.所以常用Vogel法來(lái)確定初始可行解，步驟如下:

(1)計(jì)算運(yùn)輸表中每一行和每一列次小單位運(yùn)價(jià)和最小單位運(yùn)價(jià)之間的差值，稱之為相應(yīng)的行罰數(shù)和列罰數(shù)，圈出其中的最大罰數(shù);

(2)若同時(shí)出現(xiàn)兩個(gè)以上的最大罰數(shù)，則圈出其所在行或所在列的最小運(yùn)價(jià)為最小者的最大罰數(shù);

(3)根據(jù)最大罰數(shù)值的位置在運(yùn)輸表中的適當(dāng)格中填入一個(gè)盡可能大的運(yùn)輸量，并劃去相應(yīng)的一行或一列;

(4)當(dāng)運(yùn)輸問(wèn)題某部分的產(chǎn)量和銷量相等時(shí)，在運(yùn)輸表中相應(yīng)空格處填入運(yùn)量，需同時(shí)劃去運(yùn)輸表的一行和一列，這時(shí)最終運(yùn)輸表上的數(shù)字格就會(huì)小于m+n－1，為使迭代工作順利進(jìn)行，規(guī)定只能劃去一行(或一列)，在未被劃去的一行或一列的某個(gè)空格中填入數(shù)字0;

(5)重復(fù)以上步驟，從而得到一個(gè)初始可行解.

2.2 解的最優(yōu)性檢驗(yàn)

對(duì)初始可行解的最優(yōu)性檢驗(yàn)可仿照單純形法，求可行解的各非基變量的檢驗(yàn)數(shù).若有某空格(Ai，Bj)的檢驗(yàn)數(shù)σij為負(fù)，說(shuō)明將xij作為基變量會(huì)使總運(yùn)費(fèi)減少，故當(dāng)前解不是最優(yōu)解，需要調(diào)整.若所有空格的檢驗(yàn)數(shù)全部非負(fù)，則不管怎樣調(diào)整都不會(huì)使總的運(yùn)輸費(fèi)用降低，該可行解就是最優(yōu)解，所對(duì)應(yīng)的調(diào)運(yùn)方案為最優(yōu)方案.

求檢驗(yàn)數(shù)的常用方法有兩種:位勢(shì)法和閉回路法，其中利用位勢(shì)法求檢驗(yàn)數(shù)相對(duì)來(lái)說(shuō)運(yùn)算量比較小.根據(jù)線性規(guī)劃的對(duì)偶規(guī)劃矩陣描述，運(yùn)輸問(wèn)題xij的檢驗(yàn)數(shù)σij=cij－(ui+vj)，cij、ui、vj分別為xij所在空格的單位運(yùn)價(jià)及空格所在行的行位勢(shì)和所在列的列位勢(shì).對(duì)于運(yùn)輸問(wèn)題的一個(gè)初始可行解，其基變量是xi1j1，xi2j2，…，xisjs，s=m+n－1，得方程組

2.3 解的調(diào)整和改進(jìn)［3］

若經(jīng)過(guò)最優(yōu)性檢驗(yàn)，可行解不是最優(yōu)解，則需要進(jìn)一步改進(jìn).改進(jìn)的方法是在運(yùn)輸表中做出最小負(fù)檢驗(yàn)數(shù)對(duì)應(yīng)空格的閉回路Lij，在滿足約束條件的前提下，使xij盡可能增大并相應(yīng)調(diào)整閉回路上其他頂點(diǎn)處的運(yùn)量，得到一個(gè)更好的可行解.解調(diào)整改進(jìn)的步驟如下.

(1)在運(yùn)輸表中做出最小負(fù)檢驗(yàn)數(shù)δij對(duì)應(yīng)空格的閉回路; (2)以空格(Ai，Bj)為初始點(diǎn)，沿順時(shí)針?lè)较蛞来螌?duì)閉回路上的頂點(diǎn)進(jìn)行編號(hào);

(5)對(duì)得到的新可行解進(jìn)行最優(yōu)性檢驗(yàn)，如不是最優(yōu)解，重復(fù)以上步驟進(jìn)行調(diào)整和改進(jìn)，直到得出最優(yōu)解為止.

例1某公司從3個(gè)產(chǎn)地A1、A2、A3將物品運(yùn)往4個(gè)銷地B1、B2、B3、B4，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運(yùn)往各銷地每件物品的運(yùn)費(fèi)如表1所示，問(wèn)如何調(diào)運(yùn)，可使得總運(yùn)輸費(fèi)最低?

解(1)Vogel法求初始方案，見(jiàn)表2.

表1 運(yùn)輸費(fèi)用表Tab.1Transport freight list

表2 運(yùn)輸問(wèn)題的初始方案Tab.2Initial solution for transportation problem

(2)用位勢(shì)法求檢驗(yàn)數(shù)，見(jiàn)表3.

表3 檢驗(yàn)數(shù)Tab.3Test number

由表3可知，u1+v3=c13=3，u1+v4=c14=10，u2+v1=c21=1，u2+v4=c24=8，u3+v2=c32=4，u3+v4=c34=5，得

再用σij=cij－(ui+vj)求非基變量檢驗(yàn)數(shù)δ11=0，σ12=2，σ22=2，σ23=1，σ31=9，σ33=12.

所有的非基變量檢驗(yàn)數(shù)非負(fù)，所以方案最優(yōu).

3 有轉(zhuǎn)運(yùn)的運(yùn)輸問(wèn)題

在上述討論中，我們假定物品由產(chǎn)地直接運(yùn)到銷地，不經(jīng)中間轉(zhuǎn)運(yùn)，這是一種理想的情況，而實(shí)際上往往是先將物品由產(chǎn)地運(yùn)到某個(gè)中轉(zhuǎn)站(可以是另外的產(chǎn)地、銷地或中間轉(zhuǎn)運(yùn)倉(cāng)庫(kù))，然后再轉(zhuǎn)運(yùn)到銷售地.假定有m個(gè)產(chǎn)地A1，A2，…，Am，n個(gè)銷地B1，B2，…，Bn，產(chǎn)地和銷地都可以作為中轉(zhuǎn)站使用，物品的產(chǎn)地和銷地都有m+n個(gè)，這就成為一個(gè)擴(kuò)大了的運(yùn)輸問(wèn)題.定義以下符號(hào):ai為第i個(gè)產(chǎn)地的產(chǎn)量(凈供應(yīng)量)，bj為第j個(gè)銷地的銷量(凈需求量)，cij為由第i個(gè)發(fā)送地運(yùn)到第j個(gè)接收地的單位運(yùn)價(jià)，xij為由第i個(gè)發(fā)送地運(yùn)到第j個(gè)接收地的物品數(shù)量，ci為第i個(gè)地點(diǎn)轉(zhuǎn)運(yùn)單位物品的費(fèi)用.

將產(chǎn)地和銷地統(tǒng)一編號(hào)，并把產(chǎn)地排在前面，銷地排在后面，則有

例2已知各產(chǎn)地、銷地、中間轉(zhuǎn)運(yùn)站及相互之間每噸產(chǎn)品的運(yùn)價(jià)如表5所示，則在考慮產(chǎn)銷地之間直接運(yùn)輸和非直接運(yùn)輸各種可能方案的情況下，如何將3個(gè)廠每天生產(chǎn)的產(chǎn)品運(yùn)往銷售地，使總的運(yùn)費(fèi)最少.

表5 帶有轉(zhuǎn)運(yùn)運(yùn)輸問(wèn)題的運(yùn)輸表Tab.5The transport table of transportation problem with transshipment

解(1)由于問(wèn)題中所有產(chǎn)地、中間轉(zhuǎn)運(yùn)站、銷地都可以看做產(chǎn)地，又可看做銷地，因此把整個(gè)問(wèn)題當(dāng)做有11個(gè)產(chǎn)地和11個(gè)銷地的擴(kuò)大的運(yùn)輸問(wèn)題.

(2)對(duì)擴(kuò)大的運(yùn)輸問(wèn)題建立單位運(yùn)價(jià)表.將表中不可能出現(xiàn)的運(yùn)輸方案的運(yùn)價(jià)用任意大的正數(shù)M代替.

(3)所有中間轉(zhuǎn)運(yùn)站的產(chǎn)量等于銷量.運(yùn)費(fèi)最少時(shí)不可能出現(xiàn)一批物資來(lái)回倒運(yùn)的現(xiàn)象，所以每個(gè)轉(zhuǎn)運(yùn)站的轉(zhuǎn)運(yùn)數(shù)不超過(guò)20 t.

(4)規(guī)定T1，T2，T3，T4的產(chǎn)量和銷量均為20 t.

然后用表上作業(yè)法求解(見(jiàn)表6)即可.

表6 擴(kuò)大的運(yùn)輸問(wèn)題的單位運(yùn)價(jià)表Tab.6The unit price table of expanded transportation problem

［1］胡運(yùn)權(quán).運(yùn)籌學(xué)教程［M］.3版.北京:清華大學(xué)出版社，2007:80－94.

［2］謝凡榮.產(chǎn)銷平衡運(yùn)輸問(wèn)題的表上作業(yè)法解法的一個(gè)注記［J］.運(yùn)籌與管理，2005，14(4):44－46.

［3］何莉敏，李玉，于濤，等.Vogel法求解最大值問(wèn)題［J］.鄭州大學(xué)學(xué)報(bào):理學(xué)版，2011，43(1):26－28.

Application of Table Algorithm in the Cargoes Transportation Problem with Transshipment

CHEN Hai-wei，TAO Qing-ling

(Department of Management，Shangqiu Institute of Technology，Shangqiu 476000，China)

The table algorithm on transportation problem of the production and sale balance is discussed.Vogel method is used to get the initial solution，potential method to get test number，and closed-loop method to adapt and improve the feasible solutions.And a method for the transportation problem with transshipment is proposed，with all the places of production，the middle station and pins regarded as the places of production and pins，so the problem can be solved as an expanded transport problem.

table algorithm;Vogel method;potential method;test number

O224

A

1007－0834(2012)02－0020－04

10.3969/j.issn.1007－0834.2012.02.006

2011－12－29

陳海偉(1983—)，男，河南商丘人，商丘工學(xué)院管理學(xué)院教師.