數(shù)學(xué)建模B題解答-供參考

1、鋼管訂購和運(yùn)輸摘要： 本文建立了一個運(yùn)輸問題的最優(yōu)化模型。通過分析題圖一，我們利用Floyd算法求出鐵路網(wǎng)和公路網(wǎng)各點(diǎn)間最短路線，然后轉(zhuǎn)化成最少運(yùn)輸，去掉了鐵路和公路的性質(zhì)，使運(yùn)輸網(wǎng)絡(luò)變成一張供需運(yùn)輸價格表，然后建立了一個以總費(fèi)用為目標(biāo)函數(shù)的非線性規(guī)劃模型，利用Lingo 軟件，求出問題一的最優(yōu)解為1278632萬元通過對問題一中l(wèi)ingo運(yùn)行結(jié)果的分析，我們得出S5鋼廠鋼管的銷價的變化對購運(yùn)計劃和總費(fèi)用影響最大，S1鋼廠鋼管的產(chǎn)量的上限的變化對購運(yùn)計劃和總費(fèi)用的影響最大。問題三模型的建立原理和問題一的相同，利用Lingo 軟件，求得最優(yōu)解為1407149萬元.關(guān)鍵詞：Floyd算法，非線性規(guī)

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

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

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

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

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

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

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

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

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

11、與數(shù)學(xué)建模.云南：云南大學(xué)出版社，2009附錄用matlab建立Floyd函數(shù)的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);%對于所有中轉(zhuǎn)點(diǎn)，在鐵路網(wǎng)和公路網(wǎng)上的下標(biāo)相差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代表第一個鋼管生產(chǎn)廠S1點(diǎn) end if c(i,k)D(i,6)+D1(k,34) c(i,k)=D(i,6)+D1(k,34);%34代表第六個鋼管生產(chǎn)廠S6點(diǎn) end if c(i,k)D(i,7)+D1(k,35) c(i,k)=D(i,7)+D1(k,35);%35代表第七個鋼管生產(chǎn)廠S7點(diǎn) endend%因為S1,S6,S7這三個鋼管廠有公路直接連接到鋪設(shè)節(jié)點(diǎn)，所以把這三個點(diǎn)單獨(dú)處理end 運(yùn)行結(jié)果如下：問題一用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運(yùn)行結(jié)果如下：問題三用軟件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,