1、數學模型課程設計指導書林健良華南理工大學數學學院數學模型課程設計是我們十分重要的實踐教學環節，通過本環節的訓練，我們將從理論到實踐都有較大的提高，特別是鍛煉我們解決實際問題的動手能力。數學模型課程設計的總體要求：（1） 使用可視化編程語言， 比如 VC, VB , VFP, DELPHI 等。要設計一個主界面，每個問題要有問題描述。（2） 需要提交內容： 源程序及編譯后的可執行文件；實驗報告。 其內容包括算法原理簡介，主要變量說明，算法主要流程圖，主要界面及其操作說明。公平的席位分配問題問題：某校共有m個系，第i系學生數為ni(i=1,2,m)，校學生會共設N個席位.怎樣才能公平地把這些席位分

2、配給各系？設第i系分得席位數為Ni(i=1,2,m)，算法一：判別數法。流程如下：否是開始輸入ni與N計算n與ii全為整數嗎？計算i與r對i較大的個r系分配席位Ni=i+1Ni=i輸出各Ni結束剔除已分配席位的r系對剩余系分配剩余席位但要注意，每個參加分配的系，至少分得一個席位，故當=0時，取Ni=1, 并立即剔除這些系，對其余系進行再分配。算法二：最小極差法.模型為：注意：（1）實際上可把搜索區域控制在范圍以下內 ； （2）若在“判別數法”的基礎上進行調整，一般不能保證得此模型的最優解，只能得近似解。任務要求：（1）輸入N,m,ni(i=1,2,m) （2）輸出兩種算法的最優分配方案，并加以

3、比較。網絡最短路問題問題：對于賦權有向圖 D（V，A）。V為頂點集，A為有向邊集。設vs為圖D的始點，vt為圖D的終點，求從vs到vt的一條路P，使 達到最小值。 算法：Floyd算法 若要計算網絡中任兩點之間的最短路， 則令 （初始距離矩陣）當vi與vj不直接相連時，wij=， 令，其中，為最短距離矩陣,其中p為圖頂點數.可反映任兩點的最短路的距離。特別是對于無向圖，初始距離矩陣是對稱矩陣。任務要求：（1）輸入點數n；（2）輸入各點的坐標（或直接用鼠標點擊得出）（作圖用）；（3）輸入各邊長；（4）圖示網絡圖及從始點到終點的最短路（加粗）；（5）輸出從始點到終點的最短路總長。3v1 v2 v3

4、 v4 v5 21456-2例最速降線問題O(0,0)A(x,y)BxyC沿曲線C下降問題：一小球在重力作用下，沿曲線C無摩擦地從點O(0,0)滑到點B, 才能使所花時間T最短？(見右圖)算法: 由于質點在下降時所增加的動能應等于所減少的勢能，故質點在點A(x,y)處的速度v滿足.其中，m為質點的質量。從而，且利用微積分的微元法可知T可由曲線積分求得： 任務要求：（1）選擇點：B1(1,1), B2(1,2)；（2）選擇降線類型：直線、圓弧、拋物線、擺線；（3）動畫演示小球下降過程；（4）輸出耗用時間。 病床繞拐角問題問題：在某醫院走廊拐角處，垂直相交的兩通道寬度分別是1m與1.5m, 病床寬

5、為0.80m，問病床至多為多長才能被推過此拐角？算法：如右圖，延長AB與MF的延長線交于D，與MG的延長線交于C. 設BCG=，則易知BON=AFD=ADL=,等價于若令，則即知方程在內有實根。用二分法找得任務要求：（1）把問題一般化， 輸入兩通道的寬度a和b與病床的寬度w；（2）動畫演示移動過程；（3）輸出病床能繞過拐角的最大長度L。Steiner 最短樹問題 （n=3,4）問題：在平面上給定了n個點，怎樣用一些直線段把它們連接起來，使其總長最短？S點的概念：平面上一個點有三邊相連，且任兩邊的夾角都是120°，稱這樣的點為Steiner點，簡稱S點。已證明：為了求得n個點的Stei

6、ner 最短樹，至多添加n-2個S點。n=3時，即是費爾瑪問題。n=4時，至多添加2個S點。（1） 不需添加S點的情形（2） 需添加1個S點的情形（3）需添加2個S點的情形ABCD算法步驟如下：1. 在AB的左邊找1個點E,使ABE為等邊三角形；S2S1EABCDFTa2. 找出CDE的S點S1;3. 再找出ABS1的S點S2;4. 連接AS2, BS2, S2S1, S1C, S1D得一Steiner樹，記為Ta;5. 同理可得另一Steiner樹Tb;ABCDTbS3S46. 比較Ta與Tb的總長，確定Steiner最短樹；若在CD的右邊找1個點F,使CDF為等邊三角形, 則EF就是Ta的

7、總長. 另外, 若S1S2>S3S4, 則Ta的總長<Tb的總長.任務要求：（1）輸入點數n；（2）輸入各點的坐標（或直接用鼠標點擊得出）；（3）輸出Steiner 最短樹的圖形及其總長。追逐線問題問題: 在于輯私艦發現距西方c km處有一艘走私船正以勻速a沿直線向北行駛.輯私艦立即以速度b追趕, 追趕時方向始終指向走私船,試求輯私艦追逐路線和追上走私船的時間.算法: 選取走私船逃跑方向為y軸方向,輯私艦在B(c,0)位置時發現走私船在(0,0)處,顯然輯私艦、走私船的大小比它們運動的范圍小得多,可視為兩個質點.設在輯私艦發現走私船時算起的時間為t,走私船到達A=(0,at)點,輯

8、私艦到D=(x,y),因直線DA與路線相切,由幾何關系得ABxOyD (1)對x求導 (2)輯私艦的速度，且，從而 (3)結合(2)與(3)，并記k=a/b, 則追線的模型為 (4)若記p=dy/dx, 則(4)化為解得從而 (5)1) a<b時，k<1, (5)解得 (6)當輯私艦追上走私船時，D與A重合2) a=b時，k=1, (5)解得 (7),即輯私艦追不上走私船。3) a>b時，輯私艦更加追不上走私船。任務要求： （1）輸入參數a,b,c；（2）動畫演示追逐過程；（3）輸出追上時間（若不能追上，則給出提示）。翻硬幣問題問題：桌面上有n枚硬幣, 初態是全部正面向上,現

9、讓你每輪把其中的m (mn)枚翻轉,希望最終全部反面向上. 請建立數學模型研究n, m在什么條件下此問題有解或無解. 算法：先考慮2 mn的情況.設 ， （1）其中，t為n除以m的余數，, s為正整數. 記變量k 表示當前的正面數. 顯然，從開始，經過s輪純翻轉后k=t; 當k=0時，就成功了. 性質1. 選a個正面和m-a個反面的一輪翻轉后，正面數的變化量為. ，（2）特別是，做純翻轉時，. 性質2. 當k(<2m)為偶數時，只需再翻兩輪必會成功. 把以上的條件2mn , 改為 m n .條件2mn等價于（1）式中S2, 此情況以上已經討論清楚。以下只討論S=1的情況。設 n=m+t

10、(0t<m) (3)性質3. 設 k(2)是偶數，t1, j=min(k/2, t). 按如下方法做完兩輪翻轉后，正面數下降2j.任務要求：（1）輸入參數n，m；（2）能判斷參數n，m的合理性；（3）無解時給出提示，有解時自動演示過程。滑雪問題問題: 一種滑雪比賽規則如下：在滑雪的路上插有若干面旗子，每面旗子上面有一個自然數，稱為該旗子的分數。滑雪者在經過每面旗子時，可選擇繞過或不繞過該旗子。但每次繞過旗子的分數必須大于上次繞過旗子的分數。如何滑才能使繞過的旗子的分數總和最大？算法: 設共有n面旗子，cj表示第j面旗子的分數(j=1,n)，f 為總分數。再引入0-1變量則此問題可用如下0

11、-1規劃模型來描述：任務要求：（1）輸入旗子數n (20)及每面的分數；（2）輸出繞行方案與得分；（3）動畫演示過程。幻方問題問題: 若一個 n階由1n2的正整數組成，且每行、每列與兩對角線上的n個元素之和都相等. 則稱此矩陣為n階幻方. 每行的n個元素之和稱為幻和，并記為Sn. 給定正整數, 如何構造出一個n階幻方.算法: (1) 奇數階幻方的構造方法;(2)雙偶階幻方的構造方法;(3) 單偶階幻方的構造方法任務要求：（1）輸入階數n（312）；（2）可以自動分步輸出幻方圖；（3）可以由操作者分步構造,最后作出判斷。作業安排問題問題:設共有n項作業要完成，第j項的完成期限是Tj(j=1,2,

12、n) (序數)，且不妨設。第j項的需耗用時間為tj(j=1,2,n). 若無法全部按時完成，則應怎樣安排，使能按時完成的作業數目最多。算法:以下給出求解作業安排問題的Hodgson算法流程，其中m-已檢查過的作業數，k-在已檢查過的作業中，能按時完成的作業數，T0-完成k項作業共需時間，it-能按時完成的作業序號。開始輸入n,tj,Tj(j=1,2,n); m=0,k=0,T0=0m=n?m=m+1k=k+1, ik=m+1T0= T0+tm+1結束輸出令刪除第i0項，調整it.YesYesNoNo任務要求：（1）輸入作業數n (20)，tj, Tj (j=1,2,n)；（2）輸出最優方案；人

13、口預測問題問題:假設人口增長率與成正比, 則得推廣的Logistic 模型，如何利用此模型作人口預測.算法: 記，則得，分離變量得： , (*)(*)左邊=(*)兩邊求不定積分得解得利用t=0時，x=x0得，從而a=1 時，即為Logistic模型,以下是a=0.7,a=1,a=2對應的圖注：若用美國歷史人口數據檢驗，則取a=1.2比較好任務要求：（1）采用推廣的Logistic 模型；（2）輸入一串模擬人口數，及飽和量；（3）自動優化模型參數a; （4）輸出各期預測人口數和相對誤差；（5）輸出未來兩年的人口數，誤差絕對值之和；（6）畫出對比曲線。附錄 數學模型課程設計報告（說明書）參考式樣數

14、學模型課程設計報告 學號：20054000620XXXX 姓名：XXX 專業：信息管理與信息系統 Ø 課程設計簡介： 本課程設計是對一個學期以來所學的數學模型知識的一次實踐，是對數學模型這門課程的更進一步的學習。本次實踐要求我們運用學過的數學模型知識，從老師所給出的十二道題目中抽取四道Ø 程序架構及簡要操作說明 在做該課程設計的時候，我根據自己對各種模型的熟悉程度，選了四個模型來做，分別為：黑白棋、過河問題、折射定律、追逐問題。一 本程序的大致結構如下圖所示：歡迎界面黑白棋追逐問題關于作者折射定律過河問題詳細操作及說明詳細操作及說明詳細操作及說明詳細操作及說明二 簡要操作說

15、明 本程序的操作比較簡單，任何一個接觸過電腦的人都可以很容易地操作它，只需雙擊打開exe文件，然后在歡迎窗口里選擇一個按鈕，單擊它就可以選擇相關的模型進行操作。Ø 算法及功能實現細節一 黑白棋1 問題描述 任意拿出黑白兩種顏色的棋子共n個,排成一個圓圈.然后在兩顆顏色相同的棋子中間放一顆黑色棋子,在兩顆顏色不同的棋子中間放一顆白色棋子,放完后撤掉原來的棋子.再重復以上的過程,這樣放下一圈后就拿走前次的一圈棋子,觀察黑白棋子的變化規律。2 實現算法 根據題目要求，我們可以得到以下的變化規律： 黑黑黑白白白黑白 根據這個變化規律，我們很容易想起乘法的正負變化規律：111-1-1-11-1

16、* 因此，我們可以把黑色看成1，把白色看成-1，相鄰兩棋子間的棋子的顏色的代碼由這兩個棋子的代碼的相乘得到。3 實現細節及主要變量說明 基于以上的算法分析，我們可以在程序里定義一個數組wob(white or black之意)來存儲圓盤上棋子的顏色代碼，并且通過wobi:=wobi*wobi+1這樣的運算來確定在下一步中，第i個棋子的顏色。同時，為了直觀地表示棋子的變化，我還定義一個個變量q:=pi/n(n為棋子的總數)來使棋子順時針旋轉q角度。4 詳細操作說明及結果分析 首先，我們選擇打開黑白棋模型的程序如下圖所示： 這樣，我們就可以在面板上的edit框中輸入棋子的數目，其中，在edit框的

17、輸入中，內容為經過濾的，只能輸入09的數字而不能輸入其他，這就保證了輸入的正確性。輸入棋子數，初始化后，我們可得入下圖像： 接著，我們就可以按下一步觀察它的變化規律，其中，當你按了第一次下一步按鈕后，此按鈕的文字將會變成告訴用戶你已經進行了多少次運算了。5 本程序的特點： 本程序界面非常簡潔、整齊，操作非常簡單方便，并且容錯能力特別強，基本上不引起系統崩潰。同時，實現了所要求的所有功能。二 過河問題1 問題描述 n名商人帶了m個隨從乘船渡河，現此岸有一小船只能容納兩人，商人和隨從都可以劃船。隨從們 密謀，在河的任一岸，一旦隨從比商人多，就殺人搶劫。但是如何乘船渡河的大權由商人掌握。商人們怎樣才

18、能安全過河。2 實現算法 首先，必須要n>=m設（x,y）表示此岸有x個商人和y個隨從的狀態，商人們安全是指在兩岸都安全，故當x=0,n時，y=0,1,m均可，而當x=1,2,n時,此岸要求xy,對岸要求n-xm-y,綜合即:A) n>=mB) y=0,1,m 當x=0,n時C) xy且n-xm-y 當x=1,2,n時比如，當n=3,m=3時此岸在以下狀態時，商人們在兩岸都安全：(3,3)(3,2)(3,1)(3,0)(2,2)(1,1)(0,3)(0,2)(0,1)(0,0)我們要尋求模型的解，就是要尋找此岸狀態從(n,m,1)轉移到(0,0,0)的方案。根據題意，狀態轉移時要滿

19、足下面的規則：1) z從1變為0與從0變為1交替進行；2) 當z從1變為0時，即船從此岸到對岸，此岸人數減少1或2個；即(x,y,1)(u,v,0)時, ux, vy, u+v=x+y-1 或 u+v=x+y-23) 當z從0變為1時，即船從對岸到此岸，此岸人數增加1或2個；即(x,y,0)(u,v,1)時, ux, vy, u+v=x+y+1或u+v=x+y+24) 不重復已出現過的狀態，如(3,3,1)(3,1,0)(3,3,1)；3 實現細節及主要變量說明 實現這段程序需要兩個對全局變量x,y,xo,yo ;其中xo,yo用來表示商人和隨從最初的人數，而x,y表示商人和隨從停留在此岸的人

20、數。同時還需要一個全局變量boat，當boat=1時表示船此岸，當boat=0時，表示船在彼岸。經討論得知，當xo<yo或xo=yo>=4都是不可能安全渡河的，所以對這些不做考慮；而重點考慮xo>yo的情形。開始輸入商人和隨從人數xo,yox=xo,y=yoy>0Boat=1nx-y>2Xo-x=yo-yX=x-2Y=y-1 x=x-1X=x+1y=y+1Boat=0Boat=1ynynyny讓剩下的商人渡過河去結束4 詳細操作說明及結果分析 首先，進入模型求解界面如下圖所示：輸入兩個可求解的數xo:=7,yo:=6,運行可得如下結果： 經仔細分析可知，以上這個渡

21、河方案滿足商人的安全要求。5 本程序的特點： 這個程序也具有很好的容錯功能，同時又叫高效率的算法，整個界面看上去一目了然，使用起來非常方便。雖然在形象性方面做的有的不足，但，無可置疑，這里提供了一個可行的和可理解解決方案。三 折射定律1 問題描述 設有一光線從入射點射到出射點 ,該光線在上半平面的運動速度為常數v1,在下半的平面運動速度為常數v2.此光線應沿什么路徑運動才能使花費時間最短?2 實現算法 可以證明，當入射光線，出射光線與y軸的夾角i1,i2有如下關系：（*）時，所花費的時間最短. 所以，該程序主要的工作時找到x軸上一點x,使得（*）這個關系式成立，應此可以通過取中點法來求得該點，

22、比如當sini1/sini2>v1/v2時表明此時的i1比真實時的大，x點太靠近出射點，因此應在中點和入射點里找正確的x點。反之這在中點和出射點里找正確的x點。如此下去直到找到正確的x點。3 實現細節及主要變量說明 在這個程序里，有較多的全局變量。px,py表示原點的真實坐標；x1,y1表示入射點坐標；x2,y2表示出射點坐標；v1,v2表示光線在入射點和出射點的速度。4 詳細操作說明及結果分析 下圖為進入該模型進行操作時的畫面： 在右邊的的坐標系里單擊或在左邊的面板里安提示輸入兩個左邊點，同時輸入兩點速度，再按計算按鈕就可以取得折射點x了。示意圖如下：按運動按鈕就可以看到他們的運動軌跡和運動時間了，此時，如果輸入任意x坐標，然后按重新運動按鈕，就可以得到另外一條軌跡和他