鐵路建設(shè)中鋼管的訂貨與運(yùn)輸

鐵路建設(shè)中鋼管的訂貨與運(yùn)輸

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