鋼管的訂購與運輸

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

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

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

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

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

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

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

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

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

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

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

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

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

14、費用的訂購與運輸?shù)淖钚≠M用加上單位鋼管的銷售價ip ，得出從鋼廠1S購買單位鋼管運輸?shù)近cjA 的最小費用1jA（1160p 萬元） 。 A2A3A4A5A6A7A8320.3300.2258.6198180.5163.1181.2A9A10A11A12A13A14A15224.2252256266281.2288302 同理，可用同樣的方法求出鋼廠2S3S 4S5S 6S 7S 到點jA的最小費用，從而得出從鋼廠 Si購買單位鋼管運到結(jié)點 Aj的最小總費用ijA（單位：萬元）為： 5) 從從Si 購買單位鋼管運到結(jié)點購買單位鋼管運到結(jié)點Ai的最小費用的最小費用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購買單位鋼管運到結(jié)點 Aj的最小總費用ijA（單位：萬元） (1)(1)鋪設(shè)總費用鋪設(shè)總費用總費用總費用= =鋪設(shè)總費用鋪設(shè)總費用+ +成本及運輸總費用成本及運輸總費用=C+W=C+W3.模型的建立模型的建立當鋼管從鋼廠iS 運到點jA 后， 鋼管就要向運輸點jA 的兩邊1jjAA段和jjAA1段運輸（鋪設(shè)）管道。 jy

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

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

19、dydyfA x 2）約束條件）約束條件（1 1）生生產(chǎn)產(chǎn)能能力力約約束束 因為一個鋼廠如果承擔制造鋼管任務(wù)，至少需要生產(chǎn) 500 個單位，鋼廠iS 在指定期限內(nèi)最大生產(chǎn)量為is 個單位： ijijsx 152500 或0152jijx ) 7 , 2 , 1(i （2 2） 需需求求約約束束 運到點jA 的鋼管只提供11jjjjAAAA和段的鋪設(shè)，由于鋼管運到1A 必須經(jīng)過2A ，所以01y。15A是終點，所以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軟件包編程求解軟件包編程求解分析計算結(jié)果后發(fā)現(xià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: 問題一的模型求解：分三種情況分別求解 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 個個單單位位兩種方法計算： 添加一個S7生產(chǎn)量為0的約束原模型原模型不讓不讓S7生產(chǎn)的模型生產(chǎn)的模型 計計算算結(jié)結(jié)果果：1f1278632

24、（萬元） （此時每個鋼廠的產(chǎn)量都滿足條件） 。 2) 要求鋼廠要求鋼廠S7的產(chǎn)量不小于的產(chǎn)量不小于500個單位個單位 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 計算結(jié)果：2f 1279661（萬元