数学建模与问题求解Modeling.pdf

1 数学建模与问题求解数学建模与问题求解 张铭张铭 2007 12 28 X1X2XT O1O2OT 内容简介内容简介 一 什么是数学模型一 什么是数学模型 二 数学模型分类二 数学模型分类 三 问题建模示例三 问题建模示例 四 数学模型与数据结构问题求解四 数学模型与数据结构问题求解 雷涛雷涛 五 小结五 小结 参考资源参考资源 玩具 飞机模型 火箭模型玩具 飞机模型 火箭模型 实物模型 水箱中的舰艇 风洞中的飞机 实物模型 水箱中的舰艇 风洞中的飞机 物理模型 地图 电路图 分子结构图 物理模型 地图 电路图 分子结构图 符号模型 我们常见的模型 符号模型 我们常见的模型 一 什么是数学模型一 什么是数学模型 生物生物DNA螺旋模型螺旋模型 夸克粒子 模型 社 会 演 化 模 型社 会 演 化 模 型 伟大的科学模型及实践伟大的科学模型及实践 地球板块模型地球板块模型 宇宙大爆炸 模型宇宙大爆炸 模型 用用 x 表示船速 表示船速 y 表示水速 列出方程 表示水速 列出方程 75050 75030 yx yx 答 船速每小时答 船速每小时20千米 千米 甲乙两地相距甲乙两地相距750公里 船从甲到乙顺水航行需公里 船从甲到乙顺水航行需30小时 从乙到甲逆水航行需 小时 从乙到甲逆水航行需50小时 问船的速度是多少小时 问船的速度是多少 x 20 y 5 求解求解 初级数学模型初级数学模型 航行问题 航行问题 作出简化假设 船速 水速为常数 作出简化假设 船速 水速为常数 用符号表示有关量 用符号表示有关量 x y表示船速和水速 表示船速和水速 用物理定律 匀速运动的距离等于速度乘以 时间 列出数学公式 二元一次方程 用物理定律 匀速运动的距离等于速度乘以 时间 列出数学公式 二元一次方程 求解得到数学解答 求解得到数学解答 x 20 y 5 回答原问题 船速每小时回答原问题 船速每小时20千米 千米 航行问题建模基本步骤航行问题建模基本步骤 2 数学模型和数学建模数学模型和数学建模 数学模型 通过抽象和简化 使用数学语言对 实际对象的一个刻画 以便于人们 更简明更深刻地认识所研究的对象 数学模型 通过抽象和简化 使用数学语言对 实际对象的一个刻画 以便于人们 更简明更深刻地认识所研究的对象 数学建模 根据要求 针对实际问题 组建数学模型的全过程 包括建立 求解 分析 检验等 数学建模 根据要求 针对实际问题 组建数学模型的全过程 包括建立 求解 分析 检验等 模型 实际原型主要特征的抽象和简化 一个低代价近似 模型 实际原型主要特征的抽象和简化 一个低代价近似 对于一个现实对象 为了一个特定目的 根据其内在规律 作出必要的简化假设 运用适当的数学工具 得到的一个数学结构 对于一个现实对象 为了一个特定目的 根据其内在规律 作出必要的简化假设 运用适当的数学工具 得到的一个数学结构 数学模型数学模型 电子计算机的出现及飞速发展电子计算机的出现及飞速发展 数学以空前的广度和深度向一切领域渗透数学以空前的广度和深度向一切领域渗透 数学建模作为用数学方法解决实际问题的第一步 越来越受到人们的重视 数学建模作为用数学方法解决实际问题的第一步 越来越受到人们的重视 数学建模数学建模计算机技术计算机技术 如虎添翼如虎添翼 知识经济知识经济 数学建模的重要意义数学建模的重要意义 应用领域人口 交通 经济 生态 应用领域人口 交通 经济 生态 数学方法初等数学 微分方程 规划 图 统计 数学方法初等数学 微分方程 规划 图 统计 表现特性 描述 优化 预报 决策 表现特性 描述 优化 预报 决策 建模目的建模目的 了解程度白箱灰箱黑箱 确定和随机静态和动态 线性和非线性 离散和连续 了解程度白箱灰箱黑箱 确定和随机静态和动态 线性和非线性 离散和连续 二 数学模型的分类二 数学模型的分类 模型的数学分类模型的数学分类 微分方程模型微分方程模型 差分方程模型差分方程模型 层次分析模型层次分析模型 规划模型规划模型 统计模型统计模型 模拟模拟 图论模型图论模型 三 问题建模示例三 问题建模示例 1 雨中行走问题雨中行走问题 初等数学初等数学 2 生产计划问题生产计划问题 线性规划模型线性规划模型 3 椅子能放平吗 椅子能放平吗 高等数学高等数学 4 Buffon投针实验投针实验 模拟模拟 5 马氏链模型马氏链模型 统计模型统计模型 6 坐船问题坐船问题 图论图论 3 1 雨中行问题雨中行问题 问题 外出行走遇雨 走多快才会少淋雨呢 问题 外出行走遇雨 走多快才会少淋雨呢 分析 这一问题的主要因素有分析 这一问题的主要因素有 降雨的大小降雨的大小 降雨的方向降雨的方向 路程的远近和跑的快慢路程的远近和跑的快慢 雨中行问题建模雨中行问题建模 行人速度 行人速度 u 0 0 定速沿直线 定速沿直线 雨速 雨速 Vx Vy Vz 行走的距离 行走的距离 d 前 侧 顶面积 之比前 侧 顶面积 之比1 L T 单位时间淋雨量 单位时间淋雨量 u Vx Vy L Vz T 总淋雨量 总淋雨量 R u d u u Vx Vy L Vz T 数学问题 已知数学问题 已知d Vx Vy Vz 求 求u为何值时为何值时 R u 最小 最小 雨中行问题结论雨中行问题结论 如果迎着雨走如果迎着雨走 雨迎面和垂直落下雨迎面和垂直落下 尽可能快跑尽可能快跑 如果雨是从背后落下如果雨是从背后落下 控制行走速度控制行走速度 使刚好等于雨滴速度的水平分量使刚好等于雨滴速度的水平分量 R u d u u Vx Vy L Vz T 2 线性规划模型线性规划模型 应用最广泛的方法之一 应用最广泛的方法之一 最基本的方法之一 网络规划 整数规划 目标规划和多目标规 划都是以线性规划为基础的 最基本的方法之一 网络规划 整数规划 目标规划和多目标规 划都是以线性规划为基础的 解决稀缺资源最优分配的有效方 法 使付出的费用最小或获得的 收益最大 解决稀缺资源最优分配的有效方 法 使付出的费用最小或获得的 收益最大 生产计划问题生产计划问题 A B 备用资源 煤 备用资源 煤1 2 30 劳动日劳动日3 2 60 仓库仓库0 2 24 利润利润40 50 A B各生产多少各生产多少 可获最大利润可获最大利润 x 2y 30 3x 2y 60 2y 24 x y 0 max Z 40 x 50y 生产计划问题模型生产计划问题模型 设产品设产品A B产量分别为变量产量分别为变量x y 4 0 Y X A D C B Y X A D C B 3x 2y 60 x 2y 30 2y 24 20 Max min Z C1X1 C2X2 CnXn a11X1 a12X2 a1nXn b b1 1 a21X1 a22X2 a2nXn b b2 2 am1X1 am2X2 amnXn b bm m Xj j 0 0 j 1 n 一般线性规划模型一般线性规划模型 目标函数 约束条件 决策变量 目标函数 约束条件 决策变量 X1 X2 Xn 线性规划问题求解线性规划问题求解 可行解 凸集可行解 凸集 最优解 在顶点上达到最优解 在顶点上达到 求解方法 求解方法 单纯形法单纯形法 软件包软件包 http n j jjx cZ 1 max min 2 1 0 2 1 1 njx mibxa ts j n j ijij 问题分析问题分析 模 型 假 设 模 型 假 设 通常通常 三只脚着地放稳三只脚着地放稳 四只脚着地四只脚着地 四条腿一样长 椅脚与地面点接触 四脚 连线呈正方形 四条腿一样长 椅脚与地面点接触 四脚 连线呈正方形 地面高度连续变化 可视为数学上的连续 曲面 地面高度连续变化 可视为数学上的连续 曲面 地面相对平坦 使椅子在任意位置至少三 只脚同时着地 地面相对平坦 使椅子在任意位置至少三 只脚同时着地 3 椅子在不平地面的稳定性椅子在不平地面的稳定性 模型构成模型构成 用数学语言表示椅子位置和四只脚着地的关系用数学语言表示椅子位置和四只脚着地的关系 椅子位置利用正方形椅子位置利用正方形 椅脚连线椅脚连线 的对称性的对称性 x B A D C O D C B A 用用 对角线与对角线与x轴的夹角轴的夹角 表示椅子位置表示椅子位置 四只脚着地 距离是 四只脚着地 距离是 的函数的函数 四个距离四个距离 四只脚四只脚 A C 两脚与地面距离之和两脚与地面距离之和 f B D 两脚与地面距离之和两脚与地面距离之和 g 两个距离两个距离 椅脚与地面距离为零 正方形 椅脚与地面距离为零 正方形ABCD 绕绕O点旋转点旋转 正方形 对称性 正方形 对称性 用数学语言把椅子位置和四只脚着地的关系表示出来用数学语言把椅子位置和四只脚着地的关系表示出来 f g 是连续函数 对任意 是连续函数 对任意 f g 至少一个为至少一个为0 数学 问题 数学 问题 已知 已知 f g 是连续函数是连续函数 对任意对任意 f g 0 且且 g 0 0 f 0 0 证明 存在证明 存在 0 使 使f 0 g 0 0 模型构成模型构成 地面为连续曲面地面为连续曲面 椅子在任意位置 至少三只脚着地 椅子在任意位置 至少三只脚着地 5 模型求解模型求解 给出一种简单 粗糙的证明方法给出一种简单 粗糙的证明方法 将椅子旋转将椅子旋转900 对角线 对角线AC和和BD互换 由 互换 由g 0 0 f 0 0 知 知f 2 0 g 2 0 令令h f g 则则h 0 0和和h 2 0 由由 f g的连续性知的连续性知 h为连续函数为连续函数 据连续函数的基本性 质 据连续函数的基本性 质 必存在必存在 0 使使h 0 0 即即f 0 g 0 因为因为f g 0 所以所以f 0 g 0 0 评注和思考评注和思考建模的关键建模的关键 假设条件的本质与非本质考察四脚呈长方形的椅子假设条件的本质与非本质考察四脚呈长方形的椅子 和和 f g 的确定的确定 4 Buffon投针实验投针实验 随机模拟方法 也称为随机模拟方法 也称为Monte Carlo方法 方法 人为地造出一种概率模型 使它的某些参数 恰好重合于所需计算的量 人为地造出一种概率模型 使它的某些参数 恰好重合于所需计算的量 通过实验 用统计方法求出这些参数的估 值 把这些估值作为要求的量的近似值 通过实验 用统计方法求出这些参数的估 值 把这些估值作为要求的量的近似值 18世纪下半叶的法国学者18世纪下半叶的法国学者Buffon提出用 投针试验的方法来确定圆周率 的值 提出用 投针试验的方法来确定圆周率 的值 Monte Carlo方法的最早的尝试 方法的最早的尝试 Buffon投针实验投针实验 d L 设针与平行线的夹角为 针 的中点与最近的平行线的距 离为X 相交条件为 Buffon实验结果实验结果 的 估计 成功 次数 总次数 的 估计 成功 次数 总次数l d年代学者年代学者 3 14159292180834080 8331907Lazzarini 3 159548910300 751884Fox 3 1554121832040 61855Smith 3 15956253250000 81850Wolf 祖冲之 公元祖冲之 公元429 公元公元500 介于 介于3 1415926和和3 1415927之间之间 公元公元464年年 5 Markov链链 S1 S2S3 S1 Sunny S2 Rainy S3 Cloudy 0 80 10 1 0 30 40 3 0 20 20 6 A 0 8 0 1 0 1 0 4 0 3 0 3 0 2 0 6 0 2 100 A Markov模型模型 状态集状态集 转移概 矩阵 初始状态概 向 转移概 矩阵 初始状态概 向 Markov观测观测 第一天天气第一天天气sunny 接下来接下来7天天气为天天气为sun sun rain rain sun cloudy sun 的概率是多少 的概率是多少 观察序列观察序列O S1 S1 S1 S2 S2 S1 S3 S1 P O Moel P S1 S1 S1 S2 S2 S1 S3 S1 Model P 1 P S1 S1 P S1 S1 P S2 S1 P S2 S2 P S1 S2 P S3 S1 P S1 S3 1 a11 a11 a12 a22 a21 a13 a31 1 0 8 0 8 0 1 0 4 0 3 0 1 0 2 1 536 10 4 0 80 10 1 0 30 40 3 0 20 20 6 A 6 扩展和应用扩展和应用 OMM的每个状态代表一个事件的每个状态代表一个事件 event 对应一个观察符号对应一个观察符号 observation HMM Hidden Markov Model 的每个的每个 observation对应一个对应一个event 每个状态以 不同概率发射不同的 每个状态以 不同概率发射不同的observation 线性序列相关的应用线性序列相关的应用 语音识别 基因分析语音识别 基因分析 四 图论模型与数据结构问题求解四 图论模型与数据结构问题求解 坐船问题 改编自湖南省信息学省队选 拔赛试题 坐船问题 改编自湖南省信息学省队选 拔赛试题 北大有北大有n个学生去公园划船 个学生去公园划船 一只船最多坐一只船最多坐2个人 个人 出于娱乐目的 大家决定同船的出于娱乐目的 大家决定同船的2个人要么 同姓要么同名 个人要么 同姓要么同名 每个人都必须上船 且一人不能上多只船每个人都必须上船 且一人不能上多只船 问最少需要几只船问最少需要几只船 例例1 姚金宇 李金宇 姚峰宏 陈峰宏姚金宇 李金宇 姚峰宏 陈峰宏 姚金宇 姚峰宏姚金宇 姚峰宏 陈峰宏陈峰宏 李金宇李金宇 姚金宇 李金宇姚金宇 李金宇 陈峰宏 姚峰宏陈峰宏 姚峰宏 例例2 陈峰宏 囧峰宏 罗睿辞 廖叶子陈峰宏 囧峰宏 罗睿辞 廖叶子 陈峰宏 囧峰宏陈峰宏 囧峰宏 罗睿辞罗睿辞 廖叶子廖叶子 陈峰宏 囧峰宏陈峰宏 囧峰宏 罗睿辞 廖叶子罗睿辞 廖叶子 将每一同学视为一顶点将每一同学视为一顶点 顶点之间的关系为同名或者同姓顶点之间的关系为同名或者同姓 2名同学同名或者同姓就连一条边名同学同名或者同姓就连一条边 建模建模 图模型图模型 姚金宇李金宇 姚峰宏陈峰宏 姚金宇李金宇 姚峰宏陈峰宏 图论问题图论问题 一条边代表一种坐船的搭配方式一条边代表一种坐船的搭配方式 用最少的边覆盖图中的点用最少的边覆盖图中的点 一般图的最小边覆盖问题一般图的最小边覆盖问题 一般图最大匹配问题 算法复杂 实现麻烦 一般图最大匹配问题 算法复杂 实现麻烦 姚金宇李金宇 姚峰宏陈峰宏 姚金宇李金宇 姚峰宏陈峰宏 7 图转换成二叉树图转换成二叉树 树中一个结点的左孩子跟其同姓 树中一个结点的左孩子跟其同姓 一个结点的右孩子跟其同名一个结点的右孩子跟其同名 对于原图中的每一个连通分量 一定可 以转换成一棵二叉树 对于原图中的每一个连通分量 一定可 以转换成一棵二叉树 罗睿辞 罗贯中罗纳尔多 廖睿辞 罗睿辞 罗贯中罗纳尔多 廖睿辞 罗睿辞 罗贯中 罗纳尔多 廖睿辞 罗睿辞 罗贯中 罗纳尔多 廖睿辞 问题的解决问题的解决 对于图 对于图 单独考虑原图每个连通分量单独考虑原图每个连通分量 含有含有n个点的连通分量 至少需要个点的连通分量 至少需要 n 1 div 2只船只船 每个连通分量需要船总和 是问题的下界每个连通分量需要船总和 是问题的下界 对于一棵二叉树 对于一棵二叉树 使用贪心法 一定可以构造出一个只需使用贪心法 一定可以构造出一个只需 n 1 div 2只船的解只船的解 罗睿辞 罗贯中 罗纳尔多 廖睿辞 罗睿辞 罗贯中 罗纳尔多 廖睿辞 罗纳尔多是罗贯 中的独生子 去 掉他们 罗纳尔多是罗贯 中的独生子 去 掉他们2个 树依 然连通 罗睿辞 廖睿辞 个 树依 然连通 罗睿辞 廖睿辞 廖睿辞依然是罗 睿辞的独生子 将它们分成一组 罗贯中 罗纳尔多 廖睿辞依然是罗 睿辞的独生子 将它们分成一组 罗贯中 罗纳尔多 罗睿辞 廖睿辞 罗睿辞 廖睿辞 得到了一组 最优解 得到了一组 最优解 贪心构造贪心构造 1 若叶子结点是父亲的独生子 则删 去它们 若叶子结点是父亲的独生子 则删 去它们2个 树依然保持性质个 树依然保持性质 2 若父亲结点有 若父亲结点有2个孩子个孩子 重复以上步骤直至树为空或者只剩 一个结点为止 重复以上步骤直至树为空或者只剩 一个结点为止 贪心举例贪心举例 陈峰宏 贾 由 陈 云 王 云 万金由贾 云 陈峰宏 贾 由 陈 云 王 云 万金由贾 云 贪心举例贪心举例 陈峰宏 贾 由 陈 云 王 云 万金由贾 云 陈峰宏 贾 由 陈 云 王 云 万金由贾 云 8 贪心举例贪心举例 陈峰宏 贾 由 陈 云 王 云 万金由贾 云 陈峰宏 贾 由 陈 云 王 云 万金由贾 云 陈峰宏 贾 由 陈 云 王 云 万金由贾 云 陈峰宏 贾 由 陈 云 王 云 万金由贾 云 贪心举例贪心举例 贪心举例贪心举例 陈峰宏 贾 由 陈 云 王 云 万金由 贾 云 陈峰宏 贾 由 陈 云 王 云 万金由 贾 云 贪心举例贪心举例 陈峰宏 贾 由 陈 云 王 云 万金由 贾 云 陈峰宏 贾 由 陈 云 王 云 万金由 贾 云 问题求解小结问题求解小结 建模是一个去粗取精的过程 要尽可能利用对我们有利的信 息 而忽略那些与我们目标无 关的信息 建模是一个去粗取精的过程 要尽可能利用对我们有利的信 息 而忽略那些与我们目标无 关的信息 根据需要转化模型 根据需要转化模型 LCA与与 RMQ问题之间相互转化 就是 树与序列相互辅助的经典例 子 问题之间相互转化 就是 树与序列相互辅助的经典例 子 五 小结五 小结 数学建模的一般步骤数学建模的一般步骤 建模策略建模策略 数据结构中的问题建模数据结构中的问题建模 9 社会实践理论研究 数学建模 程序实现 模型准备模型准备 模型应用模型应用分析检验分析检验 模型求解模型求解 模型建立模型建立模型假设模型假设 反馈 建模的步骤建模的步骤 模 型 假 设 模 型 假 设 针对问题特点和建模目的针对问题特点和建模目的 作出合理的 简化的假设作出合理的 简化的假设 在合理与简化之间作出折中在合理与简化之间作出折中 模 型 构 成 模 型 构 成 用数学的语言 符号描述问题用数学的语言 符号描述问题 发挥想象力发挥想象力使用类比法使用类比法 尽量采用简单的数学工具尽量采用简单的数学工具 数学建模的一般步骤数学建模的一般步骤 模型 求解 各种数学方法 软件和计算机技术 如结果的误差分析 统计分析 模型对数据的稳定性分析 模型 求解 各种数学方法 软件和计算机技术 如结果的误差分析 统计分析 模型对数据的稳定性分析 模型 分析 模型 分析 模型 检验 与实际现象 数据比较 检验模型的合理性 适用性 模型 检验 与实际现象 数据比较 检验模型的合理性 适用性 模型应用模型应用 数学建模的一般步骤数学建模的一般步骤 建模策略建模策略 自顶向下 问题分解自顶向下 问题分解 归纳策略归纳策略 得到一种高度抽象的解题模型得到一种高度抽象的解题模型 化繁为简 变未知为已知化繁为简 变未知为已知 A问题 问题 B问题问题 模拟策略 改变参数 观察变化模拟策略 改变参数 观察变化 随机模拟随机模拟 过程模拟过程模拟 设计算法时通常考虑的因素设计算法时通常考虑的因素 模型必须尽量多地体现问题的本质特征模型必须尽量多地体现问题的本质特征 并不意味着模型越复杂越好并不意味着模型越复杂越好 累赘的信息会影响算法的效率累赘的信息会影响算法的效率 模型需要反复修改模型需要反复修改 检验 修改 在实践中不断完善检验 修改 在实践中不断完善 数学模型是程序的基础数学模型是程序的基础 程序设计过程程序设计过程 问题抽象 分析问题 建立数学模型问题抽象 分析问题 建立数学模型 数据抽象 选择数据结构数据抽象 选择数据结构 算法抽象 设计算法算法抽象 设计算法 用计算机语言实现用计算机语言实现 程序程序 数据结构数据结构 算法算法 10 数据结构定义数据结构定义 数据逻辑结构数据逻辑结构 数据的存储结构数据的存储结构 数据的运算数据的运算 存储存储 数据 结构 数据 结构 逻辑逻辑 运算运算 常见的逻辑关系常见的逻辑关系 线性结构线性结构 树形结构树形结构 图结构图结构 文件结构 图 树 二叉树 线性表 文件结构 图 树 二叉树 线性表 数据的存储结构数据的存储结构 映射 逻辑映射 逻辑 存储存储 四种存储结构 四种存储结构 顺序顺序 链接链接 索引索引 散列散列 典型算法典型算法 问题规模 问题规模 n 问题空间问题空间 搜索搜索 DFS BFS 穷举穷举 百钱买百鸡百钱买百鸡 贪心贪心 Huffman树树 递归递归 回溯回溯 八皇后八皇后 分治分治 二分法检索二分法检索 动态规划动态规划 最佳二叉排序树最佳二叉排序树 数据结构与算法数据结构与算法 理论理论 算法的数学基础算法的数学基础 算法的时间和空间度量算法的时间和