數(shù)學建模的定義及分類

數(shù)學建模數(shù)學建模的定義目前還沒有統(tǒng)一的定義數(shù)學模型是為一種特殊目的而建立的一個抽象的、簡化的結構。描述現(xiàn)實世界的一部分特征表現(xiàn)事物之間的一部分客觀聯(lián)系數(shù)學模型的分類微分方程模型差分方程模型層次分析模型線性規(guī)劃模型動態(tài)規(guī)劃模型圖論模型其它模型主要內容建模的方法和步驟——汪瑜婧圖論模型的建立——羅睿辭圖論模型的選擇和關系的簡化

——雷濤其它數(shù)學模型舉例——王堯建模的方法和步驟模型準備模型假設模型的建立模型求解與分析模型檢驗模型應用問題的提出2007CUMCMB題乘公交，看奧運給定若干條公交線路，以及在每條公交線路中任意相鄰的兩站之間所花費的時間。并且給定乘客在任意站點換乘的耗時要求給出任意兩公汽站點之間線路選擇問題的一般數(shù)學模型與算法，求出最佳的公交線路.模型的假設對”最優(yōu)”的理解有三個具有代表性的指標：時間最短花費最少最方便（換乘次數(shù)最少）不同的人群對最優(yōu)的理解不同,需要根據(jù)實際定義.可以根據(jù)需要定義代價函數(shù),三個指標的權重不同,代價值也不同。以時間最短為例模型的建立G=(V,E)每個車站：G的頂點每條公交線路相鄰兩點的連線：G的邊邊的權重：耗費時間點的權重：換乘時間并不是一個簡單圖，兩點間可能有多條邊5937ac

b(8)考慮a經(jīng)過b到c的最短路徑由于有換乘的情況，只記錄任意兩點間的最短路徑是不夠的。并非一個標準的圖論模型與經(jīng)典最短路徑問題比較567ac

b(8)Min(a,b)=5Min(b,c)=3Min(a,c)=5+6=113轉化成標準的圖論模型每條公交線路抽象為一層層與層之間相連的頂點均代表同一個車站它們之間的邊(虛線)的權值為換乘花費的時間

調用M*M次Dijkstra算法才能得到最優(yōu)解

M為公交線路的總數(shù)回顧上圖導致無法使用標準算法原因:Min(a,b)和Min(b,c)之間需要計算附加耗時不用換車的線路成為最佳路徑改進的想法:一次性地處理不用換車的情況567acMin(a,b)=5Min(b,c)=3Min(a,c)=5+6=113

b(8)模型的求解標準算法:每次選擇一個新頂點進行擴展所有頂點擴展完畢即為最優(yōu)解修改后的算法每次對一個頂點所能選擇的所有公交線路擴展所有不用換乘就能到達的頂點均在一次中處理所有頂點擴展完畢即為最優(yōu)解.算法描述一次將擴展出多個頂點,用最小值堆保存初始:起點對應的節(jié)點S入堆；并賦予標志信息Time(S)=0取堆頂,對此定點,逐一枚舉所有不用換乘就能到達的頂點,更新堆中對應點的標志信息.不斷重復取堆頂?shù)倪^程,直到取出的頂點為最終目標T

Time(T)即為所求舉例說明算法步驟3245132abcdefg1298159206119225考慮頂點b到頂點g的路徑問題重述加入步行的因素,即任意兩個車站之間人都可能通過步行到達,并給出步行的時間代價.由于每兩點之間均有步行路徑,每次擴展都將涉及到所有頂點,復雜度增加不少改進的辦法

預處理找到兩個相鄰頂點之間路徑的最小值,如果它加上兩個頂點的權值之后后,仍然小于一些其它的路徑,就可以將其它路徑刪除.這樣至少 可以刪除不少步行路徑考慮實際情況,可設定步行時間的上限.567ac加入步行的路徑并給定權值20算法的總結關鍵在于如何解決換乘的耗時擴展節(jié)點的策略與經(jīng)典算法不同算法實際用到了分支界限法的思想類似于回溯法，但是求解的目標不同。目標：找到使目標函數(shù)取極值的解。分支界限法思想以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹從一個點開始，每次以一定的策略擴展一些結點。每一個活結點一旦成為擴展結點，就一次性產(chǎn)生其所有子結點，并從活節(jié)點中移除。在產(chǎn)生的子結點中，導致不可行解或導致非最優(yōu)解的子結點被舍棄，其余的加入活結點表中。選擇擴展的節(jié)點從活結點表中選擇下一擴展結點可能有不同的方式隊列式分支限界法：先入先出的原則優(yōu)先隊列式分支限界法：選擇優(yōu)先級最高的節(jié)點進行擴展最大效益問題：最大值堆最小耗費問題：最小值堆一個簡單的例子印刷電路板將布線區(qū)域劃分為n×m個方格陣列精確的電路板布線問題要求確定連接方格a的中點到方格b的中點的最短布線方案。布線時電路只能沿直線或直角布線。為避免線路相交，已布線方格做上封閉標記，其他線路布線不允許穿過封閉區(qū)域。ab11a11b2211a12212b232211a12212b2332211a12212b23432211a12212b234532211a12212b23456632211a12212b2345676732211a12212b23485678678建模步驟的總結模型的準備提出問題，搜集數(shù)據(jù)。模型的假設根據(jù)實際情況，提出合理的假設簡化問題。模型的建立根據(jù)所作的假設分析對象的因果關系，利用對象的內在規(guī)律和適當?shù)臄?shù)學工具，構造各個量間的等式關系或其它數(shù)學結構。建模步驟的總結模型的分析與求解已建立的模型是否有標準解法轉化成標準模型對已有的標準解法修改，以適應模型的求解模型的檢驗靈敏性，魯棒性模型的應用圖論模型的引入

引例

現(xiàn)有6個人，任意兩人之間或者相互認識，或者相互不認識，證明這6個人中，或者有3個人彼此都認識，或者有3個人彼此不認識思路一只有6個人，人數(shù)非常少，可以枚舉任意兩人之間的關系，然后判斷每一種情況是否符合題意。如果所有情況都滿足，則命題成立。雖然只有6個人，但是這樣做的時間復雜度可不低，枚舉次數(shù)為215

只能借助計算機了。。。有沒有人可以直接證明的辦法呢？思路二有了圖論這個強大的工具我們還是像往常一樣，以人為頂點，關系為邊，建圖但是為了以后的直觀，這里圖的建立有一點小小的不同：如果兩個人之間相互認識，則在這兩個人(頂點)間連一條紅色邊，如果兩個人不認識，則在這兩個人(頂點)間連一條藍色邊(下面會看到這樣做的好處)那么這樣我們就得到了一個由紅邊和藍邊組成的6階完全圖我們實際上要證明的就是這個圖中或者存在一個紅三角形(認識)，或者存在一個藍三角形(不認識)任取一個頂點v0，由它連出5條邊到其它的頂點，這五條邊只有紅色和藍色兩種根據(jù)抽屜原理，肯定有一種顏色的邊有3條或3條以上,不妨設為紅色viv0vjvk如果vi,vj,vk之間的邊都是藍邊，則圖中存在一個藍三角形如果至少有1條為紅邊，那么它總會與v0發(fā)出的兩條紅邊組成一個紅三角形。這樣就證明了這個命題現(xiàn)有n根長度不同的小木棍，每根木棍數(shù)量無限，取出一些小木棍可以拼出一根長度為這些小木棍長度之和的木棍。現(xiàn)在要求最小的整數(shù)k，使得長度大于等于k的木棍都能夠被給出的n根小木棍拼出。例如，現(xiàn)在有3根小木棍，長度分別3,5,7它們可以拼出長度為3,5,6,7,8,9,10,11,12,13……的木棍，看上去5就是答案，怎么證明呢？可以考慮把能夠拼出來的木棍長度x根據(jù)模3的結果分成3類(0,1,2)對于xmod3=0,3能夠拼出來，那么6,9,12……等等模3為0的數(shù)都可以被拼出來對于xmod3=1，7能被拼出來，那么7,10,13……等等都能被拼出來對于xmod3=2，5能被拼出來，那么8,11,14……等等都能被拼出來也就是說，5確實是我們要求的答案這個題看上去似乎毫無頭緒，那就先看看簡單的情況吧！根據(jù)上面的證明，可以發(fā)現(xiàn)一種思路，不妨把上述結果推廣一下：設n根木棍的長度為L1,L2,…,Ln,不妨設L1為所有木棍中最短的現(xiàn)在把能夠拼出的木棍長度根據(jù)模L1的結果分為L1類(0,1…L1-1),若某一類中的數(shù)模L1的結果為i,則它們組成的集合為Si顯然，如果存在一個集合Si為空，則問題無解現(xiàn)在考慮所有集合都不為空的情況：設每個集合的最小元為b0,b1…bl1-1(集合不為空，肯定存在最小元)那么如何去求題目要求的k呢？考慮這樣一個值：k’=max{bn}-L1，1<=n<L1,(b0=0,不考慮)L1是最短的木棍，故k’>0.⑴k’不屬于任何Si集合,否則與k’是某個S中最小元。即k’不能被小木棍拼出。⑵對任意L>k’,設LSp，L+L1>max{bn}>=bp

故L>bp-L1而Lbp(modp)所以L>=bp，所以L一定能夠被拼出由以上兩點可知，k’一定是不能被拼出的木棍長度中的最大值那么k’+1就是我們要求的答案！還剩下最后一步：求b0,b1,b2…bl1-1,也就是每個集合中的最小元事實上，每一個能被拼出來的木棍長度x，都是從0開始，用已有的小木棍拼出來的。那么就可以把集合的編號看做頂點，小木棍的長度看邊的長度，建立一個圖。對于每個點i(集合i)，都連出n條邊，長度為L1,L2…Ln。對于長度為Lk的邊，連向編號為(i+Lk)modL1的頂點。對于從頂點i到j的一條長度為L的路徑，表示集合i中的一個數(shù)加上L后得到的數(shù)屬于集合j。對于任意一個能拼出來的數(shù)x(設xmodL1=p),根據(jù)上面的建圖規(guī)則，x一定是點0到p的一條路徑的長度。反過來，0到p的所有路徑長度都屬于Sp。所以，可以得出結論：Sp中的最小元其實就是頂點0到頂點p的最短路徑長度。有了這個結論，我們就可以很容易的求出序列{bn}了至此，這個問題也就被完美的解決數(shù)學建模——模型的選擇、關系的簡化很多問題都是通過建立圖論模型解決的圖論中常見的模型有序列、樹、各種圖如何有效選擇數(shù)學模型，簡化原問題中元素之間的關系是數(shù)學建模的關鍵題目坐船問題（改編自湖南省信息學省隊選拔賽試題）北大有n個學生去公園劃船：一只船最多坐2個人；出于娛樂目的，大家決定同船的2個人要么同姓要么同名；每個人都必須上船，且不能有腳踏多只船的情況問最少需要幾只船。例子6個同學：姚金宇，李金宇，姚峰宏，陳峰宏姚金宇姚峰宏陳峰宏李金宇姚金宇李金宇陳峰宏姚峰宏例子4個同學：陳峰宏，囧峰宏，羅睿辭，廖葉子羅睿辭同學想和廖葉子同學坐同一船是不行的，因為他們不同名也不同姓陳峰宏囧峰宏羅睿辭廖葉子陳峰宏囧峰宏羅睿辭廖葉子將每一同學視為一元素，元素之間的關系為同名或者同姓構圖是很自然的思路：2名同學同名或者同姓就連一條邊一條邊就代表了一種坐船的搭配方式用最少的邊覆蓋圖中的點——一般圖的最小邊覆蓋問題一般圖最大匹配問題，算法復雜，實現(xiàn)麻煩。建模姚金宇李金宇姚峰宏陳峰宏陳峰宏囧峰宏羅睿辭廖葉子建模圖是本題信息最充分、最自然的模型，但其中數(shù)據(jù)關系存在很多冗余，沒有充分利用原題的條件單獨看同名、同姓這2種關系，它們都是等價關系，具有傳遞性那么換一種模型構造如何？把圖轉換成樹來考慮建模對于原圖中的每一個連通分量，一定可以轉換成一棵二叉樹樹中一個結點的左孩子跟其同姓；一個結點的右孩子跟其同名。證明用反證法羅睿辭羅貫中羅納爾多廖睿辭羅睿辭羅貫中羅納爾多廖睿辭問題的解決含有n個點的連通分量，至少需要(n+1)div2只船使用貪心法，一定可以構造出一個只需(n+1)div2只船的解羅睿辭羅貫中羅納爾多廖睿辭羅納爾多是羅貫中的獨生子，去掉他們2個，樹依然連通羅睿辭廖睿辭廖睿辭依然是羅睿辭的獨生子，將它們分成一組羅貫中羅納爾多羅睿辭廖睿辭得到了一個最優(yōu)解貪心構造1、若葉子結點是父親的獨生子，則刪去它們2個，樹依然保持性質2、若父親結點有2個孩子重復以上步驟直至樹為空或者只剩一個結點為止貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云陳峰宏賈由陳云王云賈寶玉賈云貪心舉例貪心舉例陳峰宏賈由陳云王云賈寶玉賈云貪心舉例陳峰宏賈由陳云王云賈寶玉賈云小結通過無向圖到二叉樹的轉化，將一個復雜的匹配問題用簡單貪心解決了建模是一個去粗取精的過程，要盡可能利用對我們有利的信息，而忽略那些與我們目標無關的信息LCA與RMQ問題之間相互轉化，就是樹形模型與序列模型相互輔助的經(jīng)典例子希望本例會對同學們今后的解題有所幫助！

數(shù)學建?？雌饋?，總會讓人覺得是一種很抽象的概念如果把概念簡單一點，再通俗一點，大概就是把一些實際中碰到的問題抽象化，化簡成類似的數(shù)學問題，然后就可以用我們已經(jīng)知道的方法和工具來求解但是其實數(shù)學建模還有很多更深刻的含義和價值，不過已經(jīng)超出我可以講述的很清楚的范圍了其它數(shù)學模型舉例

而且，其實計算機實現(xiàn)的問題建模不見得就一定局限于圖論或者其他離散數(shù)學問題的這些方面還有很多方面都是可以利用數(shù)學建模思想和方法的而有些時候，其實都是我們不經(jīng)意間已經(jīng)在數(shù)學建模了，只是自己沒有在意而已。比如說數(shù)論中有關于素數(shù)篩選和測試，因式分解算法，一些特殊的進位制問題，快速冪取模等問題其實都可以用數(shù)學建模的方式來求解。

下面我要討論的是關于組合計數(shù)問題的一些討論。組合數(shù)學的問題隨處可見，他的歷史淵源扎根于古老的數(shù)學娛樂和游戲之中，而在當今社會中同樣發(fā)揮著重要的作用。簡單的說，組合數(shù)學研究一個集合的物體進行滿足一些規(guī)則的排列。具體的說來，組合數(shù)學往往研究的是這些排列的存在性，計數(shù)和分類。有時候還需要構造出滿足條件的一個或者多個最優(yōu)的排列。排列組合，容斥原理等都是這一方面的理論。其中很多時候都會廣泛的運用到遞推和生成函數(shù)，這也是建立數(shù)學模型并用計算機求解的優(yōu)勢所在之一。E1E2E3棋盤多項式問題簡述一個國際象棋棋盤，若兩個主教互相不攻擊，則當且僅當他們不處于同一條斜線上。我們可以討論在一個n×n的棋盤上放k個互相不攻擊的主教有多少種方法？例如，當n=8，k=6時，即在8×8的棋盤上放6個主教有5599888種方法布棋方案數(shù)Rk(C)設C是一個棋盤，Rk(C)表示把k個相同的棋子布到C中，且任意兩個棋子不能處于同一行或者同一列的方案數(shù)（把斜線換成行和列），并規(guī)定對于任意的棋盤C有R0(C)=1。棋盤多項式設C是棋盤，則R(C)=∑Rk(C)×xk叫做他的棋盤多項式可以證明步棋方案數(shù)Rk(C)具有下面的性質:1)對于任意的棋盤C和正整數(shù)k，如果k大于C中方格的總數(shù)，則Rk(C)=0；2)R1(C)等于C中的方格數(shù)3)設C1和C2是2個棋盤，如果C1經(jīng)過旋轉或