運(yùn)籌學(xué)管理運(yùn)籌學(xué)講義：運(yùn)輸問題

運(yùn)籌帷幄之中決勝千里之外運(yùn)籌學(xué)課件運(yùn)輸問題1第三章運(yùn)輸問題運(yùn)輸問題是線性規(guī)劃問題的特例。產(chǎn)地：貨物發(fā)出的地點(diǎn)。銷地：貨物接收的地點(diǎn)。產(chǎn)量：各產(chǎn)地的可供貨量。銷量：各銷地的需求數(shù)量。運(yùn)輸問題就是研究如何組織調(diào)運(yùn)，既滿足各銷地的需求，又使總運(yùn)費(fèi)最小。2第一節(jié)運(yùn)輸模型某飲料在國內(nèi)有三個(gè)生產(chǎn)廠，分布在城市A1、A2、A3,其一級(jí)承銷商有4個(gè)，分布在城市B1、B2、B3、B4，已知各廠的產(chǎn)量、各承銷商的銷售量及從Ai到Bj的每噸飲料運(yùn)費(fèi)為Cij，為發(fā)揮集團(tuán)優(yōu)勢(shì)，公司要統(tǒng)一籌劃運(yùn)銷問題，求運(yùn)費(fèi)最小的調(diào)運(yùn)方案。

一、運(yùn)輸問題舉例

銷地產(chǎn)地B1B2B3B4產(chǎn)量A163255A275842A332973銷量23143第一節(jié)運(yùn)輸模型(1)決策變量。設(shè)從Ai到Bj的運(yùn)輸量為xij，(2)目標(biāo)函數(shù)minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34

(3)約束條件。產(chǎn)量之和等于銷量之和,故要滿足：供應(yīng)平衡條件x11+x12+x13+x14=5x21+x22+x23+x24=2x31+x32+x33+x34=3銷售平衡條件x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4非負(fù)性約束

xij≥0(i=1,2,3；j=1,2,3,4)

運(yùn)輸問題的LP模型

4第一節(jié)運(yùn)輸模型銷地產(chǎn)地二、表式運(yùn)輸模型A1A2…Am產(chǎn)量a1a2…amB1B2…Bn銷地b1b2…bnc11c12…c1nc21

c22…c2n…………cm1cm2…cmn

x11x12x1nx21x22x2nxm1xm2xmn5第一節(jié)運(yùn)輸模型產(chǎn)銷平衡三、運(yùn)輸問題的三種類型

6第一節(jié)運(yùn)輸模型產(chǎn)大于銷7第一節(jié)運(yùn)輸模型產(chǎn)小于銷8第二節(jié)表上作業(yè)法表上作業(yè)法適合于產(chǎn)銷平衡的運(yùn)輸問題求解步驟：找出初始方案（初始基可行解）：在mn維產(chǎn)銷平衡表上給出m+n-1個(gè)數(shù)字。

最優(yōu)性檢驗(yàn)：計(jì)算各非基變量的檢驗(yàn)數(shù)，當(dāng)ij0最優(yōu)。方案調(diào)整與改進(jìn)：確定進(jìn)基變量和離基變量，找出新的基可行解。9第二節(jié)表上作業(yè)法最小元素法“就近運(yùn)給”，從單位運(yùn)價(jià)表中最小運(yùn)價(jià)開始確定供銷關(guān)系，逐次挑選最小元素，安排運(yùn)量min{ai,bj}。最大差額法不能按最小運(yùn)費(fèi)就近供應(yīng)，就考慮次小運(yùn)費(fèi)。各行(各列)的最小運(yùn)費(fèi)與次小運(yùn)費(fèi)之差稱為行差(列差)。對(duì)最大差額處就采用最小運(yùn)費(fèi)調(diào)運(yùn)。一、確定初始方案10第二節(jié)表上作業(yè)法從單位運(yùn)價(jià)表中逐次挑選最小元素，安排運(yùn)量min{ai,bj}。然后，劃去該元素所在行或列：當(dāng)產(chǎn)大于銷，劃去該元素所在列；當(dāng)產(chǎn)小于銷，劃去該元素所在行。最小元素法銷地產(chǎn)地B1B2B3B4產(chǎn)量A163255A275842A332973銷量2314130222初始基可行解：x11=2,x13=1,x14=2,x24=2,x31=0,x32=3，Z=3811第二節(jié)表上作業(yè)法判別方法是計(jì)算非基變量的檢驗(yàn)數(shù)：ij=cij–CBPij’=cij–CBB-1Pij運(yùn)輸問題的目標(biāo)函數(shù)要求為最小，即當(dāng)ij0視為最優(yōu)。位勢(shì)法計(jì)算檢驗(yàn)數(shù)ij=cij–CBPij’=cij–CBB-1Pijij=cij–(ui+vj)

ui代表產(chǎn)地Ai的位勢(shì)量，vj代表銷地Bj的位勢(shì)量?；兞康臋z驗(yàn)數(shù)為0，即ij=cij–ui–vj=0，并令u1=0，計(jì)算各行各列的位勢(shì)量。二、最優(yōu)性檢驗(yàn)12第二節(jié)表上作業(yè)法基變量的檢驗(yàn)數(shù)ij=cij–ui–vj=0，即cij=ui+vj，且令u1=0，計(jì)算位勢(shì)量ui和vj位勢(shì)法銷地產(chǎn)地B1B2B3B4產(chǎn)量A162321525A2758422A33023973銷量2314uivj0625-1-3513第二節(jié)表上作業(yè)法計(jì)算非基變量的檢驗(yàn)數(shù)ij=cij–ui–vj位勢(shì)法（續(xù)）銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA1623215250A2758422-1A33023973-3銷量2314vj6525-2217105非基變量x12的檢驗(yàn)數(shù)12=c12–u1–v2=-2，即讓非基變量x12從0增到1，可使總運(yùn)費(fèi)減少2個(gè)單位。14第二節(jié)表上作業(yè)法確定進(jìn)基變量檢查非基變量xij的檢驗(yàn)數(shù)ij，按min{ij|

ij<0}=lk確定xlk進(jìn)基。確定離基變量非基變量xlk進(jìn)基之后，能讓它的運(yùn)量增加多少呢？就要求它所在行和列的運(yùn)量保持產(chǎn)銷平衡。保持產(chǎn)銷平衡的方法是閉回路法。閉回路法：以進(jìn)基變量xlk所在格為始點(diǎn)和終點(diǎn)，其余頂點(diǎn)均為基變量的封閉回路。閉回路的畫法：從進(jìn)基變量xlk所在格開始，用水平或垂直線向前劃，每碰到一個(gè)基變量格轉(zhuǎn)90o，繼續(xù)前進(jìn)，直到返回始點(diǎn)。奇偶點(diǎn)：始點(diǎn)是偶點(diǎn)，依次奇偶相間標(biāo)注；偶點(diǎn)標(biāo)“+”，表示運(yùn)量增加量；奇點(diǎn)標(biāo)“-”，表示運(yùn)量減少量。調(diào)整量：最小可減少的運(yùn)量，即奇點(diǎn)運(yùn)量的最小值。奇點(diǎn)運(yùn)量的最小值所在格的基變量離基。三、改進(jìn)的方法（閉回路調(diào)整法）15第二節(jié)表上作業(yè)法x12進(jìn)基最小調(diào)整量為2，x11離基銷地產(chǎn)地B1B2B3B4產(chǎn)量A1623x1221525A2758422A33023973銷量2314+-+-16第二節(jié)表上作業(yè)法非最優(yōu)方案的調(diào)整所有偶點(diǎn)的值都加上調(diào)整量；所有奇點(diǎn)的值都減去調(diào)整量；獲得一個(gè)新的運(yùn)輸方案。銷地產(chǎn)地B1B2B3B4產(chǎn)量A16

321525A2758422A33

2

973銷量2314基可行解：x12=2,x13=1,x14=2,x24=2,x31=2,x32=1，Z=342

03

22117第二節(jié)表上作業(yè)法基變量的檢驗(yàn)數(shù)ij=cij–ui–vj=0，且令u1=0，計(jì)算位勢(shì)量ui和vj四、最優(yōu)性檢驗(yàn)銷地產(chǎn)地B1B2B3B4產(chǎn)量A163221525A2758422A33221973銷量2314uivj04-1-1325所有非基變量xij的檢驗(yàn)數(shù)ij=cij

–ui–vj≥0，即得最優(yōu)解。18第三節(jié)產(chǎn)銷不平衡問題產(chǎn)銷平衡的運(yùn)輸問題采取表上作業(yè)法求解。產(chǎn)銷不平衡的運(yùn)輸問題需劃成產(chǎn)銷平衡問題再求解。產(chǎn)大于銷：虛設(shè)一個(gè)銷地Bk(多于物資在產(chǎn)地存儲(chǔ))，其運(yùn)價(jià)為0，銷量(存儲(chǔ)量)為產(chǎn)銷量之差bk=ai-bj。產(chǎn)小于銷：虛設(shè)一個(gè)產(chǎn)地Al(不足物資的脫銷量)，其運(yùn)價(jià)為0，產(chǎn)量(脫銷量)為銷產(chǎn)量之差ak=bj

-

ai

。19第三節(jié)產(chǎn)銷不平衡問題增加一個(gè)銷地一、產(chǎn)大于銷銷地產(chǎn)地B1B2B3產(chǎn)量A159215A231718A362817銷量181216銷地產(chǎn)地B1B2B3產(chǎn)量A159215A231718A362817銷量18121650-46B400045046505020第三節(jié)產(chǎn)銷不平衡問題初始基可行解銷地產(chǎn)地B1B2B3B4產(chǎn)量A1592015A2317018A3628017銷量1812164121561214

初始基可行解：x13=15,x21=6,x22=12,x31=12,x33=1,x34=4，Z=14021第三節(jié)產(chǎn)銷不平衡問題最優(yōu)性檢驗(yàn)銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA159215015A2361127018A36122810417銷量1812164vj0260-63-2511623-2非基變量x32的檢驗(yàn)數(shù)32=-2，即讓非基變量x32進(jìn)基。22第三節(jié)產(chǎn)銷不平衡問題閉回路調(diào)整x32進(jìn)基最小調(diào)整量為12，x31離基銷地產(chǎn)地B1B2B3B4產(chǎn)量A159215015A2361127018A36122x32810417銷量1812164-+-+23第三節(jié)產(chǎn)銷不平衡問題非最優(yōu)方案的調(diào)整所有偶點(diǎn)的值都加上調(diào)整量；所有奇點(diǎn)的值都減去調(diào)整量。基可行解：x13=15,x21=18,x31=0,x32=12,x31=1,x34=4，Z=34銷地產(chǎn)地B1B2B3B4產(chǎn)量A159215015A2317018A362810417銷量181216461212

180

1224第三節(jié)產(chǎn)銷不平衡問題基變量的檢驗(yàn)數(shù)ij=cij–ui–vj=0，且令u1=0，計(jì)算位勢(shì)量ui和vj最優(yōu)性檢驗(yàn)所有非基變量xij的檢驗(yàn)數(shù)ij=cij–ui–vj≥0，即得最優(yōu)解。銷地產(chǎn)地B1B2B3B4產(chǎn)量uiA159215015A231817018A360212810417銷量1812164vj0260-4-63513623225第三節(jié)產(chǎn)銷不平衡問題增加一個(gè)產(chǎn)地二、產(chǎn)小于銷銷地產(chǎn)地B1B2B3產(chǎn)量A141210A234312銷量8105銷地產(chǎn)地B1B2B3產(chǎn)量A141210A234312A3銷量810523-2200012223232326第三節(jié)產(chǎn)銷不平衡問題初始基可行解銷地產(chǎn)地B1B2B3產(chǎn)量A141210A234312A30001銷量8105100571

初始基可行解：x12=10,x13=0,x21=7,x23=5,x31=1，Z=4627第三節(jié)產(chǎn)銷不平衡問題最優(yōu)性檢驗(yàn)銷地產(chǎn)地B1B2B3產(chǎn)量uiA141102010A23743512A301001銷量8105vj01212-22210檢驗(yàn)數(shù)ij≥0，得最優(yōu)解:x12=10,x13=0,x21=7,x23=5,x31=1，Z=46由于非基變量x33的檢驗(yàn)數(shù)33=0，為多最優(yōu)解。讓x33進(jìn)基,x31離基,得另一最優(yōu)解:x12=10,x13=0,x21=8,x23=4,x33=128第四節(jié)運(yùn)輸模型的應(yīng)用短缺資源分配，“產(chǎn)小于銷”，需注意產(chǎn)銷配比問題。上例x12=10,x13=0,x21=7,x23=5,x31=1，表示銷地B1脫銷1個(gè)單位；然而x12=10,x13=0,x21=8,x23=4,x33=1，則表示銷地B3脫銷1個(gè)單位；但銷地B3的銷量為5，本身就很少，不允許脫銷，如何處理呢？自來水分配問題：水價(jià)90元/kt，管理費(fèi)45元/kt，引水費(fèi)如下表：一、短缺資源的分配問題供區(qū)水庫甲乙丙丁供水量kt/dA1613221750B1413191560C192023--50最低需求kt/d3070010最高需求kt/d507030不限如何分配供水量，保障各區(qū)最低需求，獲利最大？29第四節(jié)運(yùn)輸模型的應(yīng)用利潤=收入-成本，收入最大，成本最小，則利潤最大。收入：每天供水總量若能全部售出，每天總收入則能達(dá)到最大。丁區(qū)最高需求不限，每天總供水量能全售出。每天供水總量是一常數(shù)，水價(jià)也是常數(shù)，則每天總收入也是常數(shù)。每天總收入是常數(shù)，與水量分配無關(guān)，可以不與考慮。成本：各區(qū)管理費(fèi)相同45元/kt，每天售水總量是一常數(shù)，則管理費(fèi)也是常數(shù)。各區(qū)引水費(fèi)不同，如果總的引水費(fèi)達(dá)到最小，總成本則最低。如何分配水量，既滿足最低需求，又使總的引水費(fèi)最低？最大需求量：供水總量=50+60+50=160，四區(qū)最低需求量=30+70+10=110，故丁區(qū)最大需求量160-110+10=60。四區(qū)最大需求=50+70+30+60=210，比供水總量160多50，則是一個(gè)產(chǎn)小于銷的不平衡問題。分析30第四節(jié)運(yùn)輸模型的應(yīng)用產(chǎn)小于銷的運(yùn)輸問題化為平衡問題，虛設(shè)水庫D，供水量50。各區(qū)的最低需求為基本需求，不允許脫銷，不能由虛設(shè)水庫D供水，故單位引水費(fèi)（運(yùn)費(fèi)）為M>0。各區(qū)的最大需求與最低需求的差為額外需求，可以由虛設(shè)水庫D供水，故單位引水費(fèi)（運(yùn)費(fèi)）為0。供區(qū)水庫供水量A50B60C50甲1甲2乙丙丁1丁216161322171714141319151519192023MM銷量302070301050DM0M0M05031第四節(jié)運(yùn)輸模型的應(yīng)用用表上作業(yè)法求得最優(yōu)方案供區(qū)水庫甲1甲2乙丙丁1丁2供水量A5050B20103060C3020050D302050銷量302070301050最優(yōu)分配方案：水庫A向乙區(qū)供水50，水庫B分別向乙區(qū)、丁區(qū)供水20和40，水庫C向甲區(qū)供水50，不給丙區(qū)供水。最小引水費(fèi)：1350+1320+15(10+30)+19(30+20)=2460引水管理費(fèi)：45(50+60+50)=7200總成本：2460+7200=9600總收入：90(50+60+50)=14400最大獲利：14400-9600=474032第四節(jié)運(yùn)輸模型的應(yīng)用產(chǎn)地與銷地之間存在轉(zhuǎn)運(yùn)站。面粉轉(zhuǎn)運(yùn)問題：三個(gè)面粉加工廠，兩個(gè)糕點(diǎn)生產(chǎn)廠，兩個(gè)中轉(zhuǎn)站。二、資源轉(zhuǎn)運(yùn)問題終點(diǎn)始點(diǎn)面粉廠中轉(zhuǎn)站糕點(diǎn)廠生產(chǎn)能力A1A2A3T1T2B1B2面粉廠A1323-683A242521374A3-2321143中轉(zhuǎn)站T1352625T2-327-2糕點(diǎn)廠B