數(shù)學建模初等模型講義課件

1、數(shù)學建模第二章 初等模型數(shù)學建模第二章 初等模型 第二章 初等模型公平席位計算按揭還款Markov鏈與Google網(wǎng)頁排名選址問題與費馬點切西瓜與差分方程 第二章 初等模型公平席位計算1. 公平席位計算問題三個系學生共200名(甲100, 乙60, 丙40), 學生代表會議設20席, 按比例分配, 三個系分別為10, 6, 4席.現(xiàn)因學生轉系, 三系人數(shù)為103, 63, 34, 問20席如何分配；若增加為21席, 又如何分配。對丙系公平嗎系別學生人數(shù)比例(%)20席的分配21席的分配比例結果比例結果甲10351.510.31010.8211乙6331.56.366.627丙3417.03.4

2、43.573總和200100.020.02021.0021最大余數(shù)分配1. 公平席位計算問題三個系學生共200名(甲100, 乙1. 公平席位計算按這種最大剩余法的另一個重大缺陷是人口悖論,即人數(shù)增加了較多反而導致席位減少.系別學生人數(shù)比例(%)21席的分配人數(shù)變化21席的分配比例結果比例結果甲10351.510.821111411.2911乙6331.56.627646.346丙3417.03.573343.364總和200100.021.002121221.0021乙系人數(shù)增加1人，按最大剩余法反而少了1席，丙系人數(shù)未增加，反而多了一席！1. 公平席位計算按這種最大剩余法的另一個重大缺陷是

3、人口悖論“公平”分配方法需要一個衡量公平分配的數(shù)量指標人數(shù)席位A方n1N1B方n2N2“公平”分配方法需要一個衡量公平分配的數(shù)量指標人數(shù)席位A方n說明A增加1席, 仍對 A不公平, 該席位應分給A.討論以下幾種情況設A, B已有N1, N2 席, 若增加1席, 問應分給A, 還是B？不妨設分配開始時 n1/N1 n2/N2 , 即原方案對A不公平, 這種情況最麻煩說明A增加1席, 仍對 A不公平, 該席位應分給A.討論感覺上, 分配給B會相對公平.這種感覺如何用數(shù)學描述, 并提煉成算法實現(xiàn).感覺上, 分配給B會相對公平.這種感覺如何用數(shù)學描述, 并提模型假設 學生會共有N個席位, 各系人數(shù)分別

4、為n1, n2, ., nm，若各系分配的席位為N1, N2, ., Nm, 則各系每席實際代表的人數(shù)分別為用目標函數(shù)衡量“公平度”模型假設用目標函數(shù)衡量“公平度”回到21席例子 (甲103, 乙63, 丙34), 按照標準1試算 系別人數(shù)比例Nni / n慣例分配ai標準1分配ai甲10310.815119.361010.3乙636.6157979丙343.570311.348.5總和2002121212121第21席應該分配乙系, 標準1的分配方案：10, 7, 4.ai比慣例分配的要小回到21席例子 (甲103, 乙63, 丙34), 按照可用列表方法解決標準1(類似可解決標準2與3)席

5、位可以看成是1位接1位分配的:每個系首先分配1位, 并標以下劃線;表中找出最大的下劃線, 把它右邊的數(shù)加以下劃線;重復步驟 , 直到下劃線數(shù)字的個數(shù)=21.1234567891011甲103 51.5 34.3 25.8 20.6 17.2 14.7 12.9 11.4 10.3 9.4 乙63 31.5 21.0 15.8 12.6 10.5 9.0 7.9 7.0 6.3 5.7 丙34 17.0 11.3 8.5 6.8 5.7 4.9 4.3 3.8 3.4 3.1 可用列表方法解決標準1(類似可解決標準2與3)席位可以看成是可用列表方法解決標準11234567891011甲103 5

6、1.5 34.3 25.8 20.6 17.2 14.7 12.9 11.4 10.3 9.4 乙63 31.5 21.0 15.8 12.6 10.5 9.0 7.9 7.0 6.3 5.7 丙34 17.0 11.3 8.5 6.8 5.7 4.9 4.3 3.8 3.4 3.1 1234567891011甲103 51.5 34.3 25.8 20.6 17.2 14.7 12.9 11.4 10.3 9.4 乙63 31.5 21.0 15.8 12.6 10.5 9.0 7.9 7.0 6.3 5.7 丙34 17.0 11.3 8.5 6.8 5.7 4.9 4.3 3.8 3.4

7、 3.1 可用列表方法解決標準11234567891011甲103 5可以歸納標準1的算法過程可能最大值出現(xiàn)多個, 則按某種約定來分配可以歸納標準1的算法過程可能最大值出現(xiàn)多個, 則按某種約定上述標準公平嗎? 是否存在公平的席位分配方法？公理化約定:上述標準公平嗎? 是否存在公平的席位分配方法？公理化約定:上述標準公平嗎? 是否存在公平的席位分配方法？最大剩余法滿足性質1, 不滿足性質2,3, 準則1滿足性質2, 3，但不滿足性質1. (見p285)經(jīng)證明，當m4, N m+3, 不存在滿足滿足3條性質的分配方案!從1930年后美國眾議員席位選舉采用相等比例法(EP)!上述標準公平嗎? 是否存

8、在公平的席位分配方法？最大剩余法滿足ini比例最大剩余(慣例)最小除數(shù)(規(guī)則1)相等比例(EP)19149091.49928890216601.66222314601.46222414501.45122514401.44122614001.40121711001.10121總和100000100100100100不滿足性質1的例子ini比例最大剩余最小除數(shù)相等比例19149091.4992相等比例法(EP)相等比例法(EP)練習與思考學校共1000名學生, 235人住A宿舍, 333人住在B宿舍, 432人住在C宿舍. 學生要組織一個10人的委員會. 使分別根據(jù)標準1與標準2給出分配方案.練習

9、與思考學校共1000名學生, 235人住A宿舍, 用房產(chǎn)在銀行辦理的貸款, 該貸款要按照銀行規(guī)定的利率支付利息。貸款形式 商業(yè)貸款和公積金貸款.還款形式 等額本息和等額本金.2. 按揭還款調(diào)整日期商業(yè)基準利率公積金利率2015.08.265.15%3.25%2015.06.285.40%3.50%2015.05.115.65%3.75%2015.03.015.90%4.25%2014.11.226.15%4.00%2012.07.076.55%4.50%2012.06.096.80%4.70%2011.07.077.05%4.90%2011.04.066.80%4.70%2011.02.096

10、.60%4.50%2010.12.266.40%4.30%2010.10.206.14%4.05%2008.12.235.94%3.87%2008.11.276.12%4.05%2008.10.307.20%2008.10.277.47%2008.10.097.47%4.86%2008.09.167.74%2007.12.217.83%5.13%2007.09.157.83%5.22%2007.08.227.56%5.04%2007.07.217.38%4.95%2007.05.197.20%4.86%如貸款50萬, 分20年還清, 年利率r , 問月供是多少？用房產(chǎn)在銀行辦理的貸款, 該貸款

11、要按照銀行規(guī)定的利率支付利息2.1 等額本金計算方法如貸款w=50萬本金, 分m=20年還清, 年利率q =6.55%, 問月供(還款額)x是多少？計算原則：每月歸還的本金額始終不變, 利息會隨剩余本金的減少而減少。固定則需n=240月還清, 月利率r =0.54583%.2.1 等額本金計算方法如貸款w=50萬本金, 分m=20年如貸款w=50萬本金, 分m=20年還清, 年利率q =6.55%, 問月供(還款額)x是多少？累計已還本金則需n=240月還清, 月利率r =0.54583%.每個月還款額是變化的如貸款w=50萬本金, 分m=20年還清, 累計已還本金則需月份每月本金 y每月利息

12、 z每月月供 x已還本金 s已付利息 p12083.3 2729.2 4812.5 2083.3 2729.2 22083.3 2717.8 4801.1 4166.7 5446.9 32083.3 2706.4 4789.7 6250.0 8153.3 42083.3 2695.0 4778.4 8333.3 10848.4 52083.3 2683.7 4767.0 10416.7 13532.0 62083.3 2672.3 4755.6 12500.0 16204.3 1202083.3 1375.9 3459.3 250000.0 246305.8 1212083.3 1364.6

13、3447.9 252083.3 247670.4 1222083.3 1353.2 3436.5 254166.7 249023.6 1232083.3 1341.8 3425.2 256250.0 250365.4 237 2083.3 45.5 2128.8 493750.0 328794.3 238 2083.3 34.1 2117.4 495833.3 328828.5 239 2083.3 22.7 2106.1 497916.7 328851.2 240 2083.3 11.4 2094.7 500000.0 328862.6 20年期的等額本金的月供列表月份每月本金 y每月利息

14、z每月月供 x已還本金 s已付利息月份每月本金 y每月利息 z每月月供 x已還本金 s已付利息 p1 2777.8 2729.2 5506.9 2777.8 2729.2 2 2777.8 2714.0 5491.8 5555.6 5443.2 3 2777.8 2698.8 5476.6 8333.3 8142.0 4 2777.8 2683.7 5461.5 11111.1 10825.7 5 2777.8 2668.5 5446.3 13888.9 13494.2 6 2777.8 2653.4 5431.1 16666.7 16147.6 90 2777.8 1379.7 4157.5

15、 250000.0 184901.0 91 2777.8 1364.6 4142.4 252777.8 186265.6 92 2777.8 1349.4 4127.2 255555.6 187615.0 93 2777.8 1334.3 4112.0 258333.3 188949.3 177 2777.8 60.6 2838.4 491666.7 246898.6 178 2777.8 45.5 2823.3 494444.4 246944.1 179 2777.8 30.3 2808.1 497222.2 246974.4 180 2777.8 15.2 2792.9 500000.0

16、246989.6 15年期的等額本金的月供列表月份每月本金 y每月利息 z每月月供 x已還本金 s已付利息2.2 等額本息計算方法計算原則：月供總額保持不變, 銀行從每月月供款中, 先收利息, 后收本金, 利息會不斷減少。固定如何求每月還款額x？2.2 等額本息計算方法計算原則：月供總額保持不變, 銀如貸款w=50萬本金, 分n=240月還清, 月利率r=0.54583%, 求每個月供？如貸款w=50萬本金, 分n=240月還清, 月利率r=s0=0s0=0月份每月本金 y每月利息 z每月月供 x已還本金 s已付利息 p1 1013.4 2729.2 3742.6 1013.4 2729.2

17、2 1019.0 2723.6 3742.6 2032.4 5452.8 3 1024.5 2718.1 3742.6 3056.9 8170.8 4 1030.1 2712.5 3742.6 4087.1 10883.3 5 1035.7 2706.8 3742.6 5122.8 13590.1 6 1041.4 2701.2 3742.6 6164.2 16291.3 120 1937.0 1805.6 3742.6 171132.7 277977.7 121 1947.5 1795.1 3742.6 173080.2 279772.7 122 1958.2 1784.4 3742.6 1

18、75038.4 281557.2 123 1968.8 1773.7 3742.6 177007.3 283330.9 237 3662.0 80.6 3742.6 488893.7 398099.3 238 3682.0 60.6 3742.6 492575.7 398160.0 239 3702.1 40.5 3742.6 496277.7 398200.5 240 3722.3 20.3 3742.6 500000.0 398220.8 20年期的等額本息的月供列表月份每月本金 y每月利息 z每月月供 x已還本金 s已付利息按揭年數(shù)首月月供還款總額支付利息款106895.83665114

19、.58165114.58155506.94746989.58246989.58204812.5828864.58328864.58254395.83910739.58410739.58304118.06992614.58492614.58按揭年數(shù)每月月供還款總額支付利息款105818.32698198.02198198.02154508.13811463.36311463.36203891.52933963.65433963.65253549.861064958.06564958.06303343.321203594.95703594.95標準利率6.55%等額本息按揭貸款50萬標準利率6.5

20、5%等額本金按揭貸款50萬按揭年數(shù)首月月供還款總額支付利息款106895.836651按揭年數(shù)首月月供還款總額支付利息款106041.67613437.5113437.5154652.78669687.5169687.5203958.33725937.5225937.5253541.67782187.5282187.5303263.89838437.5338437.5按揭年數(shù)每月月供還款總額支付利息款105181.92621830.45121830.45153824.97688493.96188493.96203163.25759179.25259179.25252779.16833748.7

21、2333748.72302533.43912033.56412033.56公積金4.50%等額本息按揭貸款50萬公積金4.50%等額本金按揭貸款50萬按揭年數(shù)首月月供還款總額支付利息款106041.6761342.3 用折現(xiàn)方式計算等額本息 若銀行年利率為7%, 則一年后的107元(未來值)的現(xiàn)值就是100元.設房貸月利率為r, 每月月供x不變(未來值)每個月的月供現(xiàn)值的總和應該等于貸款現(xiàn)值50萬！2.3 用折現(xiàn)方式計算等額本息 若銀行年利率每個月的月供現(xiàn)值的總和應該等于貸款現(xiàn)值50萬！與前面推導一致, 并且簡單一些！每個月的月供現(xiàn)值的總和應該等于貸款現(xiàn)值50萬！與前面推導一致練習與思考假設你

22、借了好友5000元, 計劃3年內(nèi)還清, 準備第一年還1000, 第二年還2000, 為了不讓好心的朋友吃虧, 請問第三年應該還多少合適？(假設銀行年利率5.0%)假設商業(yè)按揭貸款50萬, 首次置業(yè)享受標準利率5.15%的8.5折, 計劃13年還清的每月等額本息的月供是多少？同2題, 現(xiàn)計劃10年還清, 要求前5年月供均為5000元, 問后5年的月供是多少？ 淘寶招財寶變現(xiàn)計算 張三6月1日以6.6%購買了1年期個人貸10000，現(xiàn)9月3日發(fā)現(xiàn)資金困難，想以5.5%的年利率變現(xiàn)出去，假設招財寶上有人愿意接手，由于招財寶平臺需要收取2%的變現(xiàn)手續(xù)費，請問張三可以最大實際到手多少錢？練習與思考假設你

23、借了好友5000元, 計劃3年內(nèi)還清, Markov鏈簡單介紹設學校有1000個學生, 飯?zhí)迷绮椭挥须u蛋和饅頭, 每個學生如果前一天吃了雞蛋, 今天再吃雞蛋的概率為0.4; 如果前一天吃的是饅頭, 則今天吃雞蛋的概率是0.8. 問經(jīng)過一段時間后, 每天吃雞蛋與饅頭的平均人數(shù)？ 昨天 今天雞蛋饅頭雞蛋0.40.8饅頭0.60.2Markov鏈簡單介紹設學校有1000個學生, 飯?zhí)迷绮椭挥?昨天 今天雞蛋饅頭雞蛋0.40.8饅頭0.60.2 昨天 雞蛋饅頭雞蛋0極限分布極限分布數(shù)學建模初等模型講義課件若aij 0, 則稱為正則Markov鏈, Ax = x的特征值1只有1個特征向量x,x就是唯一的

24、極限分布. 此時特征值1對應多個特征向量正則Markov鏈轉移概率矩陣若aij 0, 則稱為正則Markov鏈, 此時特征值1數(shù)學建模初等模型講義課件練習：一個醉漢在床與三步之遠的樓梯之間蹣跚, 每走一步朝著床走的概率比朝著樓梯走的概率是3：1. 如果到了位置1就會摔下樓梯; 到了位置4就會睡個好覺.(1)試證明: 這個醉漢最終一定回到床和樓梯這兩個位置中的一個.(2)假設他現(xiàn)在在位置2, 計算他最終在床上的概率.1 2 3 4 非正則Markov鏈練習：一個醉漢在床與三步之遠的樓梯之間蹣跚, 每走一步朝著床由Markov鏈性質, An有極限, 且極限不為0則An有一個特征值1, 其他特征值絕

25、對值小于1.Aui = li ui把不是1的特征值置零由Markov鏈性質, An有極限, 且極限不為0Aui地球由大氣層包裹, 是氣液共存態(tài). 假設每天有6%的液體蒸發(fā)為氣體, 而又有2%的氣體凝結(降雨、雪)為液體. 假如開始時有70%的液體, 30%的氣體，寫出轉移概率矩陣,A 并用軟件計算液體與氣體的最終穩(wěn)定分布.思考與練習地球由大氣層包裹, 是氣液共存態(tài). 假設每天有6%的液體3. Google搜索引擎的奧秘據(jù)統(tǒng)計超過80%的用戶靠搜索引擎獲取信息網(wǎng)站排名是網(wǎng)絡搜索引擎的核心目前Google數(shù)據(jù)庫存儲上百億網(wǎng)頁信息, 每天提供查詢服務達到3億多次背景和問題用時0.27s80萬網(wǎng)頁如何

26、對Internet的的網(wǎng)頁排名3. Google搜索引擎的奧秘據(jù)統(tǒng)計超過80%的用戶靠搜google查詢過程示意圖google查詢過程示意圖Google搜索的核心算法PageRank是 Google 用于評價一個網(wǎng)頁的重要性的一種方法. 通過該方法, Google 將各個網(wǎng)站進行排名. 用戶進行相關搜索時, Google 會將符合條件的網(wǎng)站按排名順序輸出. PageRank 算法中使用的數(shù)學知識包括：正矩陣性質、特征值和特征向量、冪迭代算法、Gauss-Seidel迭代算法等.PageRank 得分是介于 0 和 1 之間的一個數(shù),得分越大表示網(wǎng)頁越重要.Google搜索的核心算法PageRa

27、nk是 Google PageRank算法思想簡介 PageRank基于假設關系 “許多優(yōu)質的網(wǎng)頁中超鏈接的網(wǎng)頁，必定是優(yōu)質網(wǎng)頁”，以此判定所有網(wǎng)頁的重要性。 重要性由該網(wǎng)頁被訪問的概率大小來刻畫。導入鏈接數(shù) 單純意義上的受歡迎度指標導入鏈接是否來自受歡迎程度高的頁面 有根據(jù)的受歡迎指標導入鏈接源頁面的導出鏈接數(shù) 被選中的概率指標通過轉移概率矩陣來求PageRank算法思想簡介 PageRank基于假設關系通 PageRank 是基于這樣一個理論：若 B 網(wǎng)頁上有連接到 A 網(wǎng)頁的鏈接 ( 稱 B 為 A 的導入鏈接 ), 說明 B 認為 A 有鏈接價值，是一個“重要”的網(wǎng)頁. 當 B 網(wǎng)頁級

28、別 ( 重要性 ) 比較高時, 則 A 網(wǎng)頁可從 B 網(wǎng)頁這個導入鏈接分得一定的級別 ( 重要性 ), 并平均分配給 A 網(wǎng)頁上的所有導出鏈接. 在PageRank算法中, 一個網(wǎng)頁的級別(重要性)大致由下面兩個因素決定：該網(wǎng)頁的導入鏈接的數(shù)量和這些導入鏈接的級別(重要性).PageRank算法思想簡介 PageRank 是基于這樣一個理論：PageRank算法 互聯(lián)網(wǎng)是一個有向圖 每一個網(wǎng)頁是圖的一個頂點 網(wǎng)頁間的每一個超鏈接是圖的一個有向邊 用鄰接矩陣G來表示有向圖, 即， 若網(wǎng)頁 j到網(wǎng)頁i有超鏈接, 則gij =1, 否則為gij =0. PageRank計算 互聯(lián)網(wǎng)是一個有向圖Pag

29、eRank計算鄰接矩陣是一個十分龐大有相當稀疏的方陣(用黑色代表1, 用白色代表0)鄰接矩陣是一個十分龐大有相當稀疏的方陣PageRank計算 用鄰接矩陣G來表示圖, 即， 若網(wǎng)頁 j 到網(wǎng)頁i 有超鏈接, 則gij =1, 否則為gij =0. 定義矩陣G的列和與行和 其中 cj 是頁面 j 的導出鏈接數(shù)目, ri 是頁面 i 的導入鏈接數(shù)目.PageRank計算 用鄰接矩陣G來表示圖, 即， 假設我們在上網(wǎng)的時候瀏覽頁面并選擇下一個頁面, 這個過程與過去瀏覽過哪些頁面無關, 而僅依賴于當前所在的頁面, 那么這一選擇過程可以認為是一個有限狀態(tài)、離散時間的隨機過程, 其狀態(tài)轉移規(guī)律可用Mark

30、ov鏈描述.定義轉移概率矩陣PageRank計算假設我們在上網(wǎng)的時候瀏覽頁面并選擇下一個頁面, 這個過程與過但還要考慮到用戶雖然在許多場合都順著當前頁面中的鏈接前進, 但時常又會跳躍到完全無關的頁面.經(jīng)過統(tǒng)計, Google采用個15%來表示時常, 即用戶在85%的情況下沿著鏈接前進, 但有15%的情況下突然跳躍到無關的頁面中去.從而修正狀態(tài)轉移矩陣但還要考慮到用戶雖然在許多場合都順著當前頁面中的鏈接前進, 根據(jù)Markov鏈的基本性質, 以上A 是一個正則Markov鏈, 存在平穩(wěn)分布x = (x1, x2, x3, ., xN)T, 滿足x表示在極限狀態(tài)(轉移次數(shù)趨于無限)下各網(wǎng)頁被訪問的

31、概率分布.x定義為網(wǎng)頁的PageRank向量, xi 表示第 i 個網(wǎng)頁的PageRank值. 顯然概率越大, 其重要性越高是合理的.根據(jù)Markov鏈的基本性質, 以上A 是一個正則Mark分量 x 應滿足方程從另一角度看, 網(wǎng)頁 j 將它的PageRank值 xj 分成 cj 份, 分別“投票”給它鏈出的網(wǎng)頁. 網(wǎng)頁k 的PageRank值 xk 就是所有頁面投票給網(wǎng)頁k的最終值.數(shù)學建模初等模型講義課件由Markov性質, A 的最大特征值是1, 即求特征值1對應的特征向量.問：上述方程組的解是否唯一解？解是否有意義(即不會出現(xiàn)負數(shù)或大于1的數(shù))？答：上述方程組的解唯一且分量都大于0！理

32、由：Perron-Frobnius 定理.解的討論特征向量的計算需要采用冪迭代、Gauss-Seidel迭代等算法由Markov性質, A 的最大特征值是1, 即求特如果 A 是正的方陣(所有元素均大于0), 則Perron-Frobnius 定理 A 的譜半徑 (A)0，其中 , 1, 2, . , n 為 A 的特征值。 = (A) 是 A 的特征值, 且代數(shù)重數(shù)為 1, 即為單特征值。 存在唯一的 x 0, 滿足 A x = x, 且 若 是 A 的特征值, 且 (A), 則| 3的情況, 第n條直線與原有n-1條直線都相交, 最多分成n段.每1段都落在一個區(qū)域上, 并該區(qū)域分為兩塊新區(qū)

33、域！那么比S(n-1)多出n塊新區(qū)域.對于更一般n3的情況, 8.2 n個平面最多能將空間分為多少個區(qū)域F(n)?分析要滿足任意三個平面交于一點, 且無四平面共點的情況, 才會出現(xiàn)最多的分割區(qū)域.設這樣的n個平面把空間分成F(n)個區(qū)域.目標 F(n) = F(n - 1) + ?第n個平面被其它n-1個平面分成一些平面碎片, 每個平面碎片把舊空間區(qū)域分成兩塊新的空間區(qū)域.因此關鍵在于第n個平面被其它n-1個平面分成多少個碎片(區(qū)域)？8.2 n個平面最多能將空間分為多少個區(qū)域F(n)?分析設這思路因此關鍵在于第n個平面被其它n-1個平面分成多少個碎片(區(qū)域)？第n個平面與其它n-1個平面各有一條交線, 而且這些直線兩兩相交, 且無三線共點。這n-1條直線把第n個平面分成的區(qū)域個數(shù)為:思路因此關鍵在于第n個平面被其它n-1個平面分成多少個碎片(求解求解依次類推n個3-維超平面將4維空間分成的最大區(qū)域數(shù)為n個(k-1)-維超平面將k維空間分成的最大區(qū)域數(shù)為特殊地, n個(n-1)-維超平面將n維空間分成的最大區(qū)域數(shù)為依次類推n個3-維超平面將4維空間分成的最大區(qū)域數(shù)為n個(k附錄：一階差分方程的求解方法