数学模型0-序言

数学模型 2010年春季 课程安排 • 每周3学时 • 分数组成 – 平时作业，20%; – 期终考试，30%; – 期终Project，两人合作完成，50%. • 任课教师：邓明华，刘旭峰（各半学期） – 理科一号楼1579E – Tel: 62767562 (O), 13522856599 (Cell) – Email: dengmh@pku.edu.cn 关于期末论文 • 提交时间：最后一次课之前(6月16或17日)。 • 提交方式：纸质和电子版本都需要上交， 电子论文上传到FTP服务器上 (162.105.160.23)。 • 竞赛论文原则上不能作为期末论文上交。 • 杜绝论文作弊。一旦发现，无成绩而且上 报学院领导处理。避免作弊嫌疑。 什么是数学模型？ • 模型：模型是把对象实体通过适当的过滤，用适 当的表现规则描绘出的简洁的模仿品。通过这个 模仿品,人们可以了解到所研究实体的本质,而且在 形式上便于人们对实体进行分析和处理。 • 数学模型：数学模型是对于现实世界的某一特定 对象，为了某个特定目的，作出一些必要的简化 和假设，运用适当的数学工具得到的一个数学结 构。它或者能解释特定现象的现实状态，或者能 预测对象的未来状态，或者能提供处理对象的最 优决策或控制。 为什么要开设数学模型课？ • 计算机技术的飞速发展，使得数学被广泛应用社 会生活的各个方面，使之逐渐成为一种技术。而 数学模型是数学从理论到技术转化的中心环节。 • 数学应用渗透到科学技术的各个领域，各种与数 学相关的交叉学科蓬勃发展。如数理金融，生物 信息论等。这对我们的数学教育也提出了新的要 求。而数学模型无疑数数学教育改革的一个最好 的切入点。 • 数学学院把数学模型课程作为全院的必修课程。 授课内容 1. 序言 2. 线性规划模型 3. 动态规划模型与DNA序列联配(Alignment). 4. 图论模型 5. 马氏模型与隐马氏模型 6. 种群生态学(Population Dynamics) 7. 分类模型 – 人工神经网络模型 (ANN) – 决策树 (Decision Tree) – 判别分析 (LDA) – 支持向量机 8. 随机模拟 线性规划模型 • 应用最广泛的方法之一。 • 最基本的方法之一。网络规划，整数规 划，目标规划和多目标规划都是以线性 规划为基础的。 • 解决稀缺资源最优分配的有效方法，使 付出的费用最小或获得的收益最大。 生产 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 问题 A B 备用资源 煤 1 2 30 劳动日 3 2 60 仓库 0 2 24 利润 40 50 A, B各生产多少, 可获最大利润? x1 + 2x2  30 3x1 + 2x2  60 2x2  24 x1，x2  0 max Z= 40x1 +50x2 生产计划问题（续） • 设产品A, B产量分别为变量x1, x2 10 Max(min)Z=C1X1+ C2X2+…+CnXn a11X1+ a12X2+…+ a1nXn (=, )b1 a21X1+ a22X2+…+ a2nXn (=, )b2 … … … am1X1+ am2X2+…+ amnXn (=, )bm Xj 0(j=1,…,n) 一般线性规划模型 线性规划问题求解 • 可行解：凸集； • 目标函数：线性函数，当然也是连续函数； • 数学理论：最优解在顶点上达到。如何在 顶点集合中搜索，而且保证目标函数朝最 优点的方向？单纯形法。 0 X2 X1 A D C B 序列比对(Alignment) • 人类基因组计划 (HGP, 1$/base) • ACGT表示的天书。 • 基本问题：给定两串序列，它们有多大的 相似程度？换句话说，怎样将这两个序列 比对，使它们的“符合度”最好？ 序列比对－动态规划模型 • 设有序列: X=(x1,x2,,xm) 与Y=(y1,y2,,yn) ,长 度分别为 m 和 n , 现要找出最优的全局比对 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 , 使得对在给定的打分函数下得到最高分。 • 例：X=“ACGAA” Y=“AACAGAC” 打分策略为每个正确匹配加 1 分 每个配错位置减 1 分，每个插入位置减 1 分。 递推变量 • 设矩阵F=(F(i,j)) 为 X, Y 的子序列 X1,i和 Y1,j 的最佳比对得分。在我们的例子里 F(2,3) 就是 的最佳比对得分。 • 我们可以用递推的方法把 F 求出来, 而 F(m,n) 和与F(m,n) 相对应的比对方案正 是我们想要的结果。 X -- A C -- G A A Y A A C A G A C 1100-1-1-3-5A 1201-10-2-4A -10100-1-1-3G -3-2-10100-2C -5-4-3-2-101-1A -7-6-5-4-3-2-10X CAGACAAY X A -- C -- G A A Y A A C A G A C 哥尼斯堡七桥问题 • 七桥分布如右图所示。 • 问题：从A、B、C、D中的某一处出发，通 过每座桥恰好一次，再回到起点，是否可能？ A B e1 e2 e3 e4 e5 C D e6 e7 C D A B 估计食堂就餐人数 －马氏链模型 A B 就餐人数问题解答 • 不动点问题： • 马氏链(Markov Chain)不变分布. Google Page Rank • A page is important if important pages link to it. • Eigen-value problem. A T1 Tn … C(A) 韦小宝的骰子－隐马氏模型 • 两套骰子，开始以2/5的概率出千。 – 正常A：以1/6的概率出现每个点 – 不正常B：5,6出现概率为3/10,其它为1/10 • 出千的随机规律 A B0.8 0.2 0.9 0.1 韦小宝的骰子－隐马氏模型 • 观测到其一次投掷结果 • 问题：请判断韦小宝什么时候出千了？ 种群动力学 • 单物种Logistic模型 种群动力学 • 两物种捕食模型 蠓虫分类 • 89年MCM赛题：已知两类蠓虫Af和Apf的若 干数据（翼长和触角长度），要求制定一 定的方法，以正确区分两类蠓虫。 • 对于新的未知类别的蠓虫，测量其数据资 料，如何对其类型进行识别。 • 若Af是益虫，Apf是害虫，考虑该因素后， 分类方法是否需要改变以及如何改变。 多层感知器网络 • 从下到上，底层的输出是高层的输入。 • 多层感知器至少要有三层：输入层、输出层与 隐层。 O1    O2 Om H1 HkH2 Ii I2 In 输出层 隐层 输入层 Wki Wjk 误差后传算法 • 输出单元上的误差 • 隐单元上的误差 • 隐单元上的误差实际上是输出单元上误差的线性组 合(向后传播)，这就是误差后传算法的由来。 Day Outlook Temperature Humidity Wind Play Tennis 1 Sunny Hot High Weak No 2 Sunny Hot High Strong No 3 Overcast Hot High Weak Yes 4 Rain Mild High Weak Yes 5 Rain Cool Normal Weak Yes 6 Rain Cool Normal Strong No 7 Overcast Cool Normal Strong Yes 8 Sunny Mild High Weak No 9 Sunny Cool Normal Weak Yes 10 Rain Mild Normal Weak Yes 11 Sunny Mild Normal Strong Yes 12 Overcast Mild High Strong Yes 13 Overcast Hot Normal Weak Yes 14 Rain Mild High Strong No Outlook Sunny Overcast Rain Humidity Yes Wind High Normal No Yes No Yes Strong Weak 决策树实例 Buffon投针实验 －随机模拟 d L 设针与平行线的夹角为，针 的中点与最近的平行线的距 离为X，相交条件为: Buffon实验 学者 年代 l/d 总次数 成功 次数 的 估计 Wolf 1850 0.8 5000 2532 3.15956 Smith 1855 0.6 3204 1218 3.1554 Fox 1884 0.75 1030 489 3.1595 Lazzarini 1907 0.833 3408 1808 3.14159292 积分计算 数学建模一般步骤 1. 模型准备：首先要了解问题的实际背景，明确 题目的要求，收集各种必要的信息。 2. 模型假设：为了利用数学方法，通常要对问题 做出必要的、合理的假设，使问题的主要特征 凸现出来，忽略问题的次要方面。 3. 模型建立：根据所做的假设以及事物之间的联 系，构造各种量之间的关系把问题化为数学问 题，注意要尽量采用简单的数学工具。 数学建模一般步骤(Cont.) 4. 模型求解：利用已知的数学方法来求解上一步所 得到的数学问题，此时往往还要作出进一步的简 化或假设。 5. 模型分析：对所得到的解答进行分析，特别要注 意当数据变化时所得结果是否稳定。 6. 模型检验：分析所得结果的实际意义，与实际情 况进行比较，看是否符合实际，如果不够理想， 应该修改、补充假设，或重新建模，不断完善。 7. 模型应用：所建立的模型必须在实际应用中才能 产生效益，在应用中不断改进和完善。 数学模型论文结构 • 摘要 • 问题叙述 • 模型假设及模型建立 • 模型求解 • 结果显示与分析 • 模型评价 • 参考文献 • 附录 什么是好的建模论文？ • 假设合理 • 建模创新 – 模型本身的创新，巧妙的简化策略； – 巧妙、简洁的求解算法； • 结果合理，符合实际； – 对数值结果进行必要的检验和分析； – 必要的比较分析； – 明确的结论。 • 表述清晰－摘要，图表，模型总结，文献等。 草坪灌溉问题 • 静园草坪灌溉系统的改进，一个平面覆盖 的效率问题。 平面覆盖问题的解答 • 可以证明：最大覆盖效率为 • 而且可以通过正六边形覆盖达到。即把单 位圆盘放在边长为 的正六边形的顶点之 上。 草坪灌溉问题－推广 • 当多个大小不等的喷头时怎样处理，又会 有什么样的结论？ • 其他应用 – 田间自动灌溉。 – 建筑物上灯的布设。 – 信号中转站的布设。例如理科楼群中无线网络 问题。 数学模型竞赛 • 美国数学模型竞赛 (http://www.comap.com/undergraduate/con tests/), Mathematical Contest in Modeling (MCM), 1985年开始。The Interdisciplinary Contest in Modeling (ICM)，1999年开始。 • 三人组队，三天时间用英文完成一篇完整的 报告(包括问题阐述，假定与假设说明，模 型分析与设计，问题求解，模型的评价与分 析)。 数学模型竞赛(续) • 奖励：Outstanding (O)，Meritorious (M), Honorable Mention (H), Successful Participation (P)。 • 89年2月我国首次参加MCM (四个队)。 • 中国大学生数学建模竞赛 China Undergraduate Mathematical Contest in Modeling (CUMCM) (http://www.mcm.edu.cn/)。90年上海市， 1992年10个城市联赛，首次全国性竞赛。 数学软件 • 通用数学软件 Mathematica, Maple, Matlab; • 统计软件R，Splus，Statistica; • 规划软件 Lindo, Lingo; • 论文写作 – Tex套装 (Winedit, Miktex, GSview) – Word. 参考书 • 雷功炎，数学模型讲义，北京大学出版社， 1999。 • 姜启源，数学模型，高等教育出版社，1987 第一版，1993第二版，2003第三版。 • 刘来福，曾文艺，数学模型与数学建模，北 京师范大学出版社，1997第一版，2002第 二版。 • 谭永基，俞文(鱼此)，数学模型，复旦大学 出版社，1997。 • 王树禾，数学模型基础，中国科学技术大学 出版社，1996。 参考书(续) • W.F.Lucas, 微分方程模型，国防科技大 学出版社，1988。 • W.F.Lucas, 生命科学模型，国防科技大 学出版社，1996。 • W.F.Lucas, 离散与系统模型，国防科技 大学出版社，1996。 • W.F.Lucas, 政治及有关模型，国防科技 大学出版社，1996。 参考书(续) • 叶其孝，大学生数学模型竞赛辅导教材 (一)、 (二)、 (三)，湖南教育出版社，1997。 • 李尚志等，数学建模竞赛教程，江苏教育出版社， 1996。 • 叶其孝，数学建模教育与国际数学建模竞赛－工 科数学专辑，工科数学杂志社，1994。 • 李大潜，中国大学生数学建模竞赛，高等教育出 版社，1998。