《初等模型》PPT课件.ppt

上传人:牧羊曲112 文档编号:4850833 上传时间:2023-05-19 格式:PPT 页数:138 大小:1.25MB
返回 下载 相关 举报
《初等模型》PPT课件.ppt_第1页
第1页 / 共138页
《初等模型》PPT课件.ppt_第2页
第2页 / 共138页
《初等模型》PPT课件.ppt_第3页
第3页 / 共138页
《初等模型》PPT课件.ppt_第4页
第4页 / 共138页
《初等模型》PPT课件.ppt_第5页
第5页 / 共138页
点击查看更多>>
资源描述

《《初等模型》PPT课件.ppt》由会员分享,可在线阅读,更多相关《《初等模型》PPT课件.ppt(138页珍藏版)》请在三一办公上搜索。

1、数学建模(提高班),总学时 60 考试任课教师 杨尚俊1937年出生全国数学建模竞赛优秀指导教师(2000年)省级教学名师(2006年)电话 5107817邮箱,本课拟讲内容,0 引言1 初等模型2 微分方程方法建模3 层次分析方法建模4 矩阵分析方法建模7 充分发挥智力巧妙建模8 大学生数学建模竞赛,本课程的特点,以讨论具体实际问题为主要线索;以讲授数学建模的思路与方法为主要内容;以培养创新精神为主要目的.(按培训数学建模竞赛队员的高标准要求.)强调启发思路和分析、解决问题的技巧.按求解所讨论的具体数学模型的需要介绍有关数学背景知识和基本方法,即实际问题需要什么介绍什么,不强求数学方面的系统

2、性与完整性.,安徽大学从1993(4)年起就组队参加全国(国际)大学生数学建模竞赛,并取得不错的成绩.2000年在国际大学生数学建模竞赛中安大参赛3个队,其中获一等奖1队,获二等奖2队.2002年在全国大学生数学建模竞赛中安大参赛7个队,其中获国家一等奖2队,国家二等奖1队.2006年在全国大学生数学建模竞赛中安大参赛15个队,其中获国家一等奖1队,国家二等奖5队;赛区一等奖5队.2008年在国际大学生数学建模竞赛中安大参赛4个队,其中获一等奖1队,获二等奖3队.2008年在全国大学生数学建模竞赛中安大参赛15个队,其中获国家一等奖3队,国家二等奖2队;赛区一等奖5队.这些成绩不仅给安大争得荣

3、誉,更为国家培养了一些优秀人才.,引 言,0.1 数学的重要性0.2 本书主要内容0.3 本课程主要特点,数学的重要性,新世纪国家间的竞争主要是经济竞争,是人才的竞争;人才培养的关键是素质教育,数学教育在素质教育中占据重要地位.当今社会正日益数学化,数学是高科技的基础.数学在工程技术以及国民生产中发挥愈来愈重要的作用甚至是决定性的作用.,素质教育的重要性,素质教育既是“科教兴国”战略的必然选择,也是教育自身进一步发展的客观需要,更是高校发展的灵魂和动力.理工科的特征往往体现在严谨,规范的教育体系上,而综合性大学更重要的是强调个性化教育.能充分挖掘每个学生的潜力的个性化教育往往是一所综合性大学的

4、重要特征和体现,而数学建模的教育及实践正符合这方面的要求.,数学是高科技的基础,社会进步依赖于科学的创新而数学对于科学的发展则具有根本的意义.在今天,数学已成为高科技的基础,并且在一定意义上,可以说是现代文明的标志(2002年北京国际数学家大会东道国欢迎词摘录).各行各业日益依赖于数学,可以说,当今社会正日益数学化.数学正在向一切领域渗透,数学正在不停地与别的学科结合产生活跃的新兴学科.”高科技本质上是一种数学技术”的观点正在被越来越多的人接受.,2002年8月在中国首都北京举行国际数学家2002年大会,这是该国际最高级数学学术会议第一次在一个发展中国家举行.我国政府非常重视和支持这次会议,最

5、高领导人出席了会议开幕式,并为得奖者授奖.这是李岚清副总理在致大会欢迎词中的一段话.,2010年12月在北京举行“数学引领现代科技的未来”国际研讨会.从会议名称可看出数学对高科技的重要意义.不少世界著名科学家及大学校长参加会议,从参加会议人员可看出,公众对数学重要性的认可.中国科学院院长路甬祥在会上发言时阐明,科技成果分三个层次:上层是原创性成果;中层是应用性成果;下层是商业性成果.其中的原创性成果尤为重要,数学对此类成果影响最大.,2010年12月郭雷院士在“国家数学与交叉科学中心”成立仪式上的讲话,随着现代实验,观测,计算和模拟技术与手段的不断进步,数学作为逻辑推理和定量研究的有力工具,深

6、刻影响着科技进步和社会发展.在人类社会发展过程中,数学的贡献不胜枚举,比如,在著名的阿波罗登月工程中,火箭上升和轨道修正就分别运用“极大值原理”和“卡尔曼滤波”两个关键数学方法;而PageRank搜索算法则成就了全球搜索引擎Google这一巨大产业.毋庸置疑,在当今物质科学,信息科学,工程技术,经济金融等众多领域中,数学都发挥着不可替代的作用.近年来,欧美等发达国家相继采取各种措施推动数学与其他科学的交叉研究,而我国的科技发展也遇到大量与数学有关的”瓶颈性”交叉科学难题,涉及众多领域.比如,复杂空间环境下高性能飞行器的控制与导航;信息技术领域中密集/海量数据分析,复杂网络与密码体系;经济金融领

7、域中经济预测预警,财政金融风险管理;生命科学中基因与蛋白质网络分析,药物靶点识别等.然而,从目前状态看,在国家层面尚缺乏对数学科学交叉应用研究的整体布局,也缺乏稳定支持的良好机制和研究模式成立国家数学与交叉中心,正是从国家层面搭建数学与其他学科交叉合作的高水平研究平台.中心拟在信息技术,先进制造,材料环境,生物医学,经济金融,物理工程等领域与数学和系统科学有关的重大交叉问题上先期启动一批研究专题,针对科学,工程与经济中相关的重大需求,通过体制机制创新,凝聚数学及相关科学力量,提炼新科学问题,探索新科学方向,瞄准瓶颈性难题,协同攻关,促进数学及交叉应用研究的发展,力争为我国战略性,前瞻性贡献.,

8、数学在生产中起重要作用的例子,曾经有一家电器公司生产中出现成品率只有84%,并仅有50%的发货日期可以兑现所造成的严重亏损问题.他们应用统计质量控制在很短时间就成功地发现和解决了问题,使成品率稳定在95%以上,按期发货率也达到95%,当年就实现扭亏增盈1200万美元.这个故事告诉我们:数学可以在国民生产中发挥重要作用,甚至决定性作用.,Mathematical Science,Technology,Economic Compitive-ness,National Academy Press,Washington D.C.1991.该公司最先发现出现电器元件的各种性能波动太大.他们首先用数学技术

9、找出产生元件性能波动的原因是在自动控制的酸洗工序中原先确定的酸洗液PH值有问题,产生校正过度.他们再用数学技术(优选法)重新校正减少了起伏,从而解决了这个大问题.这份报告提出的如下结论也颇有启发性:“在经济竞争中数学科学是必不可少的.数学科学是一种关键性的,能够实行的(低耗高效的)技术.”,这个例子取自Glimm教授主持编撰的代表美国数学科学委员会给美国政府的公开报告:,第1章 初等模型,1.1 例子与定义 1.2 其它初等模型,简例,航行问题:已知:沿长江在相距750km的两个码头A与B之间,顺水航行时间是 30hr;逆水航行时间是50hr.试分别求出船(在静水中)和水的平均速度.,A,B,

10、解:,令船和水的平均速度分别是x和y,由题意得二元线性方程组:求解此方程组得 x=20,y=5.答案:船和水的平均速度分别是20km/hr和5km/hr.,25,15,必要的简化与说明,这里,只考虑平均速度是基本的简化,因为船和水的速度是随时间,地点而变化的.严格讲,已知的顺水,逆水航行时间是船在该河段上常年航行的平均时间;而要求的船和水的平均速度也应是该船和水在该河段上常年航行的平均速度.若把实际问题看作原型的话,则数学模型是将原型经过简化提炼而构成的替代物.这里值得注意的是:简化是构作数学模型必不可少的一步.,解决本问题也需要速度等相关的物理概念,例如,匀速直线运动,速度合成等的有关知识.

11、s=vt 或 v=s/t:速度=路程/时间 解决本问题的步骤:按照题意设定未知量并决定未知量满足的数学公式;求出这个方程组的解;并在讨论解的存在性与唯一性之后确定该唯一解就是原问题所需要的解.别忘了验证解的正确性.,什么是数学模型?,如果要下一个定义的话,可以说:数学模型是对一个实际问题,按照其内在规律作出一些必要的假设(目的为了简化和去掉不确定的因素使之能归结为一个确定的数学问题)并应用适当数学工具导出的一个数学结构.借助数学的分析与计算,全面探讨并求出所得数学模型的解,再利用有关的背景知识可以成功地将所求得的数学解用来解释和回答原先的实际问题.这一整个过程称为数学建模.可用下面的图表直观地

12、表示数学建模过程的各阶段及其联系.,实际问题,抽象,简化,假设,确定变量与参数,建立数学模型并求解,确定参数的值,交付使用从而产生经济,社会效益,用实际背景或数据等来检验数学模型,不符合实际再重来,符合实际交付使用,实际问题与其数学模型之间的关系,大家知道原型与模型之间的关系.若把实际问题看作原型的话,则数学模型是将原型经过精致地简化,提炼而构成的替代物.这里必须强调两点:第一,一般来说,原型是复杂和困难的,必须把它归结为数学模型才能解决;第二,数学模型不是原型原封不动的复制品,它只是在突出反映原型主要方面性质的近似物.这里难免会存在数学模型与原型的差异甚至矛盾,冲突.但对我们来讲,原型是根本

13、的,当二者出现无法解释的矛盾时,必须修改相关的数学模型以适应原型.,例2 气象预报问题,气象观测与气象预报,偏微分方程组的初值边值混合问题,求出数值解确定有关参数,作1天,2天到5天的气象预报,简化,归纳,使用巨型计算机,用数值结果解释气象,分析偏差及其产生原因,作为天气现象的数学模型在一百多年前就已经很成功地解决了,它是一个特殊的二阶非线性偏微分方程组的初值,边值混合问题.遗憾的是,这个偏微分方程组的混合问题很难求解,不要说,精确解找不到,就是求很粗糙近似解的计算量也惊人地巨大.在现代巨型电子计算机未出世以前,即使通过求此混合问题很粗糙近似解来作短期天气预报也是不现实的,因为花一个月甚至更多

14、时间也完成不了所需的计算.直到20世纪80年代出现每秒可完成上亿次运算的巨型计算机以后,数值天气预报这个多年的梦想才得以实现.上世纪80年代以来,我国也研制成功高水平的巨型机,保证了中央气象台每天及时而准确地发布各种天气预报,为国民生产及人民生活作出巨大贡献.,例3 安全过河问题,问题:一位老师带三名小学生:甲,乙和丙过河.假设仅有一条小渡船,最多能容纳二人;并且只有老师能划船.此外,学生乙很顽皮,无老师在场时他肯定要欺负甲和丙.老师应如何安排过河方案使四人都到达彼岸并且不发生学生乙与学生甲,丙单独相处而发生打架伤人的事故?,甲,乙,丙,师,实际问题及其数学模型不仅可以涉及数量关系,也可以涉及

15、方案,规则,措施等方面,过河问题就是一例.,过河问题的解,一种安全过河方案是:师乙过去,接着师回;师甲去,接着师乙回;师丙过去,接着师回;师乙过去.,师甲丙,乙,师乙丙,甲,师乙,甲丙,师甲乙丙,师甲乙丙,过河问题(1)的答案唯一吗?不允许重复时有几个答案?最少渡河次数是多少?如果每人都能划船结论又是如何?,思考题1-1,例4 安全过河问题,问题:三个商人每人带一随从过河.假设仅有一条小渡船,最多能容纳二人;并且因他们正处于偏僻地带,这几个不安分的随从在他们人数超过商人人数时将图谋不轨.商人们应如何安排过河方案,使六人都到达彼岸之前,不会发生随从数超过商人数情况而引发杀人越货的事故?,从1,商

16、1,从2,从3,商2,商3,切莫以为数学建模问题都像例1,例3那么简单.不信的话,请你不要参看下面一张幻灯片,试着对例4中的问题,给出你的安全过河方案.你能较快地写出一个安全过河方案吗?,2从过去 接着1从回来;2从过去 接着1从回来;2商过去 接着1商1从回来;2商过去 接着1从回来;2从过去 接着1从回来;2从过去.,过河问题的解,两点注记,按照题意,重要的是商人和随从间的人数对比,至于,商人,随从的个体差异可以不考虑。故在规划方案时只考虑商人,随从人数而不考虑商人,随从的个体差异。如果经过一次或多次来回渡河后本岸状态回复到前面曾经出现过的状态者,称为产生重复。显然,从一个安全方案可以得到

17、一个无重复的安全方案。故在规划方案时一律只考虑无重复的安全方案。,相关的数学表示与分析,河岸的状态可用三维向量(x,y,z)表示,意指在所考虑的时刻,该岸有x商人和y随从;z=0,1分别表示船在此岸,彼岸.x,y的取值范围是0,1,2,3.易见:每岸共有44=16种可能的人员状态;两岸人员状态互相唯一决定,例如,若此岸状态向量为(x,y,0),则彼岸状态向量为(3-x,3-y,1).安全状态向量中的x,y应满足条件:xy或x=0.但当一岸出现 3xy 时,另一岸状态向量(x,y,z)将出现 0 xy 也认为是不安全的状态.,所以,每岸的16种状态中恰有10种是安全的,它们组成的集合是S=(x,

18、y)|x=0 x=3x=y.上述分析也适用于有n个商人及n个随从的情况,其中,n为任意正整数.此时,安全集为 S=(x,y)|x=0 x=nx=y.在直角坐标系下安全集S的点组成字形,详见下图.,x,y,(0,0),(3,3),(2,2),(1,1),(0,1),(0,2),(0,3),(3,0),(3,2),(3,1),此岸状态图,图 1-1,解决安全过河问题(2)的数学模型,基于前面的分析建立解决n商n从安全过河问题的字形棋盘单人跳棋模型:在此岸安全集S组成的字形棋盘上,经奇数步从起点(n,n)跳到终点(0,0)为成功.跳棋规则是:每步在水平或垂直方向跳1或2格;或在45斜线方向跳1格.奇

19、数步向下向左跳;偶数步向上向右跳.一个成功的跳棋过程将给出n商n从安全过河问题的一个方案.例如,图1-1所示的成功跳棋过程正好对应我们前面提出的那个安全过河方案.,关于安全过河问题(2)解的讨论,一般来说,该问题只要有一个解就有无穷多个解.因为:在这个解的第1步之前增加两步:“1随从过去,接着再回来”,走完此两步仍回到原状态.显然,把这两步作任意次循环,都将回到原状态.所以,由一个已知解可以构造出无穷多个不同的解.换句话说,此问题解的唯一性一般不成立.我们应把两个这样的解看作同一类:其中一个解除多一个循环之外,与另一个解完全相同,这里,循环指的是一个偶数步的来回过渡,并保持循环前和循环后两岸状

20、态完全一样.今后,同一类的解中恒取那个”不允许重复的解”为代表.,注意:即使不区别商人或随从间的置换,对于不允许重复的解,解的唯一性一般地也是不成立的.例如,对于安全过河问题(2),仔细观察图1-1不难发现:从(3,3)出发,经“2从过去,接着1从回来”或“1商1从过去,接着1商回来”都达到同样的状态:”1从在彼岸,其余人员在此岸”.因此,安全过河问题(2)至少有两个不允许重复的解.每个不允许重复的解的渡河次数称为最少渡河次数.例如,对图1-1表示的那个不允许重复解最少渡河次数是11.,你能证明:”对任何正整数n,n商n从的安全过河问题,不允许重复的解一定是有限个”吗?你能证明:对3商3从安全

21、过河问题,不允许重复(但不区别商人或随从间的置换)的解个数是4吗?*若你的解法与参考答案不同,你可把它写成文发邮件给我,我下次课作适当总结.,思考题1-2,安全过河问题(2)的各种推广,1.渡船容量不变(即至多容2人),仅商人,随从人数有所改变思考题1-3 对任意正整数n2,讨论n商人和n随从能否安全过河,若能,并给出答案.思考题1-4 对任意正整数n2,讨论n+1商人和n随从能否安全过河?若能并给出答案.,2.渡船容量和商从人数都改变思考题1-5 假设渡船至多容3人,5商人和5随从能否安全过河?若能,请给出答案.并考虑怎样作更一般性的推广?思考题1-6 假设渡船至多容4人,能否证明:对任意正

22、整数n,n商人和n随从都能安全过河?给出你的答案的严格证明.,问题:某家7人(包括爸,妈,二男孩,二女孩和仆人)带一条狗需要一起过河.当时的状况是:只有一条渡船,最多容二人或一人一狗,仅爸,妈,仆人能划船,并且,仆人不在场狗会咬人,妈不在场爸要打儿子,爸不在场妈要打女儿.应如何安排过河方案使全家和狗安全(指没有人被咬或被打)过河?注:仅有两个不同的无重复解.,另一个安全过河问题,爸妈子子女女仆狗,教务处3月7日网上通知,考虑到有些同学周三下午数学建模(提高班)课程与其它课程冲突,经研究决定,从第三周开始,将章权兵老师周三下午的5-8节数学建模(提高班)上课时间调整为周六上午1-4节,上课地点调

23、至博学北楼B115,请同学们相互转告。杨尚俊老师周三下午5-8节数学建模(提高班)课程上课时间、地点不变。请同学们根据自己的时间选择上课时间。需要退选或加选的学生到任课老师处办理登记手续。上课名单将由教务处统一导入教务管理系统,一旦确定,不得退选或加选。课程结束,两个班将进行统一考察,学校数学建模领导小组将根据数学建模(提高班)课程的最后考察成绩,选拔优秀同学参加暑假数学建模竞赛培训,代表安徽大学参加今年9月举行的全国大学生数学建模竞赛。,我的补充通知,要退选或加选的学生需交申请表进行重新登记。申请表要求写上学号专业,并且要有本人签名才有效。截止日期3月16日(此后我不再办理)。,问题:某家7

24、人(包括爸,妈,二男孩,二女孩和仆人)带一条狗需要一起过河.当时的状况是:只有一条渡船,最多容二人或一人一狗,仅爸,妈,仆人能划船,并且,仆人不在场狗会咬人,妈不在场爸要打儿子,爸不在场妈要打女儿.应如何安排过河方案使全家和狗安全(指没有人被咬或被打)过河?注:仅有两个不同的无重复解.思考题:给出小孩也能独立划船的解.,另一个安全过河问题,仆狗过去 接着仆回来;仆子过去 接着仆狗回来;妈子过去 接着妈回来;爸妈过去 接着爸回来;仆狗过去 接着妈回来;爸妈过去 接着爸回来;,上述过河问题的解,狗,爸妈子子女女仆,子,爸妈子女女仆狗,子子,爸妈女女仆狗,爸女女仆狗,妈子子,子子仆狗,爸妈女女,爸妈

25、子子女女仆狗,妈子子仆狗,爸女女,爸女过去 接着仆狗回来;仆女过去 接着仆回来;仆狗过去,爸妈子子女女仆狗,女仆狗,爸妈子子女,仆狗,爸妈子子女女,仆狗过去 接着仆回来;仆子过去 接着仆狗回来;子子过去 接着子回来;爸妈过去 接着爸回来;仆狗过去 接着妈回来;爸妈过去 接着爸回来;,人人能划船增加两个解,狗,爸妈子子女女仆,子,爸妈子女女仆狗,子子,爸妈女女仆狗,爸女女仆狗,妈子子,子子仆狗,爸妈女女,爸妈子子女女仆狗,妈子子仆狗,爸女女,爸女过去 接着女回来;女女过去,爸妈子子仆狗,女女,爸妈子子女女仆狗,用归纳法证明n+1商n从能安全过河,渡河次数是4n-1(丁珍妮),证:n=1时,2商1

26、从可安全过河(1商1从去,1商回;2商去.过河次数x1=3=4n-1),结论显然成立.设n1时结论已经成立,要证n+2商n+1从时结论也成立.事实上,取前4次渡河为:1商1从去,1从回;1商1从去,1商回,则船到此岸时,此岸有n+1商n从,按归纳假设,再经xn次可安全渡到对岸.所以,n+2商n+1从也能安全过河,并且xn+1=4+xn=4+(4n-1)=4(n+1)-1.,1.2 其它初等模型,小兔繁殖问题汉诺塔问题圆内接三角形计数问题双层玻璃窗保温功效可行性分析代表席位公平分配问题最优价格制定问题,小兔繁殖问题,假设:一对刚出生的小兔(一公一母)被放到一个水草丰盛的孤岛上;2月龄及以上的每对

27、兔子每月(30天)恰好繁殖一对新兔(也是一公一母);在观察期间没有任何兔子死去.问题:试计算在观察期间的第n(n=1,2,3,)个月内岛上兔子总对数.解:记第n个月内兔子总对数为fn.则显然f1=1;因一月龄的兔不能繁殖,故f2=1.,1,2,3,4,5,6,考察期间月数,图 1-2,1对初生兔,1对成兔,当n3时,为了计算第n月兔子对数fn,要把前一个月的兔子对数fn-1加上新生兔子对数,而新生兔子对数正好等于fn-2(因每对成兔一月生一对).这就证明数列fn满足初始条件:f1=f2=1和递推关系:fn=fn-1+fn-2,n3.不难依次求得数列fn前若干项(参看图1-2)的值 如上表所示:

28、,Fibonacci数列,数列fn在理论和运用方面都非常有用,被称为Fibonacci数列.可以方便地编程计算数列fn,也可以证明它满足下列封闭公式:fn=(1/5)(un-vn),n=1,2,(2.1)其中,u=(1+5)/2,v=(1-5)/2.,试用Matlab编程求fn,其中n为任意正整数.你能严格证明公式(2.1)吗?若把小兔繁殖问题的假设从”2月龄及以上的每对兔子每一个月恰好繁殖一对新兔”改为”3(或m1)月龄及以上的每对兔子每一个月恰好繁殖一对新兔”时,你怎样推导相应的递推关系和初始条件?你能给出前10个月兔子的对数吗?,思考题 1-7,汉诺塔问题:一个著名数学游戏,游戏规则:今

29、有安装在一块木板上的3根柱子和若干中心有孔的盘子.这些盘子的直径两两不同.开始时,它们已按大小的次序套在第一根柱子上,使得每个盘子的下面没有比它小的盘子.每一次把1个盘子从一根柱子移动到另一根柱子,但是不允许这个盘子放在任何比它小的盘子上面.游戏的最终目标是把所有的盘子都放到第三根柱子上,并保持按大小次序放置,大盘子在下面.问题:令hn表示解n个盘子汉诺塔问题所需要的最少移动次数.试建立关于hn的递推关系并求出hn的依赖公式.,1,1,1,2,2,2,2,1,3,3,3,3,A,B,C,D,h2=3,1,1,1,2,2,2,2,1,3,3,3,3,A,B,C,D,3次,1次,3次,h3=7,1

30、,1,1,2,2,2,2,1,3,3,3,3,A,B,C,D,hn-1次,1次,hn-1次,hn=2hn-1+1,汉诺塔问题的解法,开始时n个盘子放在柱1.按照游戏规则和归纳法我们可以用hn-1次移动将上边的n-1个盘子移到柱2.在这些移动中保留最大的盘子不动,然后我们用一次移动将最大盘子移动到柱3.我们可以再使用hn-1次移动将柱2上的n-1个盘子移到柱3,把它们放到最大的盘子上面(这个最大的盘子一直放在柱3的底部不会破坏游戏规则).容易看出,使用更少的次数是不可能达到目的的.这就证明了hn=2hn-1+1.初始条件是h1=1,因为依照规则一个盘子可以经1次移动从柱1移到柱3.,hn=2hn

31、-1+1=2(2hn-2+1)+1=22hn-2+2+1=22(2hn-3+1)+2+1=23hn-3+22+2+1=2n-1h1+2n-2+2+1=2n-1+2n-2+2+1 用了初始条件h1=1=2n-1 用了等比数列和的公式,用迭代方法求解这个递推关系,2n-1+2n-2+2+1=2n-1的证明,令 x=2n-1+2n-2+2+1则 2n-1=2(2n-1+2n-2+2+1)-(2n-1+2n-2+2+1)=2x-x=x即 2n-1+2n-2+2+1=2n-1,在汉诺地方有一座塔,那里的僧侣们严格按照这个游戏规则从一根柱子到另一根柱子移动64个金盘子.他们一秒钟移动一个盘子.据说当他们结

32、束游戏时世界就到了末日.试问:这个世界在僧侣们开始移动盘子多久以后终结?答案:264-1秒 5000亿年,一个古老的传说,1,2,8,3,6,5,4,7,过圆周上等分点的三角形计数问题,假设n(3)为给定的正整数,并已知圆周上的n个等分点.试计算以这些等分点为顶点的一切可能的(计较顶点位置,如156与267或与154都是不同直角三角形)锐,直,钝角三角形个数.右图显示n=8的情形.,用循环数组(i,j,k)来刻画所讨论三角形的构形,其中i,j,k分别表示该三角形按反时针方向相邻二点间所夹已知等分点的个数.易见,经旋转后能重合的三角形构形相等;所讨论三角形的构形满足下列条件:i,j,k0,i+j

33、+k=n-3.(*)例如,在上面例子中的锐角三角形472,直角三角形156,钝角三角形238可分别刻画为(2,2,1),(3,0,2)和(0,4,1).,建立数学模型,构形(0,4,1)与(0,1,4)视为不同,因对应三角形238与235经任何旋转都不会重合.设ABC为有构形(i,j,k)的三角形,显然,ABC为直角三角形 maxi,j,k=n/2-1;ABC为锐角三角形 maxi,j,k n/2-1;ABC为钝角三角形 maxi,j,k n/2-1.,注 记,(i,j,k)中的i,j,k两两不同,则(i,k,j)视为与(i,j,k)构形不同的三角形构形.在具体计算直,钝角三角形个数时,只要确

34、定一切满足条件(*)的不同(非等边)三角形构形(i,j,k)的个数a,再乘以n即可.计算锐角三角形个数时,还要计算等边三角形(i=j=k)构形的个数b.则锐角三角形个数等于 n(a+b/3).,n=8时共计有 锐角构形一个:(1,2,2);直角构形3个:(1,1,3),(0,2,3),(0,3,2);钝角构形3个:(0,0,5),(0,1,4),(0,4,1)所以,锐角三角形个数是8;直,钝角三角形个数都是38=24.,n=8时三角形计数问题的解,当n=10时分别有多少锐,直,钝角三角形?当n=9时分别有多少锐,直,钝角三角形?,思考题 1-8,在复平面单位圆周上取定的n个等分点为a0,a1,

35、an-1,其中,ak=e2ki/n,k=0,1,n-1,以(0,j,k)表示顶点为a0,aj,ak满足:0jkn-1且 边a0ak为最长边的三角形.易见 三角形(0,j,k)为直(锐,钝)角三角形的充要条件是:k=n/2(n/2,n/2)令n1,n2,n3分别表示圆内接锐 角,直角,钝角三角形的个数.,0,1,n-1,2,三角形计数问题的另一种解法,j,k,m,0,1,n-1,2/n,实轴,虚轴,e2i/n,e2ki/n,k,点1的坐标向量是:(cos(2/n),sin(2/n)=e2i/n=cos(2/n)+sin(2/n)i,原点,n=2k时,n2的计算:令k=n/2,则过水平直径的直角三

36、角形是(0,j,k),j=1,2,k-1.由此可以推出 n2=n(k-1)=n(n/2-1)=n(n-2)/2.每个直角三角形顶点,在单位园周上任意移动总共可得出n个不同的直角三角形.,0,j,k,1,n-1,k-1,偶数n=2k时三角形计数问题的解,0,j,k,1,n-1,k-1,关于n2公式的另一种证明,以一条直径为斜边的一切可能的直角三角形数等于 n-2.因共有n/2条直径,故共有n(n-2)/2个直角三角形,即 n2=n(n-2)/2.,n=2k时,n3的计算 位于上半圆的钝角三角形是(0,i,j),1ijk-1 由此可以推出 n3=nCk-12=n(k-1)(k-2)/2=(n/2)

37、(n/2-1)(n/2-2).,0,j,k,1,n-1,k-1,i,n=2k时,n1的计算 n1+n2+n3=Cn3,n1=Cn3-n2-n3,其中,n2,n3 的公式如上所示.,试证:当n为偶数时,钝角三角形的个数是锐角三角形个数的三倍.,思考题 1-9,两个常用函数,这两个函数的定义域都是所有实数的集合R;陪(值)域为所有整数的集合I.地板(floor)函数:定义为不大于x的最大整数.天花板(ceiling)函数:定义为不小于x的最小整数.,-1,0,1,2,n2=0;n3=n(n-1)/2(n-1)/2-1)/2=nCk2 n1=Cn3-n2-n3.因为上半圆周上最大的等分点的编号是:(

38、n-1)/2=k.位于上半圆的钝角 三角形是:(0,i,j),其中 1ijk,0,j,1,n-1,(n1)/2,i,奇数n=2k+1时三角形计数问题的解,过大边上一点,例如点0,作直径d,则大边过此点并位于d 的两侧的一切可能的钝角三角形数等于 2Ck2=(n-1)/2(n-1)/2-1).让已知点取遍所有n个点共有2nCk2个钝角三角形,但每个三角形 都被多算了一次,故 n3=nCk2=,0,j,1,n-1,(n1)/2,i,关于n2公式的另一种证明,d,统一公式 n3=n(n-1)/2(n-1)/2-1)/2 n2=0,当n为奇数;n2=n(n-2)/2,当n为偶数.n1=Cn3-n2-n

39、3,三角形计数的统一公式,当n为奇数时,统一公式已成立.当n为偶数时,我们也已证明 n3=(n/2)(n/2-1)(n/2-2).易见,此时(因n/2是整数)成立 n/2-1=n/2-1/2=(n-1)/2,n/2-2=(n/2-1)-1=(n-1)/2-1,因此 n3=n(n-1)/2(n-1)/2-1)/2 所以,统一公式当n为偶数时也成立.,n=8时,n2=n(n-2)/2=8(8-2)/2=24;n3=n(n-1)/2(n-1)/2-1)/2=832/2=24.n1=C83-n2-n3=56-24-24=8.n=9时,n2=0;n3=943/2=54;n1=C93-n2-n3=84-5

40、4=30.n=10时,n2=10(10-2)/2=40;n3=1043/2=60;n1=C103-n2-n3=120-40-60=20.,三角形计数应用举例,双层玻璃窗保温功效可行性分析,问题:众所周知,住房内外热交换的主要部分是通过门窗的热交换.因此,为了节约空调费用,新式建筑物流行双层玻璃窗的设计,据说保温效果非常好.试从理论上对双层玻璃窗的功效作一个可行性分析.分析基点:对比有相同玻璃厚度的单,双层玻璃窗的传热过程,即对比两种情形下单位时间内通过玻璃窗单位面积流出去的热量哪个多哪个少,并算出二者相差的程度.,传热只限于通过门窗上玻璃的热传导,即忽略通过墙,地板及天花板的传热.窗户绝对密封

41、不产生对流,也不考虑辐射.只考虑处于稳定的热状态(平均状态).两种情形使用完全一样的均匀的窗玻璃.窗玻璃的面积是影响传热的唯一因素,即忽略窗框形状,深度及所用材料等因素对传热的影响.,模型假设,如图1-3所示,设S,D分别代表双层,单层玻璃的情形.对情形S,每片玻璃的厚度为d;夹层的厚度为b;室内,外近玻璃处的(常)温度,夹层靠室内,外近玻璃处的(常)温度分别为T1,T2,Ta,Tb.对情形D,每片玻璃的厚度为2d;室内,外近玻璃处的(常)温度分别为T1,T2.情形S,D单位时间内通过单位面积窗户的传热量分别记为QS,QD.,双层玻璃窗问题使用的符号,T1,T2,Ta,Tb,T1,T2,d,d

42、,b,2d,情形S,情形D,图 1-3,内,外,内,外,我们将要应用如下的物理定律Newton冷却定律:单位时间内通过厚度为b,热传导系数为k的介质的单位面积的传热量为:Q=k(T-T)/b,其中T为介质左方的温度;T为介质右方的温度,TT.,T,T,b,Newton 冷却定律,由Newton冷却定律得:QD=k1(T1-T2)/2d;QS=k1(T1-Ta)/d=k2(Ta-Tb)/b=k1(Tb-T2)/d其中,k1,k2分别为玻璃,空气的传热系数,可查手册求得;d,b,T1,T2可测量求得;Ta,Tb未知,但可通过计算求出.易见Ta-Tb=s(T1-Ta);Tb-T2=T1-Ta(令s=

43、k1b/(k2d)二式相加可求得:Ta=(s+1)T1+T2)/(s+2).进而求得:QS=k1(T1-T2)/(d(s+2).,双层玻璃窗问题的数学建模,由上面求得的公式,得出两种情形下传热量的比值是 QS/QD=2/(s+2)=f(s).(*)下面利用此公式,对双层玻璃窗的保温功效作一个详尽的分析与讨论.首先,由s0推出QSQD,即在任何情况下双层玻璃窗都有保温功效.查有关手册知:0.004k10.008;对干燥空气大约 k2=0.00025(焦尔/(度厘米秒),由此得s=k1b/(k2d)16b/d=16h(令h=b/d).,双层玻璃窗保温功效讨论,因函数f(s)=2/(s+2)的导数

44、f(s)=-2/(s+2)20,故它是s的严格递减函数,从而s16h 给出 QS/QD2/(16h+2).在通常情况下有 h=b/d4,于是QS/QD2/(16h+2)2/(64+2)=1/333%.这就是说,在通常情况下,双层玻璃窗的传热量仅为单层玻璃窗的3%.由此可见,双层玻璃窗的保温效果十分显著.这真是一个又好又省的技术,目前已开始全面推广(我家也用上了).,一个出乎意外的现象,人数分别为103,63和34的三个单位的一个20人的代表会议,上一届按照人数比例分配并参照小数尾数优先的惯例决定三单位按10,6和4分配代表席位.但下一届会议为了避免表决提案时出现10:10的僵持局面,决定增加一

45、席,他们按照上述方法算出的结果是11,7和3的分配方案(有关计算如表4-1所示).增加一席的分配结果显然对第三个单位不公平,因为他们反而比原来的分配方案减少了一席.,表1-1,问题:如何解释上述不合理现象并提出更合理的代表名额分配方案?,代表席位公平分配问题,不合理现象产生原因,按人数比例分配应该是公平的,但如何解释上述不合理现象呢?显然,其主要原因是代表席位只取整数值,即必须把公平但不是整数的理论席位值作取整处理,即将小数尾数舍去或增加为1.所以,执行的实际席位并非理论席位,从而难保其公平性.严格讲,不考虑单位人数多少单纯的小数尾数优先原则也不尽合理.,不合理现象的数学刻画(量化),建立数学

46、模型之前,必须对此不合理现象进行数学刻画.一般地,考察人数分别为pi,pj的单位i和单位j,设按某种分配方案分配给他们实际席位为ni,nj.让我们来讨论在此分配方案下对他们公平性的衡量.,显然,若pi/ni=pj/nj,则此分配(对二者)绝对公平.可惜,因ni,nj经过了取整,上述条件常常不能满足,故或者pi/nipj/nj,此时,对单位i不公平;或者 pi/nipj/nj,此时,对单位j不公平(为什么?).引进单位i的不公平值如下:ri(ni,nj)=(pi/ni-pj/nj)/(pj/nj)=pinj/(pjni)-1.现在讨论如何在已有分配方案的基础上修改增加一席的新方案.如把一席加给单

47、位j,则单位i的不公平值变为ri(ni,nj+1)=pi(nj+1)/(pjni)-1;如把一席加给单位i,则单位j的不公平值变为rj(ni+1,nj)=pj(ni+1)/(pinj)-1.,易见 ri(ni,nj+1)rj(ni+1,nj)qi qj 其中 qi=pi2/(ni(ni+1)是增加一个代表席位时衡量对单位i不公平程度的一个只依赖于i的参数.,上面的讨论引向下之增加1席的合理分配模型:把增加的1席分配给使比值qi取最大值的对应单位i(因为,未得到加1席的单位中它的不公平值最大,这个分配模型体现照顾矛盾最大者的政策,符合正确处理人民内部矛盾,建立和谐社会的原则).对所讨论的那个3单

48、位实例,先由表1-1得到20席的实际席位分配后,再按上述加1席合理分配模型得出的分配方案是:加1席给单位1,即分配方案向量为(11,6,4)(见表1-2),增加1席的合理分配模型,表1-2,结果的分析与讨论,加1席合理分配模型照顾可能最吃亏的单位,不言而喻是公平的.应用于上述3单位实例结果将不再发生增加代表名额后出现某些单位反而减少席位的不合理情况,这也是本模型合理性的一个佐证.表1-1,1-2对本例的计算结果也从一个侧面说明按老办法关于20、21席分配方案不合理.这一点也使我们认识到通常的按比例分配的办法并非绝对可靠,在某些特殊情况下,由于取整的影响也会产生显著的误差.,思路:先用常法分配1

49、9个代表席位,再用本模型加一席即可.计算结果如表1-3所示.此结果与用常法分配20个代表席位的结果不同,这一事实说明原先的分配方案其实并不合理.有趣的是,用本模型分配21个代表席位时,无论从20个代表席位的原方案或从新方案出发都得出同一正确结果(思考题).,如何用本模型合理分配20个代表名额?,表1-3,我们用表1-4给出的5单位的例子说明:上述模型也不是绝对正确.因78席时理论值小数尾数全相等,都等于0.4,故取整时可选任2单位加1,其余全舍去尾数.表1-4的两个计算结果说明,用合理加1席模型也得不出唯一合理的结果.下面将提出一个较为公平,但也较为复杂的模型方差最小模型.,合理加1席模型仍非

50、绝对正确,表1-4,代表席位分配的方差最小模型(创新),分析:要从分别有人数 p1,pm 的m个单位中选取n个代表.令 p=p1+pm,则p/n为每个席位平均代表的人数.先算出每个单位应分配代表数的理论值:b1,bm,bi=pin/p,i=1,m.照例记不大于x的最大整数为x;不小于x的最小整数为x,则ri=bi-bi为bi的小数尾数.,若 k=i=1mri 为0,则对每个i,bi都是整数(此时ni=bi),这是罕见的理想绝对公平情况.一般地,k为某个正整数,从而,总有某些bi不是整数.选定k个bi取整为bi=bi,其余取整为bi=bi.显然,对k个bi取整时,有至多Cmk种可能性.对第u种可

展开阅读全文
相关资源
猜你喜欢
相关搜索
资源标签

当前位置:首页 > 生活休闲 > 在线阅读


备案号:宁ICP备20000045号-2

经营许可证:宁B2-20210002

宁公网安备 64010402000987号