數(shù)學(xué)建模中的創(chuàng)新案例教學(xué)課件

1、數(shù)學(xué)建模中的創(chuàng)新案例2011年7月1 創(chuàng)造性是靈魂，文章要有閃光點。 好創(chuàng)意、好想法應(yīng)當(dāng)既在人意料之外，又在人意料之中。 新穎性（獨特性）與合理性皆備。 數(shù)學(xué)建模中的創(chuàng)新性2誤區(qū)之一：數(shù)學(xué)用得越高深，越有創(chuàng)造性。 解決問題是第一原則，最合適的方法是最好的方法。誤區(qū)之二：創(chuàng)造性主要體現(xiàn)在建模與求解上。 創(chuàng)造性可以體現(xiàn)在建模的各個環(huán)節(jié)上，并且可以有多種表現(xiàn)形式。 3誤區(qū)之三：好創(chuàng)意來自于靈感，可遇不可求。 好創(chuàng)意來自于對數(shù)學(xué)方法的掌握程度與對問題理解的透徹程度。 4 在高空中一個邊長為160公里的正方形區(qū)域內(nèi)，經(jīng)常有若干架飛機作水平飛行。區(qū)域內(nèi)每架飛機的位置和速度均由計算機記錄其數(shù)據(jù)。當(dāng)一架欲進入

2、該區(qū)域的飛機到達區(qū)域邊緣時，要立即計算并判斷其是否會與區(qū)域內(nèi)的飛機碰撞。如果會碰撞，則要計算如何調(diào)整各架（包括新進入的）飛機飛行的方向角，以避免碰撞?，F(xiàn)假定條件如下：案例一：飛行管理問題（95A）5不碰撞的標(biāo)準為任意兩架飛機的距離大于8公里；每架飛機飛行方向角調(diào)整的幅度不應(yīng)超過30度；所有飛機飛行速度均為800公里/小時；欲進入飛機在到達區(qū)域邊緣時，與區(qū)域內(nèi)飛機的距離應(yīng)在60公里以上；最多需考慮6架飛機；不必考慮飛機離開此區(qū)域后的狀況。 請你建立數(shù)學(xué)模型，對以下數(shù)據(jù)進行計算（方向角誤差不超過0.01度），要求飛機飛行方向角調(diào)整的幅度盡量小。（數(shù)據(jù)略）6 模型建立與求解 模型一：設(shè)第 i 架飛機

3、在調(diào)整時的 方向角為i ,調(diào)整角度為i （ i 1，2，6）。設(shè)任意兩架飛機在區(qū)域內(nèi)的最短距離為dij(i , j )，那么問題的非線性規(guī)劃模型為 7 解法：能量梯度法、懲罰函數(shù)法、序列無約束最小 化方法、逐步逼近搜索法等 模型二： 模型三：8 利用相對運動的方法得到以上模型，再簡化為線性規(guī)劃問題求解。 啟示：轉(zhuǎn)換角度看問題，也會帶來創(chuàng)新點。9 關(guān)鍵是計算速度與計算精度的平衡問題。牛頓迭代法有很高的精度，但速度較慢；線性近似法速度很快，可以滿足實時要求，但精度稍差。 “Rabbit , Turtle and Hunter” 抓住了問題的主要方面速度。 啟示：創(chuàng)造性體現(xiàn)在對問題的理解程度上， 進

4、而體現(xiàn)在建模思路上。 案例二：螺旋線交點問題（95mcmA）10案例三： 110警車配置及巡邏方案 （研究生09D）11 某城市擬增加一批配備有GPS衛(wèi)星定位系統(tǒng)及先進通訊設(shè)備的110警車。設(shè)110警車的平均巡邏速度為20km/h，接警后的平均行駛速度為40km/h。警車配置及巡邏方案要盡量滿足以下要求： D1. 警車在接警后三分鐘內(nèi)趕到現(xiàn)場的比例不低于 90；而趕到重點部位的時間必須在兩分鐘之內(nèi)。 D2. 使巡邏效果更顯著； D3. 警車巡邏規(guī)律應(yīng)有一定的隱蔽性。 12 請回答以下問題：一. 若要求滿足D1,該區(qū)最少需要配置多少輛警車巡邏？二. 請給出評價巡邏效果顯著程度的有關(guān)指標(biāo)。三 請給

5、出滿足D1且盡量滿足D2條件的警車巡邏方案及 其評價指標(biāo)值。四. 在第三問的基礎(chǔ)上，再考慮D3條件，給出你們的警車巡邏方案及其評價指標(biāo)值。五 如果該區(qū)域僅配置10輛警車，應(yīng)如何制定巡邏方案，使D1、D2盡量得到滿足？ 六. 若警車接警后的平均行駛速度提高到50km/h，回答問題三。七. 你們認為還有哪些因素、哪些情況需要考慮？給出你們相應(yīng)的解決方案。 13第三問 本問的主要技術(shù)難點在于要求二十幾輛車在“動態(tài)巡邏”條件下保持“分布均勻性”，求最優(yōu)解的計算復(fù)雜度太高，因此，尋找可接受的計算復(fù)雜度與結(jié)果的優(yōu)化之間的平衡點，是本問的關(guān)鍵所在。本問的求解充分體現(xiàn)了建模方法的多樣性，為參賽者充分發(fā)揮創(chuàng)造性

6、提供了很好的機會。主要解題方法概述如下： 14解題思路第三問 1）單車分區(qū)法：按照覆蓋率要求作區(qū)域劃分，每個區(qū)域固定一輛警車巡邏。此方法主要特點是計算簡單，但是其代價是需要車輛數(shù)較多。例如靜態(tài)時17輛車即能滿足覆蓋率要求，如果分成17個區(qū)域，每個區(qū)域1輛車，則在動態(tài)時要保持滿足覆蓋率要求就非常困難了，所以不得不增加劃分區(qū)域。此種方法通常要求配置3輛車以上，才能達到覆蓋率要求。 15解題思路第三問 2）多車分區(qū)法：為了改進以上單車分區(qū)法的缺點，可以考慮每個區(qū)域設(shè)置若干輛警車共同巡邏的方法，這樣可以減少一些車輛，但代價是計算難度的增加，且每一區(qū)域配置的車輛越多，計算難度就越大。 16解題思路第三問

7、 3）動靜結(jié)合法：有的參賽隊單純從滿足車輛數(shù)最少的目標(biāo)出發(fā)，讓有的車靜止不動，這樣即能滿足覆蓋率要求，車輛數(shù)又少。但這樣做，見警率指標(biāo)就很差了，于是就再安排一些車跑見警率。從覆蓋率與見警率效果來看，此方法很不錯，車輛數(shù)還不多（大約或輛），計算也相對簡單，似乎是一種好方法。但是這樣做，違背了問題本身的實際意義，所以未能得到評委們的認可。數(shù)學(xué)建模不是解數(shù)學(xué)題，一定要考慮問題的實際意義是什么，不能為了追求指標(biāo)的好看而罔顧其實際背景。 17解題思路-第三問 4）軟分區(qū)法：此方法由方法）延伸而來。與方法）一樣，本方法先劃分區(qū)域，每個區(qū)域配置一輛警車，與方法）不同的是，每個區(qū)域配置的警車并不是一定不能跨區(qū)

8、域巡邏，而是設(shè)置了一個跨區(qū)域因子，此因子隨著周圍區(qū)域警車的位置以及其本身的位置關(guān)系而變化。再設(shè)置一個區(qū)域中心引力因子，以保證該車不會離開自己的區(qū)域中心太遠。此方法的思想有創(chuàng)意，但在實現(xiàn)時由于各個因子之間較難平衡，所以效果改進不大。 18解題思路第三問 5）蟻群算法：此方法屬于啟發(fā)式搜索算法，在此次競賽中成為主流解法，其思想是：在道路上設(shè)置一個“氣味因子”，某段道路上跑過的車越多，則該段道路的“氣味”變大，并且“氣味”隨時間變長而衰減。巡邏車每到一個路口，根據(jù)路口其它各段道路的“氣味”大小，朝“氣味”最小的方向前進。想法蠻有創(chuàng)意，在具體實現(xiàn)時還要處理好多輛車的協(xié)同問題等細節(jié)。如果細節(jié)處理得好，此

9、方法所需要的車輛數(shù)大約為輛左右，不失為一種比較理想的方案。 19解題思路第三問 6）引力場方法：此方法與上一方法有類似之處，即每段道路依據(jù)走過的警車多少有一個“引力因子”，走過的車輛越多，則“引力”越小；同時，任兩輛車之間依據(jù)距離遠近有一個“斥力因子”，距離越近，則斥力越大。對每一輛警車而言，道路對它的“引力”與其它車輛對它的的“斥力”共同構(gòu)成了一個“引力場”，它將向著“合成引力”最大的方向前進。這也是一種挺有創(chuàng)意的想法，難處在于細節(jié)的處理（例如引力與斥力的合成）及計算上的復(fù)雜性，對計算能力有較高的要求。 20解題思路第三問 7）切片疊加法：由于靜態(tài)時車輛數(shù)較少，并且車輛可以達到“均勻分布”狀

10、態(tài)，因此一種想法是對時間進行“切片”處理：每一時刻為一個切片，在一個切片上給出所有車輛的一個“均勻分布”，構(gòu)造出充分多（例如：張）的不同切片，并且通過篩選使這些切片上的車輛分布點盡量分散，這是出于提高切片“疊加”后的車輛到達率指標(biāo)的考慮。然后對這些切片按照“擇近”原則進行排序，再對排序后的切片依次疊加，便得到一個班次（小時或小時）的巡邏方案。 21解題思路第三問這個方案的特點是車輛在巡邏時的速度可以不同，但每輛車的平均速度仍為公里/小時，其難點在于對切片的“擇近”排序的計算量很大。這是一種很有創(chuàng)意的方法，效果也不錯。大約需要輛車，可以使覆蓋率及到達率指標(biāo)都比較令人滿意?？上Т朔N解法在本次競賽論

11、文中未發(fā)現(xiàn)使用。啟示：通往羅馬的道路不止一條，但有些需 要實力的支撐。 22解題思路第三問案例四：鎖具裝箱（94B） 某廠生產(chǎn)一種彈子鎖具，每個鎖具的鑰匙有5個槽，每個槽的高度從1，2，3，4，5，6這6個數(shù)中任取一數(shù)。由于工藝及其它原因，制造鎖具時對5個槽的高度還有兩個限制：至少有3個不同的數(shù)；相鄰兩槽的高度之差不能為5。滿足以上條件的所有互不相同的鎖具稱為一批。 從顧客的利益出發(fā)，自然希望在每批鎖具中“一把鑰匙開一把鎖”。但是在當(dāng)前工藝條件下，對于同一批中兩個鎖具是否能夠互開，有以下試驗結(jié)果：若二者相對應(yīng)的5個槽的高度中有4個相同，另一個槽的高度差為1，則可能互開；在其他情況下，不可能互開

12、。23 原來，銷售部門在一批鎖具中隨意地取每60個裝一箱出售。團體顧客往往購買幾箱到幾十箱，他們抱怨購得的鎖具會出現(xiàn)互開的情形。現(xiàn)聘你為顧問，回答并解決以下的問題：（1）每一批鎖具有多少個，裝多少箱。（2）為銷售部門提出一種方案，包括如何裝箱，如何給箱子以標(biāo)志，出售時如何利用這些標(biāo)志，使團體顧客不再或減少抱怨。（3）采取你的方案，團體顧客的購買量不超過多少箱，就可以保證一定不會出現(xiàn)互開的情形。（4）按照原來的裝箱辦法，如何定量地衡量團體顧客抱怨互開的程度（試對購買一、二箱者給出具體結(jié)果）。 24 將鎖具按照槽高之和H為奇數(shù)與偶數(shù)分為兩大類，每一類裝49箱。最優(yōu)性證明。 隨機銷售方式與序貫銷售方

13、式 。 抱怨程度的度量。 三個創(chuàng)新點：25論文一（電子科大） 一、問題的重述與分析 每個鎖具的鑰匙有5個槽，令hi為第i個槽的高度，用 記一個鎖具，則一批鎖具應(yīng)滿足如下條件： 條件1 條件2 中至少有三個數(shù)不相同； 條件3 滿足以下條件的兩個鎖具 可以互開，并把這兩個鎖具稱為一個互開對： （*） 26 我們所關(guān)心的問題是：每一批鎖具共有多少個，如何衡量隨機裝箱造成的團體顧客的抱怨程度以及采取何種方案裝箱來盡量避免團體顧客的抱怨。 二、模型假設(shè)1、鑰匙的每個槽的高度在生產(chǎn)過程中能夠嚴格控制；2、滿足條件（*）的兩個鎖具一定能夠互開。三、模型建立與求解1、確定一批鎖具的總數(shù) 一批鎖具的總數(shù)為777

14、6 -（6+450+456+792+192）= 5880 個裝箱總數(shù)為 5880/60=98 箱 272、裝箱方案 設(shè)槽高之和為H，則 是互開對 設(shè) 是一個鎖具，則 也是一個鎖具，并且 鎖具，故所有鎖具分為兩部分：奇類與偶類，且數(shù)量相等，各占一半。 奇偶性恰好相反，稱為對偶 分奇、偶類分別裝箱，一批鎖具中奇偶各裝49箱，作上標(biāo)記，則只要團體顧客購買不超過49箱，就可以保證不會出現(xiàn)互開現(xiàn)象。 283、方案最優(yōu)性的證明 用計算機對互開對數(shù)進行窮舉計算得到在一批鎖具中互開對總數(shù)為22778對。 用頂點表示鎖具，用邊表示可互開，得到圖 其中 記 V1=奇類鎖具，V2 =偶類鎖具，則G0是一個二分圖，記

15、作 要證明49箱是最優(yōu)結(jié)果，等價于證明圖G0的最大點無關(guān)集含2990點，或等價于證明圖G0存在完美匹配。 引理1 二分圖 含有覆蓋V1的每個頂點的匹配的充要條件是對任意 有 定理 二分圖 的V1，V2是它的兩個最大點無關(guān)集。 29證 由奇類鎖具與偶類鎖具的對稱性可知 滿足 （1），即G0中含有覆蓋V1中每個頂點的匹配M，顯然M也覆蓋了V2中的每個頂點，于是M是完美匹配，亦即G0的最大點無關(guān)集包含點數(shù)不可能超過2980，所以我們的銷售方案是最優(yōu)的。 評注 證明有誤，例如右圖.結(jié)論是正確的，已有計算機證明.但尚未見到理論證明。4. 定量分析顧客抱怨互開的程度(1) 對于隨機裝箱的方案 互開對總數(shù)為

16、m = 22778對，平均每個鎖具與其它鎖具能組成的互開對數(shù)為 對。 30 隨機裝箱時，某一個指定的鎖具與箱中的其余59個組成互開對的平均數(shù)為 （個） 一箱中平均互開對數(shù)為 （對） 同理可知：k箱鎖具中，能與某一個指定鎖具互開的鎖具個數(shù)平均為 （個） 于是k箱中平均含有的互開對數(shù)為 31顯然，E (mk)越大，顧客抱怨程度越大。 k 1 2 49E (mk) 2.33 9.41 5693.5（2） 對于奇偶分類裝箱的方案當(dāng)購買量不超過49箱時，不會抱怨。 當(dāng)購買量超過49箱時，先從奇類中取出49箱，再從偶類中任取出k-49箱出售，平均互開對數(shù)為 （對） 故奇偶分類裝箱后團體顧客的抱怨程度減少了

17、。模型評價：（1）分析出色，結(jié)構(gòu)完整、嚴謹，較圓滿地解決題；（2）轉(zhuǎn)化為圖論問題，轉(zhuǎn)化出色，但最優(yōu)性證明有誤；（3）銷售方案不大符合實際；（4）抱怨程度的分析不夠深入。32論文二（蘭州鐵道學(xué)院） 較實際的一種銷售方案：序貫銷售。裝箱分奇偶兩類，按槽高H及字典序從小到大裝箱。 H8： （11123）（11132）（11213）（11231）（11321） H9： （11124）（11142）（11214）（11223） 這樣，每一個鎖具在一批鎖具中的位置是唯一確定的。計算任一鎖具的最小可互開距離，再對所有最小距離求極小值，得到計算結(jié)果為：2562. 2563/60=42.7 故序貫銷售時團體顧客

18、最大購買量為42箱時不會出現(xiàn)互開現(xiàn)象。 啟示：從實際背景出發(fā)，深入一步思考，尋找創(chuàng)新點。 33論文三（合肥工大） 顧客的抱怨程度一方面取決于購買的總數(shù)量，另一方面取決于檢驗的結(jié)果，并且從心理學(xué)的角度考慮，顧客更偏重于檢驗結(jié)果。 檢驗方法：從購買的T箱中取出t箱，再從這t箱中每箱各取m把，對取出的tm把鎖具作完全互開試驗。 定義抱怨函數(shù)為： 其中，K1 ： 表示購買箱數(shù)在整個抱怨程度中所占的比重； K2 ： 表示檢驗結(jié)果在整個抱怨程度中所占的比重； n ： 顧客檢驗到有n次互開的比率34對購買一箱，m10的情形進行具體分析 。如果 為確定參數(shù)K1，K2，認為： 則 所以 當(dāng)互開率達到 時，抱怨達到極值，設(shè)為100. 所以 所以， 35以下就購買1、2箱情形作具體分析。用計算機進行1000次模擬檢驗，得互開次數(shù)統(tǒng)計結(jié)果為： 互開次數(shù)n 0 1 2 3 4 5 6 7 概率Pn（%） 13.7 26.9 28.6 17.9 8.7 2.9 0.9 0 購買一、二箱的平均互開率為（每箱抽樣10把）： 故購買一、二箱的平均抱怨程度分別為： 即購買一箱的團體顧客抱怨程度更大。啟示：從實際出發(fā)，察人所未察，見人所未見。36論文4（中國科大） 抱怨程度與互開的鎖具對