數(shù)學(xué)建模2000B題

1、2000網(wǎng)易杯全國大學(xué)生網(wǎng)易杯全國大學(xué)生 數(shù)學(xué)建模競賽題目數(shù)學(xué)建模競賽題目B題題 鋼管訂購和運(yùn)輸鋼管訂購和運(yùn)輸 信息信息（語言、數(shù)據(jù)）（語言、數(shù)據(jù)） 問題問題（第一問，（第一問，,） 問題問題所屬類型所屬類型 做題做題思路和關(guān)鍵點(diǎn)思路和關(guān)鍵點(diǎn) 結(jié)果結(jié)果表示形式表示形式讀讀 題題要鋪設(shè)一條要鋪設(shè)一條 輸送天然氣的主管道輸送天然氣的主管道, ,如圖一所示。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有如圖一所示。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有。圖中粗線表示鐵路，單細(xì)線。圖中粗線表示鐵路，單細(xì)線表示公路表示公路，雙細(xì)雙細(xì)線表示要鋪設(shè)的管道（假設(shè)沿管道或者線表示要鋪設(shè)的管道（假設(shè)沿管道或者原來有公路，

2、或者原來有公路，或者和管道旁的阿拉伯?dāng)?shù)字表示里程（單位：和管道旁的阿拉伯?dāng)?shù)字表示里程（單位：KmKm）。）?；蛘呓ㄓ惺┕す坊蛘呓ㄓ惺┕す?) )，圓圈表示火車站，每段鐵路、公路，圓圈表示火車站，每段鐵路、公路1521AAA721,SSS為方便計(jì)，為方便計(jì)，1 Km1 Km主管道鋼管稱為主管道鋼管稱為1 1單位鋼管。單位鋼管。A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115

3、011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7圖一一個(gè)鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)一個(gè)鋼廠如果承擔(dān)制造這種鋼管，至少需要生產(chǎn)500500個(gè)個(gè)單位。鋼廠單位。鋼廠在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為個(gè)單位，鋼管出廠銷價(jià)個(gè)單位，鋼管出廠銷價(jià)1 1單位鋼管為單位鋼管為萬元，如下表：萬元，如下表：1234567800800 10002000 2000 2000 3000160155155160155150160iipiSisipis1單位鋼管的鐵路運(yùn)價(jià)如下表：單位鋼管的鐵路運(yùn)價(jià)如下表：里程

4、里程(km)300301350351400401450451500運(yùn)價(jià)（萬元）運(yùn)價(jià)（萬元）2023262932里程里程(km)5016006017007018008019009011000運(yùn)價(jià)運(yùn)價(jià)(萬元萬元)3744505560 1000km 1000km以上每增加以上每增加1 1至至100km100km運(yùn)價(jià)增加運(yùn)價(jià)增加5 5萬元。萬元。 公路運(yùn)輸費(fèi)用為公路運(yùn)輸費(fèi)用為1 1單位鋼管每公里單位鋼管每公里0.10.1萬元（不足整公萬元（不足整公里部分按整公里計(jì)算）。里部分按整公里計(jì)算）。鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只運(yùn)到點(diǎn)鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只運(yùn)到點(diǎn)，而是管道全線）。，而是管道

5、全線）。1521,AAA問題：問題： （1 1）請(qǐng)制定一個(gè)主管道鋼管的訂購和運(yùn)輸計(jì)劃，使總費(fèi)）請(qǐng)制定一個(gè)主管道鋼管的訂購和運(yùn)輸計(jì)劃，使總費(fèi)用最?。ńo出總費(fèi)用用最小（給出總費(fèi)用) )。（2 2）請(qǐng)就（）請(qǐng)就（1 1）的模型分析：哪個(gè)鋼廠鋼管的銷價(jià)的變化）的模型分析：哪個(gè)鋼廠鋼管的銷價(jià)的變化對(duì)購運(yùn)計(jì)劃和總費(fèi)用影響最大？哪個(gè)鋼廠鋼管的產(chǎn)量的上限對(duì)購運(yùn)計(jì)劃和總費(fèi)用影響最大？哪個(gè)鋼廠鋼管的產(chǎn)量的上限的變化對(duì)購運(yùn)計(jì)劃和總費(fèi)用的影響最大？并給出相應(yīng)的數(shù)的變化對(duì)購運(yùn)計(jì)劃和總費(fèi)用的影響最大？并給出相應(yīng)的數(shù)字字結(jié)果。結(jié)果。（3 3）如果要鋪設(shè)的管道不是一條線，而是一個(gè)樹形圖，）如果要鋪設(shè)的管道不是一條線，而是一個(gè)

6、樹形圖， 鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請(qǐng)就這種更一般的情形給出鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請(qǐng)就這種更一般的情形給出一種解決辦法，并對(duì)圖二按（一種解決辦法，并對(duì)圖二按（1 1）的要求給出模型和結(jié)果。）的要求給出模型和結(jié)果。A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7

7、圖一A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A19130190260100A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16A17A18A20(A21)圖二 問題問題所屬類型所屬類型 做題做題思路和關(guān)鍵點(diǎn)思路和關(guān)鍵點(diǎn) 結(jié)果結(jié)果表示形式表示形式 優(yōu)化模型優(yōu)化模型1 1、問題的問題的分析分析優(yōu)化問題優(yōu)化

8、問題1 1）優(yōu)化模型的數(shù)學(xué)描述）優(yōu)化模型的數(shù)學(xué)描述.,.,)(mihi210 x),.,(nxxxx321x求函數(shù)求函數(shù))(xfu 在約束條件在約束條件下的最大值或最小值，其中下的最大值或最小值，其中.,.,),)()(piggii2100 xx和和設(shè)計(jì)變量（決策變量）設(shè)計(jì)變量（決策變量）目標(biāo)函數(shù)目標(biāo)函數(shù)x)(xf x 可行域可行域tosubjectts .“受約束于”之意Iibgtsii,)( . .xJjforj )(max) min(xx.,.,.,.,.minnixnibxatsxcuinkikikniii2102111線性規(guī)劃（線性規(guī)劃（LP） 目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量的

9、目標(biāo)函數(shù)和所有的約束條件都是設(shè)計(jì)變量的線性函數(shù)。線性函數(shù)。二次規(guī)劃問題二次規(guī)劃問題.,.,.,.,.)(min,nixnibxatsxxbxcxfuinjijijnjijiijniii2102121111目標(biāo)函數(shù)為二次函數(shù)，約束條件為線性約束目標(biāo)函數(shù)為二次函數(shù)，約束條件為線性約束2）建立優(yōu)化模型的一般步驟）建立優(yōu)化模型的一般步驟1.確定設(shè)計(jì)變量和目標(biāo)變量；確定設(shè)計(jì)變量和目標(biāo)變量；2.確定目標(biāo)函數(shù)的表達(dá)式；確定目標(biāo)函數(shù)的表達(dá)式；3.尋找約束條件。尋找約束條件。 設(shè)有某物資從設(shè)有某物資從m個(gè)發(fā)點(diǎn)個(gè)發(fā)點(diǎn) 輸送到輸送到n個(gè)收點(diǎn)個(gè)收點(diǎn) 其中每個(gè)發(fā)點(diǎn)發(fā)出量分別為其中每個(gè)發(fā)點(diǎn)發(fā)出量分別為 每個(gè)收每個(gè)收點(diǎn)輸入

10、量分別為點(diǎn)輸入量分別為 ，并且滿足，并且滿足從發(fā)點(diǎn)從發(fā)點(diǎn)A到收點(diǎn)到收點(diǎn)B的距離（或單位運(yùn)費(fèi)）是已知的，設(shè)為的距離（或單位運(yùn)費(fèi)）是已知的，設(shè)為 。問題：問題：尋求一個(gè)調(diào)運(yùn)方案，使總運(yùn)輸費(fèi)用達(dá)到最小。尋求一個(gè)調(diào)運(yùn)方案，使總運(yùn)輸費(fèi)用達(dá)到最小。maaa,.,21nbbb,.,21minijjiba1),.,.,(njmicij2121例例 運(yùn)輸問題運(yùn)輸問題mAAA,21nBBB,21B1 B2 . BnA1A2Ama1a2am b1 b2 . bn.x11 x12 . x1nx21 x22 . x2nxm1 xm2 . xmn收點(diǎn)收點(diǎn)發(fā)點(diǎn)發(fā)點(diǎn) 一個(gè)調(diào)運(yùn)方案主要由一組從發(fā)點(diǎn)一個(gè)調(diào)運(yùn)方案主要由一組從發(fā)點(diǎn)

11、到收點(diǎn)到收點(diǎn) 的輸?shù)妮斔土縼砻枋觥Ｋ土縼砻枋?。iAjBijx總的費(fèi)用總的費(fèi)用njjjnnjxCxCxCxCBA11111121211111.njjjnnjxCxCxCxCBA12222222221212.minjijijxCf11A1A1的總費(fèi)用的總費(fèi)用A2A2的總費(fèi)用的總費(fèi)用s.t.njmixnjbxmiaxijmijijnjiij,.,.,.,.,.,.,21210212111minjijijxCf11min數(shù)學(xué)模型數(shù)學(xué)模型求解：單純形方法。minijjiba1問題：問題： （1 1）請(qǐng)制定一個(gè)主管道鋼管的訂購和運(yùn)輸計(jì)劃，使總費(fèi)）請(qǐng)制定一個(gè)主管道鋼管的訂購和運(yùn)輸計(jì)劃，使總費(fèi)用最?。ńo出總費(fèi)

12、用用最?。ńo出總費(fèi)用) )。（2 2）請(qǐng)就（）請(qǐng)就（1 1）的模型分析：哪個(gè)鋼廠鋼管的銷價(jià)的變化）的模型分析：哪個(gè)鋼廠鋼管的銷價(jià)的變化對(duì)購運(yùn)計(jì)劃和總費(fèi)用影響最大？哪個(gè)鋼廠鋼管的產(chǎn)量的上限對(duì)購運(yùn)計(jì)劃和總費(fèi)用影響最大？哪個(gè)鋼廠鋼管的產(chǎn)量的上限的變化對(duì)購運(yùn)計(jì)劃和總費(fèi)用的影響最大？并給出相應(yīng)的數(shù)的變化對(duì)購運(yùn)計(jì)劃和總費(fèi)用的影響最大？并給出相應(yīng)的數(shù)字字結(jié)果。結(jié)果。（3 3）如果要鋪設(shè)的管道不是一條線，而是一個(gè)樹形圖，）如果要鋪設(shè)的管道不是一條線，而是一個(gè)樹形圖， 鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請(qǐng)就這種更一般的情形給出鐵路、公路和管道構(gòu)成網(wǎng)絡(luò)，請(qǐng)就這種更一般的情形給出一種解決辦法，并對(duì)圖二按（一種解決辦法，并對(duì)

13、圖二按（1 1）的要求給出模型和結(jié)果。）的要求給出模型和結(jié)果。B1 B2 . BnS1S2S7a1a2am b1 b2 . bn.x11 x12 . x1nx21 x22 . x2nxm1 xm2 . xmn收點(diǎn)收點(diǎn)發(fā)點(diǎn)發(fā)點(diǎn) 訂購與運(yùn)輸方案訂購與運(yùn)輸方案ijxSi1234567供貨量？n=5171s.t.7151711minijijijxcW)7 , 1(,500051711isxijij)5171, 2 , 1(171jxiij)5171, 1()7 , 1(10jiorxij數(shù)學(xué)模型注注1 1： 表示單位鋼管從 運(yùn)到 的最小費(fèi)用（含訂購費(fèi)用） ijciSjB注注2 2：適合第三問，只是 n

14、=5903.目標(biāo)變量目標(biāo)變量 ：總費(fèi)用總費(fèi)用=訂購費(fèi)用訂購費(fèi)用+運(yùn)輸費(fèi)用運(yùn)輸費(fèi)用總費(fèi)用總費(fèi)用 WTPQW運(yùn)輸費(fèi)用運(yùn)輸費(fèi)用=從鋼廠到管道關(guān)節(jié)點(diǎn)從鋼廠到管道關(guān)節(jié)點(diǎn)1521,AAA的的運(yùn)輸費(fèi)用運(yùn)輸費(fèi)用 P +從管道的關(guān)節(jié)點(diǎn)到鋪設(shè)點(diǎn)的運(yùn)輸費(fèi)用從管道的關(guān)節(jié)點(diǎn)到鋪設(shè)點(diǎn)的運(yùn)輸費(fèi)用 T即：即：鋼管的訂購計(jì)劃鋼管的訂購計(jì)劃： 每個(gè)鋼廠的定貨數(shù)量。每個(gè)鋼廠的定貨數(shù)量。鋼管的運(yùn)輸鋼管的運(yùn)輸方案：方案： 從每個(gè)鋼廠運(yùn)送到每個(gè)管道從每個(gè)鋼廠運(yùn)送到每個(gè)管道區(qū)間的鋼管量。區(qū)間的鋼管量。1S2S3S4S5S6S7S1A2A3A4A5A6A7A8A9A10A11A12A13A14A15A11x12x13x14x15x16x17

15、x18x19x10, 1x11, 1x12, 1x13, 1x14, 1x15, 1xiSjAijx1）基本假設(shè)：要鋪設(shè)的管道側(cè)有公路，可運(yùn)送所需鋼管；鋼管在運(yùn)輸中由鐵路運(yùn)轉(zhuǎn)為公路運(yùn)時(shí)不計(jì)換車費(fèi)；所需鋼管均由 鋼廠提供；）（7 , 2 , 1i在具體鋪設(shè)每一公里時(shí)，只把鋼管運(yùn)輸?shù)矫恳还镩_始的地方，沿運(yùn)輸方向向前鋪設(shè)的費(fèi)用不予考慮。2 2、模型假設(shè)與符號(hào)說明模型假設(shè)與符號(hào)說明iS：1單位鋼管從鋼廠 運(yùn)到 的最小費(fèi)用（單位：萬元）；2）符號(hào)說明：）（15,2 , 1;7 ,2 , 1jiis：從 到 之間的距離（單位：千米）；jA1jAipdeijcjb：鋼廠 的最大生產(chǎn)能力；：鋼廠 的出廠鋼管

16、單位價(jià)格（單位：萬元）；：公路上1單位鋼管的每公里運(yùn)費(fèi)（d=0.1萬元）；：鐵路上1單位鋼管的運(yùn)費(fèi)（分段函數(shù)見表一）；iSiSiSjA ：運(yùn)到 地的鋼管向左鋪設(shè)的數(shù)目；jAjAjyjz 鋼廠 提供鋼管iS 鋼廠 不提供鋼管iSW ： 所求鋼管訂購、運(yùn)輸?shù)目傎M(fèi)用（單位：萬元）。：運(yùn)到 地的鋼管向右鋪設(shè)的數(shù)目；01it：鋼廠 運(yùn)到 的鋼管數(shù)；iSjAijx 目標(biāo)函數(shù)是總費(fèi)用 ：鋼管出廠總價(jià) ,運(yùn)WQPTWQPT=+，3 3、模型的建立模型的建立iijijpxQ7115171151ijijijxcP(1)(1)決策變量決策變量jyjz01itijx)15, 1()7 , 1(ji(2)(2)目標(biāo)函數(shù)

17、目標(biāo)函數(shù)輸費(fèi) ,及鋪設(shè)費(fèi) ,即 其中：1 1單位鋼管從鋼廠單位鋼管從鋼廠 運(yùn)到運(yùn)到 的最小費(fèi)用（單位：萬元）的最小費(fèi)用（單位：萬元）ijciSjA從 開始向左右兩個(gè)方向鋪設(shè)，鋪設(shè)的數(shù)量分別用 與 來表示。jAjyjz鋪設(shè)費(fèi) 可以如下確定：T單位長鋼管的費(fèi)用為d2)1 (21jjjyydyddd1512)1 (2)1 (jjjjjzzyydT故（3 3）約）約束條件束條件()01itor=jAjA1jA與的鋼管：1jjjzyb+= 生產(chǎn)能力的限制:)7 , 1(500151itsxtiijiji 運(yùn)到 的鋼管用完： )15, 2 , 1(71jzyxjjiij )14, 2 , 1(j 變量非負(fù)

18、性限制：)15, 1()7 , 1(0, 0, 0jizyxjjij 端點(diǎn)限制：01y015zs.t.15171151711512)1 (2)1 (minjjjjjijijijijijizzyydxcxpW()01itor=)7 , 1(500151itsxtiijiji)15, 2 , 1(71jzyxjjiij1jjjzyb+=)14, 2 , 1(j)15, 1()7 , 1(0, 0, 0jizyxjjij(4)(4)數(shù)學(xué)模型數(shù)學(xué)模型01y015ziSjAijc其中每一 表示單位鋼管從 到 的最小運(yùn)輸費(fèi)用，因而，求解 實(shí)際上是一個(gè)求最短“最短路經(jīng)”問題是圖論中最基本的問題之一。4 4、

19、模型的求解模型的求解關(guān)鍵1 求出目標(biāo)函數(shù)中的系數(shù) ijc關(guān)鍵2 確定約束條件中的 it 157ijcijc路徑的問題?！白疃搪方?jīng)”問題的標(biāo)準(zhǔn)算法-弗洛伊德算法。A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7圖一其中 表示從 到 的最短路程，若不能相連，求出鐵路和

20、公路的最短路徑矩陣ijaiAjA用 表示。運(yùn)用Floyd算法，得出局部最短路徑矩陣。39393939)(ijaA鐵路和公路自身分別構(gòu)成權(quán)矩陣，記為 和 。ija1A2A鐵路和公路的最短路徑矩陣的統(tǒng)一對(duì)公路，將 為公路局部最小運(yùn)費(fèi)矩陣。221.0AA對(duì)鐵路，用鐵路的費(fèi)用 進(jìn)行轉(zhuǎn)換，得局部鐵路e最小運(yùn)費(fèi)矩陣 。2A令()12min,AAA=jA對(duì)得到的A,再使用一次Floyd算法，得到全局的最短每兩點(diǎn)間最小運(yùn)費(fèi)矩陣，從中抽取出 到 之間的子矩陣即為所需的 。is求最小費(fèi)用矩陣157)(ijcC最小費(fèi)用矩陣12345678910111213141511707160314029863802053121

21、264292096010601212128014202215720531902171611109558607121142142014601560171217801920323072203200218161210105596086248282086096011121180132042607250323522166156014051310116284262051061076283097052557245322522066146013051210111279257033051071273087062657255323522166156014051310121284262051045026211028

22、072757265324522266166015051410131299276066056038226020注：表中的數(shù)據(jù)乘以注：表中的數(shù)據(jù)乘以0.10.1為對(duì)應(yīng)的最小費(fèi)用矩陣的元素。為對(duì)應(yīng)的最小費(fèi)用矩陣的元素。157)(ijcC最小費(fèi)用矩陣12345678910111213141511707160314029863802053121264292096010601212128014202215720531902171611109558607121142142014601560171217801920323072203200218161210105596086248282086096011121

23、180132042607250323522166156014051310116284262051061076283097052557245322522066146013051210111279257033051071273087062657255323522166156014051310121284262051045026211028072757265324522266166015051410131299276066056038226020注：表中的數(shù)據(jù)乘以0.1為對(duì)應(yīng)的最小費(fèi)用矩陣的元素。157)(ijcC()01itor=)7 , 1(500151itsxtiijiji)7 , 1(015

24、1isxijij模型就轉(zhuǎn)化為典型的二次規(guī)劃問題。 如果其最優(yōu)解符合原有的約束條件，則便是原問題的最優(yōu)解。 如果存在 i 使 那么)500, 0(151jijx針對(duì)這些 i 分兩種情況5000151jijijxorx找出其中的最優(yōu)的結(jié)果。s.t.15171151711512)1 (2)1 (minjjjjjijijijijijizzyydxcxpW)7 , 1(0151isxijij)15, 2 , 1(71jzyxjjiij1jjjzyb+=)14, 2 , 1(j)15, 1()7 , 1(0, 0, 0jizyxjjij根據(jù)二次規(guī)劃軟件求解模型或者運(yùn)用數(shù)學(xué)軟件Lingo5.0,編程求解01

25、y015z將 從供應(yīng)商中除去，再將第7家工廠的供貨量最優(yōu)解中500, 015174jjjxx4S改為0以及不小于500兩種情況重做。相比之下，取0的情況總費(fèi)用較小，從而也把 刪除。7S鋼管的訂購計(jì)劃鋼管的訂購計(jì)劃：1234567供貨量800800100001366120501234567供貨量8008001000010151556084.127W億元億元5 5、結(jié)果表示結(jié)果表示鋼管的運(yùn)輸鋼管的運(yùn)輸方案：方案：33420026617932130018714966460035141535186333621165合計(jì)合計(jì)1795080108320026630066435141586333621165

26、1S2S3S5S1A2A3A4A5A6A7A8A9A10A11A12A13A14A15A0104226010741851901255053212707519928616507528209157617515930145111343350iziy1A2A3A4A5A6A7A8A9A10A11A12A13A14A15A6S 1）確定哪個(gè)鋼廠的銷價(jià)的變化對(duì)購運(yùn)計(jì)劃和總費(fèi)用的影響最大6 6、靈敏度分析靈敏度分析15171151711512)1 (2)1 (minjjjjjijijijijijizzyydxcxpWs.t.)7 , 1(0151isxijij)15, 2 , 1(71jzyxjjiij1j

27、jjzyb+=)14, 2 , 1(j)15, 1()7 , 1(0, 0, 0jizyxjjij01y015z 假設(shè)該鋼廠的銷價(jià)變化在 萬元以內(nèi)，0010ip1234567160155155160155150160176170.5170.5176170.5165176154139.5139.5154139.5135154iip00iipp WW84.127W結(jié)論： 或 的銷價(jià)的變化影響最大。5S6S鋼管的訂購計(jì)劃鋼管的訂購計(jì)劃：1234567供貨量800800100001366120501234567供貨量8008001000010151556084.127W億元億元 2）確定哪個(gè)鋼廠的生產(chǎn)

28、上限的變化對(duì)購運(yùn)計(jì)劃和總費(fèi)用的影響最大 在變化 的情況下目標(biāo)函數(shù)減小量及減小的比率1%8720.0683280.0253100.02400002%17440.1366560.0516200.04800004%34880.27213120.10212400.09600006%52320.40819680.15318600.14500008%69760.54426240.20424800.193000010%87200.68532800.25631000.2420000結(jié)論： 的生產(chǎn)上限的變化影響最大。1Sisss1s2s3s5s6sWWW最小費(fèi)用矩陣12345678910111213141511

29、707160314029863802053121264292096010601212128014202215720531902171611109558607121142142014601560171217801920323072203200218161210105596086248282086096011121180132042607250323522166156014051310116284262051061076283097052557245322522066146013051210111279257033051071273087062657255323522166156014051310121284262051045026211028072757265324522266166015051410131