運(yùn)輸問題模型專業(yè)課堂

1、杭州電子科技大學(xué)杭州電子科技大學(xué) 數(shù)學(xué)教研室數(shù)學(xué)教研室杭州電子科技大學(xué)杭州電子科技大學(xué) 沈沈 灝灝二二0一一0年四月年四月1藤蔓課堂運(yùn)輸問題的一般描述運(yùn)輸問題的一般描述設(shè)某種物資有設(shè)某種物資有m個(gè)產(chǎn)地個(gè)產(chǎn)地a1,a2,am，和和n個(gè)銷地個(gè)銷地b1,b2,bn,其中其中ai的產(chǎn)量的產(chǎn)量為為ai,bjai,bj的銷量為的銷量為bjbj，產(chǎn)地產(chǎn)地ai運(yùn)往銷地運(yùn)往銷地bj的單位運(yùn)價(jià)的單位運(yùn)價(jià)cij,i=1,2,m;j=1,2,n.求盡可能滿足銷地需求且總費(fèi)用最小的求盡可能滿足銷地需求且總費(fèi)用最小的運(yùn)輸方案。運(yùn)輸方案。2藤蔓課堂n運(yùn)輸問題的數(shù)學(xué)模型可以分以下運(yùn)輸問題的數(shù)學(xué)模型可以分以下3種情種情況討論：

2、況討論：n1. 產(chǎn)銷平衡問題產(chǎn)銷平衡問題n2. 銷大于產(chǎn)問題銷大于產(chǎn)問題n產(chǎn)大于銷問題產(chǎn)大于銷問題ijx解：設(shè)產(chǎn)地ai運(yùn)往銷地bj的運(yùn)量為3藤蔓課堂1. 1.產(chǎn)銷平衡問題的數(shù)學(xué)模型產(chǎn)銷平衡問題的數(shù)學(xué)模型n產(chǎn)銷平衡時(shí)，產(chǎn)銷平衡時(shí)，n各個(gè)產(chǎn)地的物資總和正好滿足所有各個(gè)產(chǎn)地的物資總和正好滿足所有銷地的需求，運(yùn)輸問題的數(shù)學(xué)模型銷地的需求，運(yùn)輸問題的數(shù)學(xué)模型為為jjiiba4藤蔓課堂njmixnjbxmiaxtsxczijnijijnjiijninjijij, 1;, 1, 0, 1, 1,. .min11115藤蔓課堂2.2. 銷大于產(chǎn)問題的數(shù)學(xué)模型銷大于產(chǎn)問題的數(shù)學(xué)模型n銷大于產(chǎn)時(shí)，銷大于產(chǎn)時(shí)，n各

3、個(gè)銷地的需求不一定能夠得到各個(gè)銷地的需求不一定能夠得到滿足，運(yùn)輸問題的數(shù)學(xué)模型為滿足，運(yùn)輸問題的數(shù)學(xué)模型為jjiiba6藤蔓課堂njmixnjbxmiaxtsxczijnijijnjiijninjijij, 1;, 1, 0, 1, 1,. .min11117藤蔓課堂2. 2. 產(chǎn)大于銷問題的數(shù)學(xué)模型產(chǎn)大于銷問題的數(shù)學(xué)模型n銷大于產(chǎn)時(shí)，銷大于產(chǎn)時(shí)，n各個(gè)銷地的需求一定能夠得到滿足，各個(gè)銷地的需求一定能夠得到滿足，但各個(gè)產(chǎn)地的物資不一定全部運(yùn)走。但各個(gè)產(chǎn)地的物資不一定全部運(yùn)走。運(yùn)輸問題的數(shù)學(xué)模型為運(yùn)輸問題的數(shù)學(xué)模型為jjiiba8藤蔓課堂njmixnjbxmiaxtsxczijnijijnjii

4、jninjijij, 1;, 1, 0, 1, 1,. .min11119藤蔓課堂運(yùn)輸問題本質(zhì)是一個(gè)線性規(guī)劃問題運(yùn)輸問題本質(zhì)是一個(gè)線性規(guī)劃問題n運(yùn)輸問題變量比較多，系數(shù)矩陣為運(yùn)輸問題變量比較多，系數(shù)矩陣為0-1矩陣，其中大部分元素為零。計(jì)算運(yùn)矩陣，其中大部分元素為零。計(jì)算運(yùn)輸問題我們有比單純形法更好的專門輸問題我們有比單純形法更好的專門求解運(yùn)輸問題的算法。求解運(yùn)輸問題的算法。10藤蔓課堂產(chǎn)銷平衡運(yùn)輸問題的求解產(chǎn)銷平衡運(yùn)輸問題的求解n定理 產(chǎn)銷平衡運(yùn)輸問題一定產(chǎn)銷平衡運(yùn)輸問題一定存在最優(yōu)解存在最優(yōu)解 。11藤蔓課堂產(chǎn)銷平衡運(yùn)輸問題的產(chǎn)銷平衡運(yùn)輸問題的lingo模型模型nmodel:nsets:n

5、row/1.m/:a;narrange/1.n/:b;nlink(row,arrange):c,x;nendsetsndata:na=a(1) a(2) a(m);nb=b(1) b(2) b(n);12藤蔓課堂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););

6、nfor(link(i,j):x(i,j)=0;);nend13藤蔓課堂n產(chǎn)銷不平衡運(yùn)輸問題也有類似的產(chǎn)銷不平衡運(yùn)輸問題也有類似的lingo模型模型14藤蔓課堂產(chǎn)銷平衡運(yùn)輸問題的初始解產(chǎn)銷平衡運(yùn)輸問題的初始解n1. 西北角法西北角法n在運(yùn)價(jià)表的西北角選擇運(yùn)量和銷量中在運(yùn)價(jià)表的西北角選擇運(yùn)量和銷量中的較小數(shù)作為運(yùn)量（的較小數(shù)作為運(yùn)量（初始基變量初始基變量），），每確定一個(gè)初始基變量后，劃去需求每確定一個(gè)初始基變量后，劃去需求變成零的剩余列元素或劃去運(yùn)量變成變成零的剩余列元素或劃去運(yùn)量變成零的剩余行元素。零的剩余行元素。15藤蔓課堂b1b2b3b4產(chǎn)量a13 2 9 10 7 9,6a2 1 3

7、4 2 5a3 8 4 2 5 7銷量 3 ,0 8 4 616藤蔓課堂b1b2b3b4產(chǎn)量a13 26 9 10 7 9,6,0a2 1 3 4 2 5a3 8 4 2 5 7銷量 3 ,0 8,2 4 617藤蔓課堂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 618藤蔓課堂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 619藤蔓課堂b1b2b3b4產(chǎn)量a13 26 9 10 7 9,

8、6,0a2 12 3 3 4 2 5,3,0a3 8 41 2 5 7,6銷量 3 ,0 8,2,0 4,1,0 620藤蔓課堂填上填上x33=1后后,自然少去一列自然少去一列(第第3列列),這時(shí)不要再去掉第這時(shí)不要再去掉第3行。行。n注意到每填一個(gè)數(shù)據(jù)恰好減少一注意到每填一個(gè)數(shù)據(jù)恰好減少一行或一列。行或一列。21藤蔓課堂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 622藤蔓課堂總共填寫總共填寫m+n個(gè)數(shù)據(jù)個(gè)數(shù)據(jù)n填上去的填上去的m+n個(gè)數(shù)據(jù)為基變個(gè)數(shù)據(jù)為基變量量23藤蔓

9、課堂產(chǎn)銷平衡運(yùn)輸問題的初始解產(chǎn)銷平衡運(yùn)輸問題的初始解n2. 最小元素法最小元素法n選擇運(yùn)價(jià)表中最小運(yùn)價(jià)，運(yùn)量和銷量選擇運(yùn)價(jià)表中最小運(yùn)價(jià)，運(yùn)量和銷量中的較小數(shù)作為運(yùn)量（中的較小數(shù)作為運(yùn)量（初始基變量初始基變量），），每確定一個(gè)初始基變量后，劃去需求每確定一個(gè)初始基變量后，劃去需求變成零的剩余列元素或劃去運(yùn)量變成變成零的剩余列元素或劃去運(yùn)量變成零的剩余行元素。零的剩余行元素。24藤蔓課堂b1b2b3b4產(chǎn)量a1 2 9 10 7 9a23 1 3 4 2 5，2a3 8 4 2 5 7銷量 3 ,0 8 4 625藤蔓課堂b1b2b3b4產(chǎn)量a1 2 9 10 7 9a23 1 3 4 2 5，2

10、a3 8 44 2 5 7，3銷量 3 ,0 8 4，0 626藤蔓課堂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,427藤蔓課堂b1b2b3b4產(chǎn)量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,428藤蔓課堂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,029藤蔓課堂填上填上x14=4后后,

11、第第4列自然列自然被去掉被去掉n記住每填一個(gè)數(shù)據(jù)減少一記住每填一個(gè)數(shù)據(jù)減少一行或一列。行或一列。30藤蔓課堂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,031藤蔓課堂3. 3. 位勢法求檢驗(yàn)數(shù)位勢法求檢驗(yàn)數(shù)n對(duì)每個(gè)基變量對(duì)每個(gè)基變量xij，計(jì)算，計(jì)算ui和和vj，使，使 ui+vj=cij 其中其中u1=0u1=032藤蔓課堂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

12、銷量 3 ,0 8,5 4，0 6,4,033藤蔓課堂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,034藤蔓課堂b1v1=6b2v2=9b3v3=7b4v4=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,035藤蔓課堂再計(jì)算非基變量檢驗(yàn)數(shù)再計(jì)算非基變量檢驗(yàn)數(shù)nij=cij-（ui+vj）36藤蔓課堂

13、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,037藤蔓課堂11=-4 x1111=-4 x11每增加一個(gè)單每增加一個(gè)單位，目標(biāo)函數(shù)可以減少位，目標(biāo)函數(shù)可以減少4 4個(gè)單位。個(gè)單位。目標(biāo)可以減少，說明當(dāng)前目標(biāo)可以減少，說明當(dāng)前解不是最優(yōu)解解不是最優(yōu)解38藤蔓課堂閉回路法調(diào)整閉回路法調(diào)整n選選x11進(jìn)基，找到閉回路進(jìn)基，找到閉回路n x11 x14 4-n x21 x24 2+ n 3-39藤蔓課堂閉

14、回路法調(diào)整閉回路法調(diào)整n為了保證所有為了保證所有xij非負(fù)，非負(fù)，x11最多增加最多增加3。n取取x11=3n x11 +3 x14 4-3n x21 x24 2+3 n 3-340藤蔓課堂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,041藤蔓課堂重新計(jì)算檢驗(yàn)數(shù)重新計(jì)算檢驗(yàn)數(shù)42藤蔓課堂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 4

15、4 23 5 7,3,0銷量 3 ,0 8,5 4，0 6,4,043藤蔓課堂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,044藤蔓課堂22=-1 x2222=-1 x22每增加一個(gè)單每增加一個(gè)單位，目標(biāo)函數(shù)可以減少位，目標(biāo)函數(shù)可以減少1 1個(gè)單位。個(gè)單位。目標(biāo)可以減少，說明當(dāng)前目標(biāo)可以減少，說明當(dāng)前解不是最優(yōu)解解不是最優(yōu)解45藤蔓課堂閉回路法調(diào)整閉回路法調(diào)整n選選x22進(jìn)基，找到閉回路進(jìn)基，找到

16、閉回路n x12 5- x14 1 +n x22 + x24 5- 46藤蔓課堂x22最多增加最多增加5n x12 5-5 x14 1 +5n x22 + 5 x24 5-5 47藤蔓課堂x22進(jìn)基，進(jìn)基，x12和和x24經(jīng)過調(diào)整同時(shí)變成經(jīng)過調(diào)整同時(shí)變成零。但是要注意只有一個(gè)變量出基。零。但是要注意只有一個(gè)變量出基。n例如：例如：令令x12x12出基出基n得調(diào)整后的運(yùn)輸表為：得調(diào)整后的運(yùn)輸表為：48藤蔓課堂b1b2b3b4產(chǎn)量a1u1=03 2 93 106 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

17、49藤蔓課堂重新計(jì)算檢驗(yàn)數(shù)重新計(jì)算檢驗(yàn)數(shù)50藤蔓課堂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,051藤蔓課堂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 8,5 4，0 6,4,052藤蔓課堂b1v1=2b2v2=8b3v3=6b4v4=7產(chǎn)量a1u1=03 2 1

18、 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,053藤蔓課堂所有非基變量檢驗(yàn)數(shù)均非所有非基變量檢驗(yàn)數(shù)均非負(fù)，當(dāng)前解為負(fù)，當(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=32+62+67+57+53+33+34+44+42=832=8354藤蔓課堂運(yùn)輸問題數(shù)學(xué)

19、模型的應(yīng)用實(shí)例運(yùn)輸問題數(shù)學(xué)模型的應(yīng)用實(shí)例n設(shè)某制造企業(yè)根據(jù)合同要求，從當(dāng)年起需連續(xù)設(shè)某制造企業(yè)根據(jù)合同要求，從當(dāng)年起需連續(xù)三年在年末提供三年在年末提供3套型號(hào)規(guī)格相同的大型設(shè)備，套型號(hào)規(guī)格相同的大型設(shè)備，已知該廠的生產(chǎn)能力及生產(chǎn)成本如下表所示：已知該廠的生產(chǎn)能力及生產(chǎn)成本如下表所示：55藤蔓課堂生產(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 600 n第三年第三年 1 3 550 設(shè)加班生產(chǎn)情況下每套設(shè)備成本比正常生

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

21、備數(shù)， cj為初始庫存設(shè)備第為初始庫存設(shè)備第j年交貨時(shí)每臺(tái)設(shè)備維護(hù)費(fèi)，年交貨時(shí)每臺(tái)設(shè)備維護(hù)費(fèi)， aij為第為第i年正常生產(chǎn)到第年正常生產(chǎn)到第j年交貨的每臺(tái)設(shè)備成年交貨的每臺(tái)設(shè)備成本費(fèi)，本費(fèi)， bij為第為第i年加班生產(chǎn)到第年加班生產(chǎn)到第j年交貨的每臺(tái)設(shè)備成年交貨的每臺(tái)設(shè)備成本費(fèi)。本費(fèi)。上述生產(chǎn)計(jì)劃問題的數(shù)學(xué)模型為：上述生產(chǎn)計(jì)劃問題的數(shù)學(xué)模型為：57藤蔓課堂 3,2,1,0,0,04333124322.min3333232313133222212122111113333232223221312111312113213131313131jizyxzyzyzyxzyzyxzyxzyzzyyzzzyyyxxxtszbyaxczijijjijijijijijijjjj58藤蔓課堂記記a為正常生產(chǎn)時(shí)的費(fèi)用矩陣為正常生產(chǎn)時(shí)的費(fèi)用矩陣55000640600058054