數(shù)學模型——鋼管訂購和運輸.doc

鋼管訂購和運輸一、 問題提出要鋪設一條 的輸送天然氣的主管道, 如圖一所示(見下頁)。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有S1,S2,.,S7。圖中粗線表示鐵路，單細線表示公路，雙細線表示要鋪設的管道(假設沿管道或者原來有公路，或者建有施工公路)，圓圈表示火車站，每段鐵路、公路和管道旁的阿拉伯數(shù)字表示里程(單位km)。為方便計，1km主管道鋼管稱為1單位鋼管。一個鋼廠如果承擔制造這種鋼管，至少需要生產(chǎn)500個單位。鋼廠Si 在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為si 個單位，鋼管出廠銷價1單位鋼管為pi 萬元，如下表：I1234567si80080010002000200020003000Pi1601551551601551501601單位鋼管的鐵路運價如下表：里程300301350351400401500451500運價（萬元）2023262932里程（km）5016006017007018008019009011000運價（萬元）37445055601000km以上每增加1至100km運價增加5萬元。 公路運輸費用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計算）。鋼管可由鐵路、公路運往鋪設地點（不只是運到點A1,A2,.,A15 ，而是管道全線）。（1） 請制定一個主管道鋼管的訂購和運輸計劃，使總費用最?。ńo出總費用)。（2） 請就（1）的模型分析：哪個鋼廠鋼管的銷價的變化對購運計劃和總費用影響最大，哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運計劃和總費用的影響最大，并給出相應的數(shù)字結果。（3） 如果要鋪設的管道不是一條線，而是一個樹形圖，鐵路、公路和管道構成網(wǎng)絡，請就這種更一般的情形給出一種解決辦法，并對圖二按（1）的要求給出模型和結果。二、 模型假設1. 只考慮訂購費用和運輸費用，不考慮裝卸等其他費用。2. 要鋪設的管道側有公路，可運輸所需鋼管。3. 鋼管單價與訂購量、訂購次數(shù)、訂購日期無關。4. 訂購假話是指對每個廠商的訂貨數(shù)量；運輸方案是指具有如下屬性的一批記錄：管道區(qū)間、供應廠商、具體運輸路線。5. 將每一單位的管道所在地看成一個需求點，向以單位管道的所在地運輸鋼管即向一個點運輸鋼管。6. 鋼管在運送和使用中沒有損耗。三、 符號說明符號說明m鋼廠數(shù)n管網(wǎng)中的結點數(shù)r要鋪設的單位管道總數(shù)d公路上一單位鋼管的每公里運費（0.1萬元）W訂購鋼管、運輸?shù)目傎M用（單位：萬元）Si第i個鋼廠si第i個鋼廠最大生產(chǎn)鋼管數(shù)Ai管道線上第i個節(jié)點Yj運送到Aj向Aj-1鋪設的管道數(shù)Zj運送到Aj向Aj+1鋪設的管道數(shù)pi第i個鋼廠每單位鋼管的售價cij一個單位鋼管從鋼廠Si到管網(wǎng)節(jié)點Aj的最小運價tjk管網(wǎng)上相鄰節(jié)點Aj與Ak之間的邊長AjAk（里程數(shù)）Tj等于AjAj+1路段的總長度（即鋼管數(shù)）eih表示鋼廠Si到編號為h這一段的最低費用（包括訂購費用和運輸費用）zihsi到Aj的總鋼管運量四、 問題分析l 對于問題I的分析整個鋪設管道的工程看似錯綜復雜，其實可以分為三個部分：（1） 各個工廠（Si）生產(chǎn)一定數(shù)量的鋼管；（2） 把鋼管從工廠（Si）運送到鋪設管道的關節(jié)點（Ai）；（3） 從關節(jié)點（Ai）將管道運輸至鋪設地點；其中：（1） 購買鋼管的費用只與向各鋼廠訂購剛鋼管的數(shù)量有關，與運輸路線無關，只需求出最終各工廠生產(chǎn)多少單位鋼管并乘以相應單價即可（后面需考慮每個工廠最小生產(chǎn)數(shù)量及最大生產(chǎn)數(shù)量）；（2） 我們需要求出個鋼廠到各個火車站的最短里程（這里涉及最短路徑的求解，我們可以使用Dijkstra算法或Floyd算法進行求解，在題目簡單的情況下我們也可以口算求解，在這里我們使用Floyd算法進行最短路徑的求解），再根據(jù)鐵路運價得到每單位鋼管由鋼廠到火車站的最低運價。用類似方法也可以的得到火車站到個管網(wǎng)節(jié)點的最低運價，將這兩者結合起來即可得到每單位鋼管從某鋼廠到某鋪設點運輸單位鋼管的最少運輸費用cij。（3） 從關節(jié)點（Ai）將管道運輸至鋪設地點，每個關節(jié)點須向Aj-1和Aj+1兩個方向運輸和鋪設。將這三部分的費用做加和即得到第一問中所求的最小總費用。l 對于問題II的分析通過問題一里面Lingo編程運行得出的結果，分析哪個鋼廠鋼管的銷價的變化對購運計劃和總費用影響最大，哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運計劃和總費用的影響最大。l 對于問題III的分析利用同問題I同樣的方法，從而可求出某鋼廠到某某鋪設點運輸單位鋼管的最少運輸費用。五、 模型建立與求解1) 模型建立問題I模型：如上文分析所述，我們采用Floyd算法，用matlab編程求出單位鋼管從運輸?shù)降淖钚∵\輸費用，具體數(shù)據(jù)如下表：表1 單位鋼管從運輸?shù)降淖钚≠M用(包括生產(chǎn))（單位：萬元）目標函數(shù)是總費用W , 它包含三項: 鋼管出廠總價Q , 運輸費P , 及鋪設費T. 即W = Q + P + T其中 ， ， 鋪設費T可以如下來確定：開始從左右兩個方向鋪設，與單位長鋼管的費用為 + ，于是最小費用可表示為： 約束條件為:生產(chǎn)能力的限制: ， 運到的總鋼管數(shù): ， 與之間的鋼管: ， 變量非負性限制:, 其它限制：Z15=0， Y2=104故問題一的模型為：s.t. ， ， ， =0 , =104 ， =0, =0或1 (i=1,.,7) d=0.05; 2) 數(shù)值求解1. 根據(jù)模型計算得出，工廠4沒有運出貨物，需要被淘汰2. 工廠7得出的結果大于0小于500需要求在1的條件下求沒有工廠7，和有工廠7且的結果較，的出來的較小的成本，即為最優(yōu)解。經(jīng)計算沒有工廠4和7的結果是最優(yōu)的結果為1279977.萬元初始求解lingo代碼為：MODEL:Title 鋼管;sets:supply/1.7/: s,p; ! 工廠，s表示工廠最大生產(chǎn)量，p表示售價;demand/1.14/: a,tt,ww; ! 公路,y表示公路點收到的鋼管輛，a表示公路段長度，tt（i）表示從第i+1公路點向左運輸?shù)牧?，ww（i）表示從第i公路點向有運輸?shù)膇ang;link(supply,demand):c,t,w,x; !x表示第i工廠到第j公路點的運輸量，但是x無法求出，SB Lingo說我變量太多不能求了，就沒求x，t（i）表示第i+1公路點向左運輸量，w表示向右的同上;endsetsdata:c= 320.3,300.2,258.6,198,180.5,163,181.2,224.2,252,256,266,281.2,288,302, 360.3,345.2,326.6,266,250.5,241,266.2,269.2,297,301,311,326.2,333,347, 375.3,355.2,336.6,276,260.5,251,241.2,203.2,237,241,251,266.2,273,287, 410.3,395.2,376.6,316,300.5,291,276.2,244.2,222,211,221,236.2,243,257, 400.3,380.2,361.6,301,285.5,276,266.2,234.2,212,188,206,226.2,228,242, 405.3,385.2,366.6,306,290.5,281,271.2,234.2,212,201,195,176.2,161,178, 425.3,405.2,386.6,326,310.5,301,291.2,259.2,237,226,216,198.2,186,162;a= 104,301,750,606,194,205,201,680,480,300,220,210,420,500;s= 800,800,1000,2000,2000,2000,3000;p= 160,155,155,160,155,150,160;enddatainit:!ww(14) = 0;endinitmin = SUM( link(i,j): c(i,j)*( t(i,j)+w(i,j) ) ) + SUM( demand(i): (ww2+ww+tt2+tt)/20 );FOR( supply(i): SUM( demand(j): t(i,j)+w(i,j) ) = s(i); ); !因該是第i工廠到所有公路點的運輸量小于工廠的最大生產(chǎn)量;FOR( demand(j): SUM( supply(i): t(i,j) ) = tt(j); ); !所有工廠運到第j公路點的鋼管（向左運輸?shù)模?= 第j公路點向做運輸?shù)牧?FOR( demand(j): SUM( supply(i): w(i,j) ) = ww(j); ); !同上 換成向右的;FOR( demand(j): tt(j) = a(j) ); !每個公路點向左的運輸量小于左端公路長度;tt(1) = 104;ww(14) = 0; !FOR( set | cond: exp);FOR( demand(j)|j#LE#13:tt(j+1)+ww(j) = a(j+1);); !每段公路上 從右端點運來的 + 從左端點運來的 = 該段長度;tt(1) = a(1);! FOR( link(i,j): t(i,j)+w(i,j) = x(i,j); !); !FOR( demand(j): SUM( supply(i): t(i,j)+w(i,j) ) = y(j); !);end沒有工廠4和沒有工廠7的代碼：MODEL:Title 鋼管;sets:supply/1.5/: s,p; ! 工廠，s表示工廠最大生產(chǎn)量，p表示售價;demand/1.14/: a,tt,ww; ! 公路,y表示公路點收到的鋼管輛，a表示公路段長度，tt（i）表示從第i+1公路點向左運輸?shù)牧?，ww（i）表示從第i公路點向有運輸?shù)膇ang;link(supply,demand):c,t,w,x; !x表示第i工廠到第j公路點的運輸量，但是x無法求出，SB Lingo說我變量太多不能求了，就沒求x，t（i）表示第i+1公路點向左運輸量，w表示向右的同上;endsetsdata:c= 320.3,300.2,258.6,198,180.5,163,181.2,224.2,252,256,266,281.2,288,302, 360.3,345.2,326.6,266,250.5,241,266.2,269.2,297,301,311,326.2,333,347, 375.3,355.2,336.6,276,260.5,251,241.2,203.2,237,241,251,266.2,273,287, !410.3,395.2,376.6,316,300.5,291,276.2,244.2,222,211,221,236.2,243,257,; 400.3,380.2,361.6,301,285.5,276,266.2,234.2,212,188,206,226.2,228,242, 405.3,385.2,366.6,306,290.5,281,271.2,234.2,212,201,195,176.2,161,178; !425.3,405.2,386.6,326,310.5,301,291.2,259.2,237,226,216,198.2,186,162;a= 104,301,750,606,194,205,201,680,480,300,220,210,420,500;s= 800,800,1000,!2000,;2000,2000;!,3000;p= 160,155,155,!160,;155,150;!,160;enddatainit:!ww(14) = 0;endinitmin = SUM( link(i,j): c(i,j)*( t(i,j)+w(i,j) ) ) + SUM( demand(i): (ww2+ww+tt2+tt)/20 );FOR( supply(i): SUM( demand(j): t(i,j)+w(i,j) ) = s(i); ); !因該是第i工廠到所有公路點的運輸量小于工廠的最大生產(chǎn)量;FOR( demand(j): SUM( supply(i): t(i,j) ) = tt(j); ); !所有工廠運到第j公路點的鋼管（向左運輸?shù)模?= 第j公路點向做運輸?shù)牧?FOR( demand(j): SUM( supply(i): w(i,j) ) = ww(j); ); !同上 換成向右的;FOR( demand(j): tt(j) = a(j) ); !每個公路點向左的運輸量小于左端公路長度;tt(1) = 104;ww(14) = 0; !FOR( set | cond: exp);FOR( demand(j)|j#LE#13:tt(j+1)+ww(j) = a(j+1);); !每段公路上 從右端點運來的 + 從左端點運來的 = 該段長度;tt(1) = a(1);! FOR( link(i,j): t(i,j)+w(i,j) = x(i,j); !); !FOR( demand(j): SUM( supply(i): t(i,j)+w(i,j) ) = y(j); !);End結果為：1279977.萬元沒有工廠4且工廠7的生產(chǎn)量大于500代碼：MODEL:Title 鋼管;sets:supply/1.6/: s,p; ! 工廠，s表示工廠最大生產(chǎn)量，p表示售價;demand/1.14/: a,tt,ww; ! 公路,y表示公路點收到的鋼管輛，a表示公路段長度，tt（i）表示從第i+1公路點向左運輸?shù)牧?，ww（i）表示從第i公路點向有運輸?shù)膇ang;link(supply,demand):c,t,w,x; !x表示第i工廠到第j公路點的運輸量，但是x無法求出，SB Lingo說我變量太多不能求了，就沒求x，t（i）表示第i+1公路點向左運輸量，w表示向右的同上;endsetsdata:c= 320.3,300.2,258.6,198,180.5,163,181.2,224.2,252,256,266,281.2,288,302, 360.3,345.2,326.6,266,250.5,241,266.2,269.2,297,301,311,326.2,333,347, 375.3,355.2,336.6,276,260.5,251,241.2,203.2,237,241,251,266.2,273,287, !410.3,395.2,376.6,316,300.5,291,276.2,244.2,222,211,221,236.2,243,257,; 400.3,380.2,361.6,301,285.5,276,266.2,234.2,212,188,206,226.2,228,242, 405.3,385.2,366.6,306,290.5,281,271.2,234.2,212,201,195,176.2,161,178, 425.3,405.2,386.6,326,310.5,301,291.2,259.2,237,226,216,198.2,186,162;a= 104,301,750,606,194,205,201,680,480,300,220,210,420,500;s= 800,800,1000,!2000,;2000,2000,3000;p= 160,155,155,!160,;155,150,160;enddatainit:!ww(14) = 0;endinitmin = SUM( link(i,j): c(i,j)*( t(i,j)+w(i,j) ) ) + SUM( demand(i): (ww2+ww+tt2+tt)/20 );FOR( supply(i): SUM( demand(j): t(i,j)+w(i,j) ) = s(i); ); !因該是第i工廠到所有公路點的運輸量小于工廠的最大生產(chǎn)量;FOR( demand(j): SUM( supply(i): t(i,j) ) = tt(j); ); !所有工廠運到第j公路點的鋼管（向左運輸?shù)模?= 第j公路點向做運輸?shù)牧?FOR( demand(j): SUM( supply(i): w(i,j) ) = ww(j); ); !同上 換成向右的;FOR( demand(j): tt(j) = 500;tt(1) = 104;ww(14) = 0; !FOR( set | cond: exp);FOR( demand(j)|j#LE#13:tt(j+1)+ww(j) = a(j+1);); !每段公路上 從右端點運來的 + 從左端點運來的 = 該段長度;tt(1) = a(1);! FOR( link(i,j): t(i,j)+w(i,j) = x(i,j); !); !FOR( demand(j): SUM( supply(i): t(i,j)+w(i,j) ) = y(j); !);end結果為： 281006.萬元最終lingo顯示結果為： Local optimal solution found. Objective value: 1279977. Infeasibilities: 0.2842171E-13 Total solver iterations: 89 Model Title: 鋼管 Variable Value Reduced Cost S( 1) 800.0000 0.000000 S( 2) 800.0000 0.000000 S( 3) 1000.000 0.000000 S( 4) 2000.000 0.000000 S( 5) 2000.000 0.000000 P( 1) 160.0000 0.000000 P( 2) 155.0000 0.000000 P( 3) 155.0000 0.000000 P( 4) 155.0000 0.000000 P( 5) 150.0000 0.000000 A( 1) 104.0000 0.000000 A( 2) 301.0000 0.000000 A( 3) 750.0000 0.000000 A( 4) 606.0000 0.000000 A( 5) 194.0000 0.000000 A( 6) 205.0000 0.000000 A( 7) 201.0000 0.000000 A( 8) 680.0000 0.000000 A( 9) 480.0000 0.000000 A( 10) 300.0000 0.000000 A( 11) 220.0000 0.000000 A( 12) 210.0000 0.000000 A( 13) 420.0000 0.000000 A( 14) 500.0000 0.000000 TT( 1) 104.0000 0.000000 TT( 2) 226.0000 0.000000 TT( 3) 468.0000 0.000000 TT( 4) 606.0000 0.000000 TT( 5) 184.5000 0.000000 TT( 6) 190.0000 0.000000 TT( 7) 99.50000 0.000000 TT( 8) 530.0000 0.000000 TT( 9) 321.0000 0.000000 TT( 10) 270.0000 0.000000 TT( 11) 75.00000 0.000000 TT( 12) 199.0000 0.000000 TT( 13) 286.0000 0.000000 TT( 14) 165.0000 0.000000 WW( 1) 75.00000 0.000000 WW( 2) 282.0000 0.000000 WW( 3) 0.000000 0.000000 WW( 4) 9.500000 0.000000 WW( 5) 15.00000 0.000000 WW( 6) 101.5000 0.000000 WW( 7) 150.0000 0.000000 WW( 8) 159.0000 0.000000 WW( 9) 30.00000 0.000000 WW( 10) 145.0000 0.000000 WW( 11) 11.00000 0.000000 WW( 12) 134.0000 0.000000 WW( 13) 335.0000 0.000000 WW( 14) 0.000000 0.000000 C( 1, 1) 320.3000 0.000000 C( 1, 2) 300.2000 0.000000 C( 1, 3) 258.6000 0.000000 C( 1, 4) 198.0000 0.000000 C( 1, 5) 180.5000 0.000000 C( 1, 6) 163.0000 0.000000 C( 1, 7) 181.2000 0.000000 C( 1, 8) 224.2000 0.000000 C( 1, 9) 252.0000 0.000000 C( 1, 10) 256.0000 0.000000 C( 1, 11) 266.0000 0.000000 C( 1, 12) 281.2000 0.000000 C( 1, 13) 288.0000 0.000000 C( 1, 14) 302.0000 0.000000 C( 2, 1) 360.3000 0.000000 C( 2, 2) 345.2000 0.000000 C( 2, 3) 326.6000 0.000000 C( 2, 4) 266.0000 0.000000 C( 2, 5) 250.5000 0.000000 C( 2, 6) 241.0000 0.000000 C( 2, 7) 266.2000 0.000000 C( 2, 8) 269.2000 0.000000 C( 2, 9) 297.0000 0.000000 C( 2, 10) 301.0000 0.000000 C( 2, 11) 311.0000 0.000000 C( 2, 12) 326.2000 0.000000 C( 2, 13) 333.0000 0.000000 C( 2, 14) 347.0000 0.000000 C( 3, 1) 375.3000 0.000000 C( 3, 2) 355.2000 0.000000 C( 3, 3) 336.6000 0.000000 C( 3, 4) 276.0000 0.000000 C( 3, 5) 260.5000 0.000000 C( 3, 6) 251.0000 0.000000 C( 3, 7) 241.2000 0.000000 C( 3, 8) 203.2000 0.000000 C( 3, 9) 237.0000 0.000000 C( 3, 10) 241.0000 0.000000 C( 3, 11) 251.0000 0.000000 C( 3, 12) 266.2000 0.000000 C( 3, 13) 273.0000 0.000000 C( 3, 14) 287.0000 0.000000 C( 4, 1) 400.3000 0.000000 C( 4, 2) 380.2000 0.000000 C( 4, 3) 361.6000 0.000000 C( 4, 4) 301.0000 0.000000 C( 4, 5) 285.5000 0.000000 C( 4, 6) 276.0000 0.000000 C( 4, 7) 266.2000 0.000000 C( 4, 8) 234.2000 0.000000 C( 4, 9) 212.0000 0.000000 C( 4, 10) 188.0000 0.000000 C( 4, 11) 206.0000 0.000000 C( 4, 12) 226.2000 0.000000 C( 4, 13) 228.0000 0.000000 C( 4, 14) 242.0000 0.000000 C( 5, 1) 405.3000 0.000000 C( 5, 2) 385.2000 0.000000 C( 5, 3) 366.6000 0.000000 C( 5, 4) 306.0000 0.000000 C( 5, 5) 290.5000 0.000000 C( 5, 6) 281.0000 0.000000 C( 5, 7) 271.2000 0.000000 C( 5, 8) 234.2000 0.000000 C( 5, 9) 212.0000 0.000000 C( 5, 10) 201.0000 0.000000 C( 5, 11) 195.0000 0.000000 C( 5, 12) 176.2000 0.000000 C( 5, 13) 161.0000 0.000000 C( 5, 14) 178.0000 0.000000 T( 1, 1) 0.000000 28.00000 T( 1, 2) 0.000000 23.00000 T( 1, 3