數(shù)學(xué)建模 鋼管訂購和運(yùn)輸優(yōu)化模型ppt課件

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

2、 4. 4.在計算總費(fèi)用時，只考慮運(yùn)輸費(fèi)用和購買鋼管的費(fèi)用，在計算總費(fèi)用時，只考慮運(yùn)輸費(fèi)用和購買鋼管的費(fèi)用， 而不考慮其他的費(fèi)用諸如中轉(zhuǎn)費(fèi)用）而不考慮其他的費(fèi)用諸如中轉(zhuǎn)費(fèi)用） 5. 5.假設(shè)鋼管在鐵路運(yùn)輸路程超過假設(shè)鋼管在鐵路運(yùn)輸路程超過1000km,1000km,鐵路每增加鐵路每增加1 1 至至100km,1100km,1單位鋼管運(yùn)輸?shù)倪\(yùn)價增至單位鋼管運(yùn)輸?shù)倪\(yùn)價增至5 5萬元萬元. .6.訂購的鋼管數(shù)量剛好等于需要鋪設(shè)的鋼管數(shù)量7.7.銷售價和運(yùn)輸價不受市場價格變化的影響銷售價和運(yùn)輸價不受市場價格變化的影響三三. 符號說明符號說明第 個鋼廠,第個鋼廠的最大產(chǎn)量，輸送天然氣的主管道上的第個點(diǎn)，

3、第個鋼廠 1 單位鋼管的銷售價格，鋼廠向第個點(diǎn)運(yùn)輸?shù)匿摴軘?shù)量單位） 在點(diǎn)與點(diǎn)之間的公路上，運(yùn)輸點(diǎn)向點(diǎn)方向鋪設(shè)的鋼管數(shù)量，1 單位鋼管從鋼廠到點(diǎn)的最少總費(fèi)用，即公路運(yùn)費(fèi)，鐵路運(yùn)費(fèi)和鋼管銷售之和，與第個點(diǎn)相連的公路和鐵路的相交點(diǎn),與第個點(diǎn)相連的的第m條公路和鐵路的相交點(diǎn),相鄰結(jié)點(diǎn)與點(diǎn)之間的距離,四四. . 模型的建立與求解模型的建立與求解問題一：討論如何調(diào)整主管道鋼管的訂購和運(yùn)輸方案使總費(fèi)用最小問題一：討論如何調(diào)整主管道鋼管的訂購和運(yùn)輸方案使總費(fèi)用最小iSiSjA求鋼管從鋼廠求鋼管從鋼廠運(yùn)到運(yùn)輸點(diǎn)運(yùn)到運(yùn)輸點(diǎn)的最小費(fèi)用的最小費(fèi)用1 1將圖將圖1 1轉(zhuǎn)換為一系列以單位鋼管的運(yùn)輸費(fèi)用為權(quán)的賦權(quán)圖轉(zhuǎn)換為一

4、系列以單位鋼管的運(yùn)輸費(fèi)用為權(quán)的賦權(quán)圖. .iSjb所以可先求出鋼廠所以可先求出鋼廠到鐵路與公路相交點(diǎn)到鐵路與公路相交點(diǎn)的最短路徑的最短路徑. .如圖如圖3 3 由題意可知：將鋼管從鋼廠運(yùn)到運(yùn)輸點(diǎn)的費(fèi)用包括鋼管的銷售價格、鋼管的鐵路運(yùn)輸費(fèi)用和鋼管的公路運(yùn)輸費(fèi)用.在費(fèi)用最小時，對鋼管的訂購和運(yùn)輸進(jìn)行分配，可得出本問題的最佳方案.總費(fèi)用總費(fèi)用= =鋼廠到各節(jié)點(diǎn)的費(fèi)用鋼廠到各節(jié)點(diǎn)的費(fèi)用+ +主管道的運(yùn)輸鋪設(shè)費(fèi)用）主管道的運(yùn)輸鋪設(shè)費(fèi)用）450801150110030619520202120072069052017069016088462703201607029030圖-41SjA2計算單位鋼管從到到的最

5、少運(yùn)輸費(fèi)用的最少運(yùn)輸費(fèi)用1SjA根據(jù)圖根據(jù)圖4，借助圖論軟件包中求最短路的方法求出單位鋼管從，借助圖論軟件包中求最短路的方法求出單位鋼管從到的最短路，從而得出將單位鋼管從的最短路，從而得出將單位鋼管從 1S運(yùn)輸?shù)礁鬟\(yùn)輸點(diǎn)運(yùn)輸?shù)礁鬟\(yùn)輸點(diǎn)jA最小費(fèi)用。最小費(fèi)用。運(yùn)輸費(fèi)用依次為：運(yùn)輸費(fèi)用依次為：170.7170.7，160.3160.3，140.2140.2，98.698.6，3838，20.520.5，3.13.1，21.221.2，64.264.2，9292，9696，106106，121.2121.2，128128，142142單位：萬元）單位：萬元） 加上單位鋼管的銷售價加上單位鋼管的銷售價

6、 1SjA得出從鋼廠得出從鋼廠購買單位鋼管運(yùn)輸?shù)近c(diǎn)購買單位鋼管運(yùn)輸?shù)近c(diǎn)的最小費(fèi)用的最小費(fèi)用依次為依次為: : jA1330.3，320.3，300.2，258.6，198，180.5，163.1，181.2，224.2，252，256，266，281.2，288，302單位：萬元）.同理，可用同樣的方法求出鋼廠同理，可用同樣的方法求出鋼廠 到到 的最小費(fèi)用，從而得出各鋼廠Si到運(yùn)輸節(jié)點(diǎn)到運(yùn)輸節(jié)點(diǎn) Aj 最小運(yùn)總費(fèi)用。見表最小運(yùn)總費(fèi)用。見表1.LINGO LINGO 程序：程序：min-cost1.lg4 min-cost1.lg4 計算結(jié)果：計算結(jié)果：min-cost1.lgr表表1 Si 到

7、點(diǎn)到點(diǎn) Aj 的最小費(fèi)用的最小費(fèi)用2. 2. 建立模型建立模型運(yùn)輸總費(fèi)用可分為兩部分：運(yùn)輸總費(fèi)用可分為兩部分：運(yùn)輸總費(fèi)用運(yùn)輸總費(fèi)用= =鋼廠到各點(diǎn)的運(yùn)輸費(fèi)用鋼廠到各點(diǎn)的運(yùn)輸費(fèi)用+ +主管道的運(yùn)輸鋪設(shè)費(fèi)用主管道的運(yùn)輸鋪設(shè)費(fèi)用. .從而得出總費(fèi)用：從而得出總費(fèi)用：2) 2) 約束條件約束條件因此本問題可建立如下的非線性規(guī)劃模型：因此本問題可建立如下的非線性規(guī)劃模型： 非線性規(guī)劃模型可用LINGO軟件包或MATLAB軟件包來求解，但這些軟件包不能直接處理約束條件：可用分支定界法將此條件改為可用分支定界法將此條件改為模型變?yōu)槟Ｐ妥優(yōu)? 1不讓鋼廠不讓鋼廠S7S7生產(chǎn)，模型變?yōu)樯a(chǎn)，模型變?yōu)? :1f

8、計算結(jié)果：2f12786321278632萬元）（此時每個鋼廠的產(chǎn)量都滿足條件）萬元）（此時每個鋼廠的產(chǎn)量都滿足條件） 2 2要求鋼廠要求鋼廠S7 S7 產(chǎn)量不小于產(chǎn)量不小于500500個單位，模型變?yōu)閭€單位，模型變?yōu)? :計算結(jié)果：計算結(jié)果： 1279664萬元）（此時每個鋼廠的產(chǎn)量都滿足條件）. 121) ,min(minff ff比較這兩種情況，得最優(yōu)解為比較這兩種情況，得最優(yōu)解為S7不讓生產(chǎn)不讓生產(chǎn): .7,.,1,1,0,0.14,.,1.15,.,1,.7,.,1,500.)1()1(21.0151171151151,ifzyjbzyjzyxifsxftszzyyxAMinijjj

9、jjiijiijijijjjjjjiijij=1278632=1278632萬元具體的購運(yùn)計劃如表萬元具體的購運(yùn)計劃如表2 2： 訂購量A2A3A4A5A6A7A8A9A10A11A12A13A14A15S18000201133200266000000000S28001791114295003000000000S31000139111860006640000000S4000000000000000S5101503582420000004150000S6155600000000035186333621165S7000000000000000表表2 2 問題問題1 1的訂購和調(diào)運(yùn)方案的訂購和調(diào)運(yùn)方

10、案fi表示鋼廠表示鋼廠i是否使用；是否使用；xij是從鋼廠是從鋼廠i運(yùn)到節(jié)點(diǎn)運(yùn)到節(jié)點(diǎn)j的鋼管量的鋼管量yj是從節(jié)點(diǎn)是從節(jié)點(diǎn)j向左鋪設(shè)的鋼管量；向左鋪設(shè)的鋼管量；zj是向右鋪設(shè)的鋼管量是向右鋪設(shè)的鋼管量 比較好的方法：引入比較好的方法：引入0-10-1變量變量5171,1,7,1,1 ,05171,1,17,1,500,0.min71517117151711 jixjxisxtsxcijiijijijijijij LINDO/LINGO得到的結(jié)果比得到的結(jié)果比matlab得到的好得到的好yj zjjGUANDAO.lg4參考程序1運(yùn)輸問題的0-1規(guī)劃模型將全長5171km的管道按公里分段，共51

11、71個需求點(diǎn)，鋼廠為7個供應(yīng)點(diǎn)，構(gòu)成如下的運(yùn)輸問題cij為從供應(yīng)點(diǎn)i到需求點(diǎn)j的最小購運(yùn)費(fèi)xij=1表示從點(diǎn)i到點(diǎn)j購運(yùn)1單位鋼管求解時要針對規(guī)模問題尋求改進(jìn)算法Cij 規(guī)模太大麻煩規(guī)模太大麻煩 問題二、就問題二、就1 1的模型分析：哪個鋼廠鋼管的銷價的變的模型分析：哪個鋼廠鋼管的銷價的變化對購運(yùn)計劃和總費(fèi)用影響最大，哪個鋼廠鋼管的產(chǎn)量的上化對購運(yùn)計劃和總費(fèi)用影響最大，哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運(yùn)計劃和總費(fèi)用的影響最大，并給出相應(yīng)的數(shù)限的變化對購運(yùn)計劃和總費(fèi)用的影響最大，并給出相應(yīng)的數(shù)字結(jié)果字結(jié)果. . 由于鋼廠鋼管的銷售價格變化和鋼廠鋼管產(chǎn)量的上限變化對購運(yùn)計劃和總費(fèi)用造成影響，為更

12、好地考察影響，下面分別進(jìn)行討論方案中運(yùn)往各點(diǎn)的運(yùn)輸量的變化量的絕對值之和稱為運(yùn)輸方案變化量方案中運(yùn)往各點(diǎn)的運(yùn)輸量的變化量的絕對值之和稱為運(yùn)輸方案變化量1 1討論鋼廠鋼管的銷售價格變化對購運(yùn)計劃和總費(fèi)用的影響討論鋼廠鋼管的銷售價格變化對購運(yùn)計劃和總費(fèi)用的影響 當(dāng)鋼廠鋼管的銷售價格 變化時，會對購運(yùn)計劃和總費(fèi)用造成影響。為更好地觀察每一個鋼廠的銷售價格 變化時所造成的影響，本問題采用比較法。即：每次只讓一個鋼廠鋼管的銷售價格發(fā)生相同的變化，其余鋼廠鋼管的銷售價格不發(fā)生變化；當(dāng)每個鋼廠的銷售價個發(fā)生同樣的變化 C 時，求出相應(yīng)的總費(fèi)用，然后比較。分析：分析：表3 C=-5表4 C=5表5 C=1表6

13、 C=-1從上述四個表格中可以看出：鋼廠鋼管的銷售價格變化時，從上述四個表格中可以看出：鋼廠鋼管的銷售價格變化時，S6對總費(fèi)用對總費(fèi)用影響最大，影響最大，S5對購運(yùn)計劃影響最大。對購運(yùn)計劃影響最大。2) 2) 討論鋼廠產(chǎn)量的上限變化對購運(yùn)計劃和總費(fèi)用的影響討論鋼廠產(chǎn)量的上限變化對購運(yùn)計劃和總費(fèi)用的影響 本問題同樣采用比較法。即：每次只改變一個鋼廠鋼管產(chǎn)量的上限，其他鋼廠鋼管產(chǎn)量上限不發(fā)生變化的情況，利用問題一中的模型進(jìn)行討論。 a. 對產(chǎn)量不受限制的情況計算得到下表表7 產(chǎn)量不受限制的情形b. 對產(chǎn)量下降100的情況計算得到下表表8 產(chǎn)量下降100的情況c.對產(chǎn)量升高100 的情況計算得到下表

14、表9 產(chǎn)量升高100的情況結(jié)論：從上述表格中可以看出鋼廠鋼管產(chǎn)量的上限變化時，結(jié)論：從上述表格中可以看出鋼廠鋼管產(chǎn)量的上限變化時，S1對對 總費(fèi)用和總費(fèi)用和購運(yùn)計劃影響最大。購運(yùn)計劃影響最大。問題三、討論鐵路、公路構(gòu)成網(wǎng)絡(luò)的情形問題三、討論鐵路、公路構(gòu)成網(wǎng)絡(luò)的情形 本問題是討論鋪設(shè)的管道是樹形圖，鐵路、公路構(gòu)成網(wǎng)絡(luò)的情形，對于這種問題的求解過程，以圖-2進(jìn)行說明。1. 1. 鋪設(shè)管道是樹形圖時，基本解法原理鋪設(shè)管道是樹形圖時，基本解法原理圖圖-3A13258010103120124270108810706270302020304501043017506061942052016804803002

15、20210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7 為求出一般由鐵路、公路、管道構(gòu)成網(wǎng)絡(luò)情況下的最優(yōu)購運(yùn)和最小總費(fèi)用方案，首先必須求出各鋼廠到個管道節(jié)點(diǎn)的最短費(fèi)用路徑。由于在途中可能發(fā)生火車汽車火車的轉(zhuǎn)運(yùn)方案，而這種情況發(fā)生的前提條件是公路（或管道的兩端必須都是火車站點(diǎn)，由于鐵路運(yùn)輸?shù)馁M(fèi)用是分段函數(shù)，故求各鋼廠到各管道結(jié)點(diǎn)的最小費(fèi)用步驟如下：1首先找出公路的兩個端點(diǎn)都是火車站站點(diǎn)的結(jié)點(diǎn)V1,V2,Vs2) 2) 把

16、公路網(wǎng)和鐵路網(wǎng)分開，分別組成網(wǎng)絡(luò)；把公路網(wǎng)和鐵路網(wǎng)分開，分別組成網(wǎng)絡(luò)；3 3在鐵路網(wǎng)中求出各鋼廠在鐵路網(wǎng)中求出各鋼廠SiSi及各點(diǎn)及各點(diǎn)ViVi到各火車站點(diǎn)的最短路，并把它轉(zhuǎn)化到各火車站點(diǎn)的最短路，并把它轉(zhuǎn)化 為最小費(fèi)用路為最小費(fèi)用路4)4)在公路網(wǎng)中求出各管道結(jié)點(diǎn)到各火車站點(diǎn)的最短路，并把它轉(zhuǎn)化為最小在公路網(wǎng)中求出各管道結(jié)點(diǎn)到各火車站點(diǎn)的最短路，并把它轉(zhuǎn)化為最小 費(fèi)用路費(fèi)用路5 5把前面的結(jié)點(diǎn)合并成一個網(wǎng)絡(luò)，分別求出各鋼廠把前面的結(jié)點(diǎn)合并成一個網(wǎng)絡(luò)，分別求出各鋼廠Si Si 到各管道結(jié)點(diǎn)的最小到各管道結(jié)點(diǎn)的最小 運(yùn)輸費(fèi)用路。并求出各鋼廠運(yùn)輸費(fèi)用路。并求出各鋼廠 SiSi到各管道結(jié)點(diǎn)到各管道結(jié)

17、點(diǎn)AjAj的最小費(fèi)用，由此可得到的最小費(fèi)用，由此可得到最小費(fèi)用最小費(fèi)用 Aij Aij 見下表見下表10.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 70110145150145 程序：min-cost 2.lg4 2.2.一般模型一般模型故有：3.3.問題三的求解問題三的求解221) ,min(minff ff1 1不讓鋼廠不讓鋼廠S7S7生產(chǎn)，計算結(jié)果為生產(chǎn)，計算結(jié)果為: :14056111405611萬元）（此時每個鋼廠的產(chǎn)量都滿足條件）萬元）（此時每個鋼廠的產(chǎn)量都滿足條件） 2f2 2要求鋼廠要求鋼廠S7 S7 產(chǎn)量不小于產(chǎn)量不小于500500個單位，計算結(jié)果為個單位，計算結(jié)果為: : 1405197萬元）（此時每個鋼廠的產(chǎn)量都滿足條件）