管道運(yùn)輸與訂購優(yōu)化模型CAI

1、鋼管訂購和運(yùn)輸優(yōu)化模型要鋪設(shè)一條AiA2A15的輸送天然氣的主管道,如圖一所示（見反面）。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有S1,S2, S7。圖中粗線表示鐵路，單細(xì)線表示公路，雙細(xì)線表示要鋪設(shè)的管道（假設(shè)沿管道或者原來有公路，或者建有施工公路），圓圈表示火車站，每段鐵路、公路和管道旁的阿拉伯?dāng)?shù)字表示里程（單位 km）。為方便計(jì)，1km主管道鋼管稱為1單位鋼管。一個鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個單位。鋼廠Si在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為 §個單位，鋼管出廠銷價1單位鋼管為Pi萬元, 如下表：i1234567Si80080010002000200020003

2、000Pi1601551551601551501601單位鋼管的鐵路運(yùn)價如下表:里程（km）<300301350351400401450451500運(yùn)價（萬元）2023262932里程（km）501 6006017007018008019009011000運(yùn)價（萬元）37445055601000km以上每增加1至100km運(yùn)價增加5萬元。公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計(jì)算）鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只是運(yùn)到點(diǎn)A1, A2, , A5,而是管道全線）。問題：(1)請制定一個主管道鋼管的訂購和運(yùn)輸計(jì)劃，使總費(fèi)用最小(給出總費(fèi)用)。思考題：(2)請就(

3、1)的模型分析：哪個鋼廠鋼管的銷價的變化對購運(yùn)計(jì)劃和總費(fèi)用 影響最大，哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運(yùn)計(jì)劃和總費(fèi)用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。(3)如果要鋪設(shè)的管道不是一條線，而是一個樹形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請就這種更一般的情形給出一種解決辦法，并對圖二按(1)的要求給出模型和結(jié)果?；炯僭O(shè):1 .沿鋪設(shè)的主管道以有公路或者有施工公路。2 .在主管道上，每公里卸 1單位的鋼管。3 .公路運(yùn)輸費(fèi)用為1單位鋼管每公里 0.1萬元（不足整公里部分按整公里計(jì)算）4 .在計(jì)算總費(fèi)用時，只考慮運(yùn)輸費(fèi)和購買鋼管的費(fèi)用，而不考慮其他費(fèi)用。5 .在計(jì)算鋼廠的產(chǎn)量對購運(yùn)計(jì)劃影響時，只考慮鋼廠的

4、產(chǎn)量足夠滿足需要的情況，即鋼廠的產(chǎn)量不受限制。6 .假設(shè)鋼管在鐵路運(yùn)輸路程超過1000km時，鐵路每增加1至100km, 1單位鋼管的運(yùn)價增加5萬元。二.符號說明：Si：第i個鋼廠；i 1,2, ,7與：第i個鋼廠的最大產(chǎn)量；i 1,2, ,7Aj ：輸送管道（主管道）上的第 j個點(diǎn)； j 1,2,15Pi ：第i個鋼廠1單位鋼管的銷價；i 1,2,7Xj ：鋼廠Si向點(diǎn)Aj運(yùn)輸?shù)匿摴芰?；i 1,2, ,7 j 1,2, ,15tj ：在點(diǎn)Aj與點(diǎn)Aj 1之間的公路上，運(yùn)輸點(diǎn) Aj向點(diǎn)Aj 1方向鋪設(shè)的鋼管量;j 1,2,3,14（ t1 0）a。： 1單位鋼管從鋼廠 Si運(yùn)到結(jié)點(diǎn)Aj的最少總

5、費(fèi)用，即公路運(yùn)費(fèi)、鐵路運(yùn)費(fèi)和鋼管銷價之和；i 1,2,7 j 1,2,15bj ：與點(diǎn)Aj相連的公路和鐵路的相交點(diǎn)；j 2,3, ,15Aj.j 1：相鄰點(diǎn)Aj與Aj1之間的距離；j 1,2,14三.模型的建立與求解問題一：討論如何調(diào)整主管道鋼管的訂購和運(yùn)輸方案使總費(fèi)用最小由題意可知，鋼管從鋼廠Si到運(yùn)輸結(jié)點(diǎn)Aj的費(fèi)用aj包括鋼管的銷價、鋼管的 鐵路運(yùn)輸費(fèi)用和鋼管的公路運(yùn)輸費(fèi)用。在費(fèi)用 aj最小時，對鋼管的訂購和運(yùn)輸進(jìn) 行分配，可得出本問題的最佳方案。1、求鋼管從鋼廠S運(yùn)到運(yùn)輸點(diǎn)Aj的最小費(fèi)用1）將圖一轉(zhuǎn)換為一系列以單位鋼管的運(yùn)輸費(fèi)用為權(quán)的賦權(quán)圖。由于鋼管從鋼廠 Si運(yùn)到運(yùn)輸點(diǎn)Aj要通過鐵路和

6、公路運(yùn)輸，而鐵路運(yùn)輸費(fèi)用是分段函數(shù)，與全程運(yùn)輸總距離有關(guān)。又由于鋼廠S直接與鐵路相連，所以可先求出鋼廠Si到鐵路與公路相交點(diǎn) bj的最短路徑。如圖三依據(jù)鋼管的鐵路運(yùn)價表，算出鋼廠bj的最小鐵路運(yùn)輸Si到鐵路與公路相交點(diǎn)費(fèi)用，并把費(fèi)用作為邊權(quán)賦給從鋼廠S到bj的邊。再將與bj相連的公路、運(yùn)輸點(diǎn)A及其與之相連的要鋪設(shè)管道的線路（也是公路）添加到圖上，根據(jù)單位鋼管在 公路上的運(yùn)價規(guī)定，得出每一段公路的運(yùn)費(fèi)，并把此費(fèi)用作為邊權(quán)賦給相應(yīng)的邊。 以S為例得圖四31圖四鋼管從鋼廠&運(yùn)到各運(yùn)輸點(diǎn)Aj的鐵路運(yùn)輸與公路運(yùn)輸費(fèi)用權(quán)值圖2）計(jì)算單位鋼管從S1到Aj的最少運(yùn)輸費(fèi)用根據(jù)圖四，借助圖論軟件包中求最短

7、路的方法求出單位鋼管從S1到Aj的最少運(yùn)輸費(fèi)用依次為：170.7 , 160.3 , 140.2 , 98.6 , 38, 20.5 , 3.1 , 21.2 , 64.2 , 92 , 96, 106, 121.2 , 128, 142 （單位：萬元）。加上單位鋼管的銷售價Pi ,得出從鋼廠S1購買單位鋼管運(yùn)輸?shù)近c(diǎn)Aj的最小費(fèi)用aj依次為：330.3, 320.3, 300.2,258.6 , 198, 180.5 , 163.1 , 181.2 , 224.2 , 252, 256, 266, 281.2 , 288, 302 （單位：萬元）。同理，可用同樣的方法求出鋼廠 S2、&

8、、S4、S5、S6、S7到點(diǎn)Aj的最小 費(fèi)用，從而得出鋼廠到點(diǎn)的最小總費(fèi)用（單位：萬元）為：表一Si到點(diǎn)Aj最小費(fèi)用a2a3 a4a5a6 a7 a8 a9a10a11a12a13a14a15s1320.3 300.2 258.6198180.5 163 181.2 224.2252256266281.2288302s2360.3 345.2 326.6266250.5 241 226.2 269.2297301311326.2333347s3375.3 355.2 336.6276260.5 251 241.2 203.2237241251266.2273287s4410.3 395.2 3

9、76.6316300.5 291 276.2 244.2222211221236.2243257s5400.3 380.2 361.6301285.5 276 266.2 234.2212188206226.2228242s6405.3 385.2 366.6306290.5 281 271.2 234.2212201195176.2161178s7425.3 405.2 386.6326310.5 301 291.2 259.2237226216198.21861622 、建立模型運(yùn)輸總費(fèi)用可分為兩部分： 運(yùn)輸總費(fèi)用=鋼廠到各點(diǎn)的運(yùn)輸費(fèi)用 +鋪設(shè)費(fèi)用。運(yùn)輸費(fèi)用：若運(yùn)輸點(diǎn)Aj向鋼廠Si訂購Xi

10、j單位鋼管，則鋼管從鋼廠Si運(yùn)到運(yùn)輸點(diǎn)Aj所需的費(fèi)用為aijXij。由于鋼管運(yùn)到 Ai必須經(jīng)過A2,所以可不考慮 Ai ,那157么所有鋼管從各鋼廠運(yùn)到各運(yùn)輸點(diǎn)上的總費(fèi)用為：xj aj。j 2 i 1鋪設(shè)費(fèi)用：當(dāng)鋼管從鋼廠Si運(yùn)到點(diǎn)Aj后，鋼管就要向運(yùn)輸點(diǎn) Aj的兩邊AjAji 段和Aj iAj段運(yùn)輸（鋪設(shè)）管道。設(shè) Aj向AjAj i段鋪設(shè)的管道長度為 yj ,則Aj 心“tj tj I向AjAj i段的運(yùn)輸費(fèi)用為O.i （I 2 yj） （萬元）；由于相鄰運(yùn)輸j 20點(diǎn)Aj與Aj i之間的距離為Aj.j i ,那么Aji向AjAj i段鋪設(shè)的管道長為Aj.j i tj ,所對應(yīng)的鋪設(shè)費(fèi)用為

11、14道上的鋪設(shè)費(fèi)用為：j 7總費(fèi)用為：ftjtj1i 20Aj1”Aj.j tj(萬元)。所以，主管20AtiA tCj.jiLjICj.j iL j201514Xij aijt. t i A-tJ i jj.j i-20i A-tJ.j ii j20又因?yàn)橐粋€鋼廠如果承擔(dān)制造鋼管任務(wù),至少需要生產(chǎn)500個單位，鋼廠Si在指定期限內(nèi)最大生產(chǎn)量為 Si個單位，故500I5Xij j 2Si或15Xij0 因此本j 2問題可建立如下的非線性規(guī)劃模型：I4min ftj(tj i) (Aj.j i20tj)(Aj.ji 120tj)157Xij aij j 2 i 1Xijnjj 2,3, ,i5s

12、.t. 500I5Xij 215Si或 Xij 0j 2Xij 00 tji i, ,7, j 2, ,i5A Cj.j i3、模型求解1515由于MATLA壞能直接處理Z束條件：500xj'或 xj 0 ,我們可j 2先將此條件改為15 XijSi ,得到如下模型：j 2157xij aij j 2 i 1min f14 tj(tj 1)(Aj.j i tj)(Aj.j i 1 tj)j 1(2020i 115xjnj j 2,3, ,15xij si j 2xj 0 i 1,7, j 2, ,150 t A) j.j 1用MATLA陳解，分析結(jié)果后發(fā)現(xiàn)購運(yùn)方案中鋼廠S7的生產(chǎn)量不足500單位，下面我們采用不讓鋼廠 S7生產(chǎn)和要求鋼廠S7的產(chǎn)量不小于500個單位兩種方法計(jì) 算：1 ）不讓鋼廠S7生產(chǎn)計(jì)算結(jié)果：f1 1278632 （萬元）（此時每個鋼廠的產(chǎn)量都滿足條件）。2 ）要求鋼廠 S的產(chǎn)量不小于500個單位計(jì)算結(jié)果：f2 1279664 （萬元）（此時每個鋼廠的產(chǎn)量都滿足條件）比較這兩種情況，得最優(yōu)解為，min f min（ f1,f2）f1 =1278632 （萬元）具體的購運(yùn)計(jì)劃如表二：表二問題一的訂購和調(diào)運(yùn)方案訂購量A2