《數(shù)學建模 2000B題》由會員分享，可在線閱讀，更多相關《數(shù)學建模 2000B題（52頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、2000網(wǎng)易杯全國大學生 數(shù)學建模競賽題目B題 鋼管訂購和運輸 信 息 語 言 、 數(shù) 據(jù) 問 題 第 一 問 ， , 問 題所 屬 類 型 做 題思 路 和 關 鍵 點 結 果表 示 形 式讀 題 要鋪設一條 輸送天然氣的主管道,如圖一所示。經(jīng)篩選后可以生產(chǎn)這種主管道鋼管的鋼廠有。圖中粗線表示鐵路，單細線表示公路，雙細線表示要鋪設的管道假設沿管道或者原來有公路，或者和管道旁的阿拉伯數(shù)字表示里程單位：Km?；蛘呓ㄓ惺┕す?)，圓圈表示火車站，每段鐵路、公路1521 AAA 721 , SSS 為方便計，1 Km主管道鋼管稱為1單位鋼管。 A1 3 2 580 10 10 31 20 12 4

2、2 70 1088 1070 62 70 30 20 20 30 450104 301750 606 194 205 201 680 480 300 220 210 420 500600 3060 195 202 720 690 520170690 462160 320 160 110 2901150 1100 1200 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15S1S2 S3 S4 S5 S6 S7圖一 一個鋼廠如果承擔制造這種鋼管，至少需要生產(chǎn)500個單位。鋼廠在指定期限內(nèi)能生產(chǎn)該鋼管的最大數(shù)量為個單位，鋼管出廠銷價1單位鋼管為萬元，如下

3、表：1 2 3 4 5 6 7800 800 1000 2000 2000 2000 3000160 155 155 160 155 150 160iip iS isip is 1單位鋼管的鐵路運價如下表：里 程 (km) 300 301 350 351 400 401 450 451 500運 價 （ 萬 元 ） 20 23 26 29 32里 程 (km) 501 600 601 700 701 800 801 900 901 1000運 價 (萬 元 ) 37 44 50 55 60 1000km以上每增加1至100km運價增加5萬元。 公路運輸費用為1單位鋼管每公里萬元缺乏整公里局部按

4、整公里計算。鋼管可由鐵路、公路運往鋪設地點不只運到點，而是管道全線。 1521 , AAA 問題： 1請制定一個主管道鋼管的訂購和運輸方案，使總費用最小給出總費用)。2請就1的模型分析：哪個鋼廠鋼管的銷價的變化對購運方案和總費用影響最大？哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運方案和總費用的影響最大？并給出相應的數(shù)字結果。3如果要鋪設的管道不是一條線，而是一個樹形圖， 鐵路、公路和管道構成網(wǎng)絡，請就這種更一般的情形給出一種解決方法，并對圖二按1的要求給出模型和結果。 A13 2 580 10 10 31 20 12 42 70 1088 1070 62 70 30 20 2030450104 30

5、1750 606194 205 201 680480 300 220 210 420 500600 3060 195 202 720690 520170690 462160 320 160 1102901150 1100 1200A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15S1S2 S3 S4 S5 S6 S7圖一 A13 2 580 10 10 31 20 12 42 70 1088 1070 62 70 30 20 2030450104 301750 606194 205 201 680 480 300 220 210420 500600

6、3060 195 202 720690 520170690 462160 320 160 110 2901150 1100 1200 A19130 190 260 100A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15S1S2 S3 S4 S5 S6 S7A16 A17 A18 A20 (A21)圖二 問 題所 屬 類 型 做 題思 路 和 關 鍵 點 結 果表 示 形 式 優(yōu) 化 模 型 1、問題的分析優(yōu)化問題1 優(yōu) 化 模 型 的 數(shù) 學 描 述 .,.,)( mih i 210 x ),.,( nxxxx 321x求 函 數(shù) )(xfu在 約

7、 束 條 件下 的 最 大 值 或 最 小 值 ， 其 中 .,.,),)()( pigg ii 2100 xx和 設 計 變 量 決 策 變 量 目 標 函 數(shù)x)(xf x 可 行 域 tosubjectts . “受 約 束 于 之 意Iibgts ii ,)( . . x Jjfor j )(max) min( xx .,., .,.,.min nix nibxats xcuink ikikni ii 210 211 1 線性規(guī)劃LP 目標函數(shù)和所有的約束條件都是設計變量的線性函數(shù)。 二次規(guī)劃問題 .,.,. .,.,. )(min ,nix nibxats xxbxcxfuinj i

8、jij nji jiijni ii210 21 211 11目 標 函 數(shù) 為 二 次 函 數(shù) ， 約 束 條 件 為 線 性 約 束 2 建 立 優(yōu) 化 模 型 的 一 般 步 驟1.確 定 設 計 變 量 和 目 標 變 量 ；2.確 定 目 標 函 數(shù) 的 表 達 式 ；3.尋 找 約 束 條 件 。 設 有 某 物 資 從 m個 發(fā) 點 輸 送 到 n個 收 點 其 中 每 個 發(fā) 點 發(fā) 出 量 分 別 為 每 個收點 輸 入 量 分 別 為 ， 并 且 滿 足從 發(fā) 點 A到 收 點 B的 距 離 或 單 位 運 費 是 的 ， 設 為 。問 題 ： 尋 求 一 個 調(diào) 運 方 案

9、 ， 使 總 運 輸 費 用 到 達 最 小 。 maaa ,., 21nbbb ,., 21 mi n ij ji ba1),.,.,( njmic ij 2121 例 運 輸 問 題 mAAA , 21 nBBB , 21 B1 B2 . BnA1A2Am a1a2am b 1 b2 . bn. .x11 x12 . x1nx21 x22 . x2nxm1 xm2 . xmn 收點發(fā)點 一 個 調(diào) 運 方 案 主 要 由 一 組 從 發(fā) 點 到 收 點 的 輸送 量 來 描 述 。 iA jBijx 總 的 費 用 nj jjnnj xCxCxCxC BA 1 1111121211111

10、. nj jjnnj xCxCxCxC BA 1 2222222221212 . mi nj ijijxCf 1 1A1的 總 費 用A2的 總 費 用 s.t. njmix njbx miaxijmi jijnj iij ,.,., .,., .,., 21210 212111 mi nj ijijxCf 1 1min數(shù) 學 模 型求 解 ： 單 純 形 方 法 。 mi n ij ji ba1 問題： 1請制定一個主管道鋼管的訂購和運輸方案，使總費用最小給出總費用)。2請就1的模型分析：哪個鋼廠鋼管的銷價的變化對購運方案和總費用影響最大？哪個鋼廠鋼管的產(chǎn)量的上限的變化對購運方案和總費用的影

11、響最大？并給出相應的數(shù)字結果。3如果要鋪設的管道不是一條線，而是一個樹形圖， 鐵路、公路和管道構成網(wǎng)絡，請就這種更一般的情形給出一種解決方法，并對圖二按1的要求給出模型和結果。 B1 B2 . BnS1S2S7 a1a2am b 1 b2 . bn. .x11 x12 . x1nx21 x22 . x2nxm1 xm2 . xmn 收點發(fā)點 訂 購 與 運 輸 方 案 ijxSi 1 2 3 4 5 6 7供 貨 量 ？ ？ ？ ？ ？ ？ ？n=5171 s.t. 71 51711min i j ijij xcW )7,1(,500051711 isx ij ij )5171,2,1(171

12、 jxi ij )5171,1()7,1(10 jiorx ij 數(shù)學模型注1： 表示單位鋼管從 運到 的最小費用含訂購費用 ijc iS jB注2：適合第三問，只是 n=5903. 目 標 變 量 ：總 費 用 =訂 購 費 用 +運 輸 費 用總 費 用 W TPQW 運 輸 費 用 =從 鋼 廠 到 管 道 關 節(jié) 點 1521 , AAA 的運 輸 費 用 P +從 管 道 的 關 節(jié) 點 到 鋪 設 點 的 運 輸 費 用 T即 ： 鋼管的訂購方案：每個鋼廠的定貨數(shù)量。鋼管的運輸方案：從每個鋼廠運送到每個管道區(qū)間的鋼管量。1S 2S3S4S5S6S 7S 1A 2A 3A 4A 5A

13、 6A 7A 8A 9A 10A 11A 12A 13A 14A 15A11x 12x 13x 14x 15x 16x 17x 18x 19x 10,1x 11,1x 12,1x 13,1x 14,1x 15,1xiS jAijx 1根本假設：要鋪設的管道側(cè)有公路，可運送所需鋼管；鋼管在運輸中由鐵路運轉(zhuǎn)為公路運時不計換車費；所需鋼管均由 鋼廠提供；）（ 7,2,1 i在具體鋪設每一公里時，只把鋼管運輸?shù)矫恳还镩_始的地方，沿運輸方向向前鋪設的費用不予考慮。2、模型假設與符號說明iS ：1單位鋼管從鋼廠 運到 的最小費用單位：萬元；2符號說明：）（ 15,2,1;7,2,1 jiis：從 到 之

14、間的距離單位：千米；jA 1jAipdeijc jb：鋼廠 的最大生產(chǎn)能力；：鋼廠 的出廠鋼管單位價格單位：萬元；：公路上1單位鋼管的每公里運費萬元；：鐵路上1單位鋼管的運費分段函數(shù)見表一；iSiS iS jA ：運到 地的鋼管向左鋪設的數(shù)目；jAjAjy jz 鋼廠 提供鋼管iS 鋼廠 不提供鋼管iSW ： 所求鋼管訂購、運輸?shù)目傎M用單位：萬元。：運到 地的鋼管向右鋪設的數(shù)目； 01it：鋼廠 運到 的鋼管數(shù)；iS jAijx 目標函數(shù)是總費用 ：鋼管出廠總價 ,運W QP T W Q P T= + +，3、模型的建立ii j ij pxQ 71 151 71 151i j ijij xcP

15、(1)決 策 變 量 jy jz 01it ijx )15,1()7,1( ji(2)目 標 函 數(shù)輸費 ,及鋪設費 ,即 其中：1單位鋼管從鋼廠 運到 的最小費用單位：萬元ijc iS jA 從 開始向左右兩個方向鋪設，鋪設的數(shù)量分別用 與 來表示。jA jy jz鋪設費 可以如下確定：T單位長鋼管的費用為d2 )1(21 jjj yydyddd 151 2 )1(2 )1(j jjjj zzyydT故 3 約 束 條 件 ( )0 1it or=jAjA 1jA與的鋼管：1j j jz y b+ = 生產(chǎn)能力的限制: )7,1(500 151 itsxt iij iji 運到 的鋼管用完：

16、 )15,2,1(7 1 jzyx jji ij )14,2,1( j 變量非負性限制：)15,1()7,1(0,0,0 jizyx jjij 端點限制：01 y 015 z s.t. 15171 15171 151 2 )1(2 )1(min j jjjji j ijiji j iji zzyydxcxpW ( )0 1it or=)7,1(500 151 itsxt iij iji )15,2,1(71 jzyx jji ij 1j j jz y b+ = )14,2,1( j )15,1()7,1(0,0,0 jizyx jjij (4)數(shù) 學 模 型 01 y 015 z iS jAi

17、jc其中每一 表示單位鋼管從 到 的最小運輸費用，因而，求解 實際上是一個求最短“最短路經(jīng)問題是圖論中最根本的問題之一。4、模型的求解關鍵1 求出目標函數(shù)中的系數(shù) ijc關鍵2 確定約束條件中的 it 157ijc ijc路徑的問題。“最短路經(jīng)問題的標準算法-弗洛伊德算法。 A1 3 2 580 10 10 31 20 12 42 70 1088 1070 62 70 30 20 20 30 450104 301 750 606 194 205 201 680 480 300 220 210 420 500600 3060 195 202 720 690 520170690 462160 32

18、0 160 110 2901150 1100 1200 A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15S1S2 S3 S4 S5 S6 S7圖一 其中 表示從 到 的最短路程，假設不能相連，求出鐵路和公路的最短路徑矩陣ija iA jA用 表示。運用Floyd算法，得出局部最短路徑矩陣。39393939 )( ijaA鐵路和公路自身分別構成權矩陣，記為 和 。ija 1A 2A鐵路和公路的最短路徑矩陣的統(tǒng)一對公路，將 為公路局部最小運費矩陣。 221.0 AA 對鐵路，用鐵路的費用 進行轉(zhuǎn)換，得局部鐵路e最小運費矩陣 。2A令( )1 2min

19、,A A A= jA對得到的A,再使用一次Floyd算法，得到全局的最短每兩點間最小運費矩陣，從中抽取出 到 之間 的子矩陣即為所需的 。is求最小費用矩陣157)( ijcC 最小費用矩陣1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 1707 1603 1402 986 380 205 31 212 642 920 960 1060 1212 1280 14202 2157 2053 1902 1716 1110 955 860 712 1142 1420 1460 1560 1712 1780 19203 2307 2203 2002 1816 1210 105

20、5 960 862 482 820 860 960 1112 1180 13204 2607 2503 2352 2166 1560 1405 1310 1162 842 620 510 610 762 830 9705 2557 2453 2252 2066 1460 1305 1210 1112 792 570 330 510 712 730 8706 2657 2553 2352 2166 1560 1405 1310 1212 842 620 510 450 262 110 2807 2757 2653 2452 2266 1660 1505 1410 1312 992 760 660

21、 560 382 260 20注：表中的數(shù)據(jù)乘以為對應的最小費用矩陣的元素。157)( ijcC 最小費用矩陣1 2 3 4 5 6 7 8 9 10 11 12 13 14 151 1707 1603 1402 986 380 205 31 212 642 920 960 1060 1212 1280 14202 2157 2053 1902 1716 1110 955 860 712 1142 1420 1460 1560 1712 1780 19203 2307 2203 2002 1816 1210 1055 960 862 482 820 860 960 1112 1180 1320

22、4 2607 2503 2352 2166 1560 1405 1310 1162 842 620 510 610 762 830 9705 2557 2453 2252 2066 1460 1305 1210 1112 792 570 330 510 712 730 8706 2657 2553 2352 2166 1560 1405 1310 1212 842 620 510 450 262 110 2807 2757 2653 2452 2266 1660 1505 1410 1312 992 760 660 560 382 260 20注：表中的數(shù)據(jù)乘以為對應的最小費用矩陣的元素。 1

23、57)( ijcC ( )0 1it or=)7,1(500 151 itsxt iij iji )7,1(0 151 isx ij ij模型就轉(zhuǎn)化為典型的二次規(guī)劃問題。 如果其最優(yōu)解符合原有的約束條件，那么便是原問題的最優(yōu)解。 如果存在 i 使 那么)500,0( 151 j ijx針對這些 i 分兩種情況5000 151 j ijij xorx找出其中的最優(yōu)的結果。 s.t. 15171 15171 151 2 )1(2 )1(min j jjjji j ijiji j iji zzyydxcxpW )7,1(0 151 isx ij ij )15,2,1(71 jzyx jji ij 1

24、j j jz y b+ = )14,2,1( j )15,1()7,1(0,0,0 jizyx jjij 根據(jù)二次規(guī)劃軟件求解模型或者運用數(shù)學軟件Lingo5.0,編程求解 01 y 015 z 將 從供給商中除去，再將第7家工廠的供貨量最優(yōu)解中500,0 151 74 j jj xx4S改為0以及不小于500兩種情況重做。相比之下，取0的情況總費用較小，從而也把 刪除。7S 鋼管的訂購方案：1 2 3 4 5 6 7供 貨 量 800 800 1000 0 1366 1205 01 2 3 4 5 6 7供 貨 量 800 800 1000 0 1015 1556 084.127W億元5、結

25、果表示 鋼管的運輸方案：334 200 266179 321 300187 149 664600 351 415351 86 333 621 165合 計 179 508 0 1083 200 266 300 664 351 415 86 333 621 1651S2S3S5S 1A 2 A 3A 4A 5A 6A 7A 8A 9A 10A 11A 12A 13A 14A 15A 0 104 226 0 1074 185 190 125 505 321 270 75 199 286 1650 75 282 0 9 15 76 175 159 30 145 11 134 335 0iziy 1A

26、 2A 3A 4A 5A 6A 7A 8A 9A 10A 11A 12A 13A 14A 15A6S 1確定哪個鋼廠的銷價的變化對購運方案和總費用的影響最大6、靈敏度分析 15171 15171 151 2 )1(2 )1(min j jjjji j ijiji j iji zzyydxcxpWs.t. )7,1(0 151 isx ij ij )15,2,1( 71 jzyx jji ij 1j j jz y b+ = )14,2,1( j )15,1()7,1(0,0,0 jizyx jjij 01 y 015 z 假設該鋼廠的銷價變化在 萬元以內(nèi)，0010 ip1 2 3 4 5 6 7

27、160 155 155 160 155 150 160176 170.5 170.5 176 170.5 165 176154 139.5 139.5 154 139.5 135 154iip 00ii pp WW 84.127W結 論 ： 或 的 銷 價 的 變 化 影 響 最 大 。5S 6S 鋼管的訂購方案：1 2 3 4 5 6 7供 貨 量 800 800 1000 0 1366 1205 01 2 3 4 5 6 7供 貨 量 800 800 1000 0 1015 1556 084.127W億元 2確定哪個鋼廠的生產(chǎn)上限的變化對購運方案和總費用的影響最大 在變化 的情況下目標函數(shù)

28、減小量及減小的比率1% 8720.068 3280.025 3100.024 00 002% 17440.136 6560.051 6200.048 00 004% 34880.272 13120.102 12400.096 00 006% 52320.408 19680.153 18600.145 00 008% 69760.544 26240.204 24800.193 00 0010% 87200.685 32800.256 31000.242 00 00 結 論 ： 的 生 產(chǎn) 上限 的 變 化 影響 最 大 。1Sis ss 1s 2s 3s 5s 6sWWW 最小費用矩陣1 2 3

29、 4 5 6 7 8 9 10 11 12 13 14 151 1707 1603 1402 986 380 205 31 212 642 920 960 1060 1212 1280 14202 2157 2053 1902 1716 1110 955 860 712 1142 1420 1460 1560 1712 1780 19203 2307 2203 2002 1816 1210 1055 960 862 482 820 860 960 1112 1180 13204 2607 2503 2352 2166 1560 1405 1310 1162 842 620 510 610 76

30、2 830 9705 2557 2453 2252 2066 1460 1305 1210 1112 792 570 330 510 712 730 8706 2657 2553 2352 2166 1560 1405 1310 1212 842 620 510 450 262 110 2807 2757 2653 2452 2266 1660 1505 1410 1312 992 760 660 560 382 260 20注：表中的數(shù)據(jù)乘以為對應的最小費用矩陣的元素。157)( ijcC A1 3 2 580 10 10 31 20 12 42 70 1088 1070 62 70 30

31、20 2030450104 301 750 606 194 205 201 680 480 300 220 210 420 500600 3060 195 202 720690 520170690 462160 320 160 1102901150 1100 1200 A19130 190 260 100A2 A3 A4 A5 A6 A7 A8 A9 A10 A11 A12 A13 A14 A15S1S2 S3 S4 S5 S6 S7A16 A17 A18 A20 (A21)圖二 假設要鋪設的道路不是一條線，而是一個樹形圖，7、關于問題3 s.t. 21171 21171 211 2 )1(2

32、 )1(min j jjjji j ijiji j iji zzyydxcxpW ( )0 1it or=)7,1(500 211 itsxt iij iji )17,11,9,21,2,1(71 jjzyx jji ij 但1j j jz y b+ = )14,2,1( j數(shù)學模型 2 )1(2 )1(2 )1( 1717111199 mmmmmmd )17,11,9(7 1 jmzyx jjji ij 運用數(shù)學軟件編程求出：42169 ym 1301817 zy101711 mm 1901917 yz2602019 yz 1002120 yz )21,1()7,1(0,0,0 jizyx

33、jjij 016 z 018 y 021 z01 y 015 z 66.147W億元1 2 3 4 5 6 7供 貨 量 800 800 1000 0 1303 2000 0 課后練習：1求出最小費用矩陣157)( ijcC2求解問題1的二次規(guī)劃模型用數(shù)學軟件Lingo，用軟件SAS 定 題做 題 建模全程中注意的幾個問題反 復 讀 題 ， 查 閱 資 料齊 心 協(xié) 力 ， 分 工 明 確 ， 共 克 難 關做 題 開 始 ， 寫 論 文 就 開 始所 有 的 文 件 名 ， 保 存 時 必 須 說 明 內(nèi) 容摘 要 在 最 后 一 個 晚 上 開 始 寫論 文 的 風 格 要 一 致論 文 祝 長 安 大 學在 09年 建 模 競 賽 中 取 得 優(yōu) 異 成 績