管道運輸問題論文

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

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

3、表示公路， 127雙細(xì)線表示要鋪設(shè)的管道（假設(shè)沿管道或者原來有公路，或者建有施工公路），圓圈表示火車 站，每段鐵路、公路和管道旁的阿拉伯?dāng)?shù)字表示里程（單位km）。為方便計，1km主管道鋼管稱為1單位鋼管。一個鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個單位。鋼廠*在指定期限內(nèi)能i1234567si80080010002000200020003000pi1601551551601551501601單位鋼管的鐵路運價如下表:里程（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對最小運費的求解，我們米用Floyd算法。先求出鐵路網(wǎng)上鋼 管廠到鐵路上任意兩點匕，七的最短路線的長度,用matlab求得七 對

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

6、變。5.2.1第一階段:總費用為：21 p x +E21 c x i ijij iji=1 j=2i=1 j=25.2.2第二階段：由于樹形圖的出現(xiàn)，則某些管道處會出現(xiàn)多支路。則模型一中模型的七，z.不再適用，此時可考慮多增加支路變量Xj， 并增加約束，在目標(biāo)函數(shù)中增加相應(yīng)的鋪設(shè)費。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.出廠銷價、鐵路運費向公路運費的轉(zhuǎn)換：1.1運輸費用等價轉(zhuǎn)換原則：按單位運費相等原則將任意兩點的 最短鐵路線轉(zhuǎn)化為公路線。對于鐵路線上的任意兩點u和V，用Floyd 算法找出兩點間最短鐵路路線的長度匕，查鐵路運價表求得匕對應(yīng)的 鐵路單位運費/ :又設(shè)與該段鐵路等費用的公路長度為/ ,則： / = 0.1* l 史由此，我們就在V和V之間用一條等價的公路線代替V和V間的最 短鐵路

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