初等數(shù)學(xué)方法建模講稿

1、初等數(shù)學(xué)方法建模 現(xiàn)實世界中有很多問題，它的機(jī)理較簡單，用靜態(tài),線性或邏輯的方法即可建立模型，使用初等的數(shù)學(xué)方法，即可求解，我們稱之為初等數(shù)學(xué)模型。本章主要介紹有關(guān)自然數(shù)，比例關(guān)系，狀態(tài)轉(zhuǎn)移，及量剛分析等建模例子，這些問題的巧妙的分析處理方法，可使讀者達(dá)到舉一反三，開拓思路，提高分析, 解決實際問題的能力。第一節(jié) 有關(guān)自然數(shù)的幾個模型1.1鴿籠原理鴿籠原理又稱為抽屜原理，把個蘋果放入 個抽屜里，則必有一個抽屜中至少有2個蘋果。問題1：如果有個人，其中每個人至多認(rèn)識這群人中的個人（不包括自己），則至少有兩個人所認(rèn)識的人數(shù)相等。分析：我們按認(rèn)識人的個數(shù)，將個人分為類，其中類，表示認(rèn)識個人，這樣形成

2、 個“鴿籠”。若 ，則個人分成不超過 類，必有兩人屬于一類，也即有兩個人所認(rèn)識的人數(shù)相等；若 ，此時注意到類和類必有一個為空集，所以不空的“鴿籠”至多為個，也有結(jié)論成立問題2：在一個邊長為的正三角形內(nèi)最多能找到幾個點，而使這些點彼此間的距離大于.分析：邊長為1的正三角形 ，分別以為中心，為半徑圓弧，將三角形分為四個部分（如圖1-1 ），則四部分中任一部分內(nèi)兩點距離都小于 ，由鴿籠原理知道，在三角形內(nèi)最多能找四個點，使彼此間距離大于 ，且確實可找到如及三角形中心四個點。 圖111.2 “奇偶校驗”方法 所謂 “奇偶校驗”，即是如果兩個數(shù)都是奇數(shù)或偶數(shù)，則稱這兩個數(shù)具有相同的奇偶性；若一個數(shù)是奇數(shù)

3、，另一個數(shù)是偶數(shù)，則稱具有相反的奇偶性。在組合問題中，經(jīng)常使用“奇偶校驗”考慮配對問題。圖1-2問題1（菱形十二面體上的H路徑問題）：沿一菱形十二面體各棱行走，要尋找一條這樣的路徑它通過各頂點恰好一次，該問題被稱為Hamilton路徑問題。分析：我們注意到菱形十二面體每個頂點的度或者為或者為，所謂頂點的度是指通過這一頂點的棱數(shù)，如圖12；且每度頂點剛好與個度頂點相連，而每個度頂點剛好與個度 頂點相連。因此一個Hamilton路徑必是度與度頂點交錯，故若存在Hamilton 路徑，則度頂點個數(shù)，與度頂點個數(shù)要么相等，要么相差。用奇偶校驗法度頂點為奇數(shù)頂點，度頂點為偶數(shù)頂點，奇偶配對，最多只能余個

4、；而事實上菱形十二面體中，有度頂點個，度頂點個；可得結(jié)論，菱形十二面體中不存在Hamilton 路徑.1.3 自然數(shù)的因子個數(shù)與獄吏問題令 為自然數(shù) 的因子個數(shù)，則 有的為奇數(shù)，有的為偶數(shù)，見下表: n12345678910111213141516d(n)1223242434262445我們發(fā)現(xiàn)這樣一個規(guī)律，當(dāng)且僅當(dāng)為完全平方數(shù)時,為奇數(shù)；這是因為的因子是成對出現(xiàn)的,也即 ; 只有為完全平方數(shù), 才會出現(xiàn) 的情形，才為奇數(shù)。下面我們利用上述結(jié)論研究一個有趣的問題. 獄吏問題：某王國對囚犯進(jìn)行大赦，讓一獄吏n次通過一排鎖著的n間牢房，每通過一次按所定規(guī)則轉(zhuǎn)動門鎖, 每轉(zhuǎn)動一次, 原來鎖著的被打開

5、, 原來打開的被鎖上；通過n次后，門鎖開著的，牢房中的犯人放出，否則犯人不得獲釋。轉(zhuǎn)動門鎖的規(guī)則是這樣的，第一次通過牢房，要轉(zhuǎn)動每一把門鎖，即把全部鎖打開；第二次通過牢房時，從第二間開始轉(zhuǎn)動，每隔一間轉(zhuǎn)動一次；第k次通過牢房，從第k間開始轉(zhuǎn)動，每隔k-1 間轉(zhuǎn)動一次；問通過n次后，那些牢房的鎖仍然是打開的？問題分析： 牢房的鎖最后是打開的，則該牢房的鎖要被轉(zhuǎn)動奇數(shù)次；如果把n間牢房用編號，則第k間牢房被轉(zhuǎn)動的次數(shù)，取決于k是否為整除，也即k的因子個數(shù)，利用自然數(shù)因子個數(shù)定理，我們得到結(jié)論：只有編號為完全平方數(shù)的牢房門仍是開著的。14 相識問題問題：在6人的集會上，總會有3人互相認(rèn)識或互相不認(rèn)識

6、。分析：設(shè)6人為;下面分二種情形，1.至多只和兩個人相識，不妨設(shè)不認(rèn)識；若互相都認(rèn)識，則結(jié)論成立，若中有兩人不認(rèn)識，則加上，有三人互不相識. 2 至少和三人相識，不妨設(shè) 認(rèn)識；若互不相識結(jié)論成立，若有兩人相識，加上 則有三人互相認(rèn)識 。這樣，我們就證明了結(jié)論成立,這個問題的討論，我們也可以采用幾何模似的方法，如圖14圖1-4在平面上畫出六個點，表示6個人，兩點間存在連線，表示兩人相識；只需說明，圖中必有三點組成三角形（有三人相識），或有三點之間沒有一條連線（三人互不相識）即可，第二節(jié) 狀態(tài)轉(zhuǎn)移問題本節(jié)介紹兩種狀態(tài)轉(zhuǎn)移問題，解決這種問題的方法,有狀態(tài)轉(zhuǎn)移法，圖解法及用圖的鄰接距陣等。21 人、狗

7、、雞、米問題人、狗、雞、米均要過河，船上除1人劃船外，最多還能運載一物，而人不在場時，狗要吃雞，雞要吃米，問人，狗、雞、米應(yīng)如和過河？分析：假設(shè)人、狗、雞、米要從河的南岸到河的北岸，由題意，在過河的過程中，兩岸的狀態(tài)要滿足一定條件，所以該問題為有條件的狀態(tài)轉(zhuǎn)移問題。1. 允許狀態(tài)集合 我們用（w, x, y, z），w, x, y, z=0或1，表示南岸的狀態(tài)，例如（1，1，1，1）表示它們都在南岸，（0，1，1，0）表示狗，雞在南岸，人，米在北岸；很顯然有些狀態(tài)是允許的，有些狀態(tài)是不允許的，用窮舉法可列出全部10個允許狀態(tài)向量， (1, 1, 1, 1) (1, 1, 1, 0) (1, 1

8、, 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)我們將上述10個可取狀態(tài)向量組成的集合記為S，稱S為允許狀態(tài)集合 2、狀態(tài)轉(zhuǎn)移方程 對于一次過河，可以看成一次狀態(tài)轉(zhuǎn)移，我們用向量來表示決策，例（1，0，0，1）表示人，米過河。令D為允許決策集合， D= (1, x, y, z) : x+y+z=0 或 1 另外，我們注意到過河有兩種，奇數(shù)次的為從南岸到北岸，而偶數(shù)次的為北岸回到南岸，因此得到下述轉(zhuǎn)移方程， -(2.1)表示第k次狀態(tài)， 為決策向量.

9、 圖2-12. 人、狗、雞、米過河問題，即要找到， 且滿足（2.1）式。下面用狀態(tài)轉(zhuǎn)移圖求解將10個允許狀態(tài)用10個點表示，并且僅當(dāng)某個允許狀態(tài)經(jīng)過一個允許決策仍為允許狀態(tài)，則這兩個允許狀態(tài)間存在連線，而構(gòu)成一個圖, 如圖21 , 在其中尋找一條從（1，1，1，1）到（0，0，0，0）的路徑，這樣的路徑就是一個解, 可得下述路徑圖,圖2-2由圖22，有兩個解都是經(jīng)過7次運算完成，均為最優(yōu)解22 商人過河問題 三名商人各帶一個隨從乘船渡河，現(xiàn)有一只小船只能容納兩個人，由他們自己劃行，若在河的任一岸的隨從人數(shù)多于商人，他們就可能搶劫財物。但如何乘船渡河由商人決定，試給出一個商人安全渡河的方案。首先

10、介紹圖論中的一個定理G是一個圖，V（G）為G的頂點集，E(G)為G的邊集。 設(shè)G中有n個頂點; 為G的鄰接距陣，其中 定理1：設(shè)為圖的鄰接距陣，則中從頂點到頂點，長度為的道路的條數(shù)為中的行列元素.證： 對用數(shù)學(xué)歸納法 時，顯然結(jié)論成立; 假設(shè)時，定理成立， 考慮 的情形. 記的行列元素為 , 因為 , 所以 (2.2)而從 到 長的道路無非是從經(jīng)步到某頂,再從 走一步到；由歸納假設(shè)從到長為的道路共計條，而從到長為1的道路為條，所以長為的從經(jīng)步到再一步到的道路共有條，故從經(jīng)步到的路徑共有條.下面分析及求解 假設(shè)渡河是從南岸到北岸，（m，n）表示南岸有m個商人，n個隨從，全部的允許狀態(tài)共有10個 以為頂點集，考慮到奇數(shù)次渡河及偶數(shù)次渡河的不同，我們建立兩個鄰接距陣 其中 其中A表示從南岸到北岸渡河的圖的鄰接距陣，表示從北岸到南岸渡河的圖的鄰接距陣。由定理1、我們應(yīng)考慮最小的， 中1行10列的元素不為0，此時即為最少的渡河次數(shù)，而矩陣中1行10列的元素為最佳的路徑數(shù)目。經(jīng)過計算K=5時, 的第1行10列元素為2，所以需11次渡河，有兩條最佳路徑.最后我們用圖解法求解： 前面我們已求出問題的10種允許狀態(tài)，允許決策向量集合,狀態(tài)轉(zhuǎn)移方程為 , 如圖23，標(biāo)出10種允許狀態(tài)，找出從經(jīng)由允許狀態(tài)到原