1、建模案例：鋼管訂購和運輸優(yōu)化模型建模案例：鋼管訂購和運輸優(yōu)化模型20002000年年“網(wǎng)易杯全國大學(xué)生數(shù)學(xué)建模競賽網(wǎng)易杯全國大學(xué)生數(shù)學(xué)建模競賽B B綜合案例分析綜合案例分析docin/sundae_meng 一.問題的提出二二. .根本假設(shè)根本假設(shè)1.1.沿鋪設(shè)的主管道已有公路或者有施工公路沿鋪設(shè)的主管道已有公路或者有施工公路. . 2.1km 2.1km 主管道鋼管稱為一單位鋼管，在主管道上，每主管道鋼管稱為一單位鋼管，在主管道上，每千米卸千米卸1 1單位的鋼管單位的鋼管. .3.3.公路運輸費用為公路運輸費用為1 1單位鋼管每千米單位鋼管每千米0.10.1萬元萬元缺乏整千米部分按整千米計算

2、缺乏整千米部分按整千米計算 4. 4.在計算總費用時，只思索運輸費用和購買鋼管的費用，在計算總費用時，只思索運輸費用和購買鋼管的費用， 而不思索其他的費用諸如中轉(zhuǎn)費用而不思索其他的費用諸如中轉(zhuǎn)費用 5. 5.假設(shè)鋼管在鐵路運輸路程超越假設(shè)鋼管在鐵路運輸路程超越1000km,1000km,鐵路每添加鐵路每添加1 1 至至100km,1100km,1單位鋼管運輸?shù)倪\價增至單位鋼管運輸?shù)倪\價增至5 5萬元萬元. .6.訂購的鋼管數(shù)量剛好等于需求鋪設(shè)的鋼管數(shù)量7.7.銷售價和運輸價不受市場價錢變化的影響銷售價和運輸價不受市場價錢變化的影響docin/sundae_meng三三. 符號闡明符號闡明第 個

3、鋼廠,第個鋼廠的最大產(chǎn)量，保送天然氣的主管道上的第個點，第個鋼廠 1 單位鋼管的銷售價錢，鋼廠向第個點運輸?shù)匿摴軘?shù)量單位 在點與點之間的公路上，運輸點向點方向鋪設(shè)的鋼管數(shù)量，1 單位鋼管從鋼廠到點的最少總費用，即公路運費，鐵路運費和鋼管銷售之和，與第個點相連的公路和鐵路的相交點,與第個點相連的的第m條公路和鐵路的相交點,相鄰結(jié)點與點之間的間隔 ,docin/sundae_meng四四. . 模型的建立與求解模型的建立與求解問題一：討論如何調(diào)整主管道鋼管的訂購和運輸方案使總費用最小問題一：討論如何調(diào)整主管道鋼管的訂購和運輸方案使總費用最小iSiSjA求鋼管從鋼廠求鋼管從鋼廠運到運輸點運到運輸點的

4、最小費用的最小費用1 1將圖將圖1 1轉(zhuǎn)換為一系列以單位鋼管的運輸費用為權(quán)的賦權(quán)圖轉(zhuǎn)換為一系列以單位鋼管的運輸費用為權(quán)的賦權(quán)圖. .iSjb所以可先求出鋼廠所以可先求出鋼廠到鐵路與公路相交點到鐵路與公路相交點的最短途徑的最短途徑. .如圖如圖3 3 由題意可知：將鋼管從鋼廠運到運輸點的費用包括鋼管的銷售價錢、鋼管的鐵路運輸費用和鋼管的公路運輸費用.在費用最小時，對鋼管的訂購和運輸進展分配，可得出本問題的最正確方案.總費用總費用= =鋼廠到各節(jié)點的費用鋼廠到各節(jié)點的費用+ +主管道的運輸鋪設(shè)費用主管道的運輸鋪設(shè)費用docin/sundae_meng450801150110030619520202

5、120072069052017069016088462703201607029030docin/sundae_meng圖-4docin/sundae_meng1SjA2計算單位鋼管從到到的最少運輸費用的最少運輸費用1SjA根據(jù)圖根據(jù)圖4，借助圖論軟件包中求最短路的方法求出單位鋼管從，借助圖論軟件包中求最短路的方法求出單位鋼管從到的最短路，從而得出將單位鋼管從的最短路，從而得出將單位鋼管從 1S運輸?shù)礁鬟\輸點運輸?shù)礁鬟\輸點jA最小費用。最小費用。運輸費用依次為：運輸費用依次為：170.7170.7，160.3160.3，140.2140.2，98.698.6，3838，20.520.5，3.13

6、.1，21.221.2，64.264.2，9292，9696，106106，121.2121.2，128128，142142單位：萬元單位：萬元 加上單位鋼管的銷售價加上單位鋼管的銷售價 1SjA得出從鋼廠得出從鋼廠購買單位鋼管運輸?shù)近c購買單位鋼管運輸?shù)近c的最小費用的最小費用依次為依次為: : jA1330.3，320.3，300.2，258.6，198，180.5，163.1，181.2，224.2，252，256，266，281.2，288，302單位：萬元.同理，可用同樣的方法求出鋼廠同理，可用同樣的方法求出鋼廠 到到 的最小費用，從而得出各鋼廠Si到運輸節(jié)點到運輸節(jié)點 Aj 最小運總費

7、用。見表最小運總費用。見表1.LINGO LINGO 程序：程序：min-cost1.lg4 min-cost1.lg4 計算結(jié)果：計算結(jié)果：min-cost1.lgrdocin/sundae_meng表表1 Si 到點到點 Aj 的最小費用的最小費用2. 2. 建立模型建立模型運輸總費用可分為兩部分：運輸總費用可分為兩部分：運輸總費用運輸總費用= =鋼廠到各點的運輸費用鋼廠到各點的運輸費用+ +主管道的運輸鋪設(shè)費用主管道的運輸鋪設(shè)費用. .docin/sundae_mengdocin/sundae_meng從而得出總費用：從而得出總費用：2) 2) 約束條件約束條件docin/sundae_

8、meng因此本問題可建立如下的非線性規(guī)劃模型：因此本問題可建立如下的非線性規(guī)劃模型： 非線性規(guī)劃模型可用LINGO軟件包或MATLAB軟件包來求解，但這些軟件包不能直接處置約束條件：可用分支定界法將此條件改為可用分支定界法將此條件改為模型變?yōu)槟Ｐ妥優(yōu)閐ocin/sundae_meng1 1不讓鋼廠不讓鋼廠S7S7消費，模型變?yōu)橄M，模型變?yōu)? :docin/sundae_meng 計算結(jié)果：1f12786321278632萬元此時每個鋼廠的產(chǎn)量都滿足條件萬元此時每個鋼廠的產(chǎn)量都滿足條件 2 2要求鋼廠要求鋼廠S7 S7 產(chǎn)量不小于產(chǎn)量不小于500500個單位，模型變?yōu)閭€單位，模型變?yōu)? :計算

9、結(jié)果：計算結(jié)果：2f 1279664萬元此時每個鋼廠的產(chǎn)量都滿足條件. docin/sundae_meng比較這兩種情況，得最優(yōu)解為比較這兩種情況，得最優(yōu)解為S7不讓消費不讓消費: 121),min(minffff=1278632=1278632萬元詳細的購運方案如表萬元詳細的購運方案如表2 2： 訂購量A2A3A4A5A6A7A8A9A10A11A12A13A14A15S18000201133200266000000000S28001791114295003000000000S31000139111860006640000000S4000000000000000S51015035824200

10、00004150000S6155600000000035186333621165S7000000000000000表表2 2 問題問題1 1的訂購和調(diào)運方案的訂購和調(diào)運方案docin/sundae_mengfi表示鋼廠表示鋼廠i能否運用；能否運用；xij是從鋼廠是從鋼廠i運到節(jié)點運到節(jié)點j的鋼管量的鋼管量yj是從節(jié)點是從節(jié)點j向左鋪設(shè)的鋼管量；向左鋪設(shè)的鋼管量；zj是向右鋪設(shè)的鋼管量是向右鋪設(shè)的鋼管量 比較好的方法：引入比較好的方法：引入0-10-1變量變量.7,.,1,1 ,0,0.14,.,1.15,.,1,.7,.,1,500.)1()1(21.0151171151151,ifzyjbz

11、yjzyxifsxftszzyyxAMinijjjjjiijiijijijjjjjjiijij LINDO/LINGO得到的結(jié)果比得到的結(jié)果比matlab得到的好得到的好yj zjjGUANDAO.lg4參考程序docin/sundae_meng1運輸問題的0-1規(guī)劃模型將全長5171km的管道按公里分段，共5171個需求點，鋼廠為7個供應(yīng)點，構(gòu)成如下的運輸問題5171,1,7,1,1,05171,1,17,1,500,0.min71517117151711 jixjxisxtsxcijiijijijijijijcij為從供應(yīng)點i到需求點j的最小購運費xij=1表示從點i到點j購運1單位鋼管求

12、解時要針對規(guī)模問題尋求改良算法Cij 規(guī)模太大費事規(guī)模太大費事docin/sundae_meng 問題二、就問題二、就1 1的模型分析：哪個鋼廠鋼管的銷價的變的模型分析：哪個鋼廠鋼管的銷價的變化對購運方案和總費用影響最大，哪個鋼廠鋼管的產(chǎn)量的上化對購運方案和總費用影響最大，哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運方案和總費用的影響最大，并給出相應(yīng)的數(shù)限的變化對購運方案和總費用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果字結(jié)果. . 由于鋼廠鋼管的銷售價錢變化和鋼廠鋼管產(chǎn)量的上限變化對購運方案和總費用呵斥影響，為更好地調(diào)查影響，下面分別進展討論方案中運往各點的運輸量的變化量的絕對值之和稱為運輸方案變化量方案中運

13、往各點的運輸量的變化量的絕對值之和稱為運輸方案變化量1 1討論鋼廠鋼管的銷售價錢變化對購運方案和總費用的影響討論鋼廠鋼管的銷售價錢變化對購運方案和總費用的影響 當鋼廠鋼管的銷售價錢 變化時，會對購運方案和總費用呵斥影響。為更好地察看每一個鋼廠的銷售價錢 變化時所呵斥的影響，本問題采用比較法。即：每次只讓一個鋼廠鋼管的銷售價錢發(fā)生一樣的變化，其他鋼廠鋼管的銷售價錢不發(fā)生變化；當每個鋼廠的銷售價個發(fā)生同樣的變化 C 時，求出相應(yīng)的總費用，然后比較。分析：分析：docin/sundae_meng表3 C=-5表4 C=5docin/sundae_meng表5 C=1表6 C=-1從上述四個表格中可以

14、看出：鋼廠鋼管的銷售價錢變化時，從上述四個表格中可以看出：鋼廠鋼管的銷售價錢變化時，S6對總費用對總費用影響最大，影響最大，S5對購運方案影響最大。對購運方案影響最大。docin/sundae_meng2) 2) 討論鋼廠產(chǎn)量的上限變化對購運方案和總費用的影響討論鋼廠產(chǎn)量的上限變化對購運方案和總費用的影響 本問題同樣采用比較法。即：每次只改動一個鋼廠鋼管產(chǎn)量的上限，其他鋼廠鋼管產(chǎn)量上限不發(fā)生變化的情況，利用問題一中的模型進展討論。 a. 對產(chǎn)量不受限制的情況計算得到下表表7 產(chǎn)量不受限制的情形b. 對產(chǎn)量下降100的情況計算得到下表表8 產(chǎn)量下降100的情況docin/sundae_mengc

15、.對產(chǎn)量升高100 的情況計算得到下表表9 產(chǎn)量升高100的情況結(jié)論：從上述表格中可以看出鋼廠鋼管產(chǎn)量的上限變化時，結(jié)論：從上述表格中可以看出鋼廠鋼管產(chǎn)量的上限變化時，S1對對 總費用和總費用和購運方案影響最大。購運方案影響最大。問題三、討論鐵路、公路構(gòu)成網(wǎng)絡(luò)的情形問題三、討論鐵路、公路構(gòu)成網(wǎng)絡(luò)的情形 本問題是討論鋪設(shè)的管道是樹形圖，鐵路、公路構(gòu)成網(wǎng)絡(luò)的情形，對于這種問題的求解過程，以圖-2進展闡明。docin/sundae_meng1. 1. 鋪設(shè)管道是樹形圖時，根本解法原理鋪設(shè)管道是樹形圖時，根本解法原理圖圖-3A13258010103120124270108810706270302020

16、30450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7docin/sundae_meng 為求出普通由鐵路、公路、管道構(gòu)成網(wǎng)絡(luò)情況下的最優(yōu)購運和最小總費用方案，首先必需求出各鋼廠到個管道節(jié)點的最短費用途徑。由于在途中能夠發(fā)生火車汽車火車的轉(zhuǎn)運方案，而這種情況發(fā)生的前提條件是公路或管道的兩端必需都是火車站點，由于鐵路運輸?shù)馁M用是分段函數(shù)，故求各鋼廠到

17、各管道結(jié)點的最小費用步驟如下：1首先找出公路的兩個端點都是火車站站點的結(jié)點V1,V2,Vs2) 2) 把公路網(wǎng)和鐵路網(wǎng)分開，分別組成網(wǎng)絡(luò)；把公路網(wǎng)和鐵路網(wǎng)分開，分別組成網(wǎng)絡(luò)；3 3在鐵路網(wǎng)中求出各鋼廠在鐵路網(wǎng)中求出各鋼廠SiSi及各點及各點ViVi到各火車站點的最短路，并把它轉(zhuǎn)化到各火車站點的最短路，并把它轉(zhuǎn)化 為最小費用路為最小費用路4)4)在公路網(wǎng)中求出各管道結(jié)點到各火車站點的最短路，并把它轉(zhuǎn)化為最小在公路網(wǎng)中求出各管道結(jié)點到各火車站點的最短路，并把它轉(zhuǎn)化為最小 費用路費用路5 5把前面的結(jié)點合并成一個網(wǎng)絡(luò)，分別求出各鋼廠把前面的結(jié)點合并成一個網(wǎng)絡(luò)，分別求出各鋼廠Si Si 到各管道結(jié)點的

18、最小到各管道結(jié)點的最小 運輸費用路。并求出各鋼廠運輸費用路。并求出各鋼廠 Si Si到各管道結(jié)點到各管道結(jié)點AjAj的最小費用，由此可得到的最小費用，由此可得到最小費用最小費用 Aij Aij 見下表見下表docin/sundae_meng10.430.1750.3205(1)(2)(3)S2(34)(22)(23)1900.2(4)(24)60125(5)60.61(25)110(6)19.40.595(26)1(27)(28)3.1(7)(8)20.520.11.2(29)(9)68(16)4.2(30)(10)748(11)(17)(18)(12)301137(19)19(13)(20)(21)(14)(15)(31)(32)(33)122214250266.211322190190175180165108585 70110 145150145 程序：min-cost 2.lg4 docin/sundae_mengdocin/sundae