物流運籌學(xué) 課件 第4章 物流運輸

運輸問題

運輸問題是線性規(guī)劃問題，由于其約束條件的特殊性，產(chǎn)生了特殊的解法。4.1運輸問題的典型數(shù)學(xué)模型例：某公司從兩個產(chǎn)地A1、A2、A3將物品運往三個銷地B1,B2,B3，B4，各產(chǎn)地的產(chǎn)量、各銷地的銷量和各產(chǎn)地運往各銷地每件物品的運費如下表所示，問：應(yīng)如何調(diào)運可使總運輸費用最少？B1B2B3B4產(chǎn)量A165344A244756A376583銷量243413解：產(chǎn)銷平衡問題：總產(chǎn)量=總銷量＝13設(shè)xij

為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列運輸量表：B1B2B3B4產(chǎn)量A165344A244756A376583銷量243413B1B2B3B4產(chǎn)量A1x11x12x13x144A2x21x22x23x246A3x31x32x33x343銷量243413minz=6x11+5x12+3x13+4x14+4x21+4x22+7x23+5x24+7x31+6x32+5x33+8x34x11+x12+x13+x14=4x21+x22+x23+x24=6x31+x32+x33+x34=3x11+x21+x31=2x12+x22+x32=4x13+x23+x33=3x14+x24+x34=4xij≥0,i=1,2,3;j=1,2,3,4運輸問題的提出A1、A2、…、Am

表示某物資的m個產(chǎn)地；B1、B2、…、Bn

表示某物資的n個銷地；ai

表示產(chǎn)地Ai的產(chǎn)量；

bj

表示銷地Bj

的銷量；cij

表示把物資從產(chǎn)地Ai運往銷地Bj的單位運價。設(shè)

xij

為從產(chǎn)地Ai運往銷地Bj的運輸量，得到下列一般運輸量問題的模型：當(dāng)發(fā)點的發(fā)量總和為

ai，收點的收量總和為

bj相等時，稱此運輸問題為平衡運輸問題（產(chǎn)銷平衡問題）。否則稱此運輸問題為非平衡運輸問題。

產(chǎn)銷不平衡時，可加入假想的產(chǎn)地（銷大于產(chǎn)時）或銷地（產(chǎn)大于銷時）。運輸問題的圖表形式運輸問題解的結(jié)構(gòu)：

由于

ai=

bj成立

m+n個約束方程并不是獨立的。實際上只有m+n-1個是獨立的。即約束方程系數(shù)矩陣的秩為m+n-1。4.2表上作業(yè)法表上作業(yè)法其實質(zhì)是單純形法，是一種求解運輸問題的特殊方法。（1）找出初始基可行解。即在()產(chǎn)銷平衡表上用最小元素法或元素差值法給出個數(shù)字，稱為數(shù)字格。它們就是初始基變量的取值。（2）求各非基變量的檢驗數(shù)。用閉回路法和位勢法。若表上空格的檢驗數(shù)符合要求，則為最優(yōu)解；否則轉(zhuǎn)到下一步。（3）確定換入變量和換出變量，找出新的基本可行解，在表上用閉回路法調(diào)整。重復(fù)（2），（3）直到得到最優(yōu)解為止。1.最小元素法4.2.1確定初始基本可行解

發(fā)點收點B1B2B3B4發(fā)量A165344A244756A376583收量243413（1）從最小元素開始“3”即A1優(yōu)先滿足B33個單位，B3已經(jīng)滿足，劃去B3列。發(fā)點收點B1B2B3B4發(fā)量A165344A244756A376583收量2434133（2）再從最小元素開始“4”即A1優(yōu)先滿足B41個單位，A1已經(jīng)滿足，劃去A1行。發(fā)點收點B1B2B3B4發(fā)量A165344A244756A376583收量24341331（3）再從最小元素開始“4”即A2優(yōu)先滿足B12個單位，B1已經(jīng)滿足，劃去B1列。

發(fā)點收點B1B2B3B4發(fā)量A165344A244756A376583收量243413312（4）再從最小元素開始“4”即A2優(yōu)先滿足B24個單位，B2A2已經(jīng)滿足，劃去B2列A2

行。發(fā)點收點B1B2B3B4發(fā)量A165344A244756A376583收量2434133124表格中要有(m+n-1)個數(shù)字格，但有時在分配運量時則需要同時劃去一行和一列，這時需要補一個“0”（4）最后把A3滿足B43個單位，得到初始方案。發(fā)點收點B1B2B3B4發(fā)量A165344A244756A376583收量24341331243（5）得到初始方案：X13=3，X14=1，X21=2，X22=4，X34=3總運費=3*3+4*1+4*2+4*4+6*0+8*3=61（元）發(fā)點收點B1B2B3B4發(fā)量A165344A244756A376583收量243413312432.差值法（沃格爾法）

每次從當(dāng)前運價表上，計算各行各列中兩個運價(次最小和最小運價)之差值（行差值hi，列差值kj），優(yōu)先取最大差值的行或列中對應(yīng)最小運價的格來確定運輸關(guān)系，直到求出初始方案。收點發(fā)點B1B2B3B4發(fā)量行罰數(shù)A1653441A2447560A3765831收量243413

列罰數(shù)2121

2收點發(fā)點B1B2B3B4發(fā)量行罰數(shù)A16534411A24475601A37658311收量243413

列罰數(shù)2112211

23收點發(fā)點B1B2B3B4發(fā)量行罰數(shù)A165344111A244756011A376583112收量243413

列罰數(shù)211122111

233收點發(fā)點B1B2B3B4發(fā)量行罰數(shù)A1653441111A2447560111A376583112收量243413

列罰數(shù)21111221111

2331收點發(fā)點B1B2B3B4發(fā)量行罰數(shù)A16534411110A24475601110A376583112收量243413

列罰數(shù)211112211111

23311收點發(fā)點B1B2B3B4發(fā)量行罰數(shù)A16534411110A24475601110A376583112收量243413

列罰數(shù)211112211111

233113差值法初始方案如下：X13=3，X14=1，X21=2，X22=1，X24=3，X32=3，總費用=3*3+4*1+4*2+4*1+5*3+6*3=58（元）收點發(fā)點B1B2B3B4發(fā)量A165344A244756A376583收量243413233113最小元素法得到初始方案：X13=3，X14=1，X21=2，X22=4，X34=3，總運費=3*3+4*1+4*2+4*4+8*3=61（元）差值法初始方案如下：X13=3，X14=1，X21=2，X22=1，X24=3，X32=3，總運費=3*3+4*1+4*2+4*1+5*3+6*3=58（元）1.運輸規(guī)劃問題的數(shù)學(xué)模型2.求運輸規(guī)劃問題初始基本可行解，用最小元素法或者元素差額法。小結(jié)求最優(yōu)方案閉回路在初始調(diào)運方案表中，從任意空格出發(fā)，沿著縱向或橫向行進(jìn)，遇到適當(dāng)填有數(shù)據(jù)的方格90度轉(zhuǎn)彎或者繼續(xù)前進(jìn)，總能回到原來空格。這個封閉的曲線稱為閉回路?？梢宰C明：每個空格對應(yīng)著唯一的閉回路。如下表：求檢驗數(shù)

判斷一個調(diào)運方案是否已是最優(yōu)，就要判斷方案所對應(yīng)的基礎(chǔ)可行解是否最優(yōu)。在單純形法中，根據(jù)非基變量（空格）的檢驗數(shù)來判別的。若檢驗數(shù)中沒有正值，則已求得最優(yōu)。如何根據(jù)初始調(diào)運表求得檢驗數(shù)？（1）閉回路法

空格Xij的檢驗數(shù)=（第奇數(shù)次拐角點運價之和減去第偶數(shù)次拐角點運價之和）注意：奇、偶次拐角點的概念是相對的，不同教材上可能會不同?？崭馲21的檢驗數(shù)=6-5+4-4=1空格X14的檢驗數(shù)=5-4+5-4=2空格X31的檢驗數(shù)=6-5+4-5+8-7=1檢驗數(shù)都為正值，原方案不是最優(yōu)解調(diào)整方案

從一個方案調(diào)整到最優(yōu)方案的過程，就是單純形法的過程。選擇檢驗數(shù)（一般取最大）為正值的空格所對應(yīng)的變量為進(jìn)基變量，在進(jìn)基變量的回路中，比較奇數(shù)拐角點的運量，選擇一個具有最小運量的基變量作為出基變量；調(diào)整運量=min(奇數(shù)拐角點的運量)選擇（A1，B3）（檢驗數(shù)最大）調(diào)整，最小運量=min(2,3)=2最小運量=min(2,3)=2,奇數(shù)點減去2，偶數(shù)點加上2，得到新的方案?？傔\費=6*2+3*2+4*4+7*1+5*1+8*3=70（元）原方案運費為80（元）繼續(xù)求檢驗數(shù)。繼續(xù)調(diào)整運量。繼續(xù)調(diào)整運量。最小運量=1總運費=6*1+3*3+4*1+4*4+5*1+8*3=64（元）繼續(xù)計算檢驗數(shù)。繼續(xù)調(diào)整運量。最小運量=1得到新的調(diào)運方案，總運費=3*3+4*1+4*2+4*4+8*3=61（元）繼續(xù)計算檢驗數(shù)總運費=4*4+4*2+4*4+5*3=55（元）計算檢驗數(shù)：空格的檢驗數(shù)全為非正，此時是最優(yōu)解。最優(yōu)調(diào)運方案：X21=2，X22=4，X14=4，X33=3。最小運費55（元）。minz=6x11+5x12+3x13+4x14+4x21+4x22+7x23+5x24+7x31+6x32+5x33+8x34x11+x12+x13+x14=4x21+x22+x23+x24=6x31+x32+x33+x34=3x11+x21+x31=2x12+x22+x32=4x13+x23+x33=3x14+x24+x34=4xij≥0,i=1,2,3;j=1,2,3,4設(shè)u1、u2、u3、v1、v2、v3、v4分別表示對偶變量2.對偶變量法（位勢法）u1u2u3v1v2v3v44.2.2最優(yōu)解的判別對偶問題∵基變量檢驗數(shù)σij=0∴cij=ui+vj檢驗數(shù)：σij

=cij

–CBB-1Pij=cij–y*Pij=cij–(u1…

um,v1…vn)Pij=cij–(ui+vj)st

ui

+vj

≤cij

i=1,…,3j=1,…,4

ui

,vj無約束∴非基變量檢驗數(shù)σij

=cij–(ui+vj)……..(1)………(2)u1=0u2=2u3=4v1=2v2=2v3=3v4=4令c13=u1+v3=3c14=u1+v4=4c21=u2+v1=4c22=u2+v2=4c32=u3+v2=6c34=u3+v4=8公式cij=ui+vj非基變量檢驗數(shù)σij

=cij

–(ui

+vj)σ11=

c11

-(u1+v1)=6-(0+2)=4σ12=c12

-(u1+v2)=5-(0+2)=3σ23=c23

-(u2+v3)=7-(2+3)=2σ24=c24-(u2+v4)=5-(2+4)=-1σ31=c31

-(u3+v1)=7-(4+2)=1σ33=c33

-(u3+v3)=5-(4+3)=-2收點發(fā)點B1B2B3B4發(fā)量A165344A244756A376583收量243413204313

u1=0

u2=2

u3=4V1=2(4)(3)(2)(-1)(1)(-2)V2=2V3=3V4=4收點發(fā)點B1B2B3B4發(fā)量A165344A244756A376583收量243413空格的檢驗數(shù)204313(4)(3)(2)(-1)(1)(-2)存在檢驗數(shù)<0，上述調(diào)運方案不是最優(yōu)選擇空格檢驗數(shù)負(fù)數(shù)且最小(A3B3)調(diào)整，奇數(shù)頂點的運量中取最小運量=min(3,3)=3收點發(fā)點B1B2B3B4發(fā)量A165344A244756A376583收量243413204313(4)(3)(2)(-1)(1)(-2)3040新的調(diào)運方案收點發(fā)點B1B2B3B4發(fā)量A165344A244756A376583收量2434132043041、給出運輸問題的初始基可行解（初始調(diào)運方案）

1）最小元素法3146332)沃格爾法列罰數(shù)行罰數(shù)25130116213012321212017635200126

314331σ11=

c11-c13+c23-c21=3-3+2-1=12、解的最優(yōu)性檢驗

1)閉回路法126

3

3413σ12=

c12-c14+c34-c34=11-10+5-4=26

33413121σ22=

c22-c23+c13-c14+c34-c34=9-2+3–10+5-4=16

3

3413121-1σ24=

c24-c23+c13-c14=8-2+3-10=-163

3413121-110σ31=

c31-c21+c23-c13+c14-c34=7-1+2–3+10-5=10633413121-11012σ33=

c33-c13+c14-c34=10-3+10-5=12121-11012因為σ24=-1<0，所以可行解不是最優(yōu)解所以要重新調(diào)整，尋找另一可行解minz=3x11+11x12+3x13+10x14+x21+9x22+2x23+8x24

+7x31+4x32+10x33+5x34x11+x12+x13+x14=7x21+x22+x23+x24=4x31+x32+x33+x34=9x11+x21+x31=3x12+x22+x32=6x13+x23+x33=5x14+x24+x34=6xij≥0,i=1,2,3;j=1,2,3,4設(shè)u1、u2、u3、v1、v2、v3、v4分別表示對偶變量2)對偶變量法（位勢法）u1u2u3v1v2v3v4對偶變量法（位勢法）63

34130310-1-529121-11012vj

ui基變量：cij=ui+vj非基變量：σij=cij–(ui+vj)3、解的改進(jìn)（閉回路法）

334136+Δ-Δ+Δ-ΔΔ=1413x24521x231

52-14、再進(jìn)行檢驗3351261912022因為σij

≥0，所以此運輸方案是最優(yōu)方案，而σ11=0說明還有另一最優(yōu)解3.2產(chǎn)銷不平衡運輸問題

1.一般產(chǎn)銷不平衡運輸問題1)總產(chǎn)量>總銷量假想一銷地Bn+1，令銷量為

,運價c=0總產(chǎn)量>總銷量

AAA銷量

B11B2

B33

3

12

3

11

11

2

5

22

6

7

1

33

43

5

B4

4

9

5

6

產(chǎn)量

8

5

9

B5

0

0

0

4

43542222)總產(chǎn)量<總銷量假想一產(chǎn)地Am+1，令產(chǎn)量為，運價c=02.帶彈性需求的產(chǎn)銷不平衡運輸問題

需求地化肥廠B1B2B3B4產(chǎn)量A11613221750A21413191560A3192023—50最低需求最高需求3050707003010不限

B1B1′B2B3B4B4′產(chǎn)量A116161322171750A214141319151560A319192023MM50A4M0M0M050需求量30207030105021050200302030103020（海南大學(xué)2021年研究生）1、甲、乙、丙三個地區(qū)每年分別需要農(nóng)用化肥320、250、350萬噸，由A、B兩個化肥廠負(fù)責(zé)供應(yīng)。已知化肥年供應(yīng)量為A廠400萬噸，B廠450萬噸，由化肥廠到各地區(qū)的單位運價（萬元/萬噸）見下表。（18分）

甲乙丙A151822B212516需求大于產(chǎn)量，經(jīng)協(xié)商平衡，甲地區(qū)供應(yīng)量可減少0至30萬噸，乙地區(qū)需求量應(yīng)全部滿足，丙地區(qū)供應(yīng)量不少于270萬噸。試求將供應(yīng)量分配完又使總運費最低的調(diào)運方案。（只需要列出線性規(guī)劃模型，不要求計算）4.3.3兩種特殊的情況(1)某供應(yīng)地不能供應(yīng)某銷地例：有一批物資在三個供應(yīng)點，供應(yīng)給四個需求點，運價如表所示，第三供應(yīng)點不能向第四需求點運送該物資，求總運費最少調(diào)運方案。對策：在對應(yīng)的運價表格中，運價做+∞處理（一般用M表示）。(2)某供應(yīng)地至少供應(yīng)某銷地量A例：有一批物資在三個供應(yīng)點，供應(yīng)給四個需求點，運價如表所示，第A3供應(yīng)點必須調(diào)撥20單位物資給需求點B2，求總運費最少的調(diào)運方案。B1B2B3B4產(chǎn)量A1A2A3161419131320221923171516506050銷售量30705010對策：在對應(yīng)供應(yīng)地和需求地，同時減去A。B1B2B3B4產(chǎn)量A1A2A3161419131320221923171516506030(50-20)銷售量3050(70-20)5010表上作業(yè)法計算中的問題：（1）若運輸問題的某一基可行解有多個非基變量的檢驗數(shù)為負(fù)（對偶變量法），在繼續(xù)迭代時，取它們中任一變量為換入變量均可使目標(biāo)函數(shù)值得到改善，但通常取σij<0中最小者對應(yīng)的變量為換入變量。（2）多個最優(yōu)解

產(chǎn)銷平衡的運輸問題必定存最優(yōu)解。如果非基變量的σij＝0，則該問題有多個最優(yōu)解。4、再進(jìn)行檢驗335126(0)(2)(2)(1)(9)(12)因為σij≥0，得到最優(yōu)方案：X13=5，X14=2，X21=3，X24=1，X32=6，X34=3總運費=3*5+10*2+1*3+8*1+4*6+5*3=85(元)4、再進(jìn)行檢驗335126(0)(2)(2)(1)(9)(12)2031得到另一最優(yōu)方案：X11=2，X13=5，X21=1，X24=3，X32=6，X34=3總運費=3*2+5*3+1*1+8*3+4*6+5*3=85（元）另外最優(yōu)解4、再進(jìn)行檢驗335126(0)(2)(2)(1)(9)(