初等數(shù)學建模方法課件

1、第2章初等數(shù)學建模方法2.1有關自然數(shù)的幾個模型2.2狀態(tài)轉移問題2.3量綱分析法2.4類比建模方法返回第1頁，共64頁。2.1有關自然數(shù)的幾個模型2.1.1鴿籠原理 鴿籠原理又稱為抽屜原理.把;N個蘋果放入n (nN)個抽屜里.則必有一個抽屜中至少有2個蘋果. 間題1如果有;N個人.其中每個人至多認識這群人中的n(nN)個人(不包括自己)則至少有兩個人所認識的人數(shù)相等. 思想和啟發(fā)我們按認識人的個數(shù).將;N個人分為0,1,2,. ,n類.其中k(0kn)類.表T認識k個人.這樣形成0、十1個“鴿籠”.若nN-1.則;N個人分成不超過;N- 1類.必有兩人屬于一類.也即有兩個人所認識的人數(shù)相等

2、;若n=N -1.此時注意到。類和;N類必有一個為空集.所以不空的“鴿籠”至多為;N- 1個.也使結論成立.下一頁返回第2頁，共64頁。2.1有關自然數(shù)的幾個模型 問題2在一個邊長為1的正三角形內最多能找到幾個點.而使這些點彼此間的距離大于0.5. 思想和啟發(fā) 邊長為1的正三角形ABC.分別以A,B.C為中心.0. 5為半徑圓弧將三角形分為生個部分(圖2.1).則四部分中任一部分內兩點距離都小于0.5.由鴿籠原理知道.在三角形內最多能找生個點.使彼此間距離大于0. 5.且確實可找到如A.B.C及三角形中心生個點. 間題3能否在8X8的方格表ABCD的各個空格中.分別填寫1 .2 .3這3個數(shù)中

3、的任一個.使得每行、每列及對角線AC. BD的各個數(shù)的和都不相同?為什么?上一頁下一頁返回第3頁，共64頁。2.1有關自然數(shù)的幾個模型 思想和啟發(fā)若從考慮填法的種類人手.情況太復雜;這里我們注意到.方格表中行、列及對角線的總數(shù)為18個;而用1.2.3填人表格.每行、列及對角線都是8個數(shù).8個數(shù)的和最小為8.最大為22.共有22-8十1=17種;利用鴿籠原理.18個“鴿”放入17個“鴿籠”.必有兩個在一個“鴿籠”.也即必有兩個和相同.所以題目中的要求無法實現(xiàn). 間題思考在一個邊長為1的正三角形內.若要彼此間距離大于上.最多能找到幾個點?2. 1. 2“奇偶校驗”法 所謂“奇偶校驗”.是指如果兩個

4、數(shù)都是奇數(shù)或偶數(shù).則稱這兩個數(shù)具有相同的奇偶性;若一個數(shù)是奇數(shù).另一個數(shù)是偶數(shù).則稱具有相反的奇偶性.在組合幾何中會經(jīng)常遇到類似的問題.上一頁下一頁返回第4頁，共64頁。2.1有關自然數(shù)的幾個模型 間題1(鋪瓷磚問題)要用20塊方形瓷磚鋪設如圖2. 2所T圖形的地面.但當時商店只有長方形瓷磚.每塊大小等于方形的兩塊.一個人買了20塊長方形瓷磚.試著鋪地面.結果弄來弄去始終無法完整鋪好.證明用20塊長方形瓷磚鋪好如圖2. 2所示地面是不可能的. 思想和啟發(fā)問題在于用20塊長方形瓷磚正好鋪成圖2. 2所示的地面的可能性是否存在?只有可能性存在才談得上用什么方法鋪的問題. 為此.在圖2. 2上白、黑

5、相間地染色.然后仔細觀察.發(fā)現(xiàn)共有19個白格和21個黑格.一塊長方形瓷磚可蓋住一白一黑兩格.所以鋪上19塊長方形瓷磚.(無論用什么方法).總要剩下2個黑格沒有鋪.而一塊長方形瓷磚是無法蓋住2個黑格的.唯一的辦法是把最后一塊瓷磚一斷為二.上一頁下一頁返回第5頁，共64頁。2.1有關自然數(shù)的幾個模型在鋪瓷磚問題中.同色的兩個格子具有相同的奇偶性.異色的兩個格子具有相反的奇偶性.長方形瓷磚顯然只能覆蓋具有相反奇偶性的一對方格.因此.把19塊長方形瓷磚在地面上鋪好后.只有在剩下的兩個方格具有相反的奇偶性時.才有可能把最后一塊長方形瓷磚鋪上.由于剩下的兩個方格具有相同的奇偶性.因此無法鋪上最后一塊長方形

6、瓷磚.這就從理論上證明了用20塊長方形瓷磚鋪好如圖2. 2所示地面是不可能的.任何改變鋪設方式的努力都是徒勞的. 間題2(菱形十二面體上的H路徑問題)沿一菱形十二面體各棱行走.要尋找一條這樣的路徑:它通過各頂點恰好一次.該問題被稱為Hamilton路徑問題.上一頁下一頁返回第6頁，共64頁。2.1有關自然數(shù)的幾個模型 思想和啟發(fā)我們注意到菱形十二面體每個頂點的度或者為3或者為生.所謂頂點的度是指通過這一頂點的棱數(shù)(圖2. 3 ).且每3度頂點剛好與3個生度頂點相連.而每個2度頂點剛好與2個3度頂點相連.因此一個Hamilton路徑必是3度與2度頂點交錯.若存在Hamilton路徑.則3度頂點個

7、數(shù)與2度頂點個數(shù)要么相等.要么相差1.用奇偶校驗法3度頂點為奇數(shù)頂點.生度頂點為偶數(shù)頂點.奇偶配對.最多只能余1個;而事實上菱形十二面體中.有3度頂點8個.2度頂點6個;得結論:菱形十二面體中不存在Hamilton路徑. 數(shù)學中許多著名的不可能的證明都要用到奇偶校驗.上一頁下一頁返回第7頁，共64頁。2.1有關自然數(shù)的幾個模型例如歐幾里得證明厄是無理數(shù).就是用的奇偶性(讀者不妨自己動手做一下).奇偶校驗在粒子物理學也有很重要的作用.1957年美籍華人楊振寧和李政道推翻了“寧宙守恒定理”.由此獲得了諾貝爾獎.其中就是運用了奇偶校驗方法. 由上可以看出.奇偶校驗方法巧妙而簡單.極富創(chuàng)造力.在估計事

8、情不可能成立時.可考慮使用奇偶性這一方法來論證. 實例練習 (1)假設你有一張普通的國際象棋盤一組對角上的兩個方格被切掉.這樣棋盤上只剩下62個方格.若你還有31塊骨牌.每塊骨牌的大小為1X2方格.試說明用互不重疊的骨牌完全覆蓋住這張殘缺的棋盤是不可能的.上一頁下一頁返回第8頁，共64頁。2.1有關自然數(shù)的幾個模型 (2)設一所監(jiān)獄有62間囚室其排列類似8X8棋盤.看守長告訴關押在一個角落里的囚犯.只要他能夠不重復地通過每間囚室到達對角的囚室(所有相鄰囚室間都有門相通).他將獲釋.問囚犯能否獲得自由? (3)某班有29個學生坐成7行7列.每個座位的前后左右的座位叫做它的鄰座.要讓29個學生都換

9、到他的鄰座上去.問是否有這種調換位置的方案?2. 1. 3自然數(shù)的因子個數(shù)與獄吏問題 令d (n)為自然數(shù)0、的因子個數(shù).則d (n)有的為奇數(shù).有的為偶數(shù).見表2.1上一頁下一頁返回第9頁，共64頁。2.1有關自然數(shù)的幾個模型 我們發(fā)現(xiàn)這樣一個規(guī)律.當且僅當n為完全平方數(shù)時.d(n)為奇數(shù);這是因為n的因子是成對出現(xiàn)的.也即n= ab;只有n為完全平方數(shù).才會出現(xiàn)n=a2的情形.d(n)才為奇數(shù). 下面我們利用上述結論研究一個有趣的問題. 獄吏間題某土國對囚犯進行大赦.讓一獄吏n次通過一排鎖著的7、間牢房.每通過一次按所定規(guī)則轉動門鎖.每轉動一次.原來鎖著的被打開.原來打開的被鎖上;通過n次

10、后.門鎖開著的.牢房中的犯人放出.否則犯人不得獲釋.轉動門鎖的規(guī)則是這樣的:第一次通過牢房.要轉動每一把門鎖.即把全部鎖打開;第二次通過牢房時.從第二間開始轉動.每隔一間轉動一次;第k次通過牢房.從第k間開始轉動.上一頁下一頁返回第10頁，共64頁。2.1有關自然數(shù)的幾個模型每隔k-1間轉動一次;問通過n次后.哪些牢房的鎖仍然是打開的? 思想和啟發(fā)牢房的鎖最后是打開的.則該牢房的鎖要被轉動奇數(shù)次;如果把7、間牢房用1 .2.n編號.則第k間牢房被轉動的次數(shù).取決于k是否被1 .2. .n整除.也即k的因子個數(shù).利用自然數(shù)因子個數(shù)定理.我們得到結論:只有編號為完全平方數(shù)的牢房門仍是開著的.2.

11、1. 4相識問題 間題在s人的集會上.總會有3人互相認識或互相不認識. 思想和啟發(fā)在互相認識或互相不認識中.強調“互相”.因此.對于單一認識問題不子考慮.因而論證結果時.可分情況討論.上一頁下一頁返回第11頁，共64頁。第12頁，共64頁。2.1有關自然數(shù)的幾個模型 解題過程設6人為A1.A2.As下面分兩種情形: (1)A1至多只和兩個人相識.不妨設A1不認識A2.A3.A4;若A2.A3.A4互相都認識.則結論成立;若A2.A3.A4中有兩人不認識.則加上A1.有3人互不相識. (2)A1至少和3人相識.不妨設A1認識A2.A3.A4;若A2.A3.A4互不相識.則結論成立;若A2.A3.

12、A4有兩人相識.加上A1則有3人互相認識. 這樣.我們就證明了結論成立. 這個問題的討論.也可以采用幾何模擬的方法:在平面上問出6個點表示6個人.兩點間存在連線.表示兩人相識;只需說明.圖中必有3點組成三角形(有3人相識).或有3點之間沒有一條連線(3人互不相識)即可.上一頁下一頁返回第13頁，共64頁。2.1有關自然數(shù)的幾個模型 實例練習 1.9個人的集會中一定有3個人互相認識或生個人互相不認識. 2. 12個人的集會中一定有3個人互相認識或者5個人互相不認識. 3. 17個科學家中.每個科學家都和其他科學家通信.他們之間討論3個題目.且任意兩個科學家之間只討論1個題目.證明其中至少有3名科

13、學家.他們互相通信中討論的是同一題目.上一頁返回第14頁，共64頁。2. 2狀態(tài)轉移問題 本節(jié)介紹人、狗、雞、米過河及商人過河兩種狀態(tài)轉移問題.對于這類智力游戲經(jīng)過一番邏輯思索是可以找出解決辦法的.這里用數(shù)學模型求解一是為了給出建模的不例.二是因為這類模型可以解決相當廣泛的一類問題.比邏輯思索的結果容易推廣.解決這種問題的方法.有狀態(tài)轉移法、圖解法及用圖的鄰接矩陣等.2. 2. 1人、狗、雞、米問題 間題人、狗、雞、米均要過河.船上除1人劃船外.最多還能運載一物.而人不在場時.狗要吃雞.雞要吃米.問人、狗、雞、米應如何過河? 思想和啟發(fā)過河中.根據(jù)限制“人不在場時.狗要吃雞.雞要吃米”.因而.

14、考慮河兩岸狀態(tài)時.有些狀態(tài)是允許的.如狗和米在一起是可以的;有些狀態(tài)是不允許的.下一頁返回第15頁，共64頁。2. 2狀態(tài)轉移問題如雞和米在一起就不可以.如果假設人、狗、雞、米要從河的南岸到河的北岸.由題意.在過河的過程中.兩岸的狀態(tài)要滿足一定條件.所以該問題為有條件的狀態(tài)轉移問題. 解題過程 (1)允許狀態(tài)集合. 用(W.X.y.z).其中W.X.y.Z=0或1.表T南岸的狀態(tài).例如.(1 1,1 ,1)表示它們都在南岸;(0,1,1,0)表T狗、雞在南岸.人、米在北岸.很顯然有些狀態(tài)是允許的.有些狀態(tài)是不允許的.用窮舉法可列出全部70個允許狀態(tài)向量為: (1 .1 .1.1).(1.1.1

15、.0).(1.1.0.1).(1.0.1.1).(1.0.1.0).(0.0.0.0).(0.0.0.1).(0.0.1.0).(0.1.0.0).(0.1.0.1).上一頁下一頁返回第16頁，共64頁。2. 2狀態(tài)轉移問題 將上述10個可取狀態(tài)向量組成的集合記為s.稱s為允許狀態(tài)集合. (2)狀態(tài)轉移方程. 對于一次過河.可以看成一次狀態(tài)轉移.用向量來表示決策.如(7,0,0,7)表示人.米過河.令d為允許決策集合.則 d=f (1.X.y.Z) X十y十Z=0或1注意到D的形式.可得下述狀態(tài)轉移方程 s(t+1)=s t十(-1)t dt (2. 2. 1)式中.st=(wt、xt、yt

16、、zt)表T第k次狀態(tài)dt 2) ,因為A A = A 所以而從vi到 vj 長k十1的道路無非是從二經(jīng)k步到某頂點vj (1L n),再從v走一步到vj;由歸納假設從v到v，長為k的道路共計:a條而從v到v長為1的道路為aij條所以長為k十1的從v經(jīng)k步到v再一步到v的道路共有aa條故從v經(jīng)k十1步到v的路徑共有 條. 下面對問題分析及求解.上一頁下一頁返回第21頁，共64頁。2. 2狀態(tài)轉移問題 假設渡河是從南岸到北岸.(m，n)表示南岸有m個商人.n個隨從.全部的允許狀態(tài)共有10個.為v1 = (3 .3).v2 =(3 .2).v3=(3 .1).v4=(3.0).v5 =(2,2)v

17、6= (11)v7= (0,3).v8= (0.2).v9= (0.1).v10 =(0.0)以V= v1,v2.v10為頂點集.考慮到奇數(shù)次渡河及偶數(shù)次渡河的不同.我們建立兩個鄰接矩陣.即上一頁下一頁返回第22頁，共64頁。2. 2狀態(tài)轉移問題其中A表示從南岸到北岸渡河的圖的鄰接矩陣.則B=A工表示從北岸到南岸渡河的圖的鄰接矩陣. 由定理2. 1.我們應考慮最小的k.使得(AB)AA中1行10列的兀索不為0,此時2k十1即為最少的渡河次數(shù).而矩陣(AB)AA中1行10列的兀索為最佳的路徑數(shù)目. 經(jīng)過計算k=5時.(AB)A的第1行10列兀索為2.所以需11次渡河.有兩條最佳路徑. (2)多步

18、決策法. 記第k次渡河前此岸的商人數(shù)為二、隨從數(shù)為yk, k=1 ,2,.,n. xk ,yk=0,1 .2 .3.將二維向量sk =(xk, yk)定義為狀態(tài).安全渡河條件下的狀態(tài)集合稱為允許狀態(tài)集合.記作s.不難寫出上一頁下一頁返回第23頁，共64頁。2. 2狀態(tài)轉移問題S=(x ,y) x=0 ,y=0,1,2,3; x=3,y=0,12,3;x=y=1,2 (2 .2.3)記第k次渡船上的商人數(shù)為uk，隨從數(shù)為vk，將二維向量dk=(uk, vk)定為決策.允許決策集合記作D.由小船的容量可知D=(u,v) u+v=1,2 (2. 2.4)因為k為奇數(shù)時船從此岸駛向彼岸.k為偶數(shù)時船由

19、彼岸駛向此岸.所以狀態(tài)sk隨決策dk變化的規(guī)律是式(2. 2.5)稱為狀態(tài)轉移律.這樣.制訂安全渡河方案可歸結為如下的多步?jīng)Q策問題: 上一頁下一頁返回第24頁，共64頁。2. 2狀態(tài)轉移問題求決策dk EDC (k=1 ,2,.,n).使狀態(tài)、AES按照轉移律式(2. 2. 3).由初始狀態(tài)s1=(3,3)經(jīng)有限步n到狀態(tài)sn+1= (0,0). 模型求解一般對于復雜多步?jīng)Q策問題.模型求解是根據(jù)式(2.2.3)一式(2. 2.5)通過編程用計算機求解的但對于商人和隨從人數(shù)不多的簡單情況.用圖解法求解更為方便. (3)圖解法求解. 在xOy平面坐標系上出圖2. 6那樣的方格.方格點表示狀態(tài)s=

20、(x,y).允許決策dk是沿方格線移動1或2格.k為奇數(shù)時向左、下方移動.k為偶數(shù)時向右、上方移動.要確定一系列的dk使由s1=(3,3)經(jīng)過哪些點最終移至原點(0,0).上一頁下一頁返回第25頁，共64頁。2. 2狀態(tài)轉移問題 圖2. 6給出了一種移動方案.經(jīng)過決策d1,d2,.,d11.最終有s12=(0,0).這個結果很容易翻譯成渡河的方案.即上一頁返回第26頁，共64頁。2.3量綱分析法 量綱分析是20世紀初提出的.是物理領域中建立數(shù)學模型的一種方法.它是在經(jīng)驗和實驗的基礎上.利用物理定律的量綱齊次原則.確定各物抑量之間的關系.2. 3. 1量綱齊次原則與Pi定理 如果有人告訴你.1公

21、斤= 20厘米.你一定會認為這是錯的.因為你潛意識里.這是兩種不同的量.是根本無法進行比較的.是的.我們知道.許多物理量是有量綱的.有些物理量的量綱是基本的.另一些物理量的量綱則可以由基本量綱根據(jù)其定義或某些物理定律推導出來.例如在動力學中.把長度2.質量m和時間r的量綱作為基本量綱.記為下一頁返回第27頁，共64頁。2.3量綱分析法l=L ，m=M, t=T而速度v.力廠的量綱可表示為v=LT. f=MLT. 在國際單位制中.有7個基本量:長度、質量、時間、電流、溫度、光強度和物質的量.它們的量綱分別為L,M,T, I,O,J和N稱為基本量綱.任一個物理量v的量綱都可以表成基本量綱的冪次之積

22、.即 量綱齊次性原則用數(shù)學公式表示一個物理定律時.等式兩端必須保持量綱一致. 量綱分析原理當度量量綱的基本單位改變時.公式本身并不改變.例如.無論長度取什么單位.矩形的面積總等于長乘以寬.即公式S=ab并不改變.上一頁下一頁返回第28頁，共64頁。2.3量綱分析法此外.在公式中只有量綱相同的量才能進行加減運算.例如面積與長度是不允許做加減運算的.這些限制在一定程度上限定了公式的可取范圍.即一切公式都要求其等式左右具有相同的量綱.具有這種性質的公式被稱為是“量綱齊次”的. 量綱分析就是在保證量綱一致的原則下.分析和探求物理量之間的關系.定理2. 2設n個物理量x1,x2 , .,xn之間存在一個

23、函數(shù)關系 f (x1, x2,.,xn)=0 (2.3.5)x1，x2，xn為基本量綱，mp2/ n2則說明A方是吃萬的.或者說對A方是不公平的.稱為對A的相對不公平度;如果p1/ n1p2/ n2.此時rA(10.10)= 0.2 .rA2(10.10)= 0.002與前一種情形相比后一種更公平. 建立了衡量分配方案的不公平程度的數(shù)量指標rA, rB后.制訂分配方案的原則是:相對不公平度盡可能小. 首先作如下假設:上一頁下一頁返回第49頁，共64頁。2.4類比建模方法 (1)每個單位的每個人都具有相同的選舉權利; (2)每個單位至少應該分配到一個名額.如果某個單位一個名額也不應該分到的話.則應將其剔除在分配之外; (3)在名額分配的過程中.分配是穩(wěn)定的.不受任何其他因索所干擾. 假設A,B雙方已經(jīng)分別占有n1,n2個名額.下面我們考慮這樣的問題.當分配名額再增加一個時.應該給八方還是給刀方.如果這個問題解決了.那么就可以確定整個分配方案了.因為每個單位至少應分配到一個名額.我們首先分別給每個單位一個席位.然后考慮下一個名額給哪個單位.直至分配完所有名