第五章 運輸問題1運輸問題是線性規(guī)劃問題的特例。產(chǎn)地：貨物發(fā)出的地點。銷地：貨物接收的地點。產(chǎn)量：各產(chǎn)地的可供貨量。銷量：各銷地的需求數(shù)量。運輸問題就是研究如何組織調(diào)運，既滿足各銷地的需求，又使總運費最小。第一節(jié)運輸模型一、運輸問題舉例某飲料在國內(nèi)有三個生產(chǎn)廠，分布在城市A1、A2、A3,其一級承銷商有4個，分布在城市B1、B2、B3、B4，已知各廠的產(chǎn)量、各承銷商的銷售量及從Ai到Bj的每噸飲料運費為cij，為發(fā)揮集團優(yōu)勢，公司要統(tǒng)一籌劃運銷問題，求運費最小的調(diào)運方案。銷地產(chǎn)地B1B2B3B4產(chǎn)量A163255A275842A332973銷量23142第一節(jié)運輸模型3供應平衡條件①②③銷售平衡條件④⑤⑥⑦非負性約束x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34

=3x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4xij≥0

(i=1,2,3；j=1,2,3,4)運輸問題的LP模型決策變量

設從Ai到Bj的運輸量為xij，目標函數(shù)min

Z

=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34約束條件

產(chǎn)量之和等于銷量之和,故要滿足：第一節(jié)運輸模型二、表式運輸模型銷地產(chǎn)地B1B2…Bn產(chǎn)量A1c11

x11c12

x12…c1n

x1na1A2c21x21c22x22…c2nx2na2………………Amcm1

xm1cm2

xm2…cmn

xmnam銷量b1b2…bn∑ai∑bj4產(chǎn)銷平衡5第一節(jié)運輸模型三、運輸問題的三種類型m

n

ai

=

bji=1

j

=1

?

0

xj

=

1,2,...,nx

b

,i

=

1,2,...,ms.t.

ij

i

=1

ij

=

j

n

j

=1

m

xij

=

ai

,m

nmin

z

=

cij

xiji

=1

j

=1第一節(jié)運輸模型產(chǎn)大于銷6mnjii=1

a

>

bj

=1

?

0

xj

=

1,2,...,nx

b

,

x

￡

a

, i

=

1,2,...,ms.t.

ij

m

i

=1

ij

=

j

n

j

=1iijm

nmin

z

=

cij

xiji

=1 j

=1第一節(jié)運輸模型7產(chǎn)小于銷m

nji

a

<

bi=1

j

=1

?

0

xj

=

1,2,...,nx

b

,

x

=

a

, i

=

1,2,...,ms.t.

ij

m

i

=1

ij

￡

j

n

j

=1iijm

nmin

z

=

cij

xiji

=1 j

=1第一節(jié)運輸模型系數(shù)矩陣的結(jié)構(gòu)如下：四、運輸模型的特點決策變量m·n

約束方程m+n

1

1111111

11

1

1

1

1

1A

=

…

…x11

x12

x1n

x21

x22

x2n

1

1

1

…

…

…

…xm1

xm2…

xmn

m

行

n

行稀

疏陣

8第二節(jié)表上作業(yè)法9表上作業(yè)法：適合于產(chǎn)銷平衡的運輸問題求解步驟：找出初始方案（初始基可行解）：在m·n維產(chǎn)銷平衡表上給出m+n-1個數(shù)字。最優(yōu)性檢驗：計算各非基變量的檢驗數(shù)，當sij?0最優(yōu)。方案調(diào)整與改進：確定進基變量和離基變量，找出新的基可行解。第二節(jié)表上作業(yè)法10最小元素法“就近運給”，從單位運價表中最小運價開始確定供銷關(guān)系，逐次挑選最小元素，安排運量min{ai

,bj}。最大差額法不能按最小運費就近供應，就考慮次小運費。

各行(各列)的最小運費與次小運費之差稱為行差(列差)。差額越大，說明不能按最小運費調(diào)運時，運費增加最多。對最大差額處就采用最小運費調(diào)運。一、確定初始方案第二節(jié)表上作業(yè)法銷地產(chǎn)地B1

B2

B3

B4產(chǎn)量A163

2

55A275

842A332

973銷量2

3

1

4③0②①

②②初始基可行解：x11=2,x13=1,x14=2,x24=2,x31=0,x32=3，Z=3811最小元素法從單位運價表中逐次挑選最小元素，安排運量min{ai

,bj}。然后，劃去該元素所在行或列：有兩個最小元素，當產(chǎn)大于銷，劃去該元素所在任列選；其一，當產(chǎn)小于銷，劃去該元素所在比行如。選c13第二節(jié)表上作業(yè)法12最大差額法

對每行每列的運價cij

分別計算兩最小元素之差（取正值），將行差記于表右側(cè)，將列差記于表下端。在所有行差、列差中選一最大差額，若幾個同時最大，任選其一。在最大差額所在行（列）中選一最小運價，若幾個同時最小，任選其一。在(3)中所確定的最小運價格內(nèi)，確定基變量數(shù)值并畫圈，然后劃去所在行或列，具體做法同最小元素法。對剩余未劃去的行列重復上述步驟，但當只剩下最后一行（列）時，不再計算行（列）差，而直接按最小元素法分配運量，并

劃去相應的行或列。第二節(jié)表上作業(yè)法最大差額法銷地產(chǎn)地B1B2B3B4產(chǎn)量

行差A163255

1A275842

1A33297銷量231461①221

1②

①②1②②此時只剩下最后一列，不列差再計3算行差、列1差，直接按最小元素法分配運量x24=2，劃去第二行，再分配x14=2，2得到一個初始方案。初始基可行解：x12=2,x13=1,x14=2,x24=2,x31=2,x32=1，Z=34后面將會驗證，這里給出13的初3始方案1是最優(yōu)1方案。5最大差額法并不一定對所有平衡問題都給出最優(yōu)方1案0，但一般說來，它給出的方案比最小元素法要好。第二節(jié)表上作業(yè)法位勢法計算檢驗數(shù)檢驗數(shù)：ui代表產(chǎn)地Ai的位勢量，vj代表銷地Bj的位勢量?；兞康臋z驗數(shù)為0，即二、最優(yōu)性檢驗判別方法是計算非基變量的檢驗數(shù)：運輸問題的目標函數(shù)要求為最小，即當sij?0視為最優(yōu)。將基變量（畫圈數(shù)字）所在格的運價分解為兩部分：cij=ui+vj并令u1

=0，計算各行各列的位勢量。位勢量ui、vj

的總數(shù)為m+n

個，而由m+n-1個基變量的運價限定的關(guān)于ui、vj

的方程cij=ui+vj

只有m+n-1個，所以ui、vj

有無窮組解。任選一個ui

或vj并賦予任一數(shù)值，就可確定所有的ui、

vj

的值。一般的，令u1

=0。14σij

=

cij

-

(ui

+

v

j

)σij

=

cij

-(ui

+

v

j

)

=

0,第二節(jié)表上作業(yè)法位勢法基變量的檢驗數(shù)sij=cij

–ui

–vj

=0，即cij

=ui

+vj

，且令u1

=0，計算位勢量ui

和vj銷地產(chǎn)地產(chǎn)量A16B1

B2

B3

B43

2

5②

①

②5A275②2A3302③8

49

73銷量2314uivj0625-1-3515第二節(jié)表上作業(yè)法位勢法（續(xù)）計算非基變量的檢驗數(shù)sij=cij

–ui

–vj填在每個非基變量空格的右下角銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA16②3-22①5②50A27251874②2-1A3302③910753-3銷量2314vj652516非基變量x12的檢驗數(shù)s12=c12–u1–v2=-2，即讓非基變量x12從0增到1，可使總運費減少2個單位，故可以斷定最小元素法給出的初始方案非最優(yōu)。第二節(jié)表上作業(yè)法17三、改進的方法（閉回路調(diào)整法）確定進基變量檢查非基變量xij的檢驗數(shù)sij

，按min{sij|

sij

<0}=

slk

確定xlk進基。確定離基變量非基變量xlk進基之后，能讓它的運量增加多少呢？就要求它所在行和列的運量保持產(chǎn)銷平衡。保持產(chǎn)銷平衡的方法是閉回路法。閉回路法：以進基變量xlk所在格為始點和終點，其余頂點均為基變量的封閉回路。閉回路的畫法：從進基變量xlk所在格開始，用水平或垂直線向前劃，每碰到一個基變量格轉(zhuǎn)90o，繼續(xù)前進，直到返回始點。奇偶點：始點是偶點，依次奇偶相間標注；偶點標“+”，表示運量增加量；奇點標“-”，表示運量減少量。調(diào)整量：最小可減少的運量，即奇點運量的最小值。 奇點運量的最小值所在格的基變量離基。第二節(jié)表上作業(yè)法銷地產(chǎn)地B1B2B3B4產(chǎn)量A1632①5②5A27584②2A30973銷量

2

3x12

進基最小調(diào)整量為2，x11

離基14+

x1218-

②3+2-③第二節(jié)表上作業(yè)法非最優(yōu)方案的調(diào)整所有偶點的值都加上調(diào)整量；所有奇點的值都減去調(diào)整量；獲得一個新的運輸方案?；尚薪猓簒12=2,x13=1,x14=2,x24=2,x31=2,x32=1，Z=3419銷地產(chǎn)地B1B2B3B4產(chǎn)量A16②3②2①5②5A27584②2A33②02③①973銷量2314第二節(jié)表上作業(yè)法四、最優(yōu)性檢驗基變量的檢驗數(shù)sij

=cij

–ui

–vj

=0，且令u1

=0，計算位勢量ui和vj所有非基變量xij的檢驗數(shù)sij=cij

–ui–vj≥0，即得最優(yōu)解。20銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA1623②2①5②50A27453874②2-1A33②2①98733-1銷量2314vj4325第三節(jié)產(chǎn)銷不平衡問題21產(chǎn)銷平衡的運輸問題采取表上作業(yè)法求解。產(chǎn)銷不平衡的運輸問題需劃成產(chǎn)銷平衡問題再求解。產(chǎn)大于銷：虛設一個銷地Bk(多余物資的存儲)，其運價為0，銷量(存儲量)為產(chǎn)銷量之差bk

=

ai

-

bj。產(chǎn)小于銷：虛設一個產(chǎn)地Al

(不足物資的脫銷量)，其運價為0，產(chǎn)量

(脫銷量)為銷產(chǎn)量之差ak

=

bj

-

ai

。第三節(jié)產(chǎn)銷不平衡問題增加一個銷地一、產(chǎn)大于銷銷地產(chǎn)地B1B2B3產(chǎn)量50-4622B4銷地產(chǎn)地B1B2B3產(chǎn)量A159215A231718A362817銷量1812165046A1592015A2317018A3628017銷量1812164

50

50第三節(jié)產(chǎn)銷不平衡問題初始基可行解銷地產(chǎn)地B1B2B3B4產(chǎn)量A1592015A2317018A36280171215⑥12①④23銷量

18

12

16

4初始基可行解：x13=15,

x21=6,

x22=12,

x31=12,

x33=1,

x34=4，Z=140第三節(jié)產(chǎn)銷不平衡問題最優(yōu)性檢驗銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA15591121506150A23⑥1127203183A36122-28①0④176銷量1812164vj0-22-624非基變量x32的檢驗數(shù)s32=-2，即讓非基變量x32進基。第三節(jié)產(chǎn)銷不平衡問題閉回路調(diào)整銷地產(chǎn)地B1B2B3B4產(chǎn)量A159215015A2317018A368①0④17銷量

18

12x32

進基最小調(diào)整量為12，x22

離基164-

1225+⑥-

122+x32第三節(jié)產(chǎn)銷不平衡問題非最優(yōu)方案的調(diào)整所有偶點的值都加上調(diào)整量；所有奇點的值都減去調(diào)整量?；尚薪猓簒13=15,x21=18,x31=0,x32=12,x33=1,x34=4，Z=116銷地產(chǎn)地B1B2B3B4產(chǎn)量A159215015A231⑥81127018A361022128①0④17銷量181216426第三節(jié)產(chǎn)銷不平衡問題最優(yōu)性檢驗基變量的檢驗數(shù)sij=cij

–ui

–vj

=0，且令u1

=0，計算位勢量ui

和vj所有非基變量xij的檢驗數(shù)sij

=cij

–ui–vj

≥0，即得最優(yōu)解。銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA15591321506150A2318127203183A3602128①0④176銷量1812164vj0-42-627第三節(jié)產(chǎn)銷不平衡問題增加一個產(chǎn)地二、產(chǎn)小于銷23-2228銷地產(chǎn)地B1B2B3產(chǎn)量A141210A234312銷量81052223銷地產(chǎn)地B1B2B3產(chǎn)量A141210A234312A30001銷量81052323第三節(jié)產(chǎn)銷不平衡問題初始基可行解銷地產(chǎn)地B1B2B3產(chǎn)量A141210A234312A30001銷量100⑤⑦①8

10

5初始基可行解：x12=10,

x13=0,

x21=7,

x23=5,

x31=1，Z=4629第三節(jié)產(chǎn)銷不平衡問題最優(yōu)性檢驗銷地產(chǎn)地B1B2B3產(chǎn)量ui23⑦423⑤121A30①01001-2銷量8105vj21230–

檢驗數(shù)sij≥0，得最優(yōu)解:x12=10,x13=0,x21=7,x23=5,x31=1，Z=46–

由于非基變量x33

的檢驗數(shù)s33=0，為多重最優(yōu)解。讓x33進基,x31離基,得另一最優(yōu)解:x12=10,x13=0,x21=8,x23=4,x33=1第四節(jié)運輸模型的應用31一、短缺資源的分配問題短缺資源分配，“產(chǎn)小于銷”，需注意產(chǎn)銷配比問題。上例x12=10,x13=0,x21=7,x23=5,x31=1，表示銷地B1脫銷1個單位；然而x12=10,x13=0,x21=8,x23=4,x33=1，則表示銷地B3

脫銷1個單位；但銷地B3

的銷量為5，本身就很少，不允許脫銷，如何處理呢？第四節(jié)運輸模型的應用一、短缺資源的分配問題自來水分配問題：水價90元/kt，管理費45元/kt，引水費如下表：供區(qū)水庫甲乙丙丁供水量kt/dA1613221750B1413191560C192023--50最低需求kt/d3070010最高需求kt/d507030不限32如何分配供水量，保障各區(qū)最低需求，獲利最大？第四節(jié)運輸模型的應用33分析利潤=收入-成本，收入最大，成本最小，則利潤最大。收入：每天供水總量是一常數(shù)，水價也是常數(shù)，則每天總收入也是常數(shù)。每天供水總量若能全部售出，每天總收入則能達到最大。丁區(qū)最高需求不限，每天總供水量能全售出。每天總收入是常數(shù)，與水量分配無關(guān)，可以不予考慮。成本：各區(qū)管理費相同45元/kt，每天售水總量是一常數(shù)，則管理費也是常數(shù)。各區(qū)引水費不同，如果總的引水費達到最小，總成本則最低。如何分配水量，既滿足最低需求，又使總的引水費最低？最大需求量：

供水總量=50+60+50=160，四區(qū)最低需求量=30+70+10=110，故丁區(qū)最大需求量160-110+10=60。

四區(qū)最大需求=50+70+30+60=210，比供水總量160多50，則是一個產(chǎn)小于銷的不平衡問題。第四節(jié)運輸模型的應用產(chǎn)小于銷的運輸問題化為平衡問題,虛設水庫D,供水量50.各區(qū)的最低需求為基本需求，不允許脫銷，不能由虛設水庫D供水，故單位引水費（運費）為M。

各區(qū)的最大需求與最低需求的差為額外需求，可以由虛設水庫D供水，故單位引水費（運費）為0

。供區(qū)水庫甲1甲2乙丙丁1丁2供水量A16161322171750B14141319151560C19192023MM50DM0M0M050銷量30207030105034第四節(jié)運輸模型的應用用表上作業(yè)法求得最優(yōu)方案（用最大差額法給出的初始方案即為最優(yōu)）供區(qū)水庫甲1甲2乙丙丁1丁2供水量A5050B20103060C3020050D302050銷量30207030105035–

最優(yōu)分配方案：水庫A向乙區(qū)供水50，水庫B分別向乙區(qū)、丁區(qū)供水20和40，水庫C向甲區(qū)供水50，不給丙區(qū)供水。–

最小引水管理費：13

50+13 20+

15(10+30)+19(30+20)

=2460其他管理費：45

(50+60+50)=7200–

總成本：2460

=9600總收入：90(50+60+50)=14400–

最大獲利：14400-9600=4740第四節(jié)運輸模型的應用二、資源轉(zhuǎn)運問題產(chǎn)地與銷地之間存在轉(zhuǎn)運站。