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

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

2、鐵路運(yùn)價(jià)如下表：里程(km)300301350351400401450451500運(yùn)價(jià)(萬元)2023262932里程(km)5016006017007018008019009011000運(yùn)價(jià)(萬元)37445055601000km以上每增加1至100km運(yùn)價(jià)增加5萬元。公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計(jì)算）。鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只是運(yùn)到點(diǎn)，而是管道全線）。問題：（1）請制定一個(gè)主管道鋼管的訂購和運(yùn)輸計(jì)劃，使總費(fèi)用最?。ńo出總費(fèi)用)。思考題：（2）請就（1）的模型分析：哪個(gè)鋼廠鋼管的銷價(jià)的變化對購運(yùn)計(jì)劃和總費(fèi)用影響最大，哪個(gè)鋼廠鋼管的產(chǎn)量的上限的變

3、化對購運(yùn)計(jì)劃和總費(fèi)用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。（3）如果要鋪設(shè)的管道不是一條線，而是一個(gè)樹形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請就這種更一般的情形給出一種解決辦法，并對圖二按（1）的要求給出模型和結(jié)果。A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A11A711A11A8A11A911A11A10A11A12A13A14A15S1S

4、2S3S4S5S6S7圖一A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A19130190260100A2A3A4A5A6A7A8A11A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A17A18A20(A21)圖二一 基本假設(shè)：1 沿鋪設(shè)的主管道以有公路或者有施工公路。2 在主管道上，每公里卸1單位的鋼管。3 公路運(yùn)輸費(fèi)用為1單

5、位鋼管每公里0.1萬元（不足整公里部分按整公里計(jì)算）4 在計(jì)算總費(fèi)用時(shí)，只考慮運(yùn)輸費(fèi)和購買鋼管的費(fèi)用，而不考慮其他費(fèi)用。5 在計(jì)算鋼廠的產(chǎn)量對購運(yùn)計(jì)劃影響時(shí)，只考慮鋼廠的產(chǎn)量足夠滿足需要的情況，即鋼廠的產(chǎn)量不受限制。6 假設(shè)鋼管在鐵路運(yùn)輸路程超過1000km時(shí)，鐵路每增加1至100km，1單位鋼管的運(yùn)價(jià)增加5萬元。二符號(hào)說明：第個(gè)鋼廠； ：第個(gè)鋼廠的最大產(chǎn)量； ：輸送管道（主管道）上的第個(gè)點(diǎn)； ：第個(gè)鋼廠1單位鋼管的銷價(jià)； ：鋼廠向點(diǎn)運(yùn)輸?shù)匿摴芰浚?：在點(diǎn)與點(diǎn)之間的公路上，運(yùn)輸點(diǎn)向點(diǎn)方向鋪設(shè)的鋼管量； ()：1單位鋼管從鋼廠運(yùn)到結(jié)點(diǎn)的最少總費(fèi)用，即公路運(yùn)費(fèi)鐵路運(yùn)費(fèi)和 鋼管銷價(jià)之和； ：與點(diǎn)相連

6、的公路和鐵路的相交點(diǎn)； ：相鄰點(diǎn)與之間的距離； 三模型的建立與求解問題一：討論如何調(diào)整主管道鋼管的訂購和運(yùn)輸方案使總費(fèi)用最小由題意可知，鋼管從鋼廠到運(yùn)輸結(jié)點(diǎn)的費(fèi)用包括鋼管的銷價(jià)鋼管的鐵路運(yùn)輸費(fèi)用和鋼管的公路運(yùn)輸費(fèi)用。在費(fèi)用最小時(shí)，對鋼管的訂購和運(yùn)輸進(jìn)行分配，可得出本問題的最佳方案。1、 求鋼管從鋼廠運(yùn)到運(yùn)輸點(diǎn)的最小費(fèi)用1）將圖一轉(zhuǎn)換為一系列以單位鋼管的運(yùn)輸費(fèi)用為權(quán)的賦權(quán)圖。由于鋼管從鋼廠運(yùn)到運(yùn)輸點(diǎn)要通過鐵路和公路運(yùn)輸，而鐵路運(yùn)輸費(fèi)用是分段函數(shù)，與全程運(yùn)輸總距離有關(guān)。又由于鋼廠直接與鐵路相連，所以可先求出鋼廠到鐵路與公路相交點(diǎn)的最短路徑。如圖三 圖三 鐵路網(wǎng)絡(luò)圖依據(jù)鋼管的鐵路運(yùn)價(jià)表，算出鋼廠到鐵

7、路與公路相交點(diǎn)的最小鐵路運(yùn)輸費(fèi)用，并把費(fèi)用作為邊權(quán)賦給從鋼廠到的邊。再將與相連的公路、運(yùn)輸點(diǎn)及其與之相連的要鋪設(shè)管道的線路（也是公路）添加到圖上，根據(jù)單位鋼管在公路上的運(yùn)價(jià)規(guī)定，得出每一段公路的運(yùn)費(fèi)，并把此費(fèi)用作為邊權(quán)賦給相應(yīng)的邊。以為例得圖四 圖四 鋼管從鋼廠運(yùn)到各運(yùn)輸點(diǎn)的鐵路運(yùn)輸與公路運(yùn)輸費(fèi)用權(quán)值圖2）計(jì)算單位鋼管從到的最少運(yùn)輸費(fèi)用根據(jù)圖四，借助圖論軟件包中求最短路的方法求出單位鋼管從到的最少運(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（單位：萬元）。加上單位鋼管的銷售價(jià)，得出從鋼廠

8、購買單位鋼管運(yùn)輸?shù)近c(diǎn)的最小費(fèi)用依次為：330.3，320.3，300.2，258.6，198，180.5，163.1，181.2，224.2，252，256，266，281.2，288，302（單位：萬元）。同理，可用同樣的方法求出鋼廠到點(diǎn)的最小費(fèi)用，從而得出鋼廠到點(diǎn)的最小總費(fèi)用（單位：萬元）為： 表一 到點(diǎn)最小費(fèi)用a2a3a4a5a6a7a8a9a10a11a12a13a14a15s1320.3300.2258.6198180.5163181.2224.2252256266281.2288302s2360.3345.2326.6266250.5241226.2269.229730131132

9、6.2333347s3375.3355.2336.6276260.5251241.2203.2237241251266.2273287s4410.3395.2376.6316300.5291276.2244.2222211221236.2243257s5400.3380.2361.6301285.5276266.2234.2212188206226.2228242s6405.3385.2366.6306290.5281271.2234.2212201195176.2161178s7425.3405.2386.6326310.5301291.2259.2237226216198.2186162

10、2、建立模型運(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)向鋼廠訂購單位鋼管，則鋼管從鋼廠運(yùn)到運(yùn)輸點(diǎn)所需的費(fèi)用為。由于鋼管運(yùn)到必須經(jīng)過，所以可不考慮，那么所有鋼管從各鋼廠運(yùn)到各運(yùn)輸點(diǎn)上的總費(fèi)用為：。鋪設(shè)費(fèi)用：當(dāng)鋼管從鋼廠運(yùn)到點(diǎn)后，鋼管就要向運(yùn)輸點(diǎn)的兩邊段和段運(yùn)輸（鋪設(shè)）管道。設(shè)向段鋪設(shè)的管道長度為，則向段的運(yùn)輸費(fèi)用為（萬元）；由于相鄰運(yùn)輸點(diǎn)與之間的距離為，那么向段鋪設(shè)的管道長為，所對應(yīng)的鋪設(shè)費(fèi)用為（萬元）。所以，主管道上的鋪設(shè)費(fèi)用為： 總費(fèi)用為：又因?yàn)橐粋€(gè)鋼廠如果承擔(dān)制造鋼管任務(wù)，至少需要生產(chǎn)500個(gè)單位，鋼廠在指定期限內(nèi)最大生產(chǎn)量為個(gè)單位，故 或

11、因此本問題可建立如下的非線性規(guī)劃模型： 3、模型求解：由于MATLAB不能直接處理約束條件：或，我們可先將此條件改為，得到如下模型： 用MATLAB求解，分析結(jié)果后發(fā)現(xiàn)購運(yùn)方案中鋼廠的生產(chǎn)量不足500單位，下面我們采用不讓鋼廠生產(chǎn)和要求鋼廠的產(chǎn)量不小于500個(gè)單位兩種方法計(jì)算： 1）不讓鋼廠生產(chǎn) 計(jì)算結(jié)果：1278632（萬元）（此時(shí)每個(gè)鋼廠的產(chǎn)量都滿足條件）。 2）要求鋼廠的產(chǎn)量不小于500個(gè)單位 計(jì)算結(jié)果： 1279664 （萬元） （此時(shí)每個(gè)鋼廠的產(chǎn)量都滿足條件）。比較這兩種情況，得最優(yōu)解為， =1278632（萬元） 具體的購運(yùn)計(jì)劃如表二：表二 問題一的訂購和調(diào)運(yùn)方案 訂購量A2A3A4A5A6A7A8A9A10A11A12A13A14