鋼管的訂購(gòu)與運(yùn)輸

1、 建模案例：鋼管訂購(gòu)及運(yùn)輸優(yōu)化模型建模案例：鋼管訂購(gòu)及運(yùn)輸優(yōu)化模型20002000年年“網(wǎng)易杯網(wǎng)易杯”全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B B題題 一、問(wèn)題提出一、問(wèn)題提出 要鋪設(shè)一條輸送天然氣的主管道A1A2A15，能生產(chǎn)這種鋼管的廠家一共有:S1,S2,S7 。廠家與管道間的交通網(wǎng)絡(luò)交通網(wǎng)絡(luò)已知。假設(shè)沿管道或者原來(lái)有公路，或者建有施工公路。 為方便計(jì)算，1km主管道鋼管稱為1單位鋼管。一個(gè)鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500個(gè)單位。鋼廠Si在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為si 個(gè)單位，鋼廠1單位鋼管的出廠銷價(jià)為pi萬(wàn)元，如下表： I1 2 3 4 5 6 7 SI80

2、0 800 1000 2000 2000 2000 3000 Pi160 155 155 160 155 150 160 1單位鋼管的鐵路運(yùn)價(jià)鐵路運(yùn)價(jià)如下表，1000km以上每增加1至100km運(yùn)價(jià)增加5萬(wàn)元。公路運(yùn)輸費(fèi)用公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬(wàn)元（不足整公里部分按整公里計(jì)算）。鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只是運(yùn)到主管道結(jié)點(diǎn)A1,A2, A15 ,而是管道全線）。里程（km） 300 301350 351400 401450 451500 運(yùn)價(jià)（萬(wàn)元） 20 23 26 29 32 里程（km） 501600 601700 701800 801900 9011000 運(yùn)價(jià)（

3、萬(wàn)元） 37 44 50 55 60 （1 1）請(qǐng)制定一個(gè)主管道鋼管主管道鋼管的訂購(gòu)和運(yùn)輸計(jì)劃，使總費(fèi)用最?。ńo出總費(fèi)用）。 （2 2）請(qǐng)就（）的模型分析：哪個(gè)鋼廠鋼管的銷銷價(jià)的變化價(jià)的變化對(duì)購(gòu)運(yùn)計(jì)劃購(gòu)運(yùn)計(jì)劃和總費(fèi)用總費(fèi)用影響最大，哪個(gè)鋼廠鋼管的產(chǎn)量的上限的變化產(chǎn)量的上限的變化對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果。 （3 3）如果要鋪設(shè)的管道不是一條線，而是一個(gè)樹樹形圖形圖，鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請(qǐng)就這種更一般的情況給出一種解決辦法，并對(duì)圖（）的情形給出模型和結(jié)果。 需解決的問(wèn)題需解決的問(wèn)題： 二、模型假設(shè)二、模型假設(shè)1.沿鋪設(shè)的主管道以有公路或者有施工公路。2.在主管道上，

4、每公里卸1單位的鋼管。3.公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬(wàn)元（不足整公里部分按整公里計(jì)算）4.在計(jì)算總費(fèi)用時(shí)，只考慮運(yùn)輸費(fèi)和購(gòu)買鋼管的費(fèi)用，而不考慮其他費(fèi)用。5.假設(shè)鋼管在鐵路運(yùn)輸路程超過(guò)1000km時(shí)，鐵路每增加1至100km，1單位鋼管的運(yùn)價(jià)增加5萬(wàn)元。 三、符號(hào)說(shuō)明三、符號(hào)說(shuō)明iS ：第i個(gè)鋼廠； 7 , 2 , 1 i is ：第i個(gè)鋼廠的最大產(chǎn)量； 7 , 2 , 1 i jA ：輸送管道（主管道）上的第 j個(gè)點(diǎn)； 15, 2 , 1j ip ：第i個(gè)鋼廠1單位鋼管的銷價(jià)； 7 , 2 , 1i ijx ：鋼廠iS 向點(diǎn)jA 運(yùn)輸?shù)匿摴芰浚?7 , 2 , 1 i 15, 2

5、, 1 j jy ：在點(diǎn)jA 與點(diǎn)1jA之間的公路上，運(yùn)輸點(diǎn)jA 向點(diǎn)1jA方向鋪設(shè)的鋼管量；14, 3 , 2 , 1j ijA ：1 單位鋼管從鋼廠iS到點(diǎn)jA 的最少總費(fèi)用，即公路運(yùn)費(fèi)鐵路運(yùn)費(fèi)和鋼管銷價(jià)之和； 7 , 2 , 1 i 15, 2 , 1j jmb： 與點(diǎn)jA 相連的第m條公路和鐵路的相交點(diǎn)； 15, 3 , 2j，2m jd ：相鄰點(diǎn)jA 與1jA之間的距離； 14, 2 , 1j 四、模型的分析、建立、求解四、模型的分析、建立、求解 先看總費(fèi)用：總費(fèi)用總費(fèi)用：總費(fèi)用由三部分組成： 1) 1) 鋼管的訂購(gòu)費(fèi)鋼管的訂購(gòu)費(fèi)。 支付鋼廠訂購(gòu)鋼管的費(fèi)用。因?yàn)殇搹S生產(chǎn)單位鋼管的出廠

6、銷價(jià)為常量常量，所以在運(yùn)費(fèi)相同的情況下，應(yīng)從銷價(jià)低的鋼廠訂購(gòu)鋼管應(yīng)從銷價(jià)低的鋼廠訂購(gòu)鋼管。 1. 模型的分析與決策變量的設(shè)置模型的分析與決策變量的設(shè)置 根據(jù)題目要求，要制定一個(gè)主管道鋼管主管道鋼管的訂購(gòu)訂購(gòu)和運(yùn)輸運(yùn)輸計(jì)劃，使總費(fèi)用總費(fèi)用最小。 2)2) 把鋼管從鋼廠運(yùn)到主管道結(jié)點(diǎn)鋼廠運(yùn)到主管道結(jié)點(diǎn)所需的運(yùn)費(fèi)運(yùn)費(fèi)。 要注意運(yùn)輸過(guò)程中既有鐵路，也有公路既有鐵路，也有公路。 3)3) 從結(jié)點(diǎn)Ai向兩邊鋪設(shè)管道的費(fèi)用鋪設(shè)管道的費(fèi)用。 要注意每個(gè)結(jié)點(diǎn)分別向左右鋪設(shè)多少分別向左右鋪設(shè)多少？ 再看訂購(gòu)和運(yùn)輸計(jì)劃：訂購(gòu)和運(yùn)輸計(jì)劃： 所謂所謂訂購(gòu)計(jì)劃訂購(gòu)計(jì)劃：就是向每個(gè)鋼廠訂購(gòu)多少鋼管。 所謂所謂運(yùn)輸計(jì)劃運(yùn)輸計(jì)

7、劃：就是將每個(gè)鋼廠訂購(gòu)的鋼管運(yùn)輸?shù)?那些節(jié)點(diǎn)？運(yùn)多少？ 故可設(shè)：向第i個(gè)鋼廠訂購(gòu)xi單位鋼管，第i個(gè)鋼廠 運(yùn)往第j個(gè)節(jié)點(diǎn)xij單位的鋼管。 1,2,72,3,15ij 故可設(shè)：向第i個(gè)鋼廠訂購(gòu)xi單位鋼管，第i個(gè)鋼廠 運(yùn)往第j個(gè)節(jié)點(diǎn)xij單位的鋼管 。 故變量xi可以不要，少用少用7 7個(gè)變量個(gè)變量！151 iijjxx另外另外，要決定每個(gè)結(jié)點(diǎn)分別向左右鋪設(shè)多少？當(dāng)鋼管從鋼廠iS 運(yùn)到點(diǎn)jA 后， 鋼管就要向運(yùn)輸點(diǎn)jA 的兩邊1jjAA段和jjAA1段運(yùn)輸（鋪設(shè)）管道。 設(shè)jy是結(jié)點(diǎn)jA向右鋪設(shè)與1jA向左鋪設(shè)之間的交交點(diǎn)點(diǎn)（01y，015y） 。 1jA 1jy jA jy 1jA 1,2,

8、72,3,15ij2,3,14j 第二方案第二方案：也可以考慮在Aj左右各設(shè)一個(gè)變量左右各設(shè)一個(gè)變量！ 2.求單位鋼管從鋼廠運(yùn)到運(yùn)輸點(diǎn)的最小費(fèi)用求單位鋼管從鋼廠運(yùn)到運(yùn)輸點(diǎn)的最小費(fèi)用方法方法：將圖一轉(zhuǎn)換為一個(gè)以單位鋼管的運(yùn)輸費(fèi) 用為權(quán)的賦權(quán)圖，再求最短路的權(quán)。賦權(quán)圖，再求最短路的權(quán)。 由于運(yùn)輸過(guò)程中既有鐵路，也有公路，且鐵路鐵路的運(yùn)費(fèi)還是分段函數(shù)的運(yùn)費(fèi)還是分段函數(shù)，與全程運(yùn)輸總距離有關(guān) ；各路運(yùn)費(fèi)確是線性函數(shù)線性函數(shù)。1單位鋼管的鐵路運(yùn)價(jià)如下表：里程(km)300301350351400401450451500運(yùn)價(jià)(萬(wàn)元)2023262932里程(km)501600601700701800801

9、9009011000運(yùn)價(jià)(萬(wàn)元)3744505560可考慮將鐵路與公路分開考慮分開考慮。 1) 將鐵路圖轉(zhuǎn)化成費(fèi)用圖（與將鐵路圖轉(zhuǎn)化成費(fèi)用圖（與Ai對(duì)應(yīng)編號(hào)）對(duì)應(yīng)編號(hào)）圖一圖一中去掉公路得鐵路圖: 將鐵路與公路交界的點(diǎn)編號(hào) bj: 1)1) 由于鋼廠iS 直接與鐵路相連，所以可先求出鋼廠iS 到鐵路與公路相交點(diǎn)鐵路與公路相交點(diǎn)jb（對(duì)應(yīng)于 Aj）的最短路徑。 1) 將鐵路圖轉(zhuǎn)化成費(fèi)用圖將鐵路圖轉(zhuǎn)化成費(fèi)用圖 (統(tǒng)一統(tǒng)一編號(hào)編號(hào))由于鋼廠iS 直接與鐵路相連，所以可先求出鋼廠iS 到鐵鐵路路與與公公路路相相交交點(diǎn)點(diǎn)jb的最短路徑。圖一中去掉公路得鐵路圖: 圖一圖一 （2 2) ) 依據(jù)鋼管的鐵路運(yùn)

10、價(jià)表， 算出鋼廠iS 到鐵路與公路相交點(diǎn)jb的最小鐵路運(yùn)輸費(fèi)用， 并把費(fèi)用作為邊權(quán)賦給從鋼廠iS 到j(luò)b 的邊. b2b3b4b5b6b71b8b9b10b11b12b13b141b142b151b1521601408037202020608595105115125130140140可利用專業(yè)的圖論軟件包圖論軟件包或MATLABMATLAB軟件包軟件包求最短路。計(jì)算計(jì)算Si 到到bi 的最小費(fèi)用（與的最小費(fèi)用（與Ai對(duì)應(yīng)編號(hào)）對(duì)應(yīng)編號(hào)）（1 1) ) 由于鋼廠iS 直接與鐵路相連， 所以可先求出鋼廠iS 到鐵鐵路路與與公公路路相相交交點(diǎn)點(diǎn)jb（對(duì)應(yīng)于 Aj）的最短路徑。 如以S1 為例例：S1

11、到bi的最小費(fèi)用為: 依據(jù)鋼管的鐵路運(yùn)價(jià)表， 算出鋼廠iS 到鐵路與公路相交點(diǎn)jb的最小鐵路運(yùn)輸費(fèi)用， 并把費(fèi)用作為邊權(quán)賦給從鋼廠iS 到j(luò)b 的邊 再將與jb 相連的公路、運(yùn)輸點(diǎn)iA 及其與之相連的要鋪設(shè)管道的線路（也是公路）添加到圖上，根據(jù)單位鋼管在公路上的運(yùn)價(jià)規(guī)定，得出每一段公路的運(yùn)費(fèi)，并把此費(fèi)用作為邊權(quán)賦給相應(yīng)的邊。以1S 為例得圖： b1b2b3b4b5b6b7b8b9b10b11b12b13b14b15b16b1716014080372020020608595105115125130140140 可利用專業(yè)的圖論軟件包圖論軟件包或MATLABMATLAB軟件包軟件包求解,如S1到b

12、i的最小費(fèi)用為:計(jì)算計(jì)算S1到到bi的最小費(fèi)用的最小費(fèi)用(統(tǒng)一編號(hào)統(tǒng)一編號(hào)) 再將與jb 相連的公路、運(yùn)輸點(diǎn)iA 及其與之相連的要鋪設(shè)管道的線路（也是公路）添加到圖上。 b2b3b4b5b6b71b8b9b10b11b12b13b141b142b151b1521601408037202020608595105115125130140140 利用MATLABMATLAB軟件包軟件包求解,如S1到bi的最小費(fèi)用為:2) 合并鐵路和公路圖得以費(fèi)用為權(quán)的交通網(wǎng)絡(luò)圖合并鐵路和公路圖得以費(fèi)用為權(quán)的交通網(wǎng)絡(luò)圖同時(shí)根據(jù)單位鋼管在公路上的運(yùn)價(jià)規(guī)定， 得出每一段公路的運(yùn)費(fèi)，并把此費(fèi)用作為邊權(quán)賦給相應(yīng)的邊。以1S

13、為例得圖： S1到結(jié)點(diǎn)到結(jié)點(diǎn)Ai的最小費(fèi)用圖的最小費(fèi)用圖 再用圖論軟件包圖論軟件包或MATLAB軟件包軟件包求解,如S1到Ai的最小費(fèi)用（萬(wàn)元）為:A2A3A4A5A6A7A8160.3140.298.63820.53.121.2A9A10A11A12A13A14A1564.29296106121.21281423) 計(jì)算計(jì)算S1到結(jié)點(diǎn)到結(jié)點(diǎn)Ai的最小費(fèi)用的最小費(fèi)用 A2A3A4A5A6A7A8160.3140.298.63820.53.121.2A9A10A11A12A13A14A1564.29296106121.21281424) 計(jì)算單位鋼管從計(jì)算單位鋼管從S1到到Ai的訂購(gòu)與運(yùn)輸?shù)淖钚?/p>

14、費(fèi)用的訂購(gòu)與運(yùn)輸?shù)淖钚≠M(fèi)用加上單位鋼管的銷售價(jià)ip ，得出從鋼廠1S購(gòu)買單位鋼管運(yùn)輸?shù)近c(diǎn)jA 的最小費(fèi)用1jA（1160p 萬(wàn)元） 。 A2A3A4A5A6A7A8320.3300.2258.6198180.5163.1181.2A9A10A11A12A13A14A15224.2252256266281.2288302 同理，可用同樣的方法求出鋼廠2S3S 4S5S 6S 7S 到點(diǎn)jA的最小費(fèi)用，從而得出從鋼廠 Si購(gòu)買單位鋼管運(yùn)到結(jié)點(diǎn) Aj的最小總費(fèi)用ijA（單位：萬(wàn)元）為： 5) 從從Si 購(gòu)買單位鋼管運(yùn)到結(jié)點(diǎn)購(gòu)買單位鋼管運(yùn)到結(jié)點(diǎn)Ai的最小費(fèi)用的最小費(fèi)用Aij ：A2A3A4A5A6A7

15、A8A9A10A11A12A13A14A15s1320.3300.2258.6198180.5163.1181.2224.2252256266281.2288302s2360.3345.2326.6266250.5241226.2269.2297301311326.2333347s3375.3355.2336.6276260.5251241.2203.2237241251266.2273287s4410.3395.2376.6316300.5291276.2244.2222211221236.2243257s5400.3380.2361.6301285.5276266.2234.2212188

16、206226.2228242s6405.3385.2366.6306290.5281271.2234.2212201195176.2161178s7425.3405.2386.6326310.5301291.2259.2237226216198.2186162ijA從鋼廠 Si購(gòu)買單位鋼管運(yùn)到結(jié)點(diǎn) Aj的最小總費(fèi)用ijA（單位：萬(wàn)元） (1)(1)鋪設(shè)總費(fèi)用鋪設(shè)總費(fèi)用總費(fèi)用總費(fèi)用= =鋪設(shè)總費(fèi)用鋪設(shè)總費(fèi)用+ +成本及運(yùn)輸總費(fèi)用成本及運(yùn)輸總費(fèi)用=C+W=C+W3.模型的建立模型的建立當(dāng)鋼管從鋼廠iS 運(yùn)到點(diǎn)jA 后， 鋼管就要向運(yùn)輸點(diǎn)jA 的兩邊1jjAA段和jjAA1段運(yùn)輸（鋪設(shè)）管道。 jy

17、：表示結(jié)點(diǎn)jA到1jA之間的分分界界點(diǎn)點(diǎn)（01y，015y） ，鋪設(shè) 方法如下圖： 1jA 1jy jA jy 1jA 1) 1) 目標(biāo)函數(shù)目標(biāo)函數(shù) 鋪設(shè)總費(fèi)用：鋪設(shè)總費(fèi)用：設(shè)jA 向1jjAA段鋪設(shè)的管道長(zhǎng)度為jy ， 則jA 向1jjAA段的運(yùn)輸費(fèi)用為201)21 (1 . 0jjjyyy；由于相鄰運(yùn)輸點(diǎn)jA 與1jA之間的距離為jd ，那么1jA向1jjAA段鋪設(shè)的管道長(zhǎng)為jjyd ，所對(duì)應(yīng)的鋪設(shè)費(fèi)用為201jjjjydyd。 1jA 1jy jA jy 1jA 故總的鋪設(shè)費(fèi)用為：故總的鋪設(shè)費(fèi)用為： 141112020jjjjjjjyydydyC 71512ijijijWAx（2)成本及

18、運(yùn)輸總費(fèi)用：成本及運(yùn)輸總費(fèi)用：設(shè)若運(yùn)輸點(diǎn)jA向鋼廠iS 訂購(gòu)ijx單位鋼管，ijA是 1 單位鋼管從鋼廠iS到點(diǎn)jA的最少總費(fèi)用， 即公路運(yùn)費(fèi)公路運(yùn)費(fèi)鐵路運(yùn)費(fèi)鐵路運(yùn)費(fèi)和鋼鋼管銷價(jià)管銷價(jià)之和；則鋼管從鋼廠iS運(yùn)到運(yùn)輸點(diǎn)jA所需的費(fèi)用為ijijxA。由于鋼管運(yùn)到1A 必須經(jīng)過(guò)2A ，所以可不考慮1A ，那么所有鋼管從各鋼廠運(yùn)到各運(yùn)輸點(diǎn)上的總費(fèi)用為： 71512ijijijWAx目標(biāo)函數(shù)為：目標(biāo)函數(shù)為：總費(fèi)用總費(fèi)用= =鋪設(shè)總費(fèi)用鋪設(shè)總費(fèi)用+ +成本及運(yùn)輸總費(fèi)用成本及運(yùn)輸總費(fèi)用= =C+ +W 141112020jjjjjjjyydydyC 14715112112020jjjjjjijijjijyy

19、dydyfA x 2）約束條件）約束條件（1 1）生生產(chǎn)產(chǎn)能能力力約約束束 因?yàn)橐粋€(gè)鋼廠如果承擔(dān)制造鋼管任務(wù)，至少需要生產(chǎn) 500 個(gè)單位，鋼廠iS 在指定期限內(nèi)最大生產(chǎn)量為is 個(gè)單位： ijijsx 152500 或0152jijx ) 7 , 2 , 1(i （2 2） 需需求求約約束束 運(yùn)到點(diǎn)jA 的鋼管只提供11jjjjAAAA和段的鋪設(shè)，由于鋼管運(yùn)到1A 必須經(jīng)過(guò)2A ，所以01y。15A是終點(diǎn)，所以015y。 jjjiijyydx1171 )15, 3 , 2j（ 非線性規(guī)劃模型：非線性規(guī)劃模型：715141211515227111(1)()(1)min()20205000 1,

20、2,7. .0 , 0 (1,7,2,15) 2,3,15jjjjjjijijijjijiijjjijiijjjijiyydydyfA xxsxistxydijdyyxj 或或綜合上述分析，得 由于 LINGO 不能直接處理約束條件：ijijsx 152500或0152jijx，我們可先將此條件改為ijijsx 152，得到如下模型： 5.模型求解模型求解715141211527111(1)()(1)min()2020 1,2,7. .0 , 0 (1,7,2,15) 2,3,15jjjjjjijijijjijijijiijjjijiyydydyfA xxsistxydijdyyxj 1515

21、225000ijiijjjxsx或或152ijijxs 利用利用LINGO軟件包編程求解軟件包編程求解分析計(jì)算結(jié)果后發(fā)現(xiàn)購(gòu)運(yùn)方案中鋼廠4S 不不生生產(chǎn)產(chǎn)， 鋼廠7S生產(chǎn)但生生產(chǎn)產(chǎn)量量不不足足 5 50 00 0 單單位位。 用 LINGO 求解（gangguan）: Global optimal solution found. Objective value: 1275352. Objective bound: 1275352. Infeasibilities: 0.000000 Extended solver steps: 1 Total solver iterations: 381 Mod

22、el Title: 問(wèn)題一的模型求解：分三種情況分別求解 Variable Value S1DINGGOULIANG 800.0000 S2DINGGOULIANG 800.0000 S3DINGGOULIANG 1000.000 S4DINGGOULIANG 0.000000 S5DINGGOULIANG 1155.824 S6DINGGOULIANG 1170.176 S7DINGGOULIANG 245.0000 1）不讓）不讓S7生產(chǎn)的模型求解生產(chǎn)的模型求解7151412115215727111(1)()(1)min()2020, 1,2,70.0 , 0 1,7,2,15 2,3,1

23、5jjjjjjijijijjijijjjijjjjjjijiy ydydyfx Axsixstxydijdyyxj 715141211527111(1)()(1)min()2020 1,2,7.0 , 0 (1,7,2,15) 2,3,15jjjjjjij ijijjijijijiijjjijiy ydydyfAxxsist xydijdyyxj 下面我們采用不不讓讓鋼鋼廠廠7S 生生產(chǎn)產(chǎn)和要要求求鋼鋼廠廠7S 的的產(chǎn)產(chǎn)量量不不小小于于 5 50 00 0 個(gè)個(gè)單單位位兩種方法計(jì)算： 添加一個(gè)S7生產(chǎn)量為0的約束原模型原模型不讓不讓S7生產(chǎn)的模型生產(chǎn)的模型 計(jì)計(jì)算算結(jié)結(jié)果果：1f1278632

24、（萬(wàn)元） （此時(shí)每個(gè)鋼廠的產(chǎn)量都滿足條件） 。 2) 要求鋼廠要求鋼廠S7的產(chǎn)量不小于的產(chǎn)量不小于500個(gè)單位個(gè)單位 7151412115215727111(1)()(1)min()2020, 1,2, ,7500.0 , 0 1, ,7,2, ,15 2,3, ,15jjjjjjijijijjijijjjijjjjjjijiy ydydyfx Axsixstxydijdyyxj 715141211527111(1)()(1)min()2020 1,2,7.0 , 0 (1,7,2,15) 2,3,15jjjjjjij ijijjijijijiijjjijiy ydydyfAxxsist xydijdyyxj 計(jì)算結(jié)果：2f 1279661（萬(wàn)元