CUMCM-2000B 鋼管訂購和運輸

1、CUMCM-2000B CUMCM-2000B 鋼管訂購和運輸鋼管訂購和運輸由鋼管廠訂購鋼管，經(jīng)鐵由鋼管廠訂購鋼管，經(jīng)鐵路、公路運輸，鋪設一條路、公路運輸，鋪設一條鋼管管道鋼管管道1521AAAA1325801010312012427010881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道鐵路公路S1S7 鋼

2、管廠火車站450 里程（km)（沿管道建有公路）鋼 廠 i1234567產(chǎn) 量 上 限 is80080010002000200020003000銷 價ip（ 萬 元 ）160155155160155150160鋼廠的產(chǎn)量和銷價（1單位鋼管=1km管道鋼管）鋼廠產(chǎn)量的下限：500單位鋼管里程(km)300301350351400401450451500運價(萬元)2023262932里程(km)5016006017007018008019009011000運價(萬元)37445055601單位鋼管的鐵路運價1000km以上每增加1至100km運價增加5萬元1單位鋼管的公路運價：0.1萬元/km（

3、不足整公里部分按整公里計）601 = 300 + 30144 20 + 23 ?（1）制定鋼管的訂購和運輸計劃，使總費用最?。┲贫ㄤ摴艿挠嗁徍瓦\輸計劃，使總費用最小.（2）分析對購運計劃和總費用影響：哪個鋼廠鋼管銷價的）分析對購運計劃和總費用影響：哪個鋼廠鋼管銷價的變化影響最大；哪個鋼廠鋼管產(chǎn)量上限的變化影響最大？變化影響最大；哪個鋼廠鋼管產(chǎn)量上限的變化影響最大？A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003061952027206905201706904621

4、60320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）討論管道為樹形圖的情形）討論管道為樹形圖的情形問題問題1的基本模型和解法的基本模型和解法總費用最小的優(yōu)化問題總費用：訂購，運輸（由各廠Si經(jīng)鐵路、公路至各點Aj, i=1,7; j=1, 15 ），鋪設管道Aj Aj+1 （j=1, 14)由Si至Aj的最小購運費用路線及最小費用cij 由Si至Aj的最優(yōu)運量xij由Aj向Aj Aj-1段鋪設的長度yj及向Aj Aj+1段鋪設的長度y

5、j最優(yōu)購運計劃最優(yōu)購運計劃約束約束條件條件鋼廠產(chǎn)量約束：上限和下限（如果生產(chǎn)的話）運量約束：xij對i求和等于zj 加yj； zj與 yj+1之和等于Aj Aj+1段的長度ljyj zjAj基本模型基本模型由Aj向Aj Aj-1段鋪設的運量為 1+ +yj= yj( yj+1)/2由Aj向Aj Aj+1段鋪設的運量為 1+ +zj= zj( zj+1)/2)6(0, 0) 5(15, 2 , 1, 7 , 2 , 10, 0, 0)4(14, 2 , 1) 3(15, 2 , 1)2(7 , 2 , 1,5000. .) 1 ()1() 1(21 . 0min15117115171151151

6、zyjiyzxjlyzjyzxisxtsyyzzxcjjijjjjjjiijijijijjjjjjijij二次規(guī)劃求解步驟求解步驟1）求由Si至Aj的最小購運費用路線及最小費用cij 難點：公路運費是里程的線性函數(shù)，而鐵路運費是里程的分段階躍函數(shù)，故總運費不具可加性。因而計算最短路常用的Dijkstra算法、Floyd算法失效。7010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要對鐵路網(wǎng)和公路網(wǎng)進行預處理，才能使用常用需要對鐵路網(wǎng)和公路網(wǎng)進行預處理，才能使用常用算法，得

7、到最小購運費用路線。算法，得到最小購運費用路線。- 至少求至少求3次最短路次最短路如S7至A10的最小費用路線先鐵路1130km，再公路70km, 運費為77（萬元）先公路（經(jīng)A15）40km, 再鐵路1100km，再公路70km, 運費為76（萬元）的的處處理理約約束束條條件件)7 , 2 , 1(,5000)2151 isxijij問問題題求求解解。，分分解解為為上上述述形形式式的的子子的的那那些些求求解解，再再對對解解中中滿滿足足先先松松弛弛為為ixisxbjijijij5000)7, 1(0)151151 個個子子問問題題共共和和分分解解為為71511512)7, 1(5000) is

8、xxaijijjij實際上只有S4和S7需要分解成子問題求解每個子問題是標準的二次規(guī)劃，決策變量為xij,yj,zj, 不超過135個 。0, 0,0. .)(05.0min1511711512151271151zyzyxlyzzyxsxtsyyzzxcjjijjjjjijijjiijjjjjjijijijfi表示鋼廠表示鋼廠i是否使用；是否使用；xij是從鋼廠是從鋼廠i運到節(jié)點運到節(jié)點j的鋼管量的鋼管量yj是從節(jié)點是從節(jié)點j向左鋪設的鋼管量；向左鋪設的鋼管量；zj是向右鋪設的鋼管量是向右鋪設的鋼管量 c) 比較好的方法：引入比較好的方法：引入0-10-1變量變量. 7,.,1, 1 , 0,

9、 0.14,.,1.15,.,1,. 7,.,1,500. .)1 ()1(21 . 0)(151171151151,ifzyjbzyjzyxifSxftszzyyxcpMinijjjjjiijiijijijjjjjjiijiji LINDO/LINGO得到的結果比得到的結果比matlab得到的好得到的好exam1202d.lg4yj zjj問題問題1的其它模型和解法的其它模型和解法1）運輸問題的0-1規(guī)劃模型將全長5171km的管道按公里分段，共5171個需求點，鋼廠為7個供應點，構成如下的運輸問題5171,1,7,1,1,05171,1,17,1,500,0.min715171171517

10、11 jixjxisxtsxcijiijijijijijijcij為從供應點i到需求點j的最小購運費xij=1表示從點i到點j購運1單位鋼管求解時要針對規(guī)模問題尋求改進算法2）最小費用網(wǎng)絡流模型）最小費用網(wǎng)絡流模型SourceS1S2S7A1A2A15P11P1l1P21Sink(si, pi)(+, cij)(1,1),(1,li)(1,0)SourceS1S2S7A1A2A15P1P2Sink(si, pi)(+, cij)(li, f(f+1)/2)(li,0)線性費用網(wǎng)絡線性費用網(wǎng)絡(只有產(chǎn)量上限只有產(chǎn)量上限)非線性費用網(wǎng)絡非線性費用網(wǎng)絡(只有產(chǎn)量上限只有產(chǎn)量上限)邊的標記（流量上限，

11、單位費用）用標準算法(如最小費用路算法)求解無單位費用概念(f(f+1)/2), 需修改最小費用路算法2）最小費用網(wǎng)絡流模型）最小費用網(wǎng)絡流模型產(chǎn)量有下限r(nóng)i時的修正SourceSiSi(si -ri, pi)(ri, 0)(+, 0)得到的結果應加上 iiipr 才是最小費用的的處處理理同同前前約約束束條條件件)7 , 2 , 1(,5000151 isxijij注：該模型獲當年的惟一最高獎（網(wǎng)易杯）注：該模型獲當年的惟一最高獎（網(wǎng)易杯）S1S2S3S6S5S1S2S2S3S3S5S5S63) 最小面積模型A1A2A3A4A5A6A7A8A9A10A11A12A13A14A15cx作圖：Si

12、到管道x單位鋼管的最小購運費用c由各條Si首尾相連(橫坐標)組成的一條折線對應一個購運方案，折線下面的面積對應方案的費用在產(chǎn)量約束下找面積最小的折線問題問題2: 分析對購運計劃和總費用影響分析對購運計劃和總費用影響(哪個鋼廠銷價哪個鋼廠銷價變化影響最大；哪個鋼廠產(chǎn)量上限變化影響最大變化影響最大；哪個鋼廠產(chǎn)量上限變化影響最大)規(guī)劃問題的靈敏度分析問題問題3：管道為樹形圖：管道為樹形圖701088107062300220210170690462160320160A10A11A12S4S5S6130A17A18A19A20190260100, 0,500 , 0. .)(05.0min71)(2112211)(71211 jkijjkkjjkijkEjkijjiijjkjkjEjkijijijyxbyyyxsxtsyyxc(jk)是連接Aj,Ak的邊，E是樹形圖的邊集， ljk是(jk)的長度， yjk是由Aj沿(jk)鋪設的鋼管數(shù)量論文中發(fā)現(xiàn)的主要問題論文中發(fā)