1、鋼管訂購和運輸摘要： 本文建立了一個運輸問題的最優化模型。通過分析題圖一，我們利用Floyd算法求出鐵路網和公路網各點間最短路線，然后轉化成最少運輸，去掉了鐵路和公路的性質，使運輸網絡變成一張供需運輸價格表，然后建立了一個以總費用為目標函數的非線性規劃模型，利用Lingo 軟件，求出問題一的最優解為1278632萬元通過對問題一中lingo運行結果的分析，我們得出S5鋼廠鋼管的銷價的變化對購運計劃和總費用影響最大，S1鋼廠鋼管的產量的上限的變化對購運計劃和總費用的影響最大。問題三模型的建立原理和問題一的相同，利用Lingo 軟件，求得最優解為1407149萬元.關鍵詞：Floyd算法，非線性規

2、劃，0-1規劃一 問題重述有7個生產廠，可以生產輸送天然氣主管道的鋼管。要沿著的主管道鋪設, 如題圖一所示。圖中粗線表示鐵路，單細線表示公路，雙細線表示要鋪設的管道(假設沿管道或者原來有公路，或者建有施工公路)，圓圈表示火車站，每段鐵路、公路和管道旁的阿拉伯數字表示里程(單位km)。為方便計，1km主管道鋼管稱為1單位鋼管。一個鋼廠如果承擔制造這種鋼管，至少需要生產500個單位。鋼廠在指定期限內能生產該鋼管的最大數量為個單位，鋼管出廠銷價1單位鋼管為萬元，如下表：1單位鋼管的鐵路運價如下表：里程(km)300301350351400401450451500運價(萬元)2023262932里程(

3、km)5016006017007018008019009011000運價(萬元)37445055601000km以上每增加1至100km運價增加5萬元。公路運輸費用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計算）。鋼管可由鐵路、公路運往鋪設地點（不只是運到點，而是管道全線）。（1）請制定一個主管道鋼管的訂購和運輸計劃，使總費用最小（給出總費用)。（2）請就（1）的模型分析：哪個鋼廠鋼管的銷價的變化對購運計劃和總費用影響最大，哪個鋼廠鋼管的產量的上限的變化對購運計劃和總費用的影響最大，并給出相應的數字結果。（3）如果要鋪設的管道不是一條線，而是一個樹形圖，鐵路、公路和管道構成網絡，請就

4、這種更一般的情形給出一種解決辦法，并對題圖二按（1）的要求給出模型和結果。二 問題分析問題一，首先，所有鋼管必須運到天然氣主管道鋪設路線上的節點，然后才能向左或右鋪設。必須求出每個鋼管廠到每個節點的每單位鋼管的最小運輸費用。對最小運費的求解，我們采用Floyd算法。先求出鐵路網上鋼管廠到鐵路上任意兩點，的最短路線的長度,用matlab求得對應的鐵路單位運費；同理用Floyd 算法求出公路網上的任意兩點， 的最短公路路線的長度，結果乘以0.1得到公路運費。，j表示所有運輸中轉點，于是就得到從某鋼廠到某鋪設點運輸單位鋼管的最少運輸費用。每個鋪設點分別向兩個方向展開，通過Lingo編程求出最小鋪設費

5、用。運輸費用加上購買費用再加上鋪設費用就是我們所要求的總費用。問題二，通過問題一里面Lingo編程運行得出的結果，分析哪個鋼廠鋼管的銷價的變化對購運計劃和總費用影響最大，哪個鋼廠鋼管的產量的上限的變化對購運計劃和總費用的影響最大。問題三，如鋪設的管道是一個樹形圖，鐵路、公路和管道構成網絡對于題圖二，我們可以延用問題一里面的思想，在題圖一的基礎上多幾條鋪設路段，9，11，17節點的鋪設方向變為 三個方向，其他不變。三 模型的假設與符號說明1) 基本假設: eq oac(,1)鋼管在運輸中由鐵路運轉為公路運時不計中轉費用； eq oac(,2)所需鋼管均由 鋼廠提供； eq oac(,3)假設運送

6、的鋼管路途中沒有損耗。 eq oac(,4)把“鋼廠鋼管的銷價和產量上限變化對總費用和運購計劃的影響”理解為在最優解附近的微小變化對總費用和運購計劃的影響。銷價最小變化是1萬元，產量上限的最小變化是1個單位。 eq oac(,5)沿管道或者原來有公路或者建有施工公路。 eq oac(,6)一個鋼管廠如果承擔制造鋼管，至少要生產500個單位。 eq oac(,7)公路運輸費用為1單位鋼管每公里0.1萬元，不足整公里按整公里計算。2) 符號說明 : 鋼廠的最大生產能力;: 鋼廠 的出廠鋼管單位價格(單位: 萬元) ;: 公路上一單位鋼管的每公里運費( = 0. 1 萬元) ;：鐵路網上兩點間的單位

7、鋼管最少運輸費用；：題圖一公路網上兩點間的單位鋼管最少運輸費用；：題圖二公路網上兩點間的單位鋼管最少運輸費用；: 鐵路上一單位鋼管的運費(分段函數見表1) ;: 1 單位鋼管從鋼廠運到的最小費用(單位: 萬元) ;: 從 到之間的距離(單位: 千米) ;: 鋼廠運到的鋼管數;: 運到地的鋼管向左鋪設的數目;: 運到地的鋼管向右鋪設的數目;：運到地的鋼管向第三個方向鋪設的數目;: = : 問題一中所求鋼管訂購、運輸的總費用(單位: 萬元) ; : 問題二中所求鋼管訂購、運輸的總費用(單位: 萬元) ;四 模型的建立與求解問題一的模型：針對題圖一，我們采用Floyd算法，用matlab編程求出單位

8、鋼管從運輸到的最小運輸費用，具體數據如下表1：表1 單位鋼管從運輸到的最小運輸費用（單位：萬元）對表1的數據進行分析，我們得到一個非線性規劃模型：目標函數是總費用W , 它包含三項: 鋼管出廠總價Q , 運輸費P , 及鋪設費T. 即W = Q + P + T其中 ， ， 目標函數為： 約束條件為: 生產能力的限制: 運到的鋼管用完: 與之間的鋼管: 變量非負性限制: , 運到的鋼管整數限制: 運用數學軟件Lingo編程求解 最優最小費用萬元問題二的模型通過分析問題一中關于銷價的約束，Lingo運行后得到的結果得影子價格表示在最優解下“資源”增加一個單位時“效益”的增量，即每個鋼廠銷售價格每減

9、少一萬元，對總費用的影響。從表中數據分析，S5鋼廠鋼管的銷價的變化對購運計劃和總費用的影響最大。通過分析問題一中關于產量的約束，Lingo運行后得到的結果得分析表中數據，得S1鋼廠鋼管的產量上限的變化對購運計劃和總費用的影響最大。問題三的模型題圖二為樹形圖，采用Floyd算法，用matlab編程求出單位鋼管從運輸到的最小運輸費用，具體數據如下表2：表2 單位鋼管從運輸到的最小運輸費用 （單位：萬元）由于樹形圖的出現，則某些管道處會出現多支路。 則模型一中模型的 ，不再適用，此時可考慮多增加一些支路變量，并增加約束，在目標函數中增加相應的鋪設費。目標函數： 約束條件： 生產能力的限制: 運到的鋼

10、管用完: 與之間的鋼管: 變量非負性限制: , 運到的鋼管整數限制: 運用數學軟件Lingo編程求出 最優最小費用萬元五 模型優缺點1. 本文先從簡單的角度著手建立模型，采用Floyd算法，簡化運輸網絡。過程嚴謹，理論性強，邏輯嚴密，而且易于理解。2. 在計算最短路徑時，我們采用Floyd算法，相比與Dijkstra算法，減少了大量的重復計算，提高了工作效率。3. 本文大量運用了計算機程序，所有數據均由計算機處理，故誤差由計算機精度產生，模型據有良好的穩定性。參考文獻：1 謝金星,薛毅.優化建模與LINGO/LINGO軟件.北京：清華大學出版社,20052 宗容,施繼紅,尉洪,李海燕.數學實驗

11、與數學建模.云南：云南大學出版社，2009附錄用matlab建立Floyd函數的M文件，編程如下：function D,path=floyd(a)n=size(a,1);D=a;path=zeros(n,n);for i=1:n for j=1:n if D(i,j)=inf path(i,j)=j; end endendfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j)+D1(k,j+8) c(i,k)=D(i,j)+D1(k,j+8);%對于所有中轉點，在鐵路網和公路網上的下標相差8 end end endendfor i=1:7for

12、 k=1:15 if c(i,k)D(i,1)+D1(k,33) c(i,k)=D(i,1)+D1(k,33);%33代表第一個鋼管生產廠S1點 end if c(i,k)D(i,6)+D1(k,34) c(i,k)=D(i,6)+D1(k,34);%34代表第六個鋼管生產廠S6點 end if c(i,k)D(i,7)+D1(k,35) c(i,k)=D(i,7)+D1(k,35);%35代表第七個鋼管生產廠S7點 endend%因為S1,S6,S7這三個鋼管廠有公路直接連接到鋪設節點，所以把這三個點單獨處理end 運行結果如下：問題一用Lingo軟件求解的編程：model: sets: s

13、upply/S1.S7/:p,s,t; need/A1.A15/:L,R,b; links(supply,need):c,x; endsets data: s=800 800 1000 2000 2000 2000 3000; b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,; c=170.7 160.3 140.2 98.6 38.0 20.5 3.1 21.2 64.2 92.0 96.0 106.0 121.2 128.0 142.0 215.7 205.3 190.2 171.6 111.0 95.5 86.0 71.

14、2 114.2 142.0 146.0 156.0 171.2 178.0 192.0 230.7 220.3 200.2 181.6 121.0 105.5 96.0 86.2 48.2 82.0 86.0 96.0 111.2 118.0 132.0 260.7 250.3 235.2 216.6 156.0 140.5 131.0 116.2 84.2 62.0 51.0 61.0 76.2 83.0 97.0 255.7 245.3 225.2 206.6 146.0 130.5 121.0 111.2 79.2 57.0 33.0 51.0 71.2 73.0 87.0 265.7

15、255.3 235.2 216.6 156.0 140.5 131.0 121.2 84.2 62.0 51.0 45.0 26.2 11.0 28.0 275.7 265.3 245.2 226.6 166.0 150.5 141.0 131.2 99.2 77.0 66.0 56.0 38.2 26.0 2.0; enddata min=sum(links(i,j):(p(i)+c(i,j)*x(i,j)+0.05*sum(need(j):L(j)2+L(j)+R(j)2+R(j); for(supply(i):sum(need(j):x(i,j)=500*t(i); for(supply

16、(i):sum(need(j):x(i,j)D(i,j)+D2(k,j+8) h(i,m)=D(i,j)+D2(k,j+8); end end m=m+1; endendfor i=1:7 m=1; for k=1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,24,27,28,29,30,34 if h(i,m)D(i,1)+D2(k,33) h(i,m)=D(i,1)+D2(k,33); end if h(i,m)D(i,6)+D2(k,34) h(i,m)=D(i,6)+D2(k,34); end if h(i,m)D(i,7)+D2(k,35) h(i,m)=D(

17、i,7)+D2(k,35); end m=m+1; endend運行結果如下：問題三用軟件Lingo編程：model: sets: supply/S1.S7/:p,s,t; need/A1.A21/:L,R,Z,b; links(supply,need):c,x; endsets data: p=160 155 155160 155 150 160; s=800 800 1000 2000 2000 2000 3000; b=104,301,750,606,194,205,201,680,480,300,220,210,420,500,42,10,130,190,260,100; c=170.

18、7, 160.3, 140.2, 98.6, 38, 20.5, 3.1, 21.2, 64.2, 92, 96, 106, 121.2, 128, 142, 60, 95, 100, 105, 115, 125215.7, 205.3, 190.2, 171.6, 111, 95.5, 86, 71.2, 114.2, 142, 146, 156, 171.2, 178, 192, 110, 145, 150, 155, 165, 175230.7, 220.3, 200.2, 181.6, 121, 105.5, 96, 86.2, 48.2, 82, 86, 96, 111.2, 118

19、, 132, 44, 85, 90, 95, 105, 115260.7, 250.3, 235.2, 216.6, 156, 140.5, 131, 116.2, 84.2, 62, 51, 61, 76.2, 83, 97, 80, 50, 55, 60, 70, 80255.7, 245.3, 225.2, 206.6, 146, 130.5, 121, 111.2, 79.2, 57, 33, 51, 71.2, 73, 87, 75, 32, 45, 50, 65, 75265.7, 255.3, 235.2, 216.6,156, 140.5, 131, 121.2, 84.2, 62, 51, 37, 16.2, 11, 28, 80, 50, 37, 36, 10, 0275.7, 265.3, 245.2, 226.6, 166, 150.5, 141, 131.2, 99.2, 77, 64, 56, 38.2, 26, 2, 95, 63, 50,