第12章-數(shù)學(xué)建模競(jìng)賽中的部分優(yōu)化問(wèn)題

1、 優(yōu)優(yōu) 化化 建建 模模優(yōu)化建模與優(yōu)化建模與LINDO/LINGO軟件軟件第第12章數(shù)學(xué)建模競(jìng)賽中的部分優(yōu)化問(wèn)題章數(shù)學(xué)建模競(jìng)賽中的部分優(yōu)化問(wèn)題原書(shū)相關(guān)信息原書(shū)相關(guān)信息謝金星謝金星, 薛毅編，清華大學(xué)出版社薛毅編，清華大學(xué)出版社, 2005年年7月出版月出版.http:/ 優(yōu)優(yōu) 化化 建建 模模簡(jiǎn)要提綱簡(jiǎn)要提綱 1. CUMCM-1995A: 一個(gè)飛行管理問(wèn)題一個(gè)飛行管理問(wèn)題 2. CUMCM-2000B: 鋼管訂購(gòu)與運(yùn)輸鋼管訂購(gòu)與運(yùn)輸3. CUMCM-2003B：露天礦生產(chǎn)的車輛安排：露天礦生產(chǎn)的車輛安排4. CUMCM-2000D: 空洞探測(cè)空洞探測(cè) 優(yōu)優(yōu) 化化 建建 模模1995年全國(guó)大學(xué)

2、生數(shù)學(xué)建模競(jìng)賽年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽A題題 一個(gè)飛行管理問(wèn)題一個(gè)飛行管理問(wèn)題 優(yōu)優(yōu) 化化 建建 模模一個(gè)飛行管理問(wèn)題 在約10000m高空的某邊長(zhǎng)160km的正方形區(qū)域內(nèi),經(jīng)常有若干架飛機(jī)作水平飛行,區(qū)域內(nèi)每架飛機(jī)的位置和速度向量均由計(jì)算機(jī)記錄其數(shù)據(jù),以便進(jìn)行飛行管理.當(dāng)一架欲進(jìn)入該區(qū)域的飛機(jī)到達(dá)邊界區(qū)域邊緣時(shí), 記錄其數(shù)據(jù)后,要立即 計(jì)算并判斷是否會(huì)與其區(qū)域內(nèi)的飛機(jī)發(fā)生碰撞.如果會(huì)碰撞 ,則應(yīng)計(jì)算如何調(diào)整各架(包括新進(jìn)入的)飛機(jī)飛行的方向角,以避免碰撞.現(xiàn)假設(shè)條件如下: 1) 不碰撞的標(biāo)準(zhǔn)為任意兩架飛機(jī)的距離大于8km; 2)飛機(jī)飛行方向角調(diào)整的幅度不應(yīng)超過(guò)30度; 3)所有飛機(jī)飛行速度均

3、為每小時(shí)為800km; 4)進(jìn)入該區(qū)域的飛機(jī)在到達(dá)區(qū)域邊緣時(shí),與區(qū)域內(nèi)飛機(jī)的距離應(yīng)在 60km以上; 5)最多考慮6架飛機(jī); 6)不必考慮飛機(jī)離開(kāi)此區(qū)域后的狀況; 優(yōu)優(yōu) 化化 建建 模模請(qǐng)你對(duì)這個(gè)避免碰撞的飛行管理問(wèn)題建立數(shù)學(xué)模型.列出計(jì)算步驟,對(duì)以下數(shù)據(jù)進(jìn)行計(jì)算(方向角誤差不超過(guò)0.01度),要求飛機(jī)飛行方向角調(diào)整的幅度盡量小 .設(shè)該區(qū)域4個(gè)頂點(diǎn)坐標(biāo)為(0,0),(160,0),(160,160),(0,160).記錄數(shù)據(jù)為: 飛機(jī)編號(hào) 橫坐標(biāo)x 縱坐標(biāo)y 方向角(度) 1 150 140 243 2 85 85 236 3 150 155 220.5 4 145 50 159 5 130

4、150 230 新進(jìn)入 0 0 52注: 方向角指飛行方向與x軸正向的夾角 優(yōu)優(yōu) 化化 建建 模模兩架飛機(jī)不碰撞的條件兩架飛機(jī)不碰撞的條件222)()()(tjttjtijyyxxtrii,sin,cos00iitiitivtyyvtxxi064)()(2trtfijij（0 t Tij） Ti為第為第i架飛機(jī)飛出區(qū)域的時(shí)刻架飛機(jī)飛出區(qū)域的時(shí)刻不碰撞條件不碰撞條件000),(iiiyxiii0 初始位置 時(shí)刻t飛機(jī)的位置兩架飛機(jī)的距離（平方） 優(yōu)優(yōu) 化化 建建 模模),min(jiijTTT 00000000000000000000tan,223tan,23,sin,tan,23tan,2,c

5、os,tan,2tan,20,sin,tan,223tan,20,cosiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiixDyorxyifvyxyorxyDifvxxyDorxDyDifvxDxDyorxDyDifvxDT不必考慮在區(qū)域外的碰撞兩架飛機(jī)都在區(qū)域中的時(shí)間具體來(lái)看，第i架飛機(jī)在區(qū)域內(nèi)的時(shí)間飛機(jī)飛出區(qū)域的時(shí)刻飛機(jī)飛出區(qū)域的時(shí)刻 優(yōu)優(yōu) 化化 建建 模模.)(2ijijijijijczbztf整理： fij(t)的最小值 (- bij2 / 4 + cij ) ；此時(shí)其中： .2sin4*jiijijvbt 優(yōu)優(yōu) 化化 建建 模模不碰撞條件的等價(jià)表述不碰

6、撞條件的等價(jià)表述 最后，優(yōu)化模型為最后，優(yōu)化模型為 0*ijt若fij(t)大于等于肯定成立ijijTt *若fij(t)大于等于等價(jià)于0)(ijijTfijijTt *0若fij(t)大于等于等價(jià)于0)(*ijtfij, 042ijijcb 優(yōu)優(yōu) 化化 建建 模模LINGOLINGO求解求解程序程序exam1201a.lg4283. 0800/2160/2maxvDT一個(gè)簡(jiǎn)化的數(shù)學(xué)模型一個(gè)簡(jiǎn)化的數(shù)學(xué)模型任何一架飛機(jī)在區(qū)域中停留最長(zhǎng)時(shí)間 放松到任兩架飛機(jī)在這段時(shí)間不碰撞甚至放松到任兩架飛機(jī)永遠(yuǎn)不碰撞 優(yōu)優(yōu) 化化 建建 模模000),(iiiyxiii0.61iiMin其他目標(biāo)調(diào)整后的方向角 總

7、的調(diào)整量最小總的調(diào)整量最小 |max6,.,1iiMin最大調(diào)整量最小最大調(diào)整量最小 初始位置與方向角 優(yōu)優(yōu) 化化 建建 模?；谙鄬?duì)運(yùn)動(dòng)觀點(diǎn)的模型 優(yōu)優(yōu) 化化 建建 模模)22sin(),22(cos(2sin2)2cos,2sin(2sin2)2cos2sin,2sin2sin(2)sinsin,coscos(jijijijijijijijijijiijijvvvvvvvvvijijr基于相對(duì)運(yùn)動(dòng)觀點(diǎn)的模型,8sin1ijijr 優(yōu)優(yōu) 化化 建建 模模于是 . 6 , 1,30, 6 , 1,)(. .21612ijijitsMiniijjiijii數(shù)學(xué)規(guī)劃模型 優(yōu)優(yōu) 化化 建建 模模LI

8、NGOLINGO求解求解程序程序exam1201b.lg4注意：應(yīng)先計(jì)算出初始時(shí)刻的注意：應(yīng)先計(jì)算出初始時(shí)刻的ij 優(yōu)優(yōu) 化化 建建 模模2000年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題題 鋼管訂購(gòu)與運(yùn)輸鋼管訂購(gòu)與運(yùn)輸 優(yōu)優(yōu) 化化 建建 模模問(wèn)題描述問(wèn)題描述 由鋼管廠訂購(gòu)鋼管，經(jīng)鐵由鋼管廠訂購(gòu)鋼管，經(jīng)鐵路、公路運(yùn)輸，鋪設(shè)一條路、公路運(yùn)輸，鋪設(shè)一條鋼管管道鋼管管道1521AAAA13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003061952027206905

9、20170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7管道鐵路公路S1S7 鋼管廠火車站450 里程（km)（沿管道建有公路） 優(yōu)優(yōu) 化化 建建 模模鋼 廠 i1234567產(chǎn) 量 上 限 is80080010002000200020003000銷 價(jià)ip（ 萬(wàn) 元 ）160155155160155150160鋼廠的產(chǎn)量和銷價(jià)（1單位鋼管=1km管道鋼管）鋼廠產(chǎn)量的下限：500單位鋼管里程(km)300301350351400401450451500運(yùn)價(jià)(萬(wàn)元)20232629

10、32里程(km)5016006017007018008019009011000運(yùn)價(jià)(萬(wàn)元)37445055601單位鋼管的鐵路運(yùn)價(jià)1000km以上每增加1至100km運(yùn)價(jià)增加5萬(wàn)元1單位鋼管的公路運(yùn)價(jià)：0.1萬(wàn)元/km（不足整公里部分按整公里計(jì)） 優(yōu)優(yōu) 化化 建建 模模（1）制定鋼管的訂購(gòu)和運(yùn)輸計(jì)劃，使總費(fèi)用最?。┲贫ㄤ摴艿挠嗁?gòu)和運(yùn)輸計(jì)劃，使總費(fèi)用最小.（2）分析對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用影響：哪個(gè)鋼廠鋼管銷價(jià)的）分析對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用影響：哪個(gè)鋼廠鋼管銷價(jià)的變化影響最大；哪個(gè)鋼廠鋼管產(chǎn)量上限的變化影響最大？變化影響最大；哪個(gè)鋼廠鋼管產(chǎn)量上限的變化影響最大？A132580101031201242701

11、0881070627030202030450104301750606194205201680480300220210420500600306195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7A16130A17A18A19A20A21190260100（3）討論管道為樹(shù)形圖的情形）討論管道為樹(shù)形圖的情形 優(yōu)優(yōu) 化化 建建 模模問(wèn)題問(wèn)題1的基本模型和解法的基本模型和解法總費(fèi)用最小的優(yōu)化問(wèn)題總費(fèi)用：訂購(gòu)，運(yùn)輸（由各廠Si經(jīng)鐵路、公路至各點(diǎn)Aj, i=1,

12、7; j=1, 15 ），鋪設(shè)管道Aj Aj+1 （j=1, 14)由Si至Aj的最小購(gòu)運(yùn)費(fèi)用路線及最小費(fèi)用cij 由Si至Aj的最優(yōu)運(yùn)量xij由Aj向Aj Aj-1段鋪設(shè)的長(zhǎng)度yj及向Aj Aj+1段鋪設(shè)的長(zhǎng)度zj最優(yōu)購(gòu)運(yùn)計(jì)劃最優(yōu)購(gòu)運(yùn)計(jì)劃約束約束條件條件鋼廠產(chǎn)量約束：上限和下限（如果生產(chǎn)的話）運(yùn)量約束：xij對(duì)i求和等于zj 加yj； zj與 yj+1之和等于Aj Aj+1段的長(zhǎng)度ljyj zjAj-1 Aj Aj+1 優(yōu)優(yōu) 化化 建建 模?；灸Ｐ突灸Ｐ陀葾j向Aj Aj-1段鋪設(shè)的運(yùn)量為 1+ +yj= yj( yj+1)/2由Aj向Aj Aj+1段鋪設(shè)的運(yùn)量為 1+ +zj= zj(

13、 zj+1)/2)6(0, 0) 5(15, 2 , 1, 7 , 2 , 10, 0, 0)4(14, 2 , 1) 3(15, 2 , 1)2(7 , 2 , 1,5000. .) 1 ()1() 1(21 . 0min15117115171151151zyjiyzxjlyzjyzxisxtsyyzzxcjjijjjjjjiijijijijjjjjjijij二次規(guī)劃? 優(yōu)優(yōu) 化化 建建 模模求解步驟求解步驟1）求由Si至Aj的最小購(gòu)運(yùn)費(fèi)用路線及最小費(fèi)用cij 難點(diǎn)：公路運(yùn)費(fèi)是里程的線性函數(shù)，而鐵路運(yùn)費(fèi)是里程的分段階躍函數(shù)，故總運(yùn)費(fèi)不具可加性。因而計(jì)算最短路常用的Dijkstra算法、Flo

14、yd算法失效。7010881070627030202030300220210420500170690462160320160110290A10A11A12A13A14A15S4S5S6S7需要對(duì)鐵路網(wǎng)和公路網(wǎng)進(jìn)行預(yù)處理，才能使用常用需要對(duì)鐵路網(wǎng)和公路網(wǎng)進(jìn)行預(yù)處理，才能使用常用算法，得到最小購(gòu)運(yùn)費(fèi)用路線。算法，得到最小購(gòu)運(yùn)費(fèi)用路線。- 至少求至少求3次最短路次最短路如S7至A10的最小費(fèi)用路線先鐵路1130km，再公路70km, 運(yùn)費(fèi)為77（萬(wàn)元）先公路（經(jīng)A15）40km, 再鐵路1100km，再公路70km, 運(yùn)費(fèi)為76（萬(wàn)元） 優(yōu)優(yōu) 化化 建建 模模任意兩點(diǎn)之間最短路的任意兩點(diǎn)之間最短路的

15、Floyd-Warshall算法算法 1）求由Si至Aj的最小購(gòu)運(yùn)費(fèi)用路線及最小費(fèi)用cij 3次最短路的次最短路的LINGO程序：程序：Exam1202a.lg4 Exam1202b.lg4 Exam1202c.lg4., 1,min, 0)()()()1()1()1(nkjiuuuujiwuukkjkikkijkijijijiiuij(k) 是任意兩個(gè)節(jié)點(diǎn)是任意兩個(gè)節(jié)點(diǎn)i，j之間距離的臨時(shí)標(biāo)號(hào)，即從節(jié)點(diǎn)之間距離的臨時(shí)標(biāo)號(hào)，即從節(jié)點(diǎn)i到到j(luò)但不允許經(jīng)過(guò)其他節(jié)點(diǎn)但不允許經(jīng)過(guò)其他節(jié)點(diǎn)k，k+1，, n時(shí)的最短距離時(shí)的最短距離 優(yōu)優(yōu) 化化 建建 模模的的處處理理約約束束條條件件)7 , 2 , 1(

16、,5000)2151 isxijij問(wèn)問(wèn)題題求求解解。，分分解解為為上上述述形形式式的的子子的的那那些些求求解解，再再對(duì)對(duì)解解中中滿滿足足先先松松弛弛為為ixisxbjijijij5000)7, 1(0)151151 個(gè)個(gè)子子問(wèn)問(wèn)題題共共和和分分解解為為71511512)7, 1(5000) isxxaijijjij實(shí)際上只有S4和S7需要分解成子問(wèn)題求解每個(gè)子問(wèn)題是標(biāo)準(zhǔn)的二次規(guī)劃，決策變量為xij,yj,zj, 不超過(guò)135個(gè) 。0, 0,0. .)(05.0min1511711512151271151zyzyxlyzzyxsxtsyyzzxcjjijjjjjijijjiijjjjjjiji

17、jij 優(yōu)優(yōu) 化化 建建 模模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è)的鋼管量 c) 比較好的方法：引入比較好的方法：引入0-10-1變量變量. 7,.,1, 1 , 0, 0.14,.,1.15,.,1,. 7,.,1,500. .)1 ()1(21 . 0)(151171151151,ifzyjbzyjzyxifSxftszzyyxcpMinijjjjjiijiijijijjjjjjiijiji LINDO/LINGO得到的結(jié)果比得到的結(jié)果比

18、matlab得到的好得到的好exam1202d.lg4yj zjAj 優(yōu)優(yōu) 化化 建建 模模問(wèn)題問(wèn)題2: 分析對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用影響分析對(duì)購(gòu)運(yùn)計(jì)劃和總費(fèi)用影響(哪個(gè)鋼廠銷價(jià)變哪個(gè)鋼廠銷價(jià)變化影響最大；哪個(gè)鋼廠產(chǎn)量上限變化影響最大化影響最大；哪個(gè)鋼廠產(chǎn)量上限變化影響最大)規(guī)劃問(wèn)題的靈敏度分析問(wèn)題問(wèn)題3：管道為樹(shù)形圖管道為樹(shù)形圖701088107062300220210170690462160320160A10A11A12S4S5S6130A17A18A19A20190260100, 0,500 , 0. .)(05.0min71)(2112211)(71211 jkijjkkjjkijkEjki

19、jjiijjkjkjEjkijijijyxbyyyxsxtsyyxc(jk)是連接Aj,Ak的邊，E是樹(shù)形圖的邊集， ljk是(jk)的長(zhǎng)度， yjk是由Aj沿(jk)鋪設(shè)的鋼管數(shù)量 優(yōu)優(yōu) 化化 建建 模模2003年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽B題題 露天礦生產(chǎn)的車輛安排露天礦生產(chǎn)的車輛安排 優(yōu)優(yōu) 化化 建建 模模露天礦里鏟位已分成礦石和巖石露天礦里鏟位已分成礦石和巖石: 平均鐵含量不低于平均鐵含量不低于25%的為礦石，否則為巖石。每個(gè)鏟位的礦石、巖石數(shù)的為礦石，否則為巖石。每個(gè)鏟位的礦石、巖石數(shù)量，以及礦石的平均鐵含量（稱為品位）都是已知的。量，以及礦石的平均鐵含量（稱為品

20、位）都是已知的。每個(gè)鏟位至多安置一臺(tái)電鏟，電鏟平均裝車時(shí)間每個(gè)鏟位至多安置一臺(tái)電鏟，電鏟平均裝車時(shí)間5分鐘分鐘卡車在等待時(shí)所耗費(fèi)的能量也是相當(dāng)可觀的，原則上卡車在等待時(shí)所耗費(fèi)的能量也是相當(dāng)可觀的，原則上在安排時(shí)在安排時(shí)不應(yīng)發(fā)生卡車等待不應(yīng)發(fā)生卡車等待的情況。的情況。 露天礦生產(chǎn)的車輛安排露天礦生產(chǎn)的車輛安排 礦石卸點(diǎn)需要的鐵含量要求都為礦石卸點(diǎn)需要的鐵含量要求都為29.5% 1%(品位限品位限制），搭配量在一個(gè)班次（制），搭配量在一個(gè)班次（8小時(shí)）內(nèi)滿足品位限制即小時(shí)）內(nèi)滿足品位限制即可。卸點(diǎn)在一個(gè)班次內(nèi)不變?？ㄜ囕d重量為可。卸點(diǎn)在一個(gè)班次內(nèi)不變。卡車載重量為154噸，平噸，平均時(shí)速均時(shí)速28

21、km,平均卸車時(shí)間為平均卸車時(shí)間為3分鐘。分鐘。問(wèn)題：出動(dòng)幾臺(tái)電鏟，分別在哪些鏟位上；出動(dòng)幾輛問(wèn)題：出動(dòng)幾臺(tái)電鏟，分別在哪些鏟位上；出動(dòng)幾輛卡車，分別在哪些路線上各運(yùn)輸多少次卡車，分別在哪些路線上各運(yùn)輸多少次 ? 優(yōu)優(yōu) 化化 建建 模模平面示意圖 優(yōu)優(yōu) 化化 建建 模模問(wèn)題數(shù)據(jù)問(wèn)題數(shù)據(jù) 距離鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏5.202.952.742.461.900.641.27倒裝1.900.991.901.131.272.251.482.043.093.51巖場(chǎng)5.895.615.614.563.513.652.462.461.06

22、0.57巖石漏0.641.761.271.832.742.604.213.725.056.10倒裝4.423.863.710.781.621.270.50鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石量095105100105110125105130135125巖石量125110135105115135105115135125鐵含量30%28%29%32%31%33%32%31%33%31% 優(yōu)優(yōu) 化化 建建 模模問(wèn)題分析問(wèn)題分析 與典型的運(yùn)輸問(wèn)題明顯有以下不同：與典型的運(yùn)輸問(wèn)題明顯有以下不同：1. 這是運(yùn)輸?shù)V石與巖石兩種物資的問(wèn)題；這是運(yùn)輸?shù)V石與巖

23、石兩種物資的問(wèn)題；2. 屬于產(chǎn)量大于銷量的不平衡運(yùn)輸問(wèn)題；屬于產(chǎn)量大于銷量的不平衡運(yùn)輸問(wèn)題；3. 為了完成品位約束，礦石要搭配運(yùn)輸；為了完成品位約束，礦石要搭配運(yùn)輸；4. 產(chǎn)地、銷地均有單位時(shí)間的流量限制；產(chǎn)地、銷地均有單位時(shí)間的流量限制；5. 運(yùn)輸車輛只有一種，每次滿載運(yùn)輸，運(yùn)輸車輛只有一種，每次滿載運(yùn)輸，154噸噸/車次；車次；6. 鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于鏟位數(shù)多于鏟車數(shù)意味著要最優(yōu)的選擇不多于7個(gè)個(gè)產(chǎn)地作為最后結(jié)果中的產(chǎn)地；產(chǎn)地作為最后結(jié)果中的產(chǎn)地；7. 最后求出各條路線上的派出車輛數(shù)及安排。最后求出各條路線上的派出車輛數(shù)及安排。近似處理：近似處理：先求出產(chǎn)位、卸點(diǎn)每條

24、線路上的運(yùn)輸量先求出產(chǎn)位、卸點(diǎn)每條線路上的運(yùn)輸量(MIP模型模型)然后求出各條路線上的派出車輛數(shù)及安排然后求出各條路線上的派出車輛數(shù)及安排 優(yōu)優(yōu) 化化 建建 模模模型假設(shè)模型假設(shè) 卡車在一個(gè)班次中不應(yīng)發(fā)生等待或熄火后再啟動(dòng)卡車在一個(gè)班次中不應(yīng)發(fā)生等待或熄火后再啟動(dòng)的情況；的情況； 在鏟位或卸點(diǎn)處由兩條路線以上造成的沖突問(wèn)題在鏟位或卸點(diǎn)處由兩條路線以上造成的沖突問(wèn)題面前，我們認(rèn)為只要平均時(shí)間能完成任務(wù)，就認(rèn)面前，我們認(rèn)為只要平均時(shí)間能完成任務(wù)，就認(rèn)為不沖突。我們不排時(shí)地進(jìn)行討論；為不沖突。我們不排時(shí)地進(jìn)行討論； 空載與重載的速度都是空載與重載的速度都是28km/h，耗油相差很大；，耗油相差很大；

25、 卡車可提前退出系統(tǒng)，等等?？ㄜ嚳商崆巴顺鱿到y(tǒng)，等等。如理解為嚴(yán)格不等待，難以用數(shù)學(xué)規(guī)劃模型來(lái)解如理解為嚴(yán)格不等待，難以用數(shù)學(xué)規(guī)劃模型來(lái)解 個(gè)別參數(shù)隊(duì)找到了可行解個(gè)別參數(shù)隊(duì)找到了可行解 （略）（略） 優(yōu)優(yōu) 化化 建建 模模符號(hào)符號(hào) xij ：從：從i鏟位到鏟位到j(luò)號(hào)卸點(diǎn)的石料運(yùn)量號(hào)卸點(diǎn)的石料運(yùn)量 （車）（車） 單位：?jiǎn)挝唬?噸；噸； cij ：從：從i號(hào)鏟位到號(hào)鏟位到j(luò)號(hào)卸點(diǎn)的距離號(hào)卸點(diǎn)的距離 公里；公里； Tij :從從i號(hào)鏟位到號(hào)號(hào)鏟位到號(hào)j卸點(diǎn)路線上運(yùn)行一個(gè)周期平均時(shí)間卸點(diǎn)路線上運(yùn)行一個(gè)周期平均時(shí)間 分；分； Aij ：從號(hào)鏟位到號(hào)卸點(diǎn)最多能同時(shí)運(yùn)行的卡車數(shù)：從號(hào)鏟位到號(hào)卸點(diǎn)最多能同時(shí)運(yùn)

26、行的卡車數(shù) 輛；輛； Bij ：從號(hào)鏟位到號(hào)卸點(diǎn)路線上一輛車最多可運(yùn)行的次數(shù)：從號(hào)鏟位到號(hào)卸點(diǎn)路線上一輛車最多可運(yùn)行的次數(shù) 次；次； pi：i號(hào)鏟位的礦石鐵含量號(hào)鏟位的礦石鐵含量 p=(30,28,29,32,31,33,32,31,33,31) % qj : j號(hào)卸點(diǎn)任務(wù)需求，號(hào)卸點(diǎn)任務(wù)需求，q=(1.2,1.3,1.3,1.9,1.3)*10000 噸噸 cki ：i號(hào)鏟位的鐵礦石儲(chǔ)量號(hào)鏟位的鐵礦石儲(chǔ)量 萬(wàn)噸萬(wàn)噸 cyi ：i號(hào)鏟位的巖石儲(chǔ)量號(hào)鏟位的巖石儲(chǔ)量 萬(wàn)噸萬(wàn)噸 fi :描述第描述第i號(hào)鏟位是否使用的號(hào)鏟位是否使用的0-1變量，取變量，取1為使用；為使用；0為關(guān)閉。為關(guān)閉。532平均

27、速度距離到j(luò)iTij5ijijTAijijijTAB5) 1(608(近似近似) 優(yōu)優(yōu) 化化 建建 模模優(yōu)化模型cxijijij10151min5 , 1,10, 1,jiBAxijijij10, 1, 5/60851ifxijij5 , 1,208101jiijx10, 1,154/10000154/1000043521icyxxckxxxiiiiiii（1）道路能力道路能力(卡車數(shù)卡車數(shù))約束約束（2）電鏟能力約束（3）卸點(diǎn)能力約束（4）鏟位儲(chǔ)量約束（5）產(chǎn)量任務(wù)約束（6）鐵含量約束（7）電鏟數(shù)量約束（8）整數(shù)約束 5 , 1,154/101jqxjiij5 , 2 , 1,0)5 .28

28、(0)5 .30(101101jpxpxiiijiiij.7101iifxij為非負(fù)整數(shù)fi 為0-1整數(shù) 優(yōu)優(yōu) 化化 建建 模模計(jì)算結(jié)果（計(jì)算結(jié)果（LINGOLINGO軟件）軟件）鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦漏131354541111倒42424343巖場(chǎng)70701515巖漏81814343倒13132 27070鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏0.8671.8620.314倒場(chǎng)1.0771.162巖場(chǎng)1.8920.326巖石漏1.8411.229倒場(chǎng)0.6840.11.489exam1203.lg4注注: LINGO8

29、.0本來(lái)是可以得到最優(yōu)解的，但有些本來(lái)是可以得到最優(yōu)解的，但有些 LINGO8.0可能出現(xiàn)系統(tǒng)錯(cuò)誤可能出現(xiàn)系統(tǒng)錯(cuò)誤, 可能是系統(tǒng)可能是系統(tǒng)BUG 優(yōu)優(yōu) 化化 建建 模模計(jì)算結(jié)果（派車）計(jì)算結(jié)果（派車）鏟位1鏟位2鏟位3鏟位4鏟位5鏟位6鏟位7鏟位8鏟位9鏟位10礦石漏1 (29)倒場(chǎng)1 (39)1 (37)巖場(chǎng)1 (37)巖石漏1(44)1 (35)倒場(chǎng)1 (47)結(jié)論：結(jié)論：鏟位鏟位1、2、3、4、8、9、10處各放置一臺(tái)電鏟。處各放置一臺(tái)電鏟。一共使用了一共使用了13輛卡車；總運(yùn)量為輛卡車；總運(yùn)量為85628.62噸公里；噸公里；巖石產(chǎn)量為巖石產(chǎn)量為32186噸；礦石產(chǎn)量為噸；礦石產(chǎn)量為3

30、8192噸。噸。此外：此外：6輛聯(lián)合派車（方案略）輛聯(lián)合派車（方案略） 優(yōu)優(yōu) 化化 建建 模模最大化產(chǎn)量最大化產(chǎn)量結(jié)論：結(jié)論：（略）（略）目標(biāo)函數(shù)變化目標(biāo)函數(shù)變化此外：車輛數(shù)量（此外：車輛數(shù)量（20輛）限制（其實(shí)上面的模型也輛）限制（其實(shí)上面的模型也應(yīng)該有）應(yīng)該有） 優(yōu)優(yōu) 化化 建建 模模2000年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽年全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽D題題 空洞探測(cè)空洞探測(cè) 優(yōu)優(yōu) 化化 建建 模模山體隧道壩體等的某些內(nèi)部結(jié)構(gòu)可用彈性波測(cè)量來(lái)確定。簡(jiǎn)化問(wèn)題可敘述為，一塊均勻介質(zhì)構(gòu)成的矩形平板內(nèi)有一些充滿空氣的空洞。在平板的兩個(gè)鄰邊分別等距地設(shè)置若干波源，在他們的對(duì)邊對(duì)等地安放同樣多的接收器，記錄彈性波

31、由每個(gè)波源到達(dá)對(duì)邊上每個(gè)接收器的時(shí)間。根據(jù)彈性波在介質(zhì)和在空氣中不同的傳播速度來(lái)確定板內(nèi)空洞的位置 優(yōu)優(yōu) 化化 建建 模模具體問(wèn)題：一塊240(米)240(米)的平板ABCD， 在AB 邊等距地設(shè)置7個(gè)波源Pi (i=1,7),在 CD 邊等距地設(shè)置7個(gè)接收器Qj (j=1,7), 記錄由 Pi 發(fā)出的彈性波到達(dá) Qj 的時(shí)間 tij(秒) ; 在AD 邊等距地設(shè)置7個(gè)波源 Ri (i=1,7),在 BC 邊等距地設(shè)置7個(gè)接收器Sj (j=1,7), 記錄由 Ri 發(fā)出的彈性波到達(dá) Sj 的時(shí)間 ij(秒)。 已知彈性波在介質(zhì)和空氣中的傳播速度分別為2880(米/秒)和320(米/秒), 且彈

32、性波沿板邊緣的傳播速度與在介質(zhì)中的傳播速度相同 優(yōu)優(yōu) 化化 建建 模模CBADP2Q4R3S6 優(yōu)優(yōu) 化化 建建 模模TP=(tij)tij Q1 Q2 Q3 Q4 Q5 Q6 Q7P1 .0611 .0895 .1996 .2032 .4181 .4923 .5646P2 .0989 .0592 .4413 .4318 .4770 .5242 .3805P3 .3052 .4131 .0598 .4153 .4156 .3563 .1919P4 .3221 .4453 .4040 .0738 .1789 .0740 .2122P5 .3490 .4529 .2263 .1917 .0839

33、.1768 .1810P6 .3807 .3177 .2364 .3064 .2217 .0939 .1031P7 .4311 .3397 .3566 .1954 .0760 .0688 .1042 優(yōu)優(yōu) 化化 建建 模模TR=(ij)ij S1 S2 S3 S4 S5 S6 S7R1 .0645 .0602 .0813 .3516 .3867 .4314 .5721R2 .0753 .0700 .2852 .4341 .3491 .4800 .4980R3 .3456 .3205 .0974 .4093 .4240 .4540 .3112R4 .3655 .3289 .4247 .1007

34、.3249 .2134 .1017R5 .3165 .2509 .3214 .3256 .0904 .1874 .2130R6 .2749 .3891 .5895 .3016 .2058 .0841 .0706R7 .4434 .4919 .3904 .0786 .0709 .0914 .0583 優(yōu)優(yōu) 化化 建建 模模要求：(1) 確定該平面內(nèi)空洞的位置。(2) 只根據(jù)Pi發(fā)出的彈性波到達(dá)Qj的時(shí)間tij 能確定空洞的位置嗎？討論在同樣能夠確定空洞位置的前提下，減少波源和接收器的方法。 優(yōu)優(yōu) 化化 建建 模模分析: 彈性波沿平板邊緣的理論傳播時(shí)間 t=240/2880=0.0833(秒) 彈

35、性波沿平板邊緣的實(shí)際傳播時(shí)間 t11=.0611, t77=.1042, 11=.0645, 77=.0583 題目中已假設(shè)“彈性波沿板邊緣的傳播速度與在介質(zhì)中的傳播速度相同”觀測(cè)數(shù)據(jù)的最大絕對(duì)誤差為d=0.025秒.可以認(rèn)為，可以認(rèn)為，0.025*360 =9(米）以下的空洞是米）以下的空洞是探測(cè)不出的探測(cè)不出的 優(yōu)優(yōu) 化化 建建 模模假設(shè)1. 觀測(cè)數(shù)據(jù)有測(cè)量誤差。觀測(cè)數(shù)據(jù)除測(cè)量誤差外是可靠的。2. 波在傳播過(guò)程中沿直線單向傳播，且不考慮波的反射、折射以及干涉等現(xiàn)象。3.空氣密度和介質(zhì)密度都均勻 優(yōu)優(yōu) 化化 建建 模模4.“彈性波”在傳播過(guò)程中沒(méi)有能量損失。其波速僅與介質(zhì)有關(guān)，且在同一均勻介

36、質(zhì)中波速不變。彈性波沿板邊緣的傳播速度與在介質(zhì)中的傳播速度相同。5.假設(shè)平板可劃分化為網(wǎng)格，空洞定位于每個(gè)網(wǎng)格單元內(nèi),空洞大小大致相同. 優(yōu)優(yōu) 化化 建建 模模波線與網(wǎng)格交線長(zhǎng)度的計(jì)算波線與網(wǎng)格交線長(zhǎng)度的計(jì)算 (k,l) ; 52120,; 711,40kjikjikjikjikbijkl，且或如果或如果記波源記波源Pi與接收器與接收器Qj 決定的決定的波線與每個(gè)單元（波線與每個(gè)單元（k，l）的交線長(zhǎng)度為的交線長(zhǎng)度為bijkl i=j 時(shí)時(shí)123456654321 優(yōu)優(yōu) 化化 建建 模模波線與網(wǎng)格交線長(zhǎng)度的計(jì)算波線與網(wǎng)格交線長(zhǎng)度的計(jì)算 PiQj 決定的直線方程：決定的直線方程：(j - i）y

37、 = 6(x-40(i-1) i=j 以外的情況以外的情況單元單元(k,l)左邊緣直線方程左邊緣直線方程 x = 40(k-1)波線與波線與單元單元(k,l)左邊緣左邊緣對(duì)應(yīng)交點(diǎn)的對(duì)應(yīng)交點(diǎn)的y坐標(biāo)為坐標(biāo)為 y1ijkl = 240(k-i)/(j-i)， 其中其中 l-1 6(k-i)/(j-i) l (k,l) 優(yōu)優(yōu) 化化 建建 模模波線與網(wǎng)格交線長(zhǎng)度的計(jì)算波線與網(wǎng)格交線長(zhǎng)度的計(jì)算 PiQj 決定的直線方程：決定的直線方程：(j - i）y = 6(x-40(i-1) i=j 以外的情況以外的情況單元單元(k,l)右邊緣直線方程右邊緣直線方程 x = 40k波線與波線與單元單元(k,l)右邊

38、緣右邊緣對(duì)應(yīng)交點(diǎn)的對(duì)應(yīng)交點(diǎn)的y坐標(biāo)為坐標(biāo)為 y2ijkl = 240(k+1-i)/(j-i)， 其中其中 l-1 6(k+1-i)/(j-i) l (k,l) 優(yōu)優(yōu) 化化 建建 模模波線與網(wǎng)格交線長(zhǎng)度的計(jì)算波線與網(wǎng)格交線長(zhǎng)度的計(jì)算 PiQj 決定的直線方程：決定的直線方程：(j - i）y = 6(x-40(i-1) i=j 以外的情況以外的情況單元單元(k,l)下邊緣直線方程下邊緣直線方程 y = 40(l-1)波線與波線與單元單元(k,l)下邊緣下邊緣對(duì)應(yīng)交點(diǎn)的對(duì)應(yīng)交點(diǎn)的y坐標(biāo)為坐標(biāo)為 y3ijkl = 40(l-1)， 其中其中 0 6(i-k)-(i-j)(l-1) 6 (k,l) 優(yōu)優(yōu) 化化 建建 模模波線