表上作業(yè)法在有轉運的物資運輸問題中的應用

陳海偉，陶慶玲

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

表上作業(yè)法在有轉運的物資運輸問題中的應用

陳海偉，陶慶玲

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

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

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

1 運輸問題的數(shù)學模型［1］

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

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

2 表上作業(yè)法在運輸問題中的應用

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

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

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

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

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

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

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

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

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

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

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

2.3 解的調整和改進［3］

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

(1)在運輸表中做出最小負檢驗數(shù)δij對應空格的閉回路; (2)以空格(Ai，Bj)為初始點，沿順時針方向依次對閉回路上的頂點進行編號;

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

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

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

表1 運輸費用表Tab.1Transport freight list

表2 運輸問題的初始方案Tab.2Initial solution for transportation problem

(2)用位勢法求檢驗數(shù)，見表3.

表3 檢驗數(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)求非基變量檢驗數(shù)δ11=0，σ12=2，σ22=2，σ23=1，σ31=9，σ33=12.

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

3 有轉運的運輸問題

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

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

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

表5 帶有轉運運輸問題的運輸表Tab.5The transport table of transportation problem with transshipment

解(1)由于問題中所有產(chǎn)地、中間轉運站、銷地都可以看做產(chǎn)地，又可看做銷地，因此把整個問題當做有11個產(chǎn)地和11個銷地的擴大的運輸問題.

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

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

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

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

表6 擴大的運輸問題的單位運價表Tab.6The unit price table of expanded transportation problem

［1］胡運權.運籌學教程［M］.3版.北京:清華大學出版社，2007:80－94.

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

［3］何莉敏，李玉，于濤，等.Vogel法求解最大值問題［J］.鄭州大學學報:理學版，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—)，男，河南商丘人，商丘工學院管理學院教師.