鋼管訂購和運輸數(shù)學(xué)建模

1、鋼管訂購和運輸數(shù)學(xué)建模論文鋼管訂購和運輸摘 要本文建立了一個運輸問題的最優(yōu)化模型。通過對圖(一)的分析，我們首先直觀地將路線分成兩段，將圖分為兩個子圖建立了模型一, 利用分支定界法求得總費用最優(yōu)解為1279496萬元。然后對模型一進行優(yōu)化，得到全線的最優(yōu)模型二，求得總費用最優(yōu)解為1278632萬元。通過對最優(yōu)模型二的分析，我們得出鋼廠s1的上限產(chǎn)量和鋼廠s6的銷價的的變化對運購計劃和總費用的影響最大，并給出了數(shù)據(jù)結(jié)果。我們利用截取和連接的方法將樹形圖轉(zhuǎn)化成為對線性圖進行分析，并給出了一般的解決方法。對圖(二)給出的具體模型，類似與問題一,分別建立了模型三和模型四,求得最優(yōu)解分別為1408859

2、.4和1403948萬元一、 問題的提出已知有7個鋼廠，可生產(chǎn)輸送天然氣主管道的鋼管，用si表示(i=1,2,7)?，F(xiàn)有個地點（a1,a2,a15），沿著這個地點鋪設(shè)一條輸送天然氣的主管道。為方便計，1km主管道稱為單位鋼管。 一個鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個單位。鋼廠在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為個單位，鋼管出廠銷價1單位鋼管為萬元，如下表：1234567800800100020002000200030001601551551601551501601單位鋼管的鐵路運價如下表：里程(km)300301350351400401450451500運價(萬元)20232629

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

4、網(wǎng)絡(luò)，請就這種更一般的情形給出一種解決辦法，并對圖二按（1）的要求給出模型和結(jié)果。二、問題的分析 該問題是圖論中運輸問題的最優(yōu)化問題。 經(jīng)過分析，我們認(rèn)為總費用可分為兩種費用進行求解，分別為：（1）銷價和運輸鋼管至管道結(jié)點ai(i=1,2,15)的總費用（稱為成本費用）（2）鋪設(shè)過程中的運輸費用； 要解決此問題，我們認(rèn)為有兩點關(guān)鍵：（1）如何求出ai（i=1,2,15）至si(i=1,2,7)的最小成本費用；（2）如何調(diào)整使得各路徑滿足題中的最優(yōu)指標(biāo)。 針對上述問題，我們分別運用了圖上作業(yè)法、枚舉法、逐次修正法、重繞最小生成樹法等方法，在綜合考慮算法的精度和算法的復(fù)雜度后，我們選擇了圖上作業(yè)法

5、、枚舉法、逐次修正法對模型進行逐次優(yōu)化，直至求得最優(yōu)解。三、模型的基本假設(shè)及符號說明（一） 基本假設(shè)：（1）運輸方式的改變所花費用包含在運費中；（2）鐵路線上任意兩點可以直達(dá)，不需中途轉(zhuǎn)車，即鐵路線上兩點間運費按線路總長計算；（3）假設(shè)一單位鋼管可由任意長度鋼管組成，購買鋼管可以非整數(shù)單位購買;（4）不考慮其它外界因素對費用的影響；（5） 鋼管在鋪設(shè)時，先將鋼管運到結(jié)點處，再由結(jié)點處向左右兩方相鄰結(jié)點鋪設(shè)；（6） 在si廠購買鋼管要么為零,要么至少為500單位。（二）符號說明： xij：從鋼廠si運到結(jié)點aj的單位鋼管數(shù)； fij：單位鋼管從鋼廠si運到結(jié)點aj的的最少成本費用； tj：第aj

6、點與aj+1點間的路線長度，j=1,2,14； yj：從結(jié)點aj開始沿管道向右鋪設(shè)的路線長度, j=1,2,3,15； w：鋼管訂購和運輸?shù)目傎M用； mi: 鋼廠si的最小產(chǎn)量，mi=500，i=1,2,3,4,5,6,7 ni: 鋼廠si的產(chǎn)量上限，ni=si，i=1,2, ，7 bi: 圖一中各節(jié)點（見附錄七） vi: 圖二中各節(jié)點（見附錄八）四、模型的建立與求解（一）問題一及其求解：針對圖（一），我們首先采用圖上作業(yè)法對所給圖進行分析，利用枚舉法，我們求出一單位鋼管由鋼管廠si運輸至管道結(jié)點i的最小成本費用，具體數(shù)據(jù)如下表：表一 單位鋼管由si運輸至i的最小成本費用 (單位：萬元)s1s

7、2s3s4s5s6s7a1330.7370.7385.7420.7410.7415.7435.7a2320.3360.3375.3410.3400.3405.3425.3a3300.2345.2355.2395.2380.2385.2405.2a4258.6326.6336.6376.6361.6366.6386.6a5198266276316301306326a6180.5250.5260.5300.5285.5290.5310.5a7163.1241251291276281301a8181.2226.2241.2276.2266.2271.2291.2a9224.2269.2203.224

8、4.2234.2234.2259.2a10252297237222212212237a11256301241211188201226a12266311251221206195216a13281.2326.2266.2236.2226.2176.2198.2a14288333273243228161186a15302347287257242178162 這樣，原問題即轉(zhuǎn)化為通常的運輸問題。我們進一步對上表數(shù)據(jù)進行分析，得到結(jié)論：結(jié)論1：將4、s5兩列數(shù)據(jù)進行對比，發(fā)現(xiàn)同一行中s4列數(shù)據(jù)均大于s5列。由此得出，應(yīng)優(yōu)先考慮鋼廠s5，只有當(dāng)對s5的需求量超過其最大產(chǎn)量時，才需要考慮鋼廠s4。 進一步對

9、原圖進行分析可得：結(jié)論2：由于a1點只有通過a2點才能與鋼廠si連接,故模型中不需考慮往a1運輸鋼管。模型(一)：對表一數(shù)據(jù)進一步分析。將各行數(shù)據(jù)由小到大排序，發(fā)現(xiàn)由a2至a9各行中費用最小的前四個數(shù)據(jù)均在s1,s2,s3,s5列中，由a10至a15各行中費用最小的前三個數(shù)據(jù)均在s5,s6,s7中，直觀感覺到：a1至a9需要來自s6及s7等后一部分鋼廠的鋼管的可能性很小，而且a9至a15不太可能需要s1、s2、s3等前一部分鋼廠生廠的鋼管，故把原圖分為兩個子圖考慮，分別為a1至a9和a9至a15，即分為兩個子模型，分別進行最優(yōu)化，得到兩個子模型(非線性規(guī)劃模型)如下： 子模型1： 子模型2：

10、由于這兩個子模型屬于非線性規(guī)劃問題，且第一個約束條件很復(fù)雜，利用結(jié)論1、2，采用分支定界法用lingo軟件分別進行編程（見附錄一、二）得到： w1=859629.3 w2=419866.7模型一的總費用為w=w1+w2=1279496（萬元）。模型（二）：由于前面的模型直觀將管道分為兩端，即原圖分為兩個子圖，可能存在一定的誤差。下面對模型（一）進行優(yōu)化，即對主管道建立統(tǒng)一模型，如下：同樣利用結(jié)論1、2并采用分支定界法，利用lingo軟件編程（見附錄三）運行得出:最優(yōu)解w=1278632萬元，各節(jié)點向右鋪設(shè)的管道單位數(shù)：y1=0 y2=175 y3=282 y4=0 y5=10 y6=16 y7

11、=76 y8=175 y9=159 y10=30 y11=145 y12=11 y13=34 y14=335 表二 各鋼廠定購計劃：s1s2s3s4s5s6s7數(shù)量800800100001237.51333.50表三 運輸計劃如下（bi含義參見附圖七）:路 線 運量s1-b7-b6-b5-a5-a4; 335s1-b7-b6-a6; 200s1-a7; 265;s2-b8-b4-b2-b1-a2; 179s2-b8-b4-b2-b3-a3; 131.3s2-b8-s1-b7-b6-b5-a5-a4; 116s2-b8-s1-b7-b6-b5-a5; 73.7s2-b8-a8; 300 s3-b

12、9-b8-b4-b2-b3-a3; 319s3-b9-b8-s1-b7-b6-b5-a5-a4; 11s3-b9-a9; 604s5-b12-b11-b10-b9-b8-b4-b2-b3-a3; 57.7s5-b12-b11-b10-b9-b8-s1-b7-b6-b5-a5; 542.3s5-b12-b11-b10-a10; 222.5s5-b12-a11; 415s6-b16-b15-b13-b11-b10-a10; 128.8s6-b16-b15-b13-b14-a12; 86s6-b16-b15-a13; 333s6-a14; 621s6-b16-b17-a15; 165（二）問題（2）

13、的求解 通過模型（二）的求解，我們確定對圖（一）僅需要s1、s2、s3、s5、s6承擔(dān)生產(chǎn)任務(wù)即可取得最優(yōu)解。對模型所用程序進行靈敏度分析，并具體考慮當(dāng)鋼廠鋼管的銷價增加1萬元或產(chǎn)量上限增加1單位時，購運計劃和總費用的變化情況，結(jié)果如下表：表四 鋼廠si的鋼管產(chǎn)量上限增加1單位對總費用的影響s1s2s3s4s5s6s7總費用1278529127859712786071278632127863212786321278632減少量10335250000則可以發(fā)現(xiàn)：鋼廠s1的鋼管產(chǎn)量上限的變動對購運計劃和總費用影響最大。表五 鋼廠si的鋼管銷價增加1萬元對總費用的影響s1s2s3s4s5s6s7總費

14、用1279432127943212796321278632127963913798341278632增加量80080010000100712020則可以發(fā)現(xiàn)：鋼廠s6的鋼管銷價的微小變動對購運計劃和總費用影響最大。（三） 問題（3）的求解 1、一般模型 經(jīng)過對圖（一）的分析求解可以看出，訂購及運輸鋼管的總費用可由各段所需費用求和得到。若要鋪設(shè)的管道是一個樹形圖， 則可以將其轉(zhuǎn)化為線性管道進行分析。具體解題步驟如下：（1）運用圖論的最小權(quán)匹配法（簡單圖可利用枚舉法），求出從各鋼廠定購并運輸一單位鋼管至主管道各結(jié)點的最小成本費用值。（2）將樹型圖轉(zhuǎn)化為線性圖： 在樹形圖中取其最長的線形段，稱為主干

15、線形段；將圖中剩余分支截取，并通過一個虛擬段（長度t為零）聯(lián)接至主干線形段上，組成一個新的線性管道；如，圖二中a9至a16段，可將該段接到a15 點，再分別從原圖a9、a16點連一條長度為0的公路，而在a15點之間連一條長度為0的公路并增加一新的結(jié)點a9，同時約定a15點不向右鋪設(shè)管道。其它各段類似處理。（3）按照問題（一）的思路建立模型進行求解。建立如下非線性規(guī)劃模型：其中k表示鋼廠的總數(shù)，l+1表示管道節(jié)點總數(shù)。2、問題三圖（二）的求解圖（二）為樹形圖，將其轉(zhuǎn)化為類似圖（一）的線性圖。利用枚舉法，求出一單位鋼管由鋼管廠si運輸至管道結(jié)點i的最小成本費用，具體數(shù)據(jù)如下表：表六 單位鋼管由si

16、運輸至i的最小成本費用 (單位：萬元)s1s2s3s5s6s7a1330.7370.7385.4410.7410.7435.7a2320.3360.3375400.3400.3425.3a3300.2345.2355.2380.2385.2405.2a4258.6326.6336.6361.6361.6386.6a5198216276301301326a6180.5250.5260.5285.5290.5310.5a7163.1241251276278.1301a8181.2226.2241.2266.2266.2291.2a9224.2269.2203.2234.2234.2259.2a10

17、252297237212211237a11256301241188201224a12266311251206187216a13281.2326.2266.2226.2166.2198.2a14288333273228161186a15302347287242178162a16220265199230230255a17255300240187197223a18260305245200183210a19265310250205186215a20275320260220160192a21285330270230150186模型（三） 首先類似于模型一，按分段的思想建立模型。由a1a9、a16為一段可

18、得如下模型：由a21-a20-a19-a17-a11-a12-a13-a14-a15-a9-a10-a11-a17-a18為一段可得如下模型：運用lingo軟件進行編程（見附錄四、五）運行結(jié)果為： 費用w1=69127.2 w2=539732.2 則總費用為：w=w1+w2=1408859.4模型（四）： 對整個圖進行考慮，可得如下模型：利用lingo軟件編程（見附錄六）運行得出最優(yōu)解w= 1403948萬元，同時得出下表數(shù)據(jù)：表七 各鋼廠定購計劃：s1s2s3s4s5s6s7數(shù)量80080010000130320000表八 運輸計劃如下（vi含義參見附錄八）:路 線 運量s1-v7-v6-v

19、5-a5; 335s1-v7-v6-a6; 200s1-a7; 265;s2-v8-v4-v2-v1-a2; 179s2-v8-v4-v2-v3-a3; 171s2-v8-s1-v7-v6-v5-a5; 150s2-v8-a8; 300 s3-a16-v8-v4-v2-v3-a3; 336s3-a16-a9; 664s5-a17-v10-v9-a16-v8-v4-v2-v3-a3; 1s5-a17-v10-v9-a16-v8-v4-a4; 468s5-a17-v10-v9-a16-v8-s1-v7-v6-v5-a5; 131s5-a17-v10-v9-a10; 218s5-a17-a11; 380s5-a17; 105s6-a20-a18-v10-v9-a10; 175s6-a20-a19-a17-a11; 111s6-a20-a13; 393s6-a14; 571s6-v11-v12-a15; 165s6-a20-a18; 130s6-a20-a19; 95s6-a20; 260s6-a21; 100（五）模型的評價1、本文從簡單的角度入手建立模型，運用枚舉法、圖上作業(yè)法、圖論等多種方法對模型進行逐步優(yōu)化