數(shù)學(xué)建模 B題市公開課一等獎(jiǎng)省名師優(yōu)質(zhì)課賽課一等獎(jiǎng)?wù)n件

網(wǎng)易杯全國(guó)大學(xué)生

數(shù)學(xué)建模競(jìng)賽題目B題鋼管訂購和運(yùn)輸西北大學(xué)數(shù)學(xué)系竇霽虹信息（語言、數(shù)據(jù)）問題（第一問，…,）問題所屬類型做題思緒和關(guān)鍵點(diǎn)結(jié)果表示形式讀題要鋪設(shè)一條輸送天然氣主管道,如圖一所表示。經(jīng)篩選后能夠生產(chǎn)這種主管道鋼管鋼廠有。圖中粗線表示鐵路，單細(xì)線表示公路，雙細(xì)線表示要鋪設(shè)管道（假設(shè)沿管道或者原來有公路，或者和管道旁阿拉伯?dāng)?shù)字表示里程（單位：Km）?；蛘呓ㄓ惺┕す?，圓圈表示火車站，每段鐵路、公路為方便計(jì)，1Km主管道鋼管稱為1單位鋼管。A1

3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 3060 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A2

A3

A4

A5

A6

A7

A8

A9

A10

A11

A12

A13

A14

A15

S1

S2 S3 S4 S5 S6 S7 圖一 一個(gè)鋼廠假如負(fù)擔(dān)制造這種鋼管，最少需要生產(chǎn)500個(gè)單位。鋼廠在指定時(shí)限內(nèi)能生產(chǎn)該鋼管最大數(shù)量為個(gè)單位，鋼管出廠銷價(jià)1單位鋼管為萬元，以下表：1234567800800100030001601551551601551501601單位鋼管鐵路運(yùn)價(jià)以下表：里程(km)≤300301～350351～400401～450451～500運(yùn)價(jià)（萬元）2023262932里程(km)501～600601～700701～800801～900901～1000運(yùn)價(jià)(萬元)37445055601000km以上每增加1至100km運(yùn)價(jià)增加5萬元。公路運(yùn)輸費(fèi)用為1單位鋼管每公里0.1萬元（不足整公里部分按整公里計(jì)算）。鋼管可由鐵路、公路運(yùn)往鋪設(shè)地點(diǎn)（不只運(yùn)到點(diǎn)，而是管道全線）。問題：（1）請(qǐng)制訂一個(gè)主管道鋼管訂購和運(yùn)輸計(jì)劃，使總費(fèi)用最?。ńo出總費(fèi)用)。（2）請(qǐng)就（1）模型分析：哪個(gè)鋼廠鋼管銷價(jià)改變對(duì)購運(yùn)計(jì)劃和總費(fèi)用影響最大？哪個(gè)鋼廠鋼管產(chǎn)量上限改變對(duì)購運(yùn)計(jì)劃和總費(fèi)用影響最大？并給出對(duì)應(yīng)數(shù)字結(jié)果。（3）假如要鋪設(shè)管道不是一條線，而是一個(gè)樹形圖，鐵路、公路和管道組成網(wǎng)絡(luò)，請(qǐng)就這種更普通情形給出一個(gè)處理方法，并對(duì)圖二按（1）要求給出模型和結(jié)果。A1

3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 3060 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A2

A3

A4

A5

A6

A7

A8

A9

A10

A11

A12

A13

A14

A15

S1

S2 S3 S4 S5 S6 S7 圖一 A1

3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 3060 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A19 130 190 260 100 A2

A3

A4

A5

A6

A7

A8

A9

A10

A11

A12

A13

A14

A15

S1

S2 S3 S4 S5 S6S7 A16 A17 A18 A20 (A21) 圖二 問題所屬類型做題思緒和關(guān)鍵點(diǎn)結(jié)果表示形式優(yōu)化模型1、問題分析優(yōu)化問題1）優(yōu)化模型數(shù)學(xué)描述求函數(shù)在約束條件下最大值或最小值，其中和設(shè)計(jì)變量（決議變量）目標(biāo)函數(shù)可行域“受約束于”之意線性規(guī)劃（LP）

目標(biāo)函數(shù)和全部約束條件都是設(shè)計(jì)變量線性函數(shù)。西北大學(xué)數(shù)學(xué)系二次規(guī)劃問題目標(biāo)函數(shù)為二次函數(shù)，約束條件為線性約束2）建立優(yōu)化模型普通步驟1.確定設(shè)計(jì)變量和目標(biāo)變量；2.確定目標(biāo)函數(shù)表示式；3.尋找約束條件。設(shè)有某物資從m個(gè)發(fā)點(diǎn)輸送到n個(gè)收點(diǎn)

其中每個(gè)發(fā)點(diǎn)發(fā)出量分別為每個(gè)收點(diǎn)輸入量分別為，而且滿足從發(fā)點(diǎn)A到收點(diǎn)B距離（或單位運(yùn)費(fèi)）是已知，設(shè)為。問題：尋求一個(gè)調(diào)運(yùn)方案，使總運(yùn)輸費(fèi)用到達(dá)最小。例運(yùn)輸問題B1B2..….BnA1A2Ama1a2amb1b2..….bn…..…..x11

x12…...x1nx21

x22

…...

x2nxm1

xm2

…...

xmn收點(diǎn)發(fā)點(diǎn)一個(gè)調(diào)運(yùn)方案主要由一組從發(fā)點(diǎn)到收點(diǎn)輸送量來描述?？傎M(fèi)用A1總費(fèi)用A2總費(fèi)用s.t.數(shù)學(xué)模型求解：?jiǎn)渭冃畏椒?。問題：（1）請(qǐng)制訂一個(gè)主管道鋼管訂購和運(yùn)輸計(jì)劃，使總費(fèi)用最小（給出總費(fèi)用)。（2）請(qǐng)就（1）模型分析：哪個(gè)鋼廠鋼管銷價(jià)改變對(duì)購運(yùn)計(jì)劃和總費(fèi)用影響最大？哪個(gè)鋼廠鋼管產(chǎn)量上限改變對(duì)購運(yùn)計(jì)劃和總費(fèi)用影響最大？并給出對(duì)應(yīng)數(shù)字結(jié)果。（3）假如要鋪設(shè)管道不是一條線，而是一個(gè)樹形圖，鐵路、公路和管道組成網(wǎng)絡(luò)，請(qǐng)就這種更普通情形給出一個(gè)處理方法，并對(duì)圖二按（1）要求給出模型和結(jié)果。B1B2..….BnS1S2S7a1a2amb1b2..….bn…..…..x11

x12…...x1nx21

x22

…...

x2nxm1

xm2

…...

xmn收點(diǎn)發(fā)點(diǎn)訂購與運(yùn)輸方案Si1234567供貨量？？？？？？？n=5171s.t.數(shù)學(xué)模型注1：表示單位鋼管從運(yùn)到最小費(fèi)用（含訂購費(fèi)用）注2：適合第三問，只是n=5903.目標(biāo)變量：總費(fèi)用=訂購費(fèi)用+運(yùn)輸費(fèi)用總費(fèi)用W運(yùn)輸費(fèi)用=從鋼廠到管道關(guān)節(jié)點(diǎn)運(yùn)輸費(fèi)用P+從管道關(guān)節(jié)點(diǎn)到鋪設(shè)點(diǎn)運(yùn)輸費(fèi)用T即：鋼管訂購計(jì)劃：每個(gè)鋼廠定貨數(shù)量。鋼管運(yùn)輸方案：從每個(gè)鋼廠運(yùn)輸?shù)矫總€(gè)管道區(qū)間鋼管量。1）基本假設(shè)：要鋪設(shè)管道側(cè)有公路，可運(yùn)輸所需鋼管；鋼管在運(yùn)輸中由鐵路運(yùn)轉(zhuǎn)為公路運(yùn)時(shí)不計(jì)換車費(fèi)；所需鋼管均由鋼廠提供；在詳細(xì)鋪設(shè)每一公里時(shí)，只把鋼管運(yùn)輸?shù)矫恳还镩_始地方，沿運(yùn)輸方向向前鋪設(shè)費(fèi)用不予考慮。2、模型假設(shè)與符號(hào)說明：1單位鋼管從鋼廠運(yùn)到最小費(fèi)用（單位：萬元）；2）符號(hào)說明：：從到之間距離（單位：千米）；：鋼廠最大生產(chǎn)能力；：鋼廠出廠鋼管單位價(jià)格（單位：萬元）；：公路上1單位鋼管每公里運(yùn)費(fèi)（d=0.1萬元）；：鐵路上1單位鋼管運(yùn)費(fèi)（分段函數(shù)見表一）；：運(yùn)到地鋼管向左鋪設(shè)數(shù)目；鋼廠提供鋼管鋼廠不提供鋼管：所求鋼管訂購、運(yùn)輸總費(fèi)用（單位：萬元）。：運(yùn)到地鋼管向右鋪設(shè)數(shù)目；：鋼廠運(yùn)到鋼管數(shù)；目標(biāo)函數(shù)是總費(fèi)用：鋼管出廠總價(jià),運(yùn)，3、模型建立(1)決議變量(2)目標(biāo)函數(shù)輸費(fèi),及鋪設(shè)費(fèi),即其中：1單位鋼管從鋼廠運(yùn)到最小費(fèi)用（單位：萬元）從開始向左右兩個(gè)方向鋪設(shè)，鋪設(shè)數(shù)量分別用與來表示。鋪設(shè)費(fèi)能夠以下確定：?jiǎn)挝婚L(zhǎng)鋼管費(fèi)用為故（3）約束條件與鋼管：生產(chǎn)能力限制:運(yùn)到鋼管用完：

⑤變量非負(fù)性限制：端點(diǎn)限制：s.t.(4)數(shù)學(xué)模型其中每一表示單位鋼管從到最小運(yùn)輸費(fèi)用，因而，求解實(shí)際上是一個(gè)求最短“最短路經(jīng)”問題是圖論中最基本問題之一。4、模型求解關(guān)鍵1求出目標(biāo)函數(shù)中系數(shù)關(guān)鍵2確定約束條件中路徑問題。“最短路經(jīng)”問題標(biāo)準(zhǔn)算法----弗洛伊德算法。A1

3 2 5 80 10 10 31 20 12 42 70 10 88 10 70 62 70 30 20 20 30 450 104 301 750 606 194 205 201 680 480 300 220 210 420 500 600 3060 195 202 720 690 520 170 690 462 160 320 160 110 290 1150 1100 1200 A2

A3

A4

A5

A6

A7

A8

A9

A10

A11

A12

A13

A14

A15

S1

S2 S3 S4 S5 S6 S7 圖一 其中表示從到最短旅程，若不能相連，求出鐵路和公路最短路徑矩陣用表示。利用Floyd算法，得出局部最短路徑矩陣。鐵路和公路本身分別組成權(quán)矩陣，記為和。鐵路和公路最短路徑矩陣統(tǒng)一對(duì)公路，將為公路局部最小運(yùn)費(fèi)矩陣。對(duì)鐵路，用鐵路費(fèi)用進(jìn)行轉(zhuǎn)換，得局部鐵路最小運(yùn)費(fèi)矩陣。令對(duì)得到A,再使用一次Floyd算法，得到全局最短每?jī)牲c(diǎn)間最小運(yùn)費(fèi)矩陣，從中抽取出到之間子矩陣即為所需。求最小費(fèi)用矩陣最小費(fèi)用矩陣1234567891011121314151170716031402986380205312126429209601060121212801420221572053190217161110955860712114214201460156017121780192032307220318161210105596086248282086096011121180132042607250323522166156014051310116284262051061076283097052557245322522066146013051210111279257033051071273087062657255323522166156014051310121284262051045026211028072757265324522266166015051410131299276066056038226020注：表中數(shù)據(jù)乘以0.1為對(duì)應(yīng)最小費(fèi)用矩陣元素。最小費(fèi)用矩陣1234567891011121314151170716031402986380205312126429209601060121212801420221572053190217161110955860712114214201460156017121780192032307220318161210105596086248282086096011121180132042607250323522166156014051310116284262051061076283097052557245322522066146013051210111279257033051071273087062657255323522166156014051310121284262051045026211028072757265324522266166015051410131299276066056038226020注：表中數(shù)據(jù)乘以0.1為對(duì)應(yīng)最小費(fèi)用矩陣元素。模型就轉(zhuǎn)化為經(jīng)典二次規(guī)劃問題。假如其最優(yōu)解符合原有約束條件，則便是原問題最優(yōu)解。假如存在i使那么針對(duì)這些i分兩種情況找出其中最優(yōu)結(jié)果。s.t.依據(jù)二次規(guī)劃軟件求解模型或者利用數(shù)學(xué)軟件Lingo5.0,編程求解將從供給商中除去，再將第7家工廠供貨量最優(yōu)解中改為0以及大于500兩種情況重做。相比之下，取0情況總費(fèi)用較小，從而也把刪除。鋼管訂購計(jì)劃：1234567供貨量800800100001366120501234567供貨量80080010000101515560億元5、結(jié)果表示鋼管運(yùn)輸方案：33420026617932130018714966460035141535186333621165累計(jì)17950801083200266300664351415863336211650104226010741851901255053212707519928616507528209157617515930145111343350

1）確定哪個(gè)鋼廠銷價(jià)改變對(duì)購運(yùn)計(jì)劃和總費(fèi)用影響最大6、靈敏度分析s.t.假設(shè)該鋼廠銷價(jià)改變?cè)谌f元以內(nèi)，1234567160155155160155150160176170.5170.5176170.5165176154139.5139.5154139.5135154結(jié)論：或銷價(jià)改變影響最大。鋼管訂購計(jì)劃：1234567供貨量800800100001366120501234567供貨量80080010000101515560億元

2）確定哪個(gè)鋼廠生產(chǎn)上限改變對(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)上限改變影響最大。最小費(fèi)用矩陣123456789101112131415117071603140298638020531212642920960106012121280142022157205319021716111095586071211421420146015601712178019203230722031816121010559608624828208609601112118013204260725032352216615601405131011628426205106107628309705255724532252206614601305121011127925703305107127308706265725532