數(shù)學(xué)建模雷濤羅睿辭王堯汪瑜婧學(xué)習(xí)教案

1、數(shù)學(xué)數(shù)學(xué)(shxu)建模建模 雷濤雷濤 羅睿辭羅睿辭 王堯王堯 汪汪瑜婧瑜婧第一頁，共67頁。第1頁/共66頁第二頁，共67頁。第2頁/共66頁第三頁，共67頁。 王堯第3頁/共66頁第四頁，共67頁。第4頁/共66頁第五頁，共67頁。公交線路.第5頁/共66頁第六頁，共67頁。以時(shí)間最短為例第6頁/共66頁第七頁，共67頁。5937ac b(8)第7頁/共66頁第八頁，共67頁。567ac b(8)Min(a,b)=5Min(b,c)=3Min(a,c)=5+6=113第8頁/共66頁第九頁，共67頁。每條公交線路抽象為一層層與層之間相連的頂點(diǎn)均代表同一個(gè)車站它們之間的邊(虛線)的權(quán)值為換乘

2、花費(fèi)(hufi)的時(shí)間 調(diào)用(dioyng)M*M次Dijkstra算法才能得到最優(yōu)解 M為公交線路的總數(shù)第9頁/共66頁第十頁，共67頁。(byng)換車的情況567acMin(a,b)=5Min(b,c)=3Min(a,c)=5+6=113 b(8)第10頁/共66頁第十一頁，共67頁。第11頁/共66頁第十二頁，共67頁。 Time(T)即為所求第12頁/共66頁第十三頁，共67頁。3245132abcdefg1298159206119225考慮考慮(kol)頂點(diǎn)頂點(diǎn)b到頂點(diǎn)到頂點(diǎn)g的路徑的路徑第13頁/共66頁第十四頁，共67頁。第14頁/共66頁第十五頁，共67頁。567ac加入步行

3、加入步行(bxng)的的路徑路徑并給定權(quán)值并給定權(quán)值20第15頁/共66頁第十六頁，共67頁。值的解。第16頁/共66頁第十七頁，共67頁。第17頁/共66頁第十八頁，共67頁。最小耗費(fèi)問題：最小值堆第18頁/共66頁第十九頁，共67頁。路(xinl)布線不允許穿過封閉區(qū)域。第19頁/共66頁第二十頁，共67頁。ab第20頁/共66頁第二十一頁，共67頁。11a11b第21頁/共66頁第二十二頁，共67頁。2211a12212b2第22頁/共66頁第二十三頁，共67頁。32211a12212b23第23頁/共66頁第二十四頁，共67頁。32211a12212b234第24頁/共66頁第二十五頁

4、，共67頁。32211a12212b2345第25頁/共66頁第二十六頁，共67頁。32211a12212b234566第26頁/共66頁第二十七頁，共67頁。32211a12212b23456767第27頁/共66頁第二十八頁，共67頁。32211a12212b23485678678第28頁/共66頁第二十九頁，共67頁。它數(shù)學(xué)結(jié)構(gòu)。第29頁/共66頁第三十頁，共67頁。第30頁/共66頁第三十一頁，共67頁。第31頁/共66頁第三十二頁，共67頁。思路(sl)一只有6個(gè)人，人數(shù)非常少，可以枚舉任意兩人之間的關(guān)系，然后判斷每一種情況是否符合題意。如果(rgu)所有情況都滿足，則命題成立。雖然

5、只有6個(gè)人，但是這樣做的時(shí)間復(fù)雜度可不低，枚舉次數(shù)為215 只能借助計(jì)算機(jī)了。有沒有人可以直接證明(zh ji zhn mn)的辦法呢？第32頁/共66頁第三十三頁，共67頁。思路(sl)二有了圖論這個(gè)強(qiáng)大的工具我們還是像往常(wngchng)一樣，以人為頂點(diǎn)，關(guān)系為邊，建圖但是為了以后的直觀，這里圖的建立有一點(diǎn)小小的不同：如果兩個(gè)人之間相互認(rèn)識(shí)，則在這兩個(gè)人(頂點(diǎn))間連一條紅色邊，如果兩個(gè)人不認(rèn)識(shí)，則在這兩個(gè)人(頂點(diǎn))間連一條藍(lán)色邊(下面會(huì)看到這樣做的好處)那么這樣我們就得到了一個(gè)由紅邊和藍(lán)邊組成的6階完全圖我們實(shí)際上要證明的就是這個(gè)圖中或者存在一個(gè)紅三角形(認(rèn)識(shí))，或者存在一個(gè)藍(lán)三角形(不

6、認(rèn)識(shí))第33頁/共66頁第三十四頁，共67頁。任取一個(gè)(y )頂點(diǎn)v0，由它連出5條邊到其它的頂點(diǎn)，這五條邊只有紅色和藍(lán)色兩種根據(jù)抽屜原理，肯定有一種顏色的邊有3條或3條以上,不妨設(shè)為紅色viv0vjvk如果vi,vj,vk之間的邊都是藍(lán)邊，則圖中存在一個(gè)(y )藍(lán)三角形如果至少有1條為紅邊，那么它總會(huì)與v0發(fā)出的兩條紅邊組成一個(gè)(y )紅三角形。這樣就證明了這個(gè)命題第34頁/共66頁第三十五頁，共67頁。現(xiàn)有(xin yu)n根長度不同的小木棍，每根木棍數(shù)量無限，取出一些小木棍可以拼出一根長度為這些小木棍長度之和的木棍?，F(xiàn)在要求最小的整數(shù)k，使得長度大于等于k的木棍都能夠被給出的n根小木棍拼

7、出。例如，現(xiàn)在有3根小木棍，長度分別3,5,7它們可以拼出長度為3,5,6,7,8,9,10,11,12,13的木棍，看上去5就是答案，怎么證明呢？可以考慮把能夠拼出來的木棍長度x根據(jù)模3的結(jié)果分成3類(0,1,2)對(duì)于(duy)x mod 3=0,3能夠拼出來，那么6,9,12等等模3為0的數(shù)都可以被拼出來對(duì)于(duy)x mod 3=1，7能被拼出來，那么7,10,13等等都能被拼出來對(duì)于(duy)x mod 3=2，5能被拼出來，那么8,11,14等等都能被拼出來 也就是說，5確實(shí)是我們要求的答案這個(gè)題看上去似乎毫無頭緒，那就先看看(kn kn)簡單的情況吧！第35頁/共66頁第三十六頁

8、，共67頁。根據(jù)上面的證明，可以發(fā)現(xiàn)一種思路，不妨把上述結(jié)果推廣一下：設(shè)n根木棍的長度為L1,L2,Ln,不妨設(shè)L1為所有木棍中最短的現(xiàn)在把能夠拼出的木棍長度根據(jù)模L1的結(jié)果分為L1類(0,1L1-1),若某一類中的數(shù)模L1的結(jié)果為i,則它們組成的集合為Si顯然，如果存在一個(gè)集合Si為空，則問題無解現(xiàn)在考慮所有集合都不為空的情況：設(shè)每個(gè)集合的最小元為b0,b1bl1-1 (集合不為空，肯定存在最小元)那么(n me)如何去求題目要求的k呢？第36頁/共66頁第三十七頁，共67頁?？紤]這樣一個(gè)值：k=max bn - L1，1=n0. k不屬于任何Si集合,否則與k是某個(gè)S中最小元。即k不能被小

9、木棍拼出。 對(duì)任意Lk,設(shè)L Sp，L+L1maxbn=bp 故Lbp-L1而L bp (mod p) 所以 L=bp，所以L一定能夠被拼出由以上兩點(diǎn)可知，k一定是不能被拼出的木棍長度中的最大值那么k+1就是我們(w men)要求的答案！第37頁/共66頁第三十八頁，共67頁。還剩下最后一步：求b0,b1,b2bl1-1,也就是每個(gè)集合中的最小元事實(shí)上，每一個(gè)能被拼出來的木棍長度x，都是從0開始，用已有的小木棍拼出來的。那么就可以把集合的編號(hào)看做頂點(diǎn)，小木棍的長度看邊的長度，建立一個(gè)圖。對(duì)于每個(gè)點(diǎn)i(集合i)，都連出n條邊，長度為L1,L2Ln。對(duì)于長度為Lk的邊，連向編號(hào)為(i+Lk) mo

10、d L1的頂點(diǎn)。對(duì)于從頂點(diǎn)i到j(luò)的一條長度為L的路徑，表示集合i中的一個(gè)數(shù)加上L后得到的數(shù)屬于集合j。對(duì)于任意一個(gè)能拼出來的數(shù)x(設(shè)x mod L1=p),根據(jù)上面的建圖規(guī)則，x一定是點(diǎn)0到p的一條路徑的長度。反過來，0到p的所有路徑長度都屬于Sp。所以，可以得出結(jié)論：Sp中的最小元其實(shí)(qsh)就是頂點(diǎn)0到頂點(diǎn)p的最短路徑長度。有了這個(gè)結(jié)論，我們就可以很容易的求出序列bn了至此，這個(gè)問題也就被完美的解決第38頁/共66頁第三十九頁，共67頁。第39頁/共66頁第四十頁，共67頁。第40頁/共66頁第四十一頁，共67頁。姚金宇 姚峰宏陳峰宏李金宇姚金宇 李金宇陳峰宏 姚峰宏第41頁/共66頁第

11、四十二頁，共67頁。陳峰宏 囧峰宏羅睿辭廖葉子陳峰宏 囧峰宏羅睿辭 廖葉子第42頁/共66頁第四十三頁，共67頁。姚金宇李金宇姚峰宏陳峰宏陳峰宏囧峰宏羅睿辭廖葉子第43頁/共66頁第四十四頁，共67頁。第44頁/共66頁第四十五頁，共67頁。羅睿辭羅貫中羅納爾多廖睿辭羅睿辭羅貫中羅納爾多廖睿辭第45頁/共66頁第四十六頁，共67頁。羅睿辭羅貫中羅納爾多廖睿辭羅納爾多是羅貫中的獨(dú)生子，去掉他們2個(gè)，樹依然(yrn)連通羅睿辭廖睿辭廖睿辭依然是羅睿辭的獨(dú)生子，將它們分成一組羅貫中羅納爾多羅睿辭廖睿辭得到了一個(gè)最優(yōu)解第46頁/共66頁第四十七頁，共67頁。第47頁/共66頁第四十八頁，共67頁。陳峰

12、宏賈 由陳 云王 云賈寶玉賈 云第48頁/共66頁第四十九頁，共67頁。陳峰宏賈 由陳 云王 云賈寶玉賈 云第49頁/共66頁第五十頁，共67頁。陳峰宏賈 由陳 云王 云賈寶玉賈 云第50頁/共66頁第五十一頁，共67頁。陳峰宏賈 由陳 云王 云賈寶玉賈 云第51頁/共66頁第五十二頁，共67頁。陳峰宏賈 由陳 云王 云賈寶玉賈 云第52頁/共66頁第五十三頁，共67頁。陳峰宏賈 由陳 云王 云賈寶玉賈 云第53頁/共66頁第五十四頁，共67頁。第54頁/共66頁第五十五頁，共67頁。 數(shù)學(xué)建?？雌饋?，總會(huì)讓人覺得是一種很抽象的概念如果把概念簡單一點(diǎn)，再通俗一點(diǎn)，大概就是把一些實(shí)際中碰到的問題

13、抽象化，化簡成類似的數(shù)學(xué)問題，然后就可以用我們已經(jīng)知道的方法和工具來求解但是其實(shí)數(shù)學(xué)建模還有很多更深刻的含義和價(jià)值，不過已經(jīng)超出我可以講述的很清楚的范圍了其它其它(qt)數(shù)學(xué)模型舉數(shù)學(xué)模型舉例例第55頁/共66頁第五十六頁，共67頁。 而且，其實(shí)計(jì)算機(jī)實(shí)現(xiàn)的問題建模不見得就一定局限于圖論或者其他離散數(shù)學(xué)問題的這些方面還有很多方面都是可以利用數(shù)學(xué)建模思想和方法的而有些時(shí)候，其實(shí)都是我們不經(jīng)意間已經(jīng)在數(shù)學(xué)建模了，只是自己沒有在意而已。比如說數(shù)論中有關(guān)于素?cái)?shù)篩選和測(cè)試，因式分解算法，一些特殊的進(jìn)位制問題，快速冪取模等問題其實(shí)都可以用數(shù)學(xué)建模的方式來求解。第56頁/共66頁第五十七頁，共67頁。下面我

14、要討論的是關(guān)于組合計(jì)數(shù)問題的一些討論。組合數(shù)學(xué)的問題隨處可見，他的歷史淵源扎根于古老的數(shù)學(xué)娛樂和游戲之中，而在當(dāng)今社會(huì)中同樣發(fā)揮著重要的作用。簡單的說，組合數(shù)學(xué)研究一個(gè)集合的物體進(jìn)行滿足一些規(guī)則的排列。具體的說來，組合數(shù)學(xué)往往研究的是這些排列的存在性，計(jì)數(shù)和分類。有時(shí)候還需要構(gòu)造出滿足條件的一個(gè)或者多個(gè)最優(yōu)的排列。排列組合，容斥原理等都是這一方面的理論。其中很多時(shí)候都會(huì)廣泛的運(yùn)用到遞推和生成函數(shù)，這也是建立數(shù)學(xué)模型并用計(jì)算機(jī)求解的優(yōu)勢(shì)所在之一。 第57頁/共66頁第五十八頁，共67頁。E1E2E3第58頁/共66頁第五十九頁，共67頁。 一個(gè)國際象棋棋盤，若兩個(gè)主教互相不攻擊，則當(dāng)且僅當(dāng)他們不

15、處于同一條斜線上。 我們可以討論在一個(gè)nn的棋盤上放k個(gè)互相不攻擊的主教有多少種方法？ 例如，當(dāng)n=8，k=6時(shí)，即在88的棋盤上放6個(gè)主教有5599888種方法問題簡述第59頁/共66頁第六十頁，共67頁。布棋方案數(shù)Rk(C)設(shè)C是一個(gè)棋盤，Rk(C)表示把k個(gè)相同的棋子布到C中，且任意兩個(gè)棋子不能處于同一行或者同一列的方案數(shù)（把斜線換成行和列），并規(guī)定對(duì)于任意的棋盤C有 R0(C)=1。棋盤多項(xiàng)式設(shè)C是棋盤，則R(C)=Rk(C)xk叫做他的棋盤多項(xiàng)式第60頁/共66頁第六十一頁，共67頁?？梢宰C明步棋方案數(shù)可以證明步棋方案數(shù)R Rk k(C)(C)具有下面的性質(zhì)具有下面的性質(zhì): : 1)

16、 對(duì)于任意的棋盤C和正整數(shù)k，如果k大于C中方格的總數(shù)，則Rk(C)=0； 2) R1(C)等于 C中的方格數(shù) 3) 設(shè)C1和C2是2個(gè)棋盤，如果C1經(jīng)過旋轉(zhuǎn)或者翻轉(zhuǎn)變成了C2,則Rk(C1)= Rk(C2) 4) 設(shè)Ci是從棋盤C中去掉指定的方格所在的行和列以后剩下的棋盤，C1是從棋盤C中去掉指定的方格以后剩下的棋盤，則有Rk(C)= Rk-1(Ci)+ Rk(C1)（k=1） 5) 設(shè)棋盤C由兩個(gè)子棋盤C1和C2組成，如果C1和C2的步棋方案是互相獨(dú)立的，則有Rk(C)=Ri(C1) *Rk-i(C2)第61頁/共66頁第六十二頁，共67頁。顯然，在上述定義中當(dāng)k大于棋盤的格子數(shù)時(shí)Rk(C

17、)=0，所以R(C)一般只有有限項(xiàng)。例如對(duì)于R(AT)=R0(AT)+R1(AT) x+R2(AT)x2=1+2x+x2第62頁/共66頁第六十三頁，共67頁。根據(jù) Rk(C)的性質(zhì)不難得到R(C)的性質(zhì) R(C)=xR(Ci)+R(C1) R(C)=R(C1)*R(C2) 此后我們就用這兩條性質(zhì)計(jì)算棋盤多項(xiàng)式第63頁/共66頁第六十四頁，共67頁。另外，我們回到剛才的問題我們可以注意到白格主教和黑格主教是不會(huì)互相攻擊的所以問題可以化簡為白格放i(i=k)個(gè)棋子和黑格放k-i個(gè)棋子分別處理而且處理方法是一樣(yyng)的。為了直觀，我們把白格從棋盤中抽出小方格和棋盤都順時(shí)針旋轉(zhuǎn)45度，再壓縮，黑格同樣最后都可以化建成左圖情況我