管道運(yùn)輸問題論文

1、管道運(yùn)輸問題摘要：本文采用二次規(guī)劃算法來解決。首先將各鋼廠到鋪設(shè)節(jié)點(diǎn)的單位最小運(yùn)費(fèi)轉(zhuǎn)化為求最短路的方法，將鐵路的 運(yùn)輸費(fèi)用、鋼廠的運(yùn)價(jià)與公路的運(yùn)費(fèi)等價(jià)轉(zhuǎn)換，即將公路鐵路合并成一張網(wǎng)，再 利用求最短路的方法求出我們需要的單位最小運(yùn)費(fèi)。對(duì)于問題中鋼廠產(chǎn)量的約束條件， 采用0-1規(guī)劃模型解決。第二步求得沿著鋪設(shè)管道從節(jié)點(diǎn)到各施工地單位的最小運(yùn)費(fèi)，將待鋪設(shè)管道 按單位長(zhǎng)度分解成n個(gè)需求點(diǎn)，直線圖考慮左右兩個(gè)方向的運(yùn)輸，通過構(gòu)建一個(gè) 等差數(shù)列得到目標(biāo)函數(shù)。第三問樹狀圖僅需考慮沿各個(gè)方向的運(yùn)輸。該運(yùn)輸模型 的方法，避免了問題一和三的差別。最后建立一個(gè)二次規(guī)劃的算法模型，利用 lingo軟件進(jìn)行編程求得最優(yōu)

2、解。根據(jù)上述建模思想，我們求得最優(yōu)解為127.84億元。第二問即為靈敏度分 析，我們得出s6鋼廠鋼管的銷價(jià)的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用影響最大，*鋼廠鋼管的產(chǎn)量的上限的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。問題三：第 4、7兩家鋼廠補(bǔ)生產(chǎn)，1、2、3、6四家工廠飽和生產(chǎn)，余下的由5供應(yīng)， 最優(yōu)值約為140.66億元。最后對(duì)模型進(jìn)行了綜合評(píng)價(jià)，并提出了改進(jìn)方向。關(guān)鍵詞：二次規(guī)劃、0-1規(guī)劃、lingo、最短路、目標(biāo)函數(shù)一、問題的重述要鋪設(shè)一條q T氣TT A15的輸送天然氣的主管道，如圖一所示（見下頁(yè)）。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有s, S ,S。圖中粗線表示鐵路，單細(xì)線

3、表示公路， 127雙細(xì)線表示要鋪設(shè)的管道（假設(shè)沿管道或者原來有公路，或者建有施工公路），圓圈表示火車 站，每段鐵路、公路和管道旁的阿拉伯?dāng)?shù)字表示里程（單位km）。為方便計(jì)，1km主管道鋼管稱為1單位鋼管。一個(gè)鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個(gè)單位。鋼廠*在指定期限內(nèi)能i1234567si80080010002000200020003000pi1601551551601551501601單位鋼管的鐵路運(yùn)價(jià)如下表:里程（km） 0總之，該模型為：mm( 些imm( 些i=1 j=2 j必xp +蕓Xc ) +區(qū) (y +(y )| y 1 +1 + z + ij iij ijj j j

4、i =1 j=2j=2j必j必(z )j jz.J +1) 0.05s.t.支 X 3據(jù)00,s i = 1,2,.,7；s.t.iij=2 以4W x = y. + z., j = 2,3,.,15 ；i=1z.+y. +尸 A - A , j = 2,.15； z + y = |A - AlJ J + 1j+1j35 1 531y2=A2 - aj,zi5 = 0;y j ,z j 0,j=2,3,5.15；x 0,i = 1,.,7 j = 2,3,5,.,15對(duì)最小運(yùn)費(fèi)的求解，我們米用Floyd算法。先求出鐵路網(wǎng)上鋼 管廠到鐵路上任意兩點(diǎn)匕，七的最短路線的長(zhǎng)度,用matlab求得七 對(duì)

5、應(yīng)的鐵路單位運(yùn)費(fèi)D ；同理用Floyd算法求出公路網(wǎng)上的任意兩 /點(diǎn)V 的最短公路路線的長(zhǎng)度乙，結(jié)果乘以0.1得到公路運(yùn)費(fèi)D1。 j kjkjkc廣min（D + D1水），j表示所有運(yùn)輸中轉(zhuǎn)點(diǎn)，于是就得到從某鋼廠到某 鋪設(shè)點(diǎn)運(yùn)輸單位鋼管的最少運(yùn)輸費(fèi)用。約束條件：產(chǎn)量約束：支x e ）o 1500,si = 1,2,.,7j=2以4鋪設(shè)約束條件：歹x =七+勺j = 2,.,15;i=15.2題三分析求解：如鋪設(shè)的管道是一個(gè)樹形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)對(duì)于 題圖二，我們可以延用問題一里面的思想，在題圖一的基礎(chǔ)上多幾條 鋪設(shè)路段，9, 11，17節(jié)點(diǎn)的鋪設(shè)方向變?yōu)閄,Y,Z三個(gè)方向，其他不

6、變。5.2.1第一階段:總費(fèi)用為：21 p x +E21 c x i ijij iji=1 j=2i=1 j=25.2.2第二階段：由于樹形圖的出現(xiàn)，則某些管道處會(huì)出現(xiàn)多支路。則模型一中模型的七，z.不再適用，此時(shí)可考慮多增加支路變量Xj， 并增加約束，在目標(biāo)函數(shù)中增加相應(yīng)的鋪設(shè)費(fèi)。minW*=minW*=22 p x+22 c x+2i ii ii=1 j=2i=1 /=2/=2(七+(儀頃 41+ +(z.川M 41+ x +(x.m+1) 0.05(j = 9,11,17)s.t. 2 x 6折口1500,s i = 1,2,.,7 ijij=2 j=427 x = y + z,j =

7、2,3,.,15i=1Z +y = A - A , j = 2,.15； z + y = |A - A j j +1j+1j3553y2=A2 - L = 0;y . ,z j 0,j=2,3,5.15；六、模型的求解1.出廠銷價(jià)、鐵路運(yùn)費(fèi)向公路運(yùn)費(fèi)的轉(zhuǎn)換：1.1運(yùn)輸費(fèi)用等價(jià)轉(zhuǎn)換原則：按單位運(yùn)費(fèi)相等原則將任意兩點(diǎn)的 最短鐵路線轉(zhuǎn)化為公路線。對(duì)于鐵路線上的任意兩點(diǎn)u和V，用Floyd 算法找出兩點(diǎn)間最短鐵路路線的長(zhǎng)度匕，查鐵路運(yùn)價(jià)表求得匕對(duì)應(yīng)的 鐵路單位運(yùn)費(fèi)/ :又設(shè)與該段鐵路等費(fèi)用的公路長(zhǎng)度為/ ,則： / = 0.1* l 史由此，我們就在V和V之間用一條等價(jià)的公路線代替V和V間的最 短鐵路

8、線。如果V和V之間原來就有公路，就選擇新舊公路中簡(jiǎn)短的 一條。這樣我們就把鐵路運(yùn)輸網(wǎng)絡(luò)轉(zhuǎn)換成了公路運(yùn)輸網(wǎng)絡(luò)。1.2銷價(jià)等價(jià)轉(zhuǎn)換法則：按單位費(fèi)用相等將任意鋼廠的單位銷價(jià) 轉(zhuǎn)換為單位運(yùn)價(jià)。對(duì)于鋼廠s的銷售單價(jià)p，我們可以虛設(shè)一條公路線，連接鋼廠 .及另一虛設(shè)鋼廠了的銷售價(jià)為0.2特殊約束條件的處理：由于約束條件支x e0u 500，Si,i=1,7的存在，因此模型 j=2的求解不能簡(jiǎn)單地調(diào)用線性規(guī)劃或者二次規(guī)劃的軟件。引進(jìn)0-1變量f = 1,鋼廠生產(chǎn)i0，鋼廠不生產(chǎn)于是約束條件轉(zhuǎn)換為：500f x s f ,i = 1,2,.,7.j=1七、模型的評(píng)價(jià)與改進(jìn)此模型的最大優(yōu)點(diǎn)是其目標(biāo)函數(shù)為線性函數(shù)，處理起來比較簡(jiǎn)單，而且這種模型對(duì)題 目的第一問和第三問的情況都適用。它的最大缺點(diǎn)是規(guī)模太大，決