数学建模初等模型讲义课件

1、数学建模第二章 初等模型数学建模第二章 初等模型 第二章 初等模型公平席位计算按揭还款Markov链与Google网页排名选址问题与费马点切西瓜与差分方程 第二章 初等模型公平席位计算1. 公平席位计算问题三个系学生共200名(甲100, 乙60, 丙40), 学生代表会议设20席, 按比例分配, 三个系分别为10, 6, 4席.现因学生转系, 三系人数为103, 63, 34, 问20席如何分配；若增加为21席, 又如何分配。对丙系公平吗系别学生人数比例(%)20席的分配21席的分配比例结果比例结果甲10351.510.31010.8211乙6331.56.366.627丙3417.03.4

2、43.573总和200100.020.02021.0021最大余数分配1. 公平席位计算问题三个系学生共200名(甲100, 乙1. 公平席位计算按这种最大剩余法的另一个重大缺陷是人口悖论,即人数增加了较多反而导致席位减少.系别学生人数比例(%)21席的分配人数变化21席的分配比例结果比例结果甲10351.510.821111411.2911乙6331.56.627646.346丙3417.03.573343.364总和200100.021.002121221.0021乙系人数增加1人，按最大剩余法反而少了1席，丙系人数未增加，反而多了一席！1. 公平席位计算按这种最大剩余法的另一个重大缺陷是

3、人口悖论“公平”分配方法需要一个衡量公平分配的数量指标人数席位A方n1N1B方n2N2“公平”分配方法需要一个衡量公平分配的数量指标人数席位A方n说明A增加1席, 仍对 A不公平, 该席位应分给A.讨论以下几种情况设A, B已有N1, N2 席, 若增加1席, 问应分给A, 还是B？不妨设分配开始时 n1/N1 n2/N2 , 即原方案对A不公平, 这种情况最麻烦说明A增加1席, 仍对 A不公平, 该席位应分给A.讨论感觉上, 分配给B会相对公平.这种感觉如何用数学描述, 并提炼成算法实现.感觉上, 分配给B会相对公平.这种感觉如何用数学描述, 并提模型假设 学生会共有N个席位, 各系人数分别

4、为n1, n2, ., nm，若各系分配的席位为N1, N2, ., Nm, 则各系每席实际代表的人数分别为用目标函数衡量“公平度”模型假设用目标函数衡量“公平度”回到21席例子 (甲103, 乙63, 丙34), 按照标准1试算 系别人数比例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位, 并标以下划线;表中找出最大的下划线, 把它右边的数加以下划线;重复步骤 , 直到下划线数字的个数=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的算法过程可能最大值出现多个, 则按某种约定来分配可以归纳标准1的算法过程可能最大值出现多个, 则按某种约定上述标准公平吗? 是否存在公平的席位分配方法？公理化约定:上述标准公平吗? 是否存在公平的席位分配方法？公理化约定:上述标准公平吗? 是否存在公平的席位分配方法？最大剩余法满足性质1, 不满足性质2,3, 准则1满足性质2, 3，但不满足性质1. (见p285)经证明，当m4, N m+3, 不存在满足满足3条性质的分配方案!从1930年后美国众议员席位选举采用相等比例法(EP)!上述标准公平吗? 是否存

8、在公平的席位分配方法？最大剩余法满足ini比例最大剩余(惯例)最小除数(规则1)相等比例(EP)19149091.49928890216601.66222314601.46222414501.45122514401.44122614001.40121711001.10121总和100000100100100100不满足性质1的例子ini比例最大剩余最小除数相等比例19149091.4992相等比例法(EP)相等比例法(EP)练习与思考学校共1000名学生, 235人住A宿舍, 333人住在B宿舍, 432人住在C宿舍. 学生要组织一个10人的委员会. 使分别根据标准1与标准2给出分配方案.练习

9、与思考学校共1000名学生, 235人住A宿舍, 用房产在银行办理的贷款, 该贷款要按照银行规定的利率支付利息。贷款形式 商业贷款和公积金贷款.还款形式 等额本息和等额本金.2. 按揭还款调整日期商业基准利率公积金利率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 , 问月供是多少？用房产在银行办理的贷款, 该贷款

11、要按照银行规定的利率支付利息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已付利息按揭年数首月月供还款总额支付利息款106895.83665114

19、.58165114.58155506.94746989.58246989.58204812.5828864.58328864.58254395.83910739.58410739.58304118.06992614.58492614.58按揭年数每月月供还款总额支付利息款105818.32698198.02198198.02154508.13811463.36311463.36203891.52933963.65433963.65253549.861064958.06564958.06303343.321203594.95703594.95标准利率6.55%等额本息按揭贷款50万标准利率6.5

20、5%等额本金按揭贷款50万按揭年数首月月供还款总额支付利息款106895.836651按揭年数首月月供还款总额支付利息款106041.67613437.5113437.5154652.78669687.5169687.5203958.33725937.5225937.5253541.67782187.5282187.5303263.89838437.5338437.5按揭年数每月月供还款总额支付利息款105181.92621830.45121830.45153824.97688493.96188493.96203163.25759179.25259179.25252779.16833748.7

21、2333748.72302533.43912033.56412033.56公积金4.50%等额本息按揭贷款50万公积金4.50%等额本金按揭贷款50万按揭年数首月月供还款总额支付利息款106041.6761342.3 用折现方式计算等额本息 若银行年利率为7%, 则一年后的107元(未来值)的现值就是100元.设房贷月利率为r, 每月月供x不变(未来值)每个月的月供现值的总和应该等于贷款现值50万！2.3 用折现方式计算等额本息 若银行年利率每个月的月供现值的总和应该等于贷款现值50万！与前面推导一致, 并且简单一些！每个月的月供现值的总和应该等于贷款现值50万！与前面推导一致练习与思考假设你

22、借了好友5000元, 计划3年内还清, 准备第一年还1000, 第二年还2000, 为了不让好心的朋友吃亏, 请问第三年应该还多少合适？(假设银行年利率5.0%)假设商业按揭贷款50万, 首次置业享受标准利率5.15%的8.5折, 计划13年还清的每月等额本息的月供是多少？同2题, 现计划10年还清, 要求前5年月供均为5000元, 问后5年的月供是多少？ 淘宝招财宝变现计算 张三6月1日以6.6%购买了1年期个人贷10000，现9月3日发现资金困难，想以5.5%的年利率变现出去，假设招财宝上有人愿意接手，由于招财宝平台需要收取2%的变现手续费，请问张三可以最大实际到手多少钱？练习与思考假设你

23、借了好友5000元, 计划3年内还清, Markov链简单介绍设学校有1000个学生, 饭堂早餐只有鸡蛋和馒头, 每个学生如果前一天吃了鸡蛋, 今天再吃鸡蛋的概率为0.4; 如果前一天吃的是馒头, 则今天吃鸡蛋的概率是0.8. 问经过一段时间后, 每天吃鸡蛋与馒头的平均人数？ 昨天 今天鸡蛋馒头鸡蛋0.40.8馒头0.60.2Markov链简单介绍设学校有1000个学生, 饭堂早餐只有 昨天 今天鸡蛋馒头鸡蛋0.40.8馒头0.60.2 昨天 鸡蛋馒头鸡蛋0极限分布极限分布数学建模初等模型讲义课件若aij 0, 则称为正则Markov链, Ax = x的特征值1只有1个特征向量x,x就是唯一的

24、极限分布. 此时特征值1对应多个特征向量正则Markov链转移概率矩阵若aij 0, 则称为正则Markov链, 此时特征值1数学建模初等模型讲义课件练习：一个醉汉在床与三步之远的楼梯之间蹒跚, 每走一步朝着床走的概率比朝着楼梯走的概率是3：1. 如果到了位置1就会摔下楼梯; 到了位置4就会睡个好觉.(1)试证明: 这个醉汉最终一定回到床和楼梯这两个位置中的一个.(2)假设他现在在位置2, 计算他最终在床上的概率.1 2 3 4 非正则Markov链练习：一个醉汉在床与三步之远的楼梯之间蹒跚, 每走一步朝着床由Markov链性质, An有极限, 且极限不为0则An有一个特征值1, 其他特征值绝

25、对值小于1.Aui = li ui把不是1的特征值置零由Markov链性质, An有极限, 且极限不为0Aui地球由大气层包裹, 是气液共存态. 假设每天有6%的液体蒸发为气体, 而又有2%的气体凝结(降雨、雪)为液体. 假如开始时有70%的液体, 30%的气体，写出转移概率矩阵,A 并用软件计算液体与气体的最终稳定分布.思考与练习地球由大气层包裹, 是气液共存态. 假设每天有6%的液体3. Google搜索引擎的奥秘据统计超过80%的用户靠搜索引擎获取信息网站排名是网络搜索引擎的核心目前Google数据库存储上百亿网页信息, 每天提供查询服务达到3亿多次背景和问题用时0.27s80万网页如何

26、对Internet的的网页排名3. Google搜索引擎的奥秘据统计超过80%的用户靠搜google查询过程示意图google查询过程示意图Google搜索的核心算法PageRank是 Google 用于评价一个网页的重要性的一种方法. 通过该方法, Google 将各个网站进行排名. 用户进行相关搜索时, Google 会将符合条件的网站按排名顺序输出. PageRank 算法中使用的数学知识包括：正矩阵性质、特征值和特征向量、幂迭代算法、Gauss-Seidel迭代算法等.PageRank 得分是介于 0 和 1 之间的一个数,得分越大表示网页越重要.Google搜索的核心算法PageRa

27、nk是 Google PageRank算法思想简介 PageRank基于假设关系 “许多优质的网页中超链接的网页，必定是优质网页”，以此判定所有网页的重要性。 重要性由该网页被访问的概率大小来刻画。导入链接数 单纯意义上的受欢迎度指标导入链接是否来自受欢迎程度高的页面 有根据的受欢迎指标导入链接源页面的导出链接数 被选中的概率指标通过转移概率矩阵来求PageRank算法思想简介 PageRank基于假设关系通 PageRank 是基于这样一个理论：若 B 网页上有连接到 A 网页的链接 ( 称 B 为 A 的导入链接 ), 说明 B 认为 A 有链接价值，是一个“重要”的网页. 当 B 网页级

28、别 ( 重要性 ) 比较高时, 则 A 网页可从 B 网页这个导入链接分得一定的级别 ( 重要性 ), 并平均分配给 A 网页上的所有导出链接. 在PageRank算法中, 一个网页的级别(重要性)大致由下面两个因素决定：该网页的导入链接的数量和这些导入链接的级别(重要性).PageRank算法思想简介 PageRank 是基于这样一个理论：PageRank算法 互联网是一个有向图 每一个网页是图的一个顶点 网页间的每一个超链接是图的一个有向边 用邻接矩阵G来表示有向图, 即， 若网页 j到网页i有超链接, 则gij =1, 否则为gij =0. PageRank计算 互联网是一个有向图Pag

29、eRank计算邻接矩阵是一个十分庞大有相当稀疏的方阵(用黑色代表1, 用白色代表0)邻接矩阵是一个十分庞大有相当稀疏的方阵PageRank计算 用邻接矩阵G来表示图, 即， 若网页 j 到网页i 有超链接, 则gij =1, 否则为gij =0. 定义矩阵G的列和与行和 其中 cj 是页面 j 的导出链接数目, ri 是页面 i 的导入链接数目.PageRank计算 用邻接矩阵G来表示图, 即， 假设我们在上网的时候浏览页面并选择下一个页面, 这个过程与过去浏览过哪些页面无关, 而仅依赖于当前所在的页面, 那么这一选择过程可以认为是一个有限状态、离散时间的随机过程, 其状态转移规律可用Mark

30、ov链描述.定义转移概率矩阵PageRank计算假设我们在上网的时候浏览页面并选择下一个页面, 这个过程与过但还要考虑到用户虽然在许多场合都顺着当前页面中的链接前进, 但时常又会跳跃到完全无关的页面.经过统计, Google采用个15%来表示时常, 即用户在85%的情况下沿着链接前进, 但有15%的情况下突然跳跃到无关的页面中去.从而修正状态转移矩阵但还要考虑到用户虽然在许多场合都顺着当前页面中的链接前进, 根据Markov链的基本性质, 以上A 是一个正则Markov链, 存在平稳分布x = (x1, x2, x3, ., xN)T, 满足x表示在极限状态(转移次数趋于无限)下各网页被访问的

31、概率分布.x定义为网页的PageRank向量, xi 表示第 i 个网页的PageRank值. 显然概率越大, 其重要性越高是合理的.根据Markov链的基本性质, 以上A 是一个正则Mark分量 x 应满足方程从另一角度看, 网页 j 将它的PageRank值 xj 分成 cj 份, 分别“投票”给它链出的网页. 网页k 的PageRank值 xk 就是所有页面投票给网页k的最终值.数学建模初等模型讲义课件由Markov性质, A 的最大特征值是1, 即求特征值1对应的特征向量.问：上述方程组的解是否唯一解？解是否有意义(即不会出现负数或大于1的数)？答：上述方程组的解唯一且分量都大于0！理

32、由：Perron-Frobnius 定理.解的讨论特征向量的计算需要采用幂迭代、Gauss-Seidel迭代等算法由Markov性质, A 的最大特征值是1, 即求特如果 A 是正的方阵(所有元素均大于0), 则Perron-Frobnius 定理 A 的谱半径 (A)0，其中 , 1, 2, . , n 为 A 的特征值。 = (A) 是 A 的特征值, 且代数重数为 1, 即为单特征值。 存在唯一的 x 0, 满足 A x = x, 且 若 是 A 的特征值, 且 (A), 则| 3的情况, 第n条直线与原有n-1条直线都相交, 最多分成n段.每1段都落在一个区域上, 并该区域分为两块新区

33、域！那么比S(n-1)多出n块新区域.对于更一般n3的情况, 8.2 n个平面最多能将空间分为多少个区域F(n)?分析要满足任意三个平面交于一点, 且无四平面共点的情况, 才会出现最多的分割区域.设这样的n个平面把空间分成F(n)个区域.目标 F(n) = F(n - 1) + ?第n个平面被其它n-1个平面分成一些平面碎片, 每个平面碎片把旧空间区域分成两块新的空间区域.因此关键在于第n个平面被其它n-1个平面分成多少个碎片(区域)？8.2 n个平面最多能将空间分为多少个区域F(n)?分析设这思路因此关键在于第n个平面被其它n-1个平面分成多少个碎片(区域)？第n个平面与其它n-1个平面各有一条交线, 而且这些直线两两相交, 且无三线共点。这n-1条直线把第n个平面分成的区域个数为:思路因此关键在于第n个平面被其它n-1个平面分成多少个碎片(求解求解依次类推n个3-维超平面将4维空间分成的最大区域数为n个(k-1)-维超平面将k维空间分成的最大区域数为特殊地, n个(n-1)-维超平面将n维空间分成的最大区域数为依次类推n个3-维超平面将4维空间分成的最大区域数为n个(k附录：一阶差分方程的求解方法