鐵路建設中鋼管的訂貨與運輸

鐵路建設中鋼管的訂貨與運輸

1鋼管公路、公路如圖1所示，管道應安裝在a1a2鈉的輸天然氣管道中。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有S1,S2,…,S7。圖中粗線表示鐵路,單細線表示公路,雙細線表示要鋪設的管道(假設沿管道或者原來有公路,或者建有施工公路),圓圈表示火車站,每段鐵路、公路和管道旁的阿拉伯數(shù)字表示里程(單位km)。為方便計劃,1km主管道鋼管稱1單位鋼管。一個鋼廠如果承擔制造這種鋼管,至少需要生產(chǎn)500個單位。鋼廠Si在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為si個單位,鋼管出廠銷價1單位鋼管為pi萬元(見表1)。1單位鋼管的鐵路運價見表2。1000km以上每增加1～100km運價增加5萬元。公路運輸費用為1單位鋼管每千米0.1萬元(不足整千米部分按整千米計算)。鋼管可由鐵路、公路運往(不只是運到點A1,A2,…,A15,而是管道全線)。需制定一個主管道鋼管的訂購和運輸計劃,使總費用最小。2以一個中心集形成圖論體系在待鋪設公路A1,A15上,由于公路運費及鋼管都是以1km為單位,則可以將每千米作為一個單位,得到一個待鋪設公路的頂點集V={V1,V2,…,V5171},把提供鋼管的鋼廠{S1,S2,…,S7}作為另一個頂點集S,則可以用S和V為頂點集形成一個二部圖(S,V),這樣,鋼管的訂購與運輸問題就可以用圖論方法來解決。2.1鐵路、公路、綠化設計首先考慮每個鋼廠分別運送1單位鋼管到各中轉(zhuǎn)點A1,A2,…,A15的最小運輸費用。由圖1可知,所有的道路構(gòu)成網(wǎng)狀圖形,且從每個鋼廠出發(fā)要到達各中轉(zhuǎn)點,必先經(jīng)鐵路,再轉(zhuǎn)公路。此時鐵路的運輸費用與線路的長度不是線性關(guān)系,所以無法使用圖的標準最短路算法,因此必須先對鐵路做一些處理,再計算單位鋼管到各中轉(zhuǎn)點A1,A2,…,A15的運輸費用。具體步驟如下:①利用圖的標準最短路算法,將鐵路網(wǎng)絡圖簡化為任兩點Vi,Vj之間的最短路徑圖L(可用Floyd算法計算,如果兩點之間不連通,認為它們之間的最短路長度為+∞)。②利用題中的鐵路運價表將L中的每條最短路徑轉(zhuǎn)化為運輸費用,將運輸費用圖記為F。③將原圖中剩下的每條公路,按長度換算為每條公路的運輸費用(包括要沿線鋪設管道的公路),由公路路程圖得出公路運輸費用圖J,若兩點不連通,則令Jij=+∞。④在Vi,Vj之間用一條等價的運輸費用邊來替代Vi,Vj間的最短的鐵路線。如果Vi,Vj之間還存在一條公路運費邊,就選擇兩者之間較小的一條邊,這樣就將原來的鐵路、公路運輸圖轉(zhuǎn)換為運輸費用圖。⑤利用圖的標準最短路算法,求公路費用圖中任一個S點到任一個Aj(j=1,…,15)的最小費用路徑,得出最小運輸費用表?？紤]管道沿線的運輸費用,可以計算鋼管運輸?shù)戒佋O地點的費用Cij,其中Cij表示為從鋼廠Si出發(fā)經(jīng)Aj或Aj+1到鋪設地點的運輸費用。2.2“去邊法”調(diào)整作完全二部圖(S,V),邊集E,用eij表示連接Si和Vj的邊(1≤i≤7,1≤j≤5171),如圖2所示。每條邊權(quán)eij為從鋼廠Si到鋪設地點Vj的單位鋼管運輸費用cij與鋼管價格pi之和,即eij=pi+cij。定義1:對于S中每個頂點Si,稱Si鋼廠的最大生產(chǎn)能力為Si的上限,稱Si鋼廠的至少生產(chǎn)能力為Si的下限。定義2:對于V中每個頂點Vj,若eij=min{e1j,e2j,…,e7j},則稱eij為頂點Vj的最優(yōu)邊。定義3:對于V中每個頂點Vj,若ekj=min{e1j,e2j,…,ei-1j,ei+1j,…,e7j},則稱ekj為頂點Vj的次優(yōu)邊。先不考慮鋼廠生產(chǎn)能力上限的限制,對于每個頂點Vj,只保留Vj的最優(yōu)邊。這樣V中每個頂點Vj有且僅有一條邊和S中的頂點相連(即Vj的度數(shù)恒為1),并且Vj上的邊即為Vj的最優(yōu)邊。此時對于每個頂點Si都有一個度數(shù),這個度數(shù)就是對鋼廠Si的鋼管需求量。此時各最優(yōu)邊權(quán)之和即為總費用的下界(見表3)。此時各最優(yōu)邊權(quán)之和即為總費用的下界,其值為1144707.1萬元。但是,這個結(jié)果不滿足S1鋼廠的生產(chǎn)上限為800的要求,為此,必須進行調(diào)整。假設S1的度數(shù)為m,且m>S1的上限,和S1相連的鋪設地點集為{V1,V2,…,Vm},見圖3。由于需要“去邊”使S1的度數(shù)m逐漸減小,直到不超過S1的上限。以S1為例(見圖4),若去掉e11,則V1度數(shù)為0,為保證V1的度數(shù)恒為1,必須找另一個頂點Si(i≠1)和V1相連。由于e11是頂點V1的最優(yōu)邊,所以邊ei1≥e11,產(chǎn)生“費用差”=ei1-e11≥0,即“換邊”后的增加費用。為保證增加的費用最小,應在去掉e11后添加V1上的次優(yōu)邊。由此產(chǎn)生V1的“最小增加費用”u1,u1等于V1對應的次優(yōu)邊的權(quán)減去其對應的最優(yōu)邊的權(quán)。逐點考慮V1,V2,…,Vm,可得到“最小增加費用鏈”u1,u2,…,um。選取uk=min{u1,u2,…,um}所對應的邊e1k,作為S1要去掉的邊,同時添加頂點Vk對應的次優(yōu)邊eik。此時S1的度數(shù)減小1,而Si的度數(shù)增加1。為防止Si的度數(shù)超過其上限,必須在Si到達上限時,將所有與Si廠相連的頂點的對應費用改為+∞。用“去邊法”調(diào)整的具體步驟如下:①從最小費用矩陣中選取每列最小值。②對各鋼廠Si計算需求量。③計算每列最小值與次小值的差值。④對需求量大于上限的鋼廠,選取對應最小增加費用,同時檢驗被選鋼廠需求量是否達到產(chǎn)量上限:a.如果達到或超過上限,令該次小值為+∞。重復上述③和④步驟。b.如果未達到產(chǎn)量上限,用次優(yōu)邊代替最優(yōu)邊,令最優(yōu)邊對應鋼廠的需求量減1,次優(yōu)邊對應鋼廠的需求量加1,重復步驟③和④到所有鋼廠的需求量不大于產(chǎn)量上限。經(jīng)過“去邊法”調(diào)整得到的結(jié)果見表4,將調(diào)整后的邊權(quán)相加,得到訂購與運輸總費用為1277692.2萬元。鑒于鋼廠S7的訂購量為245km,不滿足生產(chǎn)下限的要求,必須進行調(diào)整,使其的訂購量或者為0,或者至少為500。類似于去邊法,分別將S7的供應量改為0(S7點去掉245條邊)和500(S7點增加255條邊),得到總費用分別為1280972.2萬元和1287637.2萬元,顯然,不應該向鋼廠S7訂購鋼管。2.3在有2.2年表ab假設鋪設地點Vp和Vq的供應點分別是Si和Sj,費用分別是Cip和Cjq,如果將Vp和Vq點的供應廠家對調(diào)為:Sj供應Vp,Si供應Vq,而相應的費用為Cjp和Ciq,此時,若Cjp+Ciq<Cip+Cjq,則說明對調(diào)后可以使總費用降低。具體步驟如下:①對于任意兩個鋪設地點Vi和Vj滿足以下條件a.i≠j;b.對應的供應點不為S4和S7鋼廠(因為S4和S7鋼廠的需求