鋼管訂購和運輸?shù)囊?guī)劃模型

1、 鋼管訂購和運輸?shù)囊?guī)劃模型丹妮摘要：本文就天然氣管道鋼管的訂購和運輸問題，建立了使訂購和運輸總費用最小的優(yōu)化模型.我們把計算分為訂貨和鐵路，公路費用的計算及管道上運輸費用的計算兩個部分.對第一部分的計算，我們采用了增減約束條件的方法，避免了求解一組多分支規(guī)劃的繁重的計算.對第二部分的計算，我們綜合各種可能情況作出比較，從而使計算簡化，并求出了最優(yōu)的鋼管訂購和運輸計劃.對于第二問，我們把每個鋼廠的銷價及生產(chǎn)上限在一定圍浮動，觀察比較得出鋼廠鋼管的銷價的變化對購運計劃和總費用影響最大，鋼廠鋼管的產(chǎn)量的上限的變化對購運計劃和總費用的影響最大.在第三問中運用第一問的方法建立模型，同樣求出了鐵路，公路和

2、管道構(gòu)成網(wǎng)絡(luò)時總費用最小的鋼管訂購和運輸計劃.一 題的重述要鋪設(shè)一條的輸送天然氣的主管道.經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有.連接鋼廠（i=1,15）和的有鐵路和公路.沿管道或者原來有公路，或者建有施工公路.一個鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個單位.已知鋼廠在指定期限能生產(chǎn)該鋼管的最大數(shù)量，鋼管出廠銷價及1單位鋼管的鐵路運價和公路運輸費.鋼管不只是運到點 而是管道全線.問如何制定一個主管道鋼管的訂購和運輸計劃，使總費用最??；哪個鋼廠的銷價變化對購運計劃和總費用影響最大，哪個鋼廠鋼管的產(chǎn)量的上限的變化對可以計劃和總費用的影響最大；如果要鋪設(shè)的管道不是一條線，而是一個樹形圖，鐵路

3、，公路和管道構(gòu)成網(wǎng)絡(luò)，如何建立相應(yīng)的模型和如何求解.A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A11A711A11A8A11A911A11A10A11A12A13A14A15S1S2S3S4S5S6S7圖一A132580101031201242701088107062703020203045010430175060619420520

4、16804803002202104205006003060195202720690520170690462160320160110290115011001200A19130190260100A2A3A4A5A6A7A8A11A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A17A18A20(A21)圖二二 本假設(shè)與符號約定1) 1km主管道鋼管稱為1單位鋼管；2) 假設(shè)在鋼廠的訂購貨量為個單位；3) 對于圖一，鐵路和公路相交的車站從左到右分別記為；4) 對于圖二，鐵路和公路相交的車站或者鐵路和管道相交的車站從左到右分別記為；5) 假設(shè)鋼廠流經(jīng)站的鋼管量為個單位；6)

5、假設(shè)處的到貨量為；7) 假設(shè)1單位鋼管從鋼廠運到的運價為；8) 鋼廠在指定期限能生產(chǎn)該鋼管的最大數(shù)量是個單位；9) 鋼管出廠銷價1單位鋼管為萬元；10) 假設(shè)鐵路運費是整段計算的（從貨物上車到下車一次性收費），二不是分段計算；11) 沿管道公路的運費計算與其他公路一致，且不考慮流量限制的問題.三 問題的分析從圖上可以看出，各鋼廠訂購的鋼管必先經(jīng)鐵路或公路運往主管道與公路的各節(jié)點上再沿主管道進行運輸和鋪設(shè).因此，我們可以把運輸?shù)目傎M用分為在非管道（鐵路或公路）上的運輸費用和主管道上的運輸費用兩部分來計算.對于非管道上的運輸.由于鋼廠承擔(dān)制造鋼管后至少生產(chǎn)500個單位，所以對于每一個鋼廠來說，訂購

6、量要么為0，要么就大于或等于500個單位，這就構(gòu)成一組個的多分支線性規(guī)劃問題，計算將非常復(fù)雜.但我們可以采用如下辦法簡化計算：對所有鋼廠的產(chǎn)量先不設(shè)下限進行求解，若解出來的訂購量都符合不小于500個單位的情況則為可行解，若解出來的訂購量中有不為0的，但小于500個單位，則在約束條件中加進這個訂購量的下限進行求解，直至得出符合條件的最優(yōu)解.對于管道上的鋼管運輸鋪設(shè)的費用則比較復(fù)雜，鋼管從一個點出發(fā)，可以單純沿管道公路進行運輸，也可以一邊運輸一邊鋪設(shè)，要使運輸費最優(yōu)是類似一次規(guī)劃的非線性規(guī)劃問題，由于變量多，計算量大，因此要進行一定的簡化.我們現(xiàn)證明一重要結(jié)論：當(dāng)管道上各節(jié)點的鋼管量等于與節(jié)點相連

7、接的兩邊管道總長度的一半時，管道上鋼管的運輸費最小.設(shè)運價為y，運量為x,y是x的函數(shù)，并且有（其中路程單位為km）.假設(shè)一段長為S的路程，量為x的鋼管從其中一端點出發(fā)，y-x的關(guān)系如圖所示： y y ykx ks kx k(x-s) 0 x s x 0 s x 0 s x運費g即是圖中陰影部分的面積.當(dāng)x<s時，當(dāng)x=s時，當(dāng)x>s時，容易看出，當(dāng)x>s時，對g來求導(dǎo)有：，推出為穩(wěn)定點.在0,s區(qū)間上，所以當(dāng)時，費用是最小的，由此方法我們計算出管線上的最小運輸費t=61593.275萬元.四 模型的建立和求解1,通過上面的分析，我們首先先令各鋼廠訂購的鋼管運往各節(jié)點的鐵（公

8、）路運費和訂購費最優(yōu)，然后我們把各鋼廠訂購的鋼管分成17份分別運往與公路相連的火車站.由于鐵路軌道成樹狀分布，所以這樣的最優(yōu)路線是確定的.通過對圖一的分析，我們發(fā)現(xiàn)， 這四段管道路有這樣的情況：1單位鋼管從這些管道路之一運過的運費，比從連結(jié)該管道路兩端點的最短的公（鐵）路線運過的運費要高.也就是說，與其將鋼管經(jīng)過這些管道路運輸，不如發(fā)生“倒運”.因此，這些管道路左右兩邊的鋼管存貨應(yīng)該要滿足兩邊管道鋪設(shè)的需要，而不應(yīng)該經(jīng)這四段管道路進行貨物調(diào)送.根據(jù)前面的假設(shè)，我們列出如下以鐵（公）路運費和訂購費為目標(biāo)函數(shù)的線性規(guī)劃：s.t 由于只對作非負(fù)限制時，計算出低于下界500，所以需另加約束條件重新求解

9、得：f=1015556, .這樣，我們得到各節(jié)點的鋼管量，然后一邊運輸一邊鋪設(shè)這些鋼管，求出所需運費為 q=366409.05萬元，所以這樣的運輸方案得到的總費用為m=1381965.05萬元. 對于這個方案我們還要進行調(diào)整.由上面的討論我們知道，當(dāng)管道上各節(jié)點的鋼管量剛好等于與節(jié)點相連接的兩邊管道總長度的一半時，在管道上的運輸費用最小.我們把（）( 0, 254.5, 525.5, 678, 400, 199.5, 203, 440.5, 580, 390, 260, 215, 315, 460, 250 ) 作為約束條件加進上述規(guī)劃中，解得m=13066563萬元，可見這樣的運輸方案更優(yōu).

10、我們可以再考慮把各鋼廠的鋼管運到各節(jié)點后，再通過運輸調(diào)整到運輸最小時分鋼量分布.調(diào)整的運輸費用為.其中是1單位鋼管從到沿管線運輸?shù)膬r格，是從到沿管線的鋼管運輸量.因此我們又得到如下規(guī)劃 其中，s.t （加上一規(guī)劃約束條件中的（1）至（16）及（25）用Maple軟件解得：F=1203697.575, 經(jīng)過比較，我們認(rèn)為這個訂購和運輸?shù)姆桨甘亲顑?yōu)的.由此可得詳細(xì)的訂運方案如下：（1）7個鋼廠的訂購量分別為.（2）鋼廠的鋼管分3批運輸，第一批197個單位運往，第二批400個單位運到，第三批203個單位直接沿公路運到.鋼廠的鋼管分兩批運輸，第一批359.5個單位運往，另一批經(jīng)運到.鋼廠的鋼管也分兩批

11、運輸，第一批420個單位經(jīng) 運到，另一批580個單位經(jīng)運往.鋼廠的鋼管分六批運輸，第一批45個單位運往,第二批166個單位運往，第三批61個單位運往，第四批199.5個單位經(jīng)運到，第五批390單位運到，第六批260個單位運往.鋼廠的鋼管分三批運輸，第一批115個單位往，第二批315個單位往，第三批420個單位直接沿公路運往.鋼廠的鋼管全部直接運到.2，根據(jù)我們建立的模型，保持其它條件不變，令各個鋼廠的鋼管銷價上浮或下降5，可得到總費用的變化幅度和運購計劃的變化情況，如下表：項目p1上調(diào)5%最小值1209827變幅6400（0.53%）x1800x2800x31000x40x51181x6890

12、x7500下調(diào)5%1197297-6400（0.5%）800800100001181890500P2上調(diào)5%12098976199（0.5%）800800100007911280500下調(diào)5%11974976200（5.2%）800800100001181890500P3上調(diào)5%12114477749（6.4%）800800100001181890500下調(diào)5%1195947-7750（6.4%）800800100007911280500P4上調(diào)5%12036970800800100007901280500下調(diào)5%12036970800800100001181890500P5上調(diào)5%12083

13、224625（3.8%）800800100002001871500下調(diào)5%12083224625（3.8%）800800100002001871500P6上調(diào)5%12103726675（5.5%）800800100001181890500下調(diào)5%12103726675（5.5%）800800100001181890500P7上調(diào)5%12076974000（3.3%）800800100007911280500下調(diào)5%1199697-4000（3.3%）800800100001181890500從上表比較可得，鋼廠的鋼管銷價的變化對總費用及購運計劃影響最大. 用同樣的方法，保持其他條件不變，令各個

14、鋼廠鋼管產(chǎn)量的上限上浮或下降10%，得出總費用和購運計劃的變化情況：項目最小值變幅X1X2X3X4X5X6X7S1上調(diào)10%1195457-8240(0.69%)880800100001101890500下調(diào)10%12119378240(0.68%)720800100001261890500S2上調(diào)10%1200497-3200(0.27%)800880100001101890500下調(diào)10%12068973200(0.27%)800720100001261890500S3上調(diào)10%12011972500(0.21%)800800110001081890500下調(diào)10%12061972500(

15、0.21%)80080090001281890500S5上調(diào)10%12036970800800100007911280500下調(diào)10%12036970800800100001181890500S6上調(diào)10%12036970800800100001181890500下調(diào)10%12036970800800100007911280500S7上調(diào)10%12036970800800100001181890500下調(diào)10%12036970800800100001181890500同樣由上表可得出，鋼廠的鋼管產(chǎn)量的上限的變化對總費用及購運計劃的影響最大.3、如圖二，要鋪設(shè)的管道不是一條線，而是一個樹形圖，鐵

16、路、公路和管道構(gòu)成網(wǎng)絡(luò).管道運輸最優(yōu)時各個的存鋼量為對于這三個兼為火（汽）車中轉(zhuǎn)站的點，我們把它們一分為二看待.以為例，一方面看成的貨物由此經(jīng)過，一方面看成，其鋼管量為與之相連接的兩段管道總長度的一半，并且鋼管直接從它運到主管道.根據(jù)第一問的做法，先把的鋼管量預(yù)置成L的數(shù)量值，這樣沿主管道的運輸費用就能降到最低，在此基礎(chǔ)上對各鋼廠的定貨量及其分流方式進行調(diào)配.然后，使用第一問的方法列出線性規(guī)劃如下：初次求解結(jié)果，因此我們加入約束條件，再次求解：最小費用 （萬元），其中e是當(dāng)節(jié)點上的鋼管量取自中的數(shù)值時，仿照問題一中的計算方法所得出的管道上的運輸費用，萬元.五 模型的優(yōu)缺點分析及其推廣 我們建立

17、的模型具有較強的可行性和可操作性，并且具有相當(dāng)?shù)膶嶋H意義.雖然我們未能對多個分支規(guī)劃組逐個進行求解從而得出最優(yōu)解，但我們對模型進行了適當(dāng)?shù)慕坪喕幚?，減少了計算量和計算難度，最后得出可行解.我們建立模型的方法和思想對其它類似題材也適用，在建筑運輸方面適用性較強，并可以推廣到社會生活中相關(guān)的多個領(lǐng)域中去.對于類似的問題，對模型的決策性因素加以具體對照分析即可.參考文獻：1程里文，吳江，運籌學(xué)模型與方法教程，清華大學(xué)，20002L.庫珀，U.N勃哈特，L.J勒布朗（美），運籌學(xué)模型概論，科學(xué)技術(shù)，19873寶碇，瑞清，隨機規(guī)劃與模糊規(guī)劃，清華大學(xué)，19984世奇，杜慧琴，Maple計算機代數(shù)系統(tǒng)

18、應(yīng)用及程序設(shè)計，大學(xué)，1999. （文章編輯：黃綺玲顏學(xué)友）接83頁DijS1S2S3S4S5S6S7A10000000A2160.3205.3220.3250.3245.3255.3265.3A3140.2190.2200.2235.2225.2235.2245.3A498.6171.6181.6216.6206.6216.6226.6A538111121156146156166A620.595.5105.5140.5130.5140.5150.5A73.188.198.1133.1123.1133.1143.1A821.271.286.2116.2111.2121.2131.2A964.2114.248.284.279.