鋼管訂購和運輸數(shù)學建模論文

1精品文檔——精品文檔精品資料精品文檔一精品資料鋼管訂購和運輸本文建立了一個運輸問題的最優(yōu)化模型。通過對圖(一)的分析，我們首先直觀地將路線分成兩段，將圖分為兩個子圖建立了模型一，利用分支定界法求得總費用最優(yōu)解為1279496萬元。然后對模型一進行優(yōu)化，得到全線的最優(yōu)模型二，求得總費用最優(yōu)解為1278632萬元。通過對最優(yōu)模型二的分析，我們得出鋼廠S1的上限產量和鋼廠S6的銷價的的變化對運購計劃和總費用的影響最大，并給出了數(shù)據(jù)我們利用截取和連接的方法將樹形圖轉化成為對線性圖進行分鋼管訂購和運輸數(shù)學建模論文2析，并給出了一般的解決方法。對圖(二)給出的具體模型，類似與問題一，分別建立了模型三和模型四，求得最優(yōu)解分別為1408859.4和1403948萬元.鋼管訂購和運輸數(shù)學建模論文3一、問題的提出已知有7個鋼廠，可生產輸送天然氣主管道的鋼管，用S;表。現(xiàn)有15個地點沿著這15個地點鋪設一條輸送天然氣的主管道。為方便計，1km主管道稱為1一個鋼廠如果承擔制造這種鋼管，至少需要生產500個單位。鋼廠s;在指定期限內能生產該鋼管的最大數(shù)量為s;個單位，鋼管出廠銷價1單位鋼管為p,萬元，如下表：i12345671單位鋼管的鐵路運價如下表：里程(km)301～350351～400401～450451～500運價(萬元)里程(km)501～600601～700701～800801～900901～10001000km以上每增加1至100km運價增加5萬元。公路運輸費用為1單位鋼管每公里0.1萬元(不足整公里部分按整公里計算)。鋼管可由鐵路、公路運往鋪設地點(不只是運到點A,A?,…,A?s,而是管道全線)。(1)請制定一個主管道鋼管的訂購和運輸計劃，使總費用最小(給鋼管訂購和運輸數(shù)學建模論文4(2)請就(1)的模型分析：哪個鋼廠鋼管的銷價的變化對購運計劃和總費用影響最大，哪個鋼廠鋼管的產量的上限的變化對購運計劃和總費用的影響最大，并給出相應的數(shù)字結果。(3)如果要鋪設的管道不是一條線，而是一個樹形圖，鐵路、公路和管道構成網(wǎng)絡，請就這種更一般的情形給出一種解決辦法，并對圖二按(1)的要求給出模型和結果。二、問題的分析該問題是圖論中運輸問題的最優(yōu)化問題。(1)銷價和運輸鋼管至管道結點Aj(i=1,2,…,15)的總費用(稱為成本費用)(2)鋪設過程中的運輸費用；要解決此問題，我們認為有兩點關鍵：(1)如何求出Ai(i=1,2,……,15)至(2)如何調整使得各路徑滿足題中的最優(yōu)指標。針對上述問題，我們分別運用了圖上作業(yè)法、枚舉法、逐次修正法、重繞最小生成樹法等方法，在綜合考慮算法的精度和算法的復雜度后，我們選擇了圖上作業(yè)法、枚舉法、逐次修正法對模型進行逐次優(yōu)化，直至求得最優(yōu)解。鋼管訂購和運輸數(shù)學建模論文5三、模型的基本假設及符號說明(1)運輸方式的改變所花費用包含在運費中；(2)鐵路線上任意兩點可以直達，不需中途轉車，即鐵路線上兩點間運費按線路總長計算；(3)假設一單位鋼管可由任意長度鋼管組成，購買鋼管可以非整數(shù)(4)不考慮其它外界因素對費用的影響；(5)鋼管在鋪設時，先將鋼管運到結點處，再由結點處向左右兩方相鄰結點鋪設；(6)在Si廠購買鋼管要么為零，要么至少為500單位。(二)符號說明：x?:從鋼廠S;運到結點A;的單位鋼管數(shù)；f;:單位鋼管從鋼廠S;運到結點A;的的最少成本費用；t:第A;點與Aj?點間的路線長度，j=1,2,…,14;y;:從結點A;開始沿管道向右鋪設的路線長度，j=1,2,3,…,15;w:鋼管訂購和運輸?shù)目傎M用；bi:圖一中各節(jié)點(見附錄七)Vi:圖二中各節(jié)點(見附錄八)6四、模型的建立與求解(一)問題一及其求解：針對圖(一),我們首先采用圖上作業(yè)法對所給圖進行分析，利用枚舉法，我們求出一單位鋼管由鋼管廠S;運輸至管道結點A;的最小成本費用，具體數(shù)據(jù)如下表：表一單位鋼管由S;運輸至A;的最小成本費用(單位：萬元)O這樣，原問題即轉化為通常的運輸問題。我們進一步對上表數(shù)據(jù)進行分析，得到結論：結論1:將S4、S5兩列數(shù)據(jù)進行對比，發(fā)現(xiàn)同一行中S4列數(shù)據(jù)均大于S5列。由此得出，應優(yōu)先考慮鋼廠S5,只有當對S5的需求量超過其最大產量時，才需要考慮鋼廠S4。進一步對原圖進行分析可得：結論2:由于A1點只有通過A2點才能與鋼廠Si連接，故模型中不需考慮往A1運輸鋼管。鋼管訂購和運輸數(shù)學建模論文7模型(一):對表一數(shù)據(jù)進一步分析。將各行數(shù)據(jù)由小到大排序，發(fā)現(xiàn)由A2至A15各行中費用最小的前三個數(shù)據(jù)均在S5,S6,S7中，直觀感覺到：A1至A9需要來自S6及S7等后一部分鋼廠的鋼管的可能性很小，而且A9至A15不太可能需要S1、S2、S3等前一部分鋼廠生廠的鋼管，故把原圖分為兩個子圖考慮，分別為A1至A9和A9至A15,即分為兩個子模型，分別進行最優(yōu)化，得到兩個子模型(非線性規(guī)劃子模型1:子模型2:鋼管訂購和運輸數(shù)學建模論文8附錄一、二)得到：w1=859629.3W2=419866.7模型(二):可能存在一定的誤差。下面對模型(一)進行優(yōu)化，即對主管道建立鋼管訂購和運輸數(shù)學建模論文9附錄三)運行得出：最優(yōu)解W=1278632萬元，各節(jié)點向右鋪設的管道單位數(shù)：Y14=335表二各鋼廠定購計劃：數(shù)量00表三運輸計劃如下(bi含義參見附圖七):路線運量S1-b7-b6-A6:S2-b8-S1-b7-b6-b5-A5-A4;116S3-b9-b8-b4-b2-b3-A3;319鋼管訂購和運輸數(shù)學建模論文S6-b16-b15-b13-b14-A12;86通過模型(二)的求解，我們確定對圖(一)僅需要S1、S2、S3、S5、S6承擔生產任務即可取得最優(yōu)解。對模型所用程序進行靈敏度分析，并具體考慮當鋼廠鋼管的銷價增加1萬元或產量上限增加1單位時，購運計劃和總費用的變化情況，結果如下表：表四鋼廠Si的鋼管產量上限增加1單位對總費用的影響總費用減少量0000則可以發(fā)現(xiàn)：鋼廠S1的鋼管產量上限的變動對購運計劃和總費用表五鋼廠Si的鋼管銷價增加1萬元對總費用的影響總費用增加量00則可以發(fā)現(xiàn)：鋼廠S6的鋼管銷價的微小變動對購運計劃和總費用鋼管訂購和運輸數(shù)學建模論文1、一般模型經過對圖(一)的分析求解可以看出，訂購及運輸鋼管的總費用可由各段所需費用求和得到。若要鋪設的管道是一個樹形圖，則可以將其轉化為線性管道進行分析。具體解題步驟如下：(1)運用圖論的最小權匹配法(簡單圖可利用枚舉法),求出從各鋼廠定購并運輸一單位鋼管至主管道各結點的最小成本費用值。(2)將樹型圖轉化為線性圖：在樹形圖中取其最長的線形段，稱為主干線形段；將圖中剩余分支截取，并通過一個虛擬段(長度t為零)聯(lián)接至主干線形段上，組成一個新的線性管道；如，圖二中A9至A16段，可將該段接到A15點，再分別從原圖A9、A16點連一條長度為0的公路，而在A15點之間連一條長度為0的公路并增加一新的結點A9,同時約定A15點不向右鋪設管道。其它各段類似處理。(3)按照問題(一)的思路建立模型進行求解。建立如下非線性鋼管訂購和運輸數(shù)學建模論文2、問題三圖(二)的求解圖(二)為樹形圖，將其轉化為類似圖(一)的線性圖。利用枚舉法，求出一單位鋼管由鋼管廠Si運輸至管道結點Ai的最小成本費表六單位鋼管由Si運輸至Ai的最小成本費用(單位：萬元A1410.7410.7435.7A2400.3400.3425.3A3405.2A4A5A6A7A8A9A10A11A12A13A14A15鋼管訂購和運輸數(shù)學建模論文A16A17A18A19A20A21模型(三)首先類似于模型一，按分段的思想建立模型。由A1…A9、A16由A21-A20-A19-A17-A11-A12-A13-A14-A15-A9-A10-A11-A17-A18為鋼管訂購和運輸數(shù)學建模論文運用LINGO軟件進行編程(見附錄四、五)運行結果為：費用w1=869127.2w2=539732.2模型(四):對整個圖進行考慮，可得如下模型：利用LINGO軟件編程(見附錄六)運行得出最優(yōu)解w=1403948萬元，同時得出下表數(shù)據(jù)：表七各鋼廠定購計劃：數(shù)量00表八運輸計劃如下(Vi含義參見附錄八):路線運量S1-V7-V6-A6;200S1-A7;S2-V8-S1-V7-V6-V5-A5;150S3-A16-V8-V4-V2-V3-A3;336S6-A20-A13;393S6-A14;571S6-V11-V12-A15;165S6-A20-A18;130S6-A20-A19;95(五)模型的評價1、本文從簡單的角度入手建立模型，運用枚舉法、圖上作業(yè)法、圖論等多種方法對模型進行逐步優(yōu)化。過程嚴謹，理論性強，邏輯嚴密，而且易于理解。2、模型一、三為問題的近似解，但涉及變量少，易于求解，且精度較高；模型二、四為問題的精確解，變量多，求解稍難。3、一般模型(1)(2)式具有很強的通用性，網(wǎng)絡、樹型圖轉化為線性圖的方法也具有一般性；4、本文大量運用了計算機程序，所有數(shù)據(jù)均由計算機處理，故誤差由計算機精度產生，模型具有較好的穩(wěn)定性。參考文獻(1)李德、錢頌迪運籌學清華大學出版社1982年；(2)許卓群等數(shù)據(jù)結構高等教育出版社1987年；鋼管訂購和運輸數(shù)學建模論文(3)滕傳琳管理運籌學中國鐵道出版社(4)[美]E米涅卡網(wǎng)絡和圖的最優(yōu)計算方法1986年；中國道出鐵版社1984年；本題是一個典型的離散優(yōu)化問題，實際上最終歸結為兩個二次規(guī)劃模型。求解的關鍵包括定購和運輸單價的計算、二次規(guī)劃模型的建立和求解。其中的難點是題中復雜圖的恰當處理和模型中變量數(shù)特別是整型變量數(shù)過多的靈活解決。本優(yōu)秀論文在對這兩問題的處理上頗有特色：其一是對問題一的圖，作者首先根據(jù)直觀分析，將原圖分成兩個小圖分別求解，再合二為一建立優(yōu)化模型；而針對問題二的樹形圖，通過增加一個長度為零費用為零的線路轉化為線性圖后，問題二的求解方法就與問題一的求解方法相同了。這是“從簡單到復雜，從局部到全局，化繁瑣為簡單”的建模思想的具體體現(xiàn)。其二是對變量數(shù)過多問題的解決，作者經過約束