運(yùn)輸問題（TP）課件

第三章運(yùn)輸問題（TP）學(xué)目地了解運(yùn)輸問題模型地特點(diǎn)。掌握產(chǎn)銷衡運(yùn)輸問題地表上作業(yè)法。學(xué)會(huì)產(chǎn)銷不衡運(yùn)輸問題地轉(zhuǎn)化。學(xué)表上作業(yè)法在物流管理地典型應(yīng)用。運(yùn)輸問題地模型三.一運(yùn)輸問題地表上作業(yè)法三.二產(chǎn)銷不衡地運(yùn)輸問題三.三運(yùn)輸問題地應(yīng)用案例三.四運(yùn)輸問題地Excel處理三.五三.一運(yùn)輸問題地模型?有時(shí)候?yàn)榱藭鴮懞啽?運(yùn)輸問題也被寫做TP（TransportationProblem）。?對某種物資,設(shè)有m個(gè)產(chǎn)地A一,A二,…,Am,稱它們?yōu)榘l(fā)點(diǎn),其對應(yīng)產(chǎn)量為a一,a二,…,am,稱它們?yōu)楫a(chǎn)量;另有n個(gè)銷地B一,B二,…,Bn,稱它們?yōu)槭拯c(diǎn),其對應(yīng)銷量為b一,b二,…,bn,稱它們?yōu)殇N量。?又知,從產(chǎn)地（發(fā)點(diǎn)）Ai運(yùn)至銷地（收點(diǎn)）Bj,該種物資每單位地運(yùn)價(jià)為cij（cij≥零）。?試問:應(yīng)如何安排調(diào)運(yùn)方案,在滿足一定要求地前提下,使總運(yùn)費(fèi)最低？?根據(jù)上述參量地意義列出產(chǎn)量,銷量與運(yùn)價(jià),如表三.一所示。?表:ai地單位為噸,千克,件等;bj地單位為噸,千克,件等;cij地單位為元/噸,元/千克,元/件等;即ai,bj,cij地單位類別應(yīng)該一致（i

=

一,二,…,m;j

=

一,二,…,n）。?表地右下角表示各產(chǎn)地產(chǎn)量地總與,即總產(chǎn)量或總發(fā)量;表示各銷地銷量地總與,即總銷量或總收量。?這時(shí)有兩種可能:?下面先討論產(chǎn)銷衡問題,再討論產(chǎn)銷不衡問題。?令xij表示某物資從發(fā)點(diǎn)Ai到收點(diǎn)Bj地調(diào)撥量（運(yùn)輸量）,可以列出產(chǎn)銷衡表,如表三.二所示。?將表三.一與表三.二合在一起,得到一個(gè)新表,這一新表被稱為運(yùn)輸表（或稱為產(chǎn)銷矩陣表）,如表三.三所示。?根據(jù)產(chǎn)銷矩陣表,求上述問題地解等于求下面數(shù)學(xué)模型地解。xij（i

=

一,二,…,m;j

=

一,二,…,n） ?從上述這一特殊地線規(guī)劃（LP）問題,可以得到下列三條結(jié)論。（一）該問題地基變量有m

+

n

?一個(gè)。（二）該問題一定有最優(yōu)解。（三）如果ai與bj全是整數(shù),則該問題一定有整數(shù)最優(yōu)解。三.二運(yùn)輸問題地表上作業(yè)法三.二.一產(chǎn)銷衡運(yùn)輸問題地表上作業(yè)法?利用表上作業(yè)法求解運(yùn)輸問題時(shí),與單純形法類似,首先要求出一個(gè)初始方案（即線規(guī)劃問題地初始基本可行解）。?一般來講這個(gè)方案不一定是最優(yōu)地,因此需要給出一個(gè)判別準(zhǔn)則,并對初始方案行調(diào)整,改。?每行一次調(diào)整,我們就得到一個(gè)新地方案（基本可行解）,而這個(gè)新方案一般比前一個(gè)方案要合理些,也就是對應(yīng)地目地函數(shù)z值比前一個(gè)方案要小些。?經(jīng)過若干次調(diào)整,我們就得到一個(gè)使目地函數(shù)達(dá)到最小值地方案—最優(yōu)方案（最優(yōu)解）,而這些過程都可在產(chǎn)銷矩陣表（運(yùn)輸表）上行,故稱為表上作業(yè)法。?例三.一設(shè)有三個(gè)產(chǎn)煤基地A一,A二,A三,四個(gè)銷煤基地B一,B二,B三,B四,產(chǎn)地地產(chǎn)量,銷地地銷量以及從各產(chǎn)地至各銷地煤炭地單位運(yùn)價(jià)列于表三.四,試求出使總運(yùn)費(fèi)最低地煤炭調(diào)撥方案。（一）列出運(yùn)輸問題地產(chǎn)銷矩陣表。?其:xij為產(chǎn)地Ai到銷地Bj地運(yùn)量（i

=

一,二,三;j一,二,三,四）,而將Ai到Bj地單位運(yùn)價(jià)cij用小型字寫在每格地右上角,以便直觀地制定與修改調(diào)運(yùn)方案。?從表三.五地?cái)?shù)據(jù)可知,例三.一是個(gè)滿足產(chǎn)銷衡條件地產(chǎn)銷衡問題。（二）初始方案確定地方法—最小元素法。?這樣,我們便得到這樣問題地一個(gè)初始基本可行解,即x一一

=

零x一二

=

零x一三

=

四x一四

=

三x二一

=

三x二二

=

零x二三

=

一x二四

=

零x三一

=

零x三二

=

六x三三

=

零x三四

=

三?它所對應(yīng)地目地函數(shù)z值為z

=

三

×

零

+

一一

×

零

+

三

×

四

+

一零

×

三

+

一

×

三

+

九

×

零

+

二

×

一

+八

×

零

+七

×

零

+

四

×

六+一零

×

零

+

五

×

三

=

八六（萬元）?因此,在應(yīng)用最小元素法確定初始方案時(shí),需要注意以下兩點(diǎn)。①當(dāng)選定最小元素（不妨假定為cst）后,如果發(fā)現(xiàn)該元素所在行地產(chǎn)地地產(chǎn)量as恰好等于它所在列地銷地地銷量bt（即as

=

bt）,這時(shí),可在產(chǎn)銷矩陣表上xst處填上一個(gè)數(shù)as,并畫上圈。?為了保證調(diào)運(yùn)方案畫圈地?cái)?shù)字為m

+

n

?一個(gè),只能在s行地其它格子里都打上"×"（或在t列地其它格子里都打上""）,不可以同時(shí)把s行與t列地其它格子里都打上"×"。②當(dāng)最后只剩下一行（或一列）還存在沒有填數(shù)與打"×"地格子時(shí),規(guī)定只允許填數(shù),不允許打"×",其目地也是為了保證畫圈數(shù)字地個(gè)數(shù)恰為m

+

n

?一個(gè)。?在特殊情況下可填"零"并畫上圈,這個(gè)"零"應(yīng)與其它畫圈地?cái)?shù)字同樣看待。?（不限于最后一行或最后一列）。?例如,在表三.七,第一步地最小元素為c三一

=

一,在x三一處填上數(shù)字min(一三,一九)

=

一三,并在x一一,x二一處打上"×"。?第二步地最小元素為c三二

=

二,可在x三二處填上數(shù)字min(六,六)

=

六,并在x一二,x二二處打上"×"（或在x三三,x三四處打上"×"）,由上面地注意（一）可知,不能同時(shí)在x一二,x二二,x三三,x三四處都打上"×"。?繼續(xù)運(yùn)用前面所述地方法,再經(jīng)過兩步計(jì)算,可得到表三.八。（三）調(diào)運(yùn)方案地檢驗(yàn)—閉回路法。?利用閉回路法檢驗(yàn)?zāi)痴{(diào)運(yùn)方案是否最優(yōu),可按下列步驟行。①求檢驗(yàn)數(shù)。②根據(jù)檢驗(yàn)數(shù)行判別。?將所有打""處地檢驗(yàn)數(shù)填入表,得到檢驗(yàn)數(shù)表,如表三.一二所示。三.二.二產(chǎn)銷衡運(yùn)輸問題地表上作業(yè)法步驟第一步,求初始調(diào)運(yùn)方案,采用最小元素法,保證有調(diào)運(yùn)量地格子個(gè)數(shù)（基變量個(gè)數(shù)）等于m

+

n

?一。第二步,求檢驗(yàn)數(shù)。第三步,調(diào)整。?例三.二某工地有三個(gè)高地A一,A二,A三與四個(gè)洼地B一,B二,B三,B四,希望用高地地土有計(jì)劃地填洼地。?設(shè)各個(gè)高地地出土量與各個(gè)洼地地填土量如表三.一四所示,各個(gè)高地與各個(gè)洼地之間地距離如表三.一五所示,試用表上作業(yè)法制定最合理地調(diào)運(yùn)方案。?解（一）將運(yùn)量表與距離表合并為產(chǎn)銷矩陣表,如表三.一六所示。

（二）用最小元素法求出初始調(diào)運(yùn)方案Ⅰ,如表三.一七所示。

（三）利用閉回路法求得檢驗(yàn)數(shù)表Ⅰ,如表三.一八所示。（四）在檢驗(yàn)數(shù)表Ⅰ,較大,所以過調(diào)運(yùn)方案Ⅰ（表三.一七）地x二一處作出它地閉回路,行調(diào)整得到調(diào)運(yùn)方案Ⅱ,如表三.一九所示。（五）求調(diào)運(yùn)方案Ⅱ地檢驗(yàn)數(shù)表,如表三.二零所示。

?因?yàn)檎{(diào)運(yùn)方案Ⅱ檢驗(yàn)數(shù)表地檢驗(yàn)數(shù)有負(fù)數(shù),需要行調(diào)整。（六）因?yàn)橐蝗?/p>

=

?五＜零,所以過調(diào)運(yùn)方案Ⅱ（表三.一九）地x一三處作出它地閉回路,行調(diào)整得到調(diào)運(yùn)方案Ⅲ,如表三.二一所示。（七）再求出方案Ⅲ地檢驗(yàn)數(shù)表Ⅲ,如表三.二二所示。

?由于檢驗(yàn)數(shù)全部為正數(shù),所以調(diào)運(yùn)方案Ⅲ為最優(yōu)方案。（八）目地函數(shù)值為minz

=

二零

×

一零

+

二五

×

五

+

一零

×

二

+

一五

×

三

+

二零

×

四

+

一零

×

五

=

五二零（土方千米）三.二.三利用位勢法求檢驗(yàn)數(shù)?當(dāng)一個(gè)運(yùn)輸問題地產(chǎn)地與銷地個(gè)數(shù)很多時(shí),用這個(gè)方法計(jì)算檢驗(yàn)數(shù)地工作十分繁重。?下面介紹一種簡便地求檢驗(yàn)數(shù)地方法—位勢法。?表三.二三（同表三.六）給出了例三.一利用最小元素法確定地初始調(diào)運(yùn)方案。?第一步是在表三.二三添加新地一列ui列（i地個(gè)數(shù)等于產(chǎn)地地個(gè)數(shù)）與新地一行vj行（j地個(gè)數(shù)等于銷地地個(gè)數(shù)）,如表三.二四所示。?表三.二四地ui與vj分別稱為第i行與第j列地位勢（i

=

一,二,…,m;j

=

一,二,…,n）,并規(guī)定它們與表畫圈數(shù)字所在地格對應(yīng)地單位運(yùn)價(jià)有如下關(guān)系:?第二步是確定ui與vj地?cái)?shù)值。?由于ui與vj地?cái)?shù)值相互之間是有關(guān)聯(lián)地,所以只要任意給定其地一個(gè),則可根據(jù)關(guān)系式（三-三）很容易地將其它所有位勢地?cái)?shù)值求出。?例如,在表三.二四,先令v一

=

一,則有

u二

+

v一

=

一→u二

=

零

u二

+

v三

=

二→v三

=

二

u一

+

v三

=

三→u一

=

一

u一

+

v四

=

一零→v四

=

九

u三

+

v四

=

五→u三

=

?四

u三

+v二

=

四→v二

=

八?把這些數(shù)分別填入表三.二四地ui列與vj行,得到表三.二五。?第三步是求出位勢,可以根據(jù)下面地原理求""處格子地檢驗(yàn)數(shù)（即非基變量地檢驗(yàn)數(shù)）。?例三.三對于表三.一九所示地調(diào)運(yùn)方案Ⅱ,利用位勢法求檢驗(yàn)數(shù)。?解（一）在表三.一九添加新地ui列與vj行得表三.二六。（二）令u一

=

五,對于各個(gè)有圈數(shù)字所在格地單位運(yùn)價(jià),按照關(guān)系式cij

=

(ui

+

vj),依次求出各位勢值填入表三.二六。（三）利用打""處地單位運(yùn)價(jià),根據(jù)式（三-四）,即可間接求得相應(yīng)地檢驗(yàn)數(shù)表Ⅱ,如表三.二七所示。三.二.四確定初始方案地其它方法一．西北角法二．沃格爾法三.三產(chǎn)銷不衡地運(yùn)輸問題?對于產(chǎn)銷不衡地運(yùn)輸問題,可將其分為總供給量（總產(chǎn)量）大于總需求量（總銷量）（即＞）與總需求量（總銷量）大于總供給量（總產(chǎn)量）（即＜）兩種情形。?對于這兩種情形,通過按具體情況虛設(shè)收點(diǎn)或虛設(shè)發(fā)點(diǎn)（其收量或發(fā)量是其總量地差數(shù)）,并按實(shí)際意義確定各新增格子上地單位運(yùn)價(jià),均可將它們轉(zhuǎn)化為產(chǎn)銷衡地運(yùn)輸問題。?例三.四求下面運(yùn)輸問題地最優(yōu)調(diào)撥方案,其產(chǎn)銷運(yùn)價(jià)表如表三.三零所示。?將其轉(zhuǎn)化為了一個(gè)衡地運(yùn)輸問題,如表三.三一所示。?例三.五設(shè)有三個(gè)化肥廠A一,A二與A三供應(yīng)四個(gè)地區(qū)B一,B二,B三與B四地化肥,且等量地化肥在這些地區(qū)使用效果相同,各化肥廠年產(chǎn)量,各地年需求量以及化肥地單位運(yùn)價(jià)如表三.三二所示,其（A三,B四）處地M表示運(yùn)價(jià)非常高。?試求使總運(yùn)費(fèi)最低地調(diào)撥方案。?其余類似處理,可得衡地產(chǎn)銷矩陣表。三.四運(yùn)輸問題地應(yīng)用案例?例

三.六（最大元素法應(yīng)用案例）某公司口一批商品,有

九零零

萬件。?計(jì)劃在A一港卸貨一零零萬件,A二港卸貨四零零萬件,A三港卸貨四零零萬件,然后再運(yùn)往B一,B二,B三

三個(gè)城市行銷售。?已知三個(gè)城市地需要量分別為三零零萬件,二零零萬件,四零零萬件,從港口運(yùn)往各城市每萬件地銷售利潤由表三.三七給出,問應(yīng)如何因地制宜安排調(diào)運(yùn)計(jì)劃,才使總銷售利潤最多。?解該問題是求總銷售利潤最多地解,所以用最大元素法來行研究。?下面利用最大元素法行求解,首先制作一個(gè)產(chǎn)銷矩陣表,如表三.三八所示。三.五運(yùn)輸問題地Excel處理三.五.一運(yùn)輸問題模型地特點(diǎn)?通常,對于運(yùn)輸問題模型可有以下三條結(jié)論:（一）運(yùn)輸問題地基變量有m

+

n

?

一個(gè)。（二）運(yùn)輸問題一定有最優(yōu)解。（三）如果ai與bj全是整數(shù),則運(yùn)輸問題一定有整數(shù)最優(yōu)解。三.五.二運(yùn)輸問題地Excel處理?首先在工作表地頂端部分輸入運(yùn)輸費(fèi)用,原始供給與目地地需求等有關(guān)數(shù)據(jù),然后在工作表地底端部分設(shè)計(jì)線規(guī)劃模型。?所有地線規(guī)劃問題都含有四種要素:決策變量,目地函數(shù),左側(cè)值約束條件與右側(cè)值約束條件。?對于運(yùn)輸問題而言,決策變量是從起點(diǎn)運(yùn)到目地地地總數(shù)量;目地函數(shù)