鋼管訂購(gòu)和運(yùn)輸?shù)囊?guī)劃模型

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

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

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

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

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

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

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

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

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

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

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

12、1x6890x7500下調(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

13、%12083224625（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從上表比較可得，鋼廠的鋼管銷價(jià)的變化對(duì)總費(fèi)用及購(gòu)運(yùn)計(jì)劃影響最大. 用同樣的方法，保持其他條件

14、不變，令各個(gè)鋼廠鋼管產(chǎn)量的上限上浮或下降10%，得出總費(fèi)用和購(gòu)運(yùn)計(jì)劃的變化情況：項(xiàng)目最小值變幅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%120619

15、72500(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)量的上限的變化對(duì)總費(fèi)用及購(gòu)運(yùn)計(jì)劃的影響最大.3、如圖二，要鋪設(shè)的管道不是一條線，而是一

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

17、推廣 我們建立的模型具有較強(qiáng)的可行性和可操作性，并且具有相當(dāng)?shù)膶?shí)際意義.雖然我們未能對(duì)多個(gè)分支規(guī)劃組逐個(gè)進(jìn)行求解從而得出最優(yōu)解，但我們對(duì)模型進(jìn)行了適當(dāng)?shù)慕坪?jiǎn)化處理，減少了計(jì)算量和計(jì)算難度，最后得出可行解.我們建立模型的方法和思想對(duì)其它類似題材也適用，在建筑運(yùn)輸方面適用性較強(qiáng)，并可以推廣到社會(huì)生活中相關(guān)的多個(gè)領(lǐng)域中去.對(duì)于類似的問(wèn)題，對(duì)模型的決策性因素加以具體對(duì)照分析即可.參考文獻(xiàn)：1程里文，吳江，張玉林，運(yùn)籌學(xué)模型與方法教程，清華大學(xué)出版社，北京，20002L.庫(kù)珀，U.N勃哈特，L.J勒布朗（美），運(yùn)籌學(xué)模型概論，上?？茖W(xué)技術(shù)出版社，上海，19873劉寶碇，趙瑞清，隨機(jī)規(guī)劃與模糊規(guī)劃，清華

18、大學(xué)出版社，北京，19984李世奇，杜慧琴，Maple計(jì)算機(jī)代數(shù)系統(tǒng)應(yīng)用及程序設(shè)計(jì)，重慶大學(xué)出版社，1999. （文章編輯：黃綺玲顏學(xué)友）接83頁(yè)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.