運(yùn)輸問題模型

1、運(yùn)輸問題模型二0一0年四月1運(yùn)輸問題的一般描述設(shè)某種物資有m個(gè)產(chǎn)地A1,A2,Am，和n個(gè)銷地B1,B2,Bn,其中Ai的產(chǎn)量為ai,Bj的銷量為bj，產(chǎn)地Ai運(yùn)往銷地Bj的單位運(yùn)價(jià)Cij,i=1,2,m;j=1,2,n.求盡可能滿足銷地需求且總費(fèi)用最小的運(yùn)輸方案。2運(yùn)輸問題的數(shù)學(xué)模型可以分以下3種情況討論：1. 產(chǎn)銷平衡問題2. 銷大于產(chǎn)問題產(chǎn)大于銷問題解：設(shè)產(chǎn)地Ai運(yùn)往銷地Bj的運(yùn)量為31.產(chǎn)銷平衡問題的數(shù)學(xué)模型產(chǎn)銷平衡時(shí)，各個(gè)產(chǎn)地的物資總和正好滿足所有銷地的需求，運(yùn)輸問題的數(shù)學(xué)模型為42. 銷大于產(chǎn)問題的數(shù)學(xué)模型銷大于產(chǎn)時(shí)，各個(gè)銷地的需求不一定能夠得到滿足，運(yùn)輸問題的數(shù)學(xué)模型為52. 產(chǎn)

2、大于銷問題的數(shù)學(xué)模型銷大于產(chǎn)時(shí)，各個(gè)銷地的需求一定能夠得到滿足，但各個(gè)產(chǎn)地的物資不一定全部運(yùn)走。運(yùn)輸問題的數(shù)學(xué)模型為6運(yùn)輸問題本質(zhì)是一個(gè)線性規(guī)劃問題運(yùn)輸問題變量比較多，系數(shù)矩陣為0-1矩陣，其中大部分元素為零。計(jì)算運(yùn)輸問題我們有比單純形法更好的專門求解運(yùn)輸問題的算法。7產(chǎn)銷平衡運(yùn)輸問題的求解定理 產(chǎn)銷平衡運(yùn)輸問題一定存在最優(yōu)解 。8產(chǎn)銷平衡運(yùn)輸問題的Lingo模型MODEL:sets:row/1.m/:a;arrange/1.n/:b;link(row,arrange):c,x;endsetsdata:a=a(1) a(2) a(m);b=b(1) b(2) b(n);9C=c(1,1) c(

3、1,2) c(1,n), c(2,1) c(2,2) c(2,n), c(m,1) c(m,2) c(m,n);enddataOBJmin=sum(link(i,j):c(i,j)*x(i,j);for(row(i):sum(arrange(j):x(i,j)=a(i););for(arrange(j):sum(row(i):x(i,j)=b(j););for(link(i,j):x(i,j)=0;);END10產(chǎn)銷不平衡運(yùn)輸問題也有類似的Lingo模型11產(chǎn)銷平衡運(yùn)輸問題的初始解1. 西北角法在運(yùn)價(jià)表的西北角選擇運(yùn)量和銷量中的較小數(shù)作為運(yùn)量（初始基變量），每確定一個(gè)初始基變量后，劃去需求變成

4、零的剩余列元素或劃去運(yùn)量變成零的剩余行元素。121314151617填上x33=1后,自然少去一列(第3列),這時(shí)不要再去掉第3行。注意到每填一個(gè)數(shù)據(jù)恰好減少一行或一列。1819總共填寫m+n個(gè)數(shù)據(jù)填上去的m+n個(gè)數(shù)據(jù)為基變量20產(chǎn)銷平衡運(yùn)輸問題的初始解2. 最小元素法選擇運(yùn)價(jià)表中最小運(yùn)價(jià)，運(yùn)量和銷量中的較小數(shù)作為運(yùn)量（初始基變量），每確定一個(gè)初始基變量后，劃去需求變成零的剩余列元素或劃去運(yùn)量變成零的剩余行元素。212223242526填上x14=4后,第4列自然被去掉記住每填一個(gè)數(shù)據(jù)減少一行或一列。27283. 位勢(shì)法求檢驗(yàn)數(shù)對(duì)每個(gè)基變量xij，計(jì)算ui和vj，使 ui+vj=cij 其中u

5、1=029303132再計(jì)算非基變量檢驗(yàn)數(shù)ij=cij-（ui+vj）333411=-4 x11每增加一個(gè)單位，目標(biāo)函數(shù)可以減少4個(gè)單位。目標(biāo)可以減少，說明當(dāng)前解不是最優(yōu)解35閉回路法調(diào)整選x11進(jìn)基，找到閉回路 x11 x14 4- x21 x24 2+ 3-36閉回路法調(diào)整為了保證所有xij非負(fù)，x11最多增加3。取x11=3 x11 +3 x14 4-3 x21 x24 2+3 3-33738重新計(jì)算檢驗(yàn)數(shù)39404122=-1 x22每增加一個(gè)單位，目標(biāo)函數(shù)可以減少1個(gè)單位。目標(biāo)可以減少，說明當(dāng)前解不是最優(yōu)解42閉回路法調(diào)整選x22進(jìn)基，找到閉回路 x12 5- x14 1 + x22

6、 + x24 5- 43X22最多增加5 x12 5-5 x14 1 +5 x22 + 5 x24 5-5 44X22進(jìn)基，x12和x24經(jīng)過調(diào)整同時(shí)變成零。但是要注意只有一個(gè)變量出基。例如：令x12出基得調(diào)整后的運(yùn)輸表為：4546重新計(jì)算檢驗(yàn)數(shù)47484950所有非基變量檢驗(yàn)數(shù)均非負(fù)，當(dāng)前解為最優(yōu)解最優(yōu)解為： X11*=3，x14*=6，x22*=5，x32*=3，x33*=4，其余xij*=0最優(yōu)目標(biāo)值為Z*=32+67+53+34+42=8351運(yùn)輸問題數(shù)學(xué)模型的應(yīng)用實(shí)例設(shè)某制造企業(yè)根據(jù)合同要求，從當(dāng)年起需連續(xù)三年在年末提供3套型號(hào)規(guī)格相同的大型設(shè)備，已知該廠的生產(chǎn)能力及生產(chǎn)成本如下表所

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

8、每臺(tái)設(shè)備成本費(fèi)， bij為第i年加班生產(chǎn)到第j年交貨的每臺(tái)設(shè)備成本費(fèi)。上述生產(chǎn)計(jì)劃問題的數(shù)學(xué)模型為：54記A為正常生產(chǎn)時(shí)的費(fèi)用矩陣55B為加班生產(chǎn)時(shí)的費(fèi)用矩陣C=（0，40 ，80）56生產(chǎn)計(jì)劃問題的Lingo模型為MODEL:sets:row/1,2,3/;arrange/1,2,3/:c,x;link(row,arrange):a,b,y,z;Endsetsdata:c=0,40,80;a=500,540,580,0,600,640,0,0,550;b=570,610,650,0,670,710,0,0,620;enddata57OBJmin=sum(arrange(j):c(j)*x(j)+sum(link(i,j):a(i,j)*y(i,j)+sum(link(i,j):b(i,j)*z(i,j);sum(arrange(j):x(j)=2;sum(arrange(j):y(1,j)=2;sum(arrange(j):z(1,j)=3;y(2,2)+y(2,3)=4; z(2,2)+z(2,3)=2; y(3,3)=1; z(3,3)=0;); for(link(i,j):y(i,j)=0