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

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