鋼管訂購(gòu)和運(yùn)輸數(shù)學(xué)建模

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

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

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

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

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

6、點(diǎn)與aj+1點(diǎn)間的路線長(zhǎng)度，j=1,2,14； yj：從結(jié)點(diǎn)aj開始沿管道向右鋪設(shè)的路線長(zhǎng)度, j=1,2,3,15； w：鋼管訂購(gòu)和運(yùn)輸?shù)目傎M(fèi)用； 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é)點(diǎn)（見(jiàn)附錄七） vi: 圖二中各節(jié)點(diǎn)（見(jiàn)附錄八）四、模型的建立與求解（一）問(wèn)題一及其求解：針對(duì)圖（一），我們首先采用圖上作業(yè)法對(duì)所給圖進(jìn)行分析，利用枚舉法，我們求出一單位鋼管由鋼管廠si運(yùn)輸至管道結(jié)點(diǎn)i的最小成本費(fèi)用，具體數(shù)據(jù)如下表：表一 單位鋼管由si運(yùn)輸至i的最小成本費(fèi)用 (單位：萬(wàn)元)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 這樣，原問(wèn)題即轉(zhuǎn)化為通常的運(yùn)輸問(wèn)題。我們進(jìn)一步對(duì)上表數(shù)據(jù)進(jìn)行分析，得到結(jié)論：結(jié)論1：將4、s5兩列數(shù)據(jù)進(jìn)行對(duì)比，發(fā)現(xiàn)同一行中s4列數(shù)據(jù)均大于s5列。由此得出，應(yīng)優(yōu)先考慮鋼廠s5，只有當(dāng)對(duì)s5的需求量超過(guò)其最大產(chǎn)量時(shí)，才需要考慮鋼廠s4。 進(jìn)一步對(duì)

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

10、由于這兩個(gè)子模型屬于非線性規(guī)劃問(wèn)題，且第一個(gè)約束條件很復(fù)雜，利用結(jié)論1、2，采用分支定界法用lingo軟件分別進(jìn)行編程（見(jiàn)附錄一、二）得到： w1=859629.3 w2=419866.7模型一的總費(fèi)用為w=w1+w2=1279496（萬(wàn)元）。模型（二）：由于前面的模型直觀將管道分為兩端，即原圖分為兩個(gè)子圖，可能存在一定的誤差。下面對(duì)模型（一）進(jìn)行優(yōu)化，即對(duì)主管道建立統(tǒng)一模型，如下：同樣利用結(jié)論1、2并采用分支定界法，利用lingo軟件編程（見(jiàn)附錄三）運(yùn)行得出:最優(yōu)解w=1278632萬(wàn)元，各節(jié)點(diǎn)向右鋪設(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 表二 各鋼廠定購(gòu)計(jì)劃：s1s2s3s4s5s6s7數(shù)量800800100001237.51333.50表三 運(yùn)輸計(jì)劃如下（bi含義參見(jiàn)附圖七）:路 線 運(yùn)量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（二）問(wèn)題（2）

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

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

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

16、運(yùn)輸至i的最小成本費(fèi)用 (單位：萬(wàn)元)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為一段可得如下模型：運(yùn)用lingo軟件進(jìn)行編程（見(jiàn)附錄四、五）運(yùn)行結(jié)果為： 費(fèi)用w1=69127.2 w2=539732.2 則總費(fèi)用為：w=w1+w2=1408859.4模型（四）： 對(duì)整個(gè)圖進(jìn)行考慮，可得如下模型：利用lingo軟件編程（見(jiàn)附錄六）運(yùn)行得出最優(yōu)解w= 1403948萬(wàn)元，同時(shí)得出下表數(shù)據(jù)：表七 各鋼廠定購(gòu)計(jì)劃：s1s2s3s4s5s6s7數(shù)量80080010000130320000表八 運(yùn)輸計(jì)劃如下（vi含義參見(jiàn)附錄八）:路 線 運(yùn)量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（五）模型的評(píng)價(jià)1、本文從簡(jiǎn)單的角度入手建立模型，運(yùn)用枚舉法、圖上作業(yè)法、圖論等多種方法對(duì)模型進(jìn)行逐步優(yōu)化