運輸問題模型ppt課件

1、.杭州電子科技大學(xué)杭州電子科技大學(xué) 數(shù)學(xué)教研室數(shù)學(xué)教研室杭州電子科技大學(xué)杭州電子科技大學(xué) 沈沈 灝灝二二0一一0年四月年四月.運輸問題的一般描述運輸問題的一般描述設(shè)某種物資有設(shè)某種物資有m個產(chǎn)地個產(chǎn)地A1,A2,Am，和和n個銷地個銷地B1,B2,Bn,其中其中Ai的產(chǎn)量的產(chǎn)量為為ai,Bjai,Bj的銷量為的銷量為bjbj，產(chǎn)地，產(chǎn)地Ai運往銷地運往銷地Bj的單位運價的單位運價Cij,i=1,2,m;j=1,2,n.求盡可能滿足銷地需求且總費用最小的求盡可能滿足銷地需求且總費用最小的運輸方案。運輸方案。.n運輸問題的數(shù)學(xué)模型可以分以下運輸問題的數(shù)學(xué)模型可以分以下3種情種情況討論：況討論：n1

2、. 產(chǎn)銷平衡問題產(chǎn)銷平衡問題n2. 銷大于產(chǎn)問題銷大于產(chǎn)問題n產(chǎn)大于銷問題產(chǎn)大于銷問題ijx解：設(shè)產(chǎn)地Ai運往銷地Bj的運量為.1. 1.產(chǎn)銷平衡問題的數(shù)學(xué)模型產(chǎn)銷平衡問題的數(shù)學(xué)模型n產(chǎn)銷平衡時，產(chǎn)銷平衡時，n各個產(chǎn)地的物資總和正好滿足所有各個產(chǎn)地的物資總和正好滿足所有銷地的需求，運輸問題的數(shù)學(xué)模型銷地的需求，運輸問題的數(shù)學(xué)模型為為jjiiba.njmixnjbxmiaxtsxczijnijijnjiijninjijij, 1;, 1, 0, 1, 1,. .min1111.2.2. 銷大于產(chǎn)問題的數(shù)學(xué)模型銷大于產(chǎn)問題的數(shù)學(xué)模型n銷大于產(chǎn)時，銷大于產(chǎn)時，n各個銷地的需求不一定能夠得到各個銷地的

3、需求不一定能夠得到滿足，運輸問題的數(shù)學(xué)模型為滿足，運輸問題的數(shù)學(xué)模型為jjiiba.njmixnjbxmiaxtsxczijnijijnjiijninjijij, 1;, 1, 0, 1, 1,. .min1111.2. 2. 產(chǎn)大于銷問題的數(shù)學(xué)模型產(chǎn)大于銷問題的數(shù)學(xué)模型n銷大于產(chǎn)時，銷大于產(chǎn)時，n各個銷地的需求一定能夠得到滿足，各個銷地的需求一定能夠得到滿足，但各個產(chǎn)地的物資不一定全部運走。但各個產(chǎn)地的物資不一定全部運走。運輸問題的數(shù)學(xué)模型為運輸問題的數(shù)學(xué)模型為jjiiba.njmixnjbxmiaxtsxczijnijijnjiijninjijij, 1;, 1, 0, 1, 1,. .m

4、in1111.運輸問題本質(zhì)是一個線性規(guī)劃問題運輸問題本質(zhì)是一個線性規(guī)劃問題n運輸問題變量比較多，系數(shù)矩陣為運輸問題變量比較多，系數(shù)矩陣為0-1矩陣，其中大部分元素為零。計算運矩陣，其中大部分元素為零。計算運輸問題我們有比單純形法更好的專門輸問題我們有比單純形法更好的專門求解運輸問題的算法。求解運輸問題的算法。.產(chǎn)銷平衡運輸問題的求解產(chǎn)銷平衡運輸問題的求解n定理 產(chǎn)銷平衡運輸問題一定產(chǎn)銷平衡運輸問題一定存在最優(yōu)解存在最優(yōu)解 。.產(chǎn)銷平衡運輸問題的產(chǎn)銷平衡運輸問題的Lingo模型模型nMODEL:nsets:nrow/1.m/:a;narrange/1.n/:b;nlink(row,arrange

5、):c,x;nendsetsndata:na=a(1) a(2) a(m);nb=b(1) b(2) b(n);.nC=c(1,1) c(1,2) c(1,n), c(2,1) c(2,2) c(2,n), c(m,1) c(m,2) c(m,n);nenddatanOBJmin=sum(link(i,j):c(i,j)*x(i,j);nfor(row(i):sum(arrange(j):x(i,j)=a(i););nfor(arrange(j):sum(row(i):x(i,j)=b(j););nfor(link(i,j):x(i,j)=0;);nEND.n產(chǎn)銷不平衡運輸問題也有類似的產(chǎn)銷不

6、平衡運輸問題也有類似的Lingo模型模型.產(chǎn)銷平衡運輸問題的初始解產(chǎn)銷平衡運輸問題的初始解n1. 西北角法西北角法n在運價表的西北角選擇運量和銷量中在運價表的西北角選擇運量和銷量中的較小數(shù)作為運量（的較小數(shù)作為運量（初始基變量初始基變量），），每確定一個初始基變量后，劃去需求每確定一個初始基變量后，劃去需求變成零的剩余列元素或劃去運量變成變成零的剩余列元素或劃去運量變成零的剩余行元素。零的剩余行元素。.B1B2B3B4產(chǎn)量A13 2 9 10 7 9,6A2 1 3 4 2 5A3 8 4 2 5 7銷量 3 ,0 8 4 6.B1B2B3B4產(chǎn)量A13 26 9 10 7 9,6,0A2 1

7、 3 4 2 5A3 8 4 2 5 7銷量 3 ,0 8,2 4 6.B1B2B3B4產(chǎn)量A13 26 9 10 7 9,6,0A2 12 3 4 2 5,3A3 8 4 2 5 7銷量 3 ,0 8,2,0 4 6.B1B2B3B4產(chǎn)量A13 26 9 10 7 9,6,0A2 12 3 3 4 2 5,3,0A3 8 4 2 5 7銷量 3 ,0 8,2,0 4,1 6.B1B2B3B4產(chǎn)量A13 26 9 10 7 9,6,0A2 12 3 3 4 2 5,3,0A3 8 41 2 5 7,6銷量 3 ,0 8,2,0 4,1,0 6.填上填上x33=1后后,自然少去一列自然少去一列(

8、第第3列列),這時不要再去掉第這時不要再去掉第3行。行。n注意到每填一個數(shù)據(jù)恰好減少一注意到每填一個數(shù)據(jù)恰好減少一行或一列。行或一列。.B1B2B3B4產(chǎn)量A13 26 9 10 7 9,6,0A2 12 3 3 4 2 5,3,0A3 8 41 26 5 7,6銷量 3 ,0 8,2,0 4,1,0 6.總共填寫總共填寫m+n個數(shù)據(jù)個數(shù)據(jù)n填上去的填上去的m+n個數(shù)據(jù)為基變個數(shù)據(jù)為基變量量.產(chǎn)銷平衡運輸問題的初始解產(chǎn)銷平衡運輸問題的初始解n2. 最小元素法最小元素法n選擇運價表中最小運價，運量和銷量選擇運價表中最小運價，運量和銷量中的較小數(shù)作為運量（中的較小數(shù)作為運量（初始基變量初始基變量）

9、，），每確定一個初始基變量后，劃去需求每確定一個初始基變量后，劃去需求變成零的剩余列元素或劃去運量變成變成零的剩余列元素或劃去運量變成零的剩余行元素。零的剩余行元素。.B1B2B3B4產(chǎn)量A1 2 9 10 7 9A23 1 3 4 2 5，2A3 8 4 2 5 7銷量 3 ,0 8 4 6.B1B2B3B4產(chǎn)量A1 2 9 10 7 9A23 1 3 4 2 5，2A3 8 44 2 5 7，3銷量 3 ,0 8 4，0 6.B1B2B3B4產(chǎn)量A1 2 9 10 7 9A23 1 3 42 2 5,2,0A3 8 44 2 5 7，3銷量 3 ,0 8 4，0 6,4.B1B2B3B4產(chǎn)

10、量A1 2 9 10 7 9A23 1 3 42 2 5,2,0A3 83 44 2 5 7,3,0銷量 3 ,0 8,5 4，0 6,4.B1B2B3B4產(chǎn)量A1 2 9 104 7 9,5A23 1 3 42 2 5,2,0A3 83 44 2 5 7,3,0銷量 3 ,0 8,5 4，0 6,4,0.填上填上x14=4后后,第第4列自然列自然被去掉被去掉n記住每填一個數(shù)據(jù)減少一記住每填一個數(shù)據(jù)減少一行或一列。行或一列。.B1B2B3B4產(chǎn)量A1 25 9 104 7 9,5A23 1 3 42 2 5,2,0A3 83 44 2 5 7,3,0銷量 3 ,0 8,5 4，0 6,4,0.

11、3. 3. 位勢法求檢驗數(shù)位勢法求檢驗數(shù)n對每個基變量對每個基變量xij，計算，計算ui和和vj，使，使 ui+vj=cij 其中其中u1=0u1=0.B1B2V2=9B3B4V4=7產(chǎn)量A1u1=0 25 9 104 7 9,5A23 1 3 42 2 5,2,0A3 83 44 2 5 7,3,0銷量 3 ,0 8,5 4，0 6,4,0.B1B2V2=9B3B4V4=7產(chǎn)量A1u1=0 25 9 104 7 9,5A2u2=-53 1 3 42 2 5,2,0A3u3=-5 83 44 2 5 7,3,0銷量 3 ,0 8,5 4，0 6,4,0.B1v1=6B2v2=9B3v3=7B4

12、V4=7產(chǎn)量A1u1=0 25 9 104 7 9,5A2u2=-53 1 3 42 2 5,2,0A3u3=-5 83 44 2 5 7,3,0銷量 3 ,0 8,5 4，0 6,4,0.再計算非基變量檢驗數(shù)再計算非基變量檢驗數(shù)nij=cij-（ui+vj）.B1v1=6B2v2=9B3v3=7B4V4=7產(chǎn)量A1u1=0-4 25 93 104 7 9,5A2u2=-53 1-1 3 2 42 2 5,2,0A3u3=-57 83 44 23 5 7,3,0銷量 3 ,0 8,5 4，0 6,4,0.11=-4 x1111=-4 x11每增加一個單每增加一個單位，目標(biāo)函數(shù)可以減少位，目標(biāo)函

13、數(shù)可以減少4 4個單位。個單位。目標(biāo)可以減少，說明當(dāng)前目標(biāo)可以減少，說明當(dāng)前解不是最優(yōu)解解不是最優(yōu)解.閉回路法調(diào)整閉回路法調(diào)整n選選x11進基，找到閉回路進基，找到閉回路n x11 x14 4-n x21 x24 2+ n 3-.閉回路法調(diào)整閉回路法調(diào)整n為了保證所有為了保證所有xij非負，非負，x11最多增加最多增加3。n取取x11=3n x11 +3 x14 4-3n x21 x24 2+3 n 3-3.B1B2B3B4產(chǎn)量A1u1=03 25 93 101 7 9,5A2 1-1 3 2 45 2 5,2,0A37 83 44 23 5 7,3,0銷量 3 ,0 8,5 4，0 6,4,

14、0.重新計算檢驗數(shù)重新計算檢驗數(shù).B1v1=2B2v2=9B3B4v4=7產(chǎn)量A1u1=03 25 93 101 7 9,5A2u2=-5 1-1 3 2 45 2 5,2,0A3u3=-57 83 44 23 5 7,3,0銷量 3 ,0 8,5 4，0 6,4,0.B1v1=2B2v2=9B3V3=7B4v4=7產(chǎn)量A1u1=03 25 93 101 7 9,5A2u2=-54 1-1 3 2 45 2 5,2,0A3u3=-511 83 44 23 5 7,3,0銷量 3 ,0 8,5 4，0 6,4,0.22=-1 x2222=-1 x22每增加一個單每增加一個單位，目標(biāo)函數(shù)可以減少位

15、，目標(biāo)函數(shù)可以減少1 1個單位。個單位。目標(biāo)可以減少，說明當(dāng)前目標(biāo)可以減少，說明當(dāng)前解不是最優(yōu)解解不是最優(yōu)解.閉回路法調(diào)整閉回路法調(diào)整n選選x22進基，找到閉回路進基，找到閉回路n x12 5- x14 1 +n x22 + x24 5- .X22最多增加最多增加5n x12 5-5 x14 1 +5n x22 + 5 x24 5-5 .X22進基，進基，x12和和x24經(jīng)過調(diào)整同時變成經(jīng)過調(diào)整同時變成零。但是要注意只有一個變量出基。零。但是要注意只有一個變量出基。n例如：例如：令令x12x12出基出基n得調(diào)整后的運輸表為：得調(diào)整后的運輸表為：.B1B2B3B4產(chǎn)量A1u1=03 2 93 1

16、06 7 9,5A24 15 3 2 40 2 5,2,0A311 83 44 23 5 7,3,0銷量 3 ,0 8,5 4，0 6,4,0.重新計算檢驗數(shù)重新計算檢驗數(shù).B1v1=2B2B3B4v4=7產(chǎn)量A1u1=03 2 93 106 7 9,5A2u2=-54 15 3 2 40 2 5,2,0A311 83 44 23 5 7,3,0銷量 3 ,0 8,5 4，0 6,4,0.B1v1=2B2v2=8B3B4v4=7產(chǎn)量A1u1=03 2 93 106 7 9,5A2u2=-54 15 3 2 40 2 5,2,0A3u3=-411 83 44 23 5 7,3,0銷量 3 ,0

17、8,5 4，0 6,4,0.B1v1=2B2v2=8B3V3=6B4v4=7產(chǎn)量A1u1=03 2 1 94 106 7 9,5A2u2=-54 15 3 3 40 2 5,2,0A3u3=-410 83 44 22 5 7,3,0銷量 3 ,0 8,5 4，0 6,4,0.所有非基變量檢驗數(shù)均非所有非基變量檢驗數(shù)均非負，當(dāng)前解為負，當(dāng)前解為最優(yōu)解最優(yōu)解n最優(yōu)解為：最優(yōu)解為： X11X11* *=3=3，x14x14* *=6=6，x22x22* *=5=5，x32x32* *=3=3，x33x33* *=4=4，其余，其余xijxij* *=0=0n最優(yōu)目標(biāo)值為最優(yōu)目標(biāo)值為nZ Z* *=3

18、=32+62+67+57+53+33+34+44+42=832=83.運輸問題數(shù)學(xué)模型的應(yīng)用實例運輸問題數(shù)學(xué)模型的應(yīng)用實例n設(shè)某制造企業(yè)根據(jù)合同要求，從當(dāng)年起需連續(xù)設(shè)某制造企業(yè)根據(jù)合同要求，從當(dāng)年起需連續(xù)三年在年末提供三年在年末提供3套型號規(guī)格相同的大型設(shè)備，套型號規(guī)格相同的大型設(shè)備，已知該廠的生產(chǎn)能力及生產(chǎn)成本如下表所示：已知該廠的生產(chǎn)能力及生產(chǎn)成本如下表所示：.生產(chǎn)能力與生產(chǎn)成本表生產(chǎn)能力與生產(chǎn)成本表n年度年度 正常生產(chǎn)可正常生產(chǎn)可 加班生產(chǎn)可加班生產(chǎn)可 正常生產(chǎn)正常生產(chǎn) 完成設(shè)備數(shù)完成設(shè)備數(shù) 完成設(shè)備數(shù)完成設(shè)備數(shù) 成本成本(萬萬)n第一年第一年 2 3 500n第二年第二年 4 2 60

19、0 n第三年第三年 1 3 550 設(shè)加班生產(chǎn)情況下每套設(shè)備成本比正常生產(chǎn)時高設(shè)加班生產(chǎn)情況下每套設(shè)備成本比正常生產(chǎn)時高70萬元萬元,每套設(shè)備不及時交貨積壓一年的維護費每套設(shè)備不及時交貨積壓一年的維護費用為用為40萬元。該廠現(xiàn)庫存有萬元。該廠現(xiàn)庫存有2套設(shè)備，希望第三套設(shè)備，希望第三年末完成合同要求后還能儲存年末完成合同要求后還能儲存1臺設(shè)備，問如何臺設(shè)備，問如何安排生產(chǎn)，才能使總成本最低。安排生產(chǎn)，才能使總成本最低。.解解：設(shè)設(shè)xj為初始存貨用于第為初始存貨用于第j年交貨的設(shè)備數(shù)年交貨的設(shè)備數(shù) yij為第為第i年正常生產(chǎn)用于第年正常生產(chǎn)用于第j年交貨的設(shè)備數(shù)，年交貨的設(shè)備數(shù)， zij為第為第

20、i年加班生產(chǎn)用于第年加班生產(chǎn)用于第j年交貨的設(shè)備數(shù)，年交貨的設(shè)備數(shù)， cj為初始庫存設(shè)備第為初始庫存設(shè)備第j年交貨時每臺設(shè)備維護費，年交貨時每臺設(shè)備維護費， aij為第為第i年正常生產(chǎn)到第年正常生產(chǎn)到第j年交貨的每臺設(shè)備成本年交貨的每臺設(shè)備成本費，費， bij為第為第i年加班生產(chǎn)到第年加班生產(chǎn)到第j年交貨的每臺設(shè)備成年交貨的每臺設(shè)備成本費。本費。上述生產(chǎn)計劃問題的數(shù)學(xué)模型為：上述生產(chǎn)計劃問題的數(shù)學(xué)模型為：. 3,2,1,0,0,04333124322.min3333232313133222212122111113333232223221312111312113213131313131jizyxzyzyzyxzyzyxzyxzyzzyyzzzyyyxxxtszbyaxczijijjijijijijijijjjj.記記A為正常生產(chǎn)時的費用矩陣為正常生產(chǎn)時的費用矩陣550006406000580540500