數(shù)學(xué)建模論文-管道訂購運輸問題-圖論;非線性規(guī)劃;最優(yōu)解;LINGO

數(shù)學(xué)建模論文鋼管訂購和運輸問題摘要在實際的生產(chǎn)建設(shè)的過程中，通常對于建設(shè)的材料，一般都是從原料生產(chǎn)地運輸過來的。對于原材料的訂購、運輸，如何節(jié)約成本，減少費用，制定最優(yōu)方案，是開發(fā)商們必須要解決的問題。本文就鋼管訂購和運輸問題，建立相應(yīng)的模型，研究訂購運輸問題的最優(yōu)方案的制定。針對問題一，通過對交通網(wǎng)絡(luò)及管道圖的分析，由于運輸?shù)穆肪€中既有鐵路又有公路，分別考慮只用鐵路運輸和只用公路運輸情況下的最短路徑，在考慮鐵路公路交叉運輸?shù)那闆r，建立圖論模型，利用MATLAB進行求解，對于管道的訂購，建立規(guī)劃模型，結(jié)合題中所給的數(shù)據(jù)，列出方程，利用LINGO軟件進行編程求解，得到了總費用的最小值為127.8632億元，并列出了主鋼管的訂購與運輸計劃。針對問題二，結(jié)合問題一中的模型，利用LINGO軟件進行靈敏度分析，得到了各鋼廠的影子價格，通過對影子價格的分析，得到了各鋼廠鋼管銷價與產(chǎn)量的上限變化對購運計劃和總費用的影響，其中S5鋼廠銷價變化對購運計劃和總費用的影響最大，S1鋼廠產(chǎn)量變化對購運計劃和總費用的影響最大。針對問題三，由于管道為樹狀圖，建立非線性規(guī)劃模型，通過建立目標函數(shù)，利用LINGO軟件求出最優(yōu)解，得到到管道為樹狀圖時，總費用的最小值為140.6631億元。關(guān)鍵詞：圖論；非線性規(guī)劃；最優(yōu)解；LINGO一、問題重述鋼管訂購和運輸問題：1.要鋪設(shè)一條的輸送天然氣的主管道。2.經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有。3.如圖所示，圖中粗線表示鐵路，單細線表示公路，雙細線表示要鋪設(shè)的管道（假設(shè)沿管道或者原有公路，或者建有施工公路）。4.圓圈表示火車站，每段鐵路、公路和管道旁的阿拉伯數(shù)字表示里程（單位）5.為方便計算，1主管道鋼管稱為1單位鋼管。問題如下：（1）請制定一個主管道鋼管的訂購和運輸計劃，使總費用最小（給出總費用）。（2）請就（1）的模型分析：那個鋼廠鋼管的銷價的變化對預(yù)購計劃和中費用影響最大，那個鋼廠鋼管的產(chǎn)量的上限的變化對云購計劃和總費用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。（3）如果要鋪設(shè)的管道不是一條線，而是一個樹形圖，鐵路，公路和管道構(gòu)成網(wǎng)絡(luò)，請就這種跟一般的情形給出一種解決辦法，并對圖二按（1）的要求給出模型和結(jié)果。二、問題的分析針對問題一，要求制定主管道的訂購和運輸計劃，并且使得費用最小。通過對交通網(wǎng)絡(luò)及管道圖的分析，鋼廠與主管道之間既存在鐵路，又存在公路;對于管道的運輸建立圖論模型，將運輸轉(zhuǎn)化為求公路、鐵路的最短路徑問題，使得運費最小，求得最優(yōu)的運輸路徑，結(jié)合管道訂購，建立線性規(guī)劃模型，運用LINGO進行求解，進而得出總費用的最小值及訂購與運輸?shù)淖顑?yōu)方案。針對問題二，要求對問題（1）中的模型，分析鋼廠變化鋼管的銷價變化和產(chǎn)量上限的變化對購運計劃和總費用的影響。根據(jù)問題一中的模型，運用LINGO軟件進行靈敏性分析，得到各變量變化的影響值。針對問題三，要求對鐵路，公路和管道構(gòu)成的網(wǎng)絡(luò)，給出一種解決辦法，并按（1）中的要求給出模型和結(jié)果。由于是鐵路，公路，管道構(gòu)成的網(wǎng)絡(luò)，且管道為樹形圖，建立非線性規(guī)劃模型，通過列出目標函數(shù)和各約束條件，運用LINGO軟件進行求解。三、模型假設(shè)1.通只考慮訂購費用和運輸費用，不考慮裝卸等其它費用。2.在運輸和鋪設(shè)過程中無能量損耗。3.鋼管單價與訂購量、訂購次數(shù)、訂購日期無關(guān)。4.沿管道或者原來有公路或者建有施工公路。四、符號說明表1符號說明符號說明從鋼廠i運行到j(luò)的鋼管量從節(jié)點j向左鋪設(shè)的鋼管量從節(jié)點j向右鋪設(shè)的鋼管量鋼廠i是否生產(chǎn)從第i個鋼廠到鋪設(shè)節(jié)點j的訂購和運輸費用鐵路任意兩點間的最小運輸費用公路任意兩點間的最小運輸費表示i，j兩點之間的鐵路路程c第i個鋼廠的最大供應(yīng)量最小運輸費用五、模型的建立與求解5.1問題一的求解根據(jù)題中所給數(shù)據(jù)，我們可以先計算出從供應(yīng)點到需求點的小購運費（即出廠售價與運輸費用之和），再根據(jù)求解總費用，總費用應(yīng)包括：訂購費用（已包含在中），運輸費用（由各廠經(jīng)鐵路、公路至各點，，），鋪設(shè)管道()的運費。5.1.1運費矩陣的計算模型購買單位鋼管及從（）運送到（）的最小購運費用的計算：1.計算鐵路任意兩點間的小運輸費用構(gòu)造鐵路距離賦權(quán)圖,其中V=W由于鐵路運費不是連續(xù)的，故不能直接用Floyd算法來計算最小運輸費用。但可以用Floyd算法來計算任意兩點間的最短鐵路距離值，再依據(jù)題中的鐵路運價表，來計算最小運輸費用。這就巧妙的避開鐵路運費不是連續(xù)的問題。最終計算出鐵路任意兩點間的最小運輸費用。其中，路徑值無窮大時的費用也為無窮大。2.計算公路任意兩點間的小運輸費用構(gòu)造公路距離賦權(quán)圖,其中V同上，W2=依據(jù)題中“公路運輸費用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計算）”，計算出公路任意兩點間的最小運輸費用。路徑值為無窮大時的費用也為無窮大。3.計算任意兩點間的小運輸費用由于可以用鐵路、公路交叉運送，所以任意相鄰兩點間的小運輸費用為鐵路、公路兩者小運輸費用的小值。構(gòu)造鐵路公路的混合賦權(quán)完全圖，W2=cij~對圖G應(yīng)用Floyd算法，就可以計算出（）到()的最小運送費用cij~(單位：萬元)見表1。A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1170.7160.3140.298.63820.53.121.264.2929616121.2128142S2215.7205.3190.2171.611195.58671.2114.2142146156171.2178192S3230.7220.3200.2181.6121105.59686.248.2828696111.2118132S4260.7250.3235.2216.6156140.5131116.284.262516176.28397S5255.7245.3225.2206.6146130.5121111.279.257335171.27387S6265.7255.3235.2216.6156140.5131121.284.262514526.21128S7275.7265.3245.2226.6166150.5141131.299.276665638.2262表1最小運輸費計算結(jié)果任意兩點間的最小運輸費用加上出廠售價,得到單位鋼管從任一個到的購買和運送最小費用。4.總費用的數(shù)學(xué)規(guī)劃模型分析題目可以知道約束條件應(yīng)包括：鋼廠產(chǎn)量約束：上限和下限（如果生產(chǎn)的話）；運量約束:對求和等于加；與之和等于段的長度。由向段鋪設(shè)管道的運輸總路程為:由向段鋪設(shè)管道的運輸總路程為:根據(jù)以上條件可以建立模型如下：其中（）是連接的邊，是樹形圖的邊集，是從到的長度，是由沿（）鋪設(shè)的鋼管數(shù)量。運用LINGO進行編程求解的到總費用的最小值為127.8632億元。主管道鋼管的訂購和運輸計劃：S1S2S3S4S5S6S7A1A2179A3132.46375.54A4140.5894.99125.38107.06A5194.42226.0278.16117.41A6200A7265A8300A9664A10290.7460.3A11415A1286A13333A14621A151655.2問題二的求解通過分析問題一中關(guān)于銷價的約束，Lingo運行后得到的結(jié)果得影子價格表示在最優(yōu)解下“資源”增加一個單位時“效益”的增量，即每個鋼廠銷售價格每減少一萬元，對總費用的影響。從表中數(shù)據(jù)分析，S5鋼廠鋼管的銷價的變化對購運計劃和總費用的影響最大。通過分析問題一中關(guān)于產(chǎn)量的約束，Lingo運行后得到的結(jié)果得分析表中數(shù)據(jù)，得S1鋼廠鋼管的產(chǎn)量上限的變化對購運計劃和總費用的影響最大。5.3問題三的求解當管道為樹形圖時，建立與上面類似的非線性規(guī)劃模型：通過LINGO進行編程求解得到最小費用為：140.6631億元。主管道的訂購與運輸計劃如下：S1S2S3S4S5S6A1A2179A3205.2151.7151.1A4120.5115.876.1155.6A5214.566.2335.7A6200A7265A8300A9664A10126225A11380A12111A13393A14571A15165A1642A17155A1880A1995A20260A21100六、模型的評價此模型是針對鋼管訂購運輸問題的處理方案,其中主要方面在于運輸路徑的選擇，模型中將路徑的選擇分成兩大部分處理，先將貨物運到節(jié)點，再從節(jié)點向全線運輸。同時，在解決第一個問題時，把鐵路和公路分開計算，最后進行統(tǒng)一，簡化了運算。但模型也存在一些不足之處，在對鐵路運費矩陣和公路運費矩陣進行統(tǒng)一時，取的還是相對近似值。另外，由于我們在建立約束條件時要求從節(jié)點向其他方向運輸時，相鄰兩節(jié)點運量加和恰好等于兩點間線路距離，因此忽略了跨節(jié)點運輸?shù)那闆r，而這里面可能出現(xiàn)較之更優(yōu)的方案。在解決本題時，我們主要采用的是通過點來表示線路的，同時應(yīng)用圖論中的floyd算法解決最短路徑問題。在生活中，求最短路徑的問題常常會碰到，我們可以對模型稍加修改，使之符合問題的條件，進而進行求解。七、參考文獻[1]司守奎，孫兆亮，數(shù)學(xué)建模算法與應(yīng)用[M]，北京：國防工業(yè)出版社，2013。[2]姜啟源，葉俊，數(shù)學(xué)模型(第三版)[M]，北京：高等教育出版社，2003。[3]汪小帆，李翔，陳光榮，復(fù)雜網(wǎng)絡(luò)理論及其應(yīng)用，北京：清華大學(xué)出版社，2009。[4]謝金星,薛毅.《優(yōu)化建模與LINGO/LINGO軟件》.北京：清華大學(xué)出版。八、附錄問題一求解代碼：model:sets:!nodes表示節(jié)點集合;nodes/S1,S2,S3,S4,S5,S6,S7,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12,B13,B14,B15,B16,B17/;!c1(i,j)表示節(jié)點i到j(luò)鐵路運輸?shù)淖钚∵\價（萬元）,c2(i,j)表示節(jié)點i到j(luò)公路運輸?shù)馁M-113-用鄰接矩陣，c(i,j)表示節(jié)點i到j(luò)的最小運價，path標志最短路徑上走過的頂點;link(nodes,nodes):w,c1,c2,c,path1,path;supply/S1..S7/:S,P,f;need/A1..A15/:b,y,z;!y表示每一點往左鋪的量，z表示往右鋪的量;linkf(supply,need):cf,X;endsetsdata:S=80080010002000200020003000;P=160155155160155150160;b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,0;path1=0;path=0;w=0;c2=0;!以下是格式化輸出計算的中間結(jié)果和最終結(jié)果;@text(MiddleCost.txt)=@writefor(supply(i):@writefor(need(j):@format(cf(i,j),'6.1f')),@newline(1));@text(Train_path.txt)=@writefor(nodes(i):@writefor(nodes(j):@format(path1(i,j),'5.0f')),@newline(1));@text(Final_path.txt)=@writefor(nodes(i):@writefor(nodes(j):@format(path(i,j),'5.0f')),@newline(1));@text(FinalResult.txt)=@writefor(supply(i):@writefor(need(j):@format(x(i,j),'5.0f')),@newline(1));@text(FinalResult.txt)=@write(@newline(1));@text(FinalResult.txt)=@writefor(need:@format(y,'5.0f'));@text(FinalResult.txt)=@write(@newline(2));@text(FinalResult.txt)=@writefor(need:@format(z,'5.0f'));enddatacalc:!輸入鐵路距離鄰接矩陣的上三角元素;w(1,29)=20;w(1,30)=202;w(2,30)=1200;w(3,31)=690;w(4,34)=690;w(5,33)=462;w(6,38)=70;w(7,39)=30;w(23,25)=450;w(24,25)=80;w(25,27)=1150;w(26,28)=306;w(27,30)=1100;w(28,29)=195;w(30,31)=720;w(31,32)=520;w(32,34)=170;w(33,34)=88;w(34,36)=160;w(35,36)=70;w(36,37)=320;w(37,38)=160;w(38,39)=290;@for(link(i,j):w(i,j)=w(i,j)+w(j,i));!輸入鐵路距離鄰接矩陣的下三角元素;@for(link(i,j)|i#ne#j:w(i,j)=@if(w(i,j)#eq#0,20000,w(i,j)));!無鐵路連接，元素為充分大的數(shù);!以下就是最短路計算公式（Floyd-Warshall算法）;@for(nodes(k):@for(nodes(i):@for(nodes(j):tm=@smin(w(i,j),w(i,k)+w(k,j));path1(i,j)=@if(w(i,j)#gt#tm,k,path1(i,j));w(i,j)=tm)));!以下就是按最短路w查找相應(yīng)運費C1的計算公式;@for(link|w#eq#0:C1=0);@for(link|w#gt#0#and#w#le#300:C1=20);@for(link|w#gt#300#and#w#le#350:C1=23);@for(link|w#gt#350#and#w#le#400:C1=26);@for(link|w#gt#400#and#w#le#450:C1=29);@for(link|w#gt#450#and#w#le#500:C1=32);@for(link|w#gt#500#and#w#le#600:C1=37);@for(link|w#gt#600#and#w#le#700:C1=44);@for(link|w#gt#700#and#w#le#800:C1=50);@for(link|w#gt#800#and#w#le#900:C1=55);@for(link|w#gt#900#and#w#le#1000:C1=60);@for(link|w#gt#1000:C1=60+5*@floor(w/100-10)+@if(@mod(w,100)#eq#0,0,5));!輸入公路距離鄰接矩陣的上三角元素;c2(1,14)=31;c2(6,21)=110;c2(7,22)=20;c2(8,9)=104;c2(9,10)=301;c2(9,23)=3;c2(10,11)=750;c2(10,24)=2;c2(11,12)=606;c2(11,27)=600;c2(12,13)=194;c2(12,26)=10;c2(13,14)=205;c2(13,28)=5;c2(14,15)=201;c2(14,29)=10;c2(15,16)=680;c2(15,30)=12;c2(16,17)=480;c2(16,31)=42;c2(17,18)=300;c2(17,32)=70;c2(18,19)=220;c2(18,33)=10;c2(19,20)=210;c2(19,35)=10;c2(20,21)=420;c2(20,37)=62;c2(21,22)=500;c2(21,38)=30;c2(22,39)=20;@for(link(i,j):c2(i,j)=c2(i,j)+c2(j,i));!輸入公路距離鄰接矩陣的下三角元素;@for(link(i,j):c2(i,j)=0.1*c2(i,j));!距離轉(zhuǎn)化成費用;@for(link(i,j)|i#ne#j:c2(i,j)=@if(c2(i,j)#eq#0,10000,c2(i,j)));!無公路連接，元素為充分大的數(shù);@for(link:C=@if(C1#le#C2,C1,C2));!C1和C2矩陣對應(yīng)元素取最小;@for(nodes(k):@for(nodes(i):@for(nodes(j):tm=@smin(C(i,j),C(i,k)+C(k,j));path(i,j)=@if(C(i,j)#gt#tm,k,path(i,j));C(i,j)=tm)));@for(link(i,j)|i#le#7#and#j#ge#8#and#j#le#22:cf(i,j-7)=c(i,j));!提取下面二次規(guī)劃模型需要的7×15矩陣;endcalc[obj]min=@sum(linkf(i,j):(cf(i,j)+p(i))*x(i,j))+0.05*@sum(need(j):y(j)^2+y(j)+z(j)^2+z(j));!約束;@for(supply(i):[con1]@sum(need(j):x(i,j))<=S(i)*f(i));@for(supply(i):[con2]@sum(need(j):x(i,j))>=500*f(i));@for(need(j):[con3]@sum(supply(i):x(i,j))=y(j)+z(j));@for(need(j)|j#NE#15:[con4]z(j)+y(j+1)=b(j));y(1)=0;z(15)=0;@for(supply:@bin(f));@for(need:@gin(y));end問題三的求解代碼：model:sets:!nodes表示節(jié)點集合;nodes/S1,S2,S3,S4,S5,S6,S7,A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12,A13,A14,A15,A16,A17,A18,A19,A20,B1,B2,B3,B4,B5,B6,B7,B8,B9,B10,B11,B12/;!c1(i,j)表示節(jié)點i到j(luò)鐵路運輸?shù)淖钚挝贿\價（萬元）,c2(i,j)表示節(jié)點i到j(luò)公路運輸?shù)泥徑訖?quán)重矩陣，c(i,j)表示節(jié)點i到j(luò)的最小單位運價，path標志最短路徑上走過的頂點;link(nodes,nodes):w,c1,c2,c,path1,path;supply/S1..S7/:s,p,f;need/A1..A21/:b,y,z;!y表示每一點往節(jié)點編號小的方向鋪設(shè)量，z表示往節(jié)點編號大的方向鋪設(shè)量;linkf(supply,need):cf,x;special/1..3/:sx;!鋪設(shè)節(jié)點9，11，17往最大編號節(jié)點方向的鋪設(shè)量;endsetsdata:s=80080010002000200020003000;p=160155155160155150160;b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,42,10,130,190,260,100,0;path1=0;path=0;w=0;c2=0;!以下是格式化輸出計算的中間結(jié)果和最終結(jié)果;@text(MiddleCost.txt)=@writefor(supply(i):@writefor(need(j):@format(cf(i,j),'6.1f')),@newline(1));@text(Train_path.txt)=@writefor(nodes(i):@writefor(nodes(j):@format(path1(i,j),'5.0f')),@newline(1));@text(Final_path.txt)=@writefor(nodes(i):@writefor(nodes(j):@format(path(i,j),'5.0f')),@newline(1));@text(FinalResult.txt)=@writefor(supply(i):@writefor(need(j):@format(x(i,j),'5.0f')),@newline(1));@text(FinalResult.txt)=@write(@newline(1));@text(FinalResult.txt)=@writefor(need:@format(y,'5.0f'));@text(FinalResult.txt)=@write(@newline(2));@text(FinalResult.txt)=@writefor(need:@format(z,'5.0f'));enddatacalc:!輸入鐵路距離鄰接矩陣的上三角元素;w(28,30)=450;w(29,30)=80;w(30,32)=1150;w(31,33)=306;w(33,34)=195;w(1,34)=20;w(1,35)=202;w(32,35)=1100;w(2,35)=1200;w(23,35)=720;w(3,23)=690;w(23,36)=520;w(36,37)=170;w(4,37)=690;w(5,24)=462;w(24,37)=88;w(25,37)=160;w(25,26)=70;w(25,27)=320;w(27,38)=160;w(6,38)=70;w(38,39)=290;w(7,39)=30;@for(link(i,j):w(i,j)=w(i,j)+w(j,i));!輸入鐵路距離鄰接矩陣的下三角元素;@for(link(i,j)|i#ne#j:w(i,j)=@if(w(i,j)#eq#0,20000,w(i,j)));!無鐵路連接，元素為充分大的數(shù);!以下就是最短路計算公式（Floyd-Warshall算法）;@for(nodes(k):@for(nodes(i):@for(nodes(j):tm=@smin(w(i,j),w(i,k)+w(k,j));path1(i,j)=@if(w(i,j)#gt#tm,k,path1(i,j));w(i,j)=tm)));!以下就是按最短路w查找相應(yīng)運費C1的計算公式;@for(link|w#eq#0:C1=0);@for(link|w#gt#0#and#w#le#300:C1=20);@for(link|w#gt#300#and#w#le#350:C1=23);@for(link|w#gt#350#and#w#le#400:C1=26);@for(link|w#gt#400#and#w#le#450:C1=29);@for(link|w#gt#450#and#w#le#500:C1=32);@for(link|w#gt#500#and#w#le#600:C1=37);@for(link|w#gt#600#and#w#le#700:C1=44);@for(link|w#gt#700#and#w#le#800:C1=50);@for(link|w#gt#800#and#w#le#900:C1=55);@for(link|w#gt#900#and#w#le#1000:C1=60);@for(link|w#gt#1000:C1=60+5*@floor(w/100-10)+@if(@mod(w,100)#eq#0,0,5));!輸入公路距離鄰接矩陣的上三角元素;c2(8,9)=104;c2(9,10)=301;c2(10,11)=750;c2(11,12)=606;c2(12,13)=194;c2(13,14)=205;c2(14,15)=201;c2(15,16)=680;c2(16,17)=480;c2(16,23)=42;c2(17,18)=300;c2(18,19)=220;c2(18,24)=10;c2(19,20)=210;c2(20,21)=420;c2(21,22)=500;c2(24,25)=130;c2(24,26)=190;c2(26,27)=260;c2(6,27)=100;c2(9,28)=3;c2(10,29)=2;c2(11,32)=600;c2(12,31)=10;c2(13,33)=5;c2(14,34)=10;c2(1,14)=31;c2(15,35)=12;c2(17,36)=70;c2(19,26)=10;c2(20,27)=62;c2(6,21)=110;c2(21,38)=30;c2(22,39)=20;c2(7,22