数学建模_计算机模拟技术1.pdf

模拟技术模拟技术 河南师范大学数学学院河南师范大学数学学院 1 模拟基础 模拟基础 2 Monte Carlo模拟 模拟 3 模拟模型案例模拟模型案例 1 模拟基础模拟基础 1 0 模拟的背景 思路模拟的背景 思路 应用领域 应用领域 第二次世界大战期间 第二次世界大战期间 J V Neumann等人将进行的等人将进行的 中 子扩散 中 子扩散 的科研项目取名为的科研项目取名为 Monte Carlo 运输系统模拟运输系统模拟 摩天大楼安全疏散系统模拟摩天大楼安全疏散系统模拟 国民经济发展模拟国民经济发展模拟 人口增长系统模拟人口增长系统模拟 供水系统模拟供水系统模拟 管理系统模拟管理系统模拟 雷达系统模拟雷达系统模拟 战争系统模拟 模拟思路 战争系统模拟 模拟思路 模拟模拟 对系统抽象建模 对系统抽象建模 试验试验 根据模型设计算法 编程进行反复试验 根据模型设计算法 编程进行反复试验 估计估计 根据试验数据 根据试验数据 收集收集 根据试验结果作出判断 根据试验结果作出判断 1 1 模拟的基本知识1 1 模拟的基本知识 1 1 1 模拟的概念及作用模拟的概念及作用 现实系统的数学或逻辑模型可能十分复 杂 例如大多数具有随机因素的复杂系 统 其中的一些随机性因素很难用准确的 数学公式表述 从而也无法对整个系统采 用解析法求解 模拟是处理这类实际问题 的有力工具 现实系统的数学或逻辑模型可能十分复 杂 例如大多数具有随机因素的复杂系 统 其中的一些随机性因素很难用准确的 数学公式表述 从而也无法对整个系统采 用解析法求解 模拟是处理这类实际问题 的有力工具 模拟通常借助于计算机进行 计算机模拟 在已经建立的数学 逻辑模 型的基础之上 通过计算机试验 对一个 系统按照一定的决策原则或作业规则 由 一个状态变换为另一个状态的行为进行描 述和分析 模拟通常借助于计算机进行 计算机模拟 在已经建立的数学 逻辑模 型的基础之上 通过计算机试验 对一个 系统按照一定的决策原则或作业规则 由 一个状态变换为另一个状态的行为进行描 述和分析 模拟的作用 模拟的作用 对于很难用解析方法加以处理的问题 模 拟是一种有效的技术 对于很难用解析方法加以处理的问题 模 拟是一种有效的技术 对建模过程中的假设进行鉴定 对理论研 究的结论加以检验 对建模过程中的假设进行鉴定 对理论研 究的结论加以检验 对不同的实现方案进行多次模拟 按照既 定的目标函数对不同方案进行比较 从中 选择最优方案 对不同的实现方案进行多次模拟 按照既 定的目标函数对不同方案进行比较 从中 选择最优方案 1 1 2 模拟的分类 通常 模拟时间是模拟的主要自变量 设计正确的模拟时间推进机理 模拟过程中 应根据系统的特性正确推进模拟时间 使 系统中各要素与发生的事件保持同步 1 1 2 模拟的分类 通常 模拟时间是模拟的主要自变量 设计正确的模拟时间推进机理 模拟过程中 应根据系统的特性正确推进模拟时间 使 系统中各要素与发生的事件保持同步 推进模拟时间的基本方法 推进模拟时间的基本方法 下次事件法 将模拟时间由一个事件发生 的时间点推进到紧接着的下一次事件发生 的时间点 下次事件法 将模拟时间由一个事件发生 的时间点推进到紧接着的下一次事件发生 的时间点 固定时间步长法 模拟时间每次均以相等 的固定步长向前推进 每到达一个新的模 拟时间点需检查相应时间段内是否发生了 事件 需根据实际问题合理设置模拟时间 发生改变的步长 固定时间步长法 模拟时间每次均以相等 的固定步长向前推进 每到达一个新的模 拟时间点需检查相应时间段内是否发生了 事件 需根据实际问题合理设置模拟时间 发生改变的步长 根据模拟过程中因变量的变化情况进行分类 根据模拟过程中因变量的变化情况进行分类 1 离散型模拟 因变量在与事件时间有关的具体模 拟时间点呈离散性变化 大多数系统 如排队服务 系统 可采用离散型模拟 时间推进方法 一般采用下次事件法 应当重点对系统状态可能发生改变的事件进行描述 并确定这些事件之间的逻辑关系 离散型模拟 因变量在与事件时间有关的具体模 拟时间点呈离散性变化 大多数系统 如排队服务 系统 可采用离散型模拟 时间推进方法 一般采用下次事件法 应当重点对系统状态可能发生改变的事件进行描述 并确定这些事件之间的逻辑关系 排队系统通常采用离散型模拟模型 其中 发生系 统状态变化的事件有两个 一是有顾客到达 二 是服务员完成服务 将最近发生上述两种事件之 一的时刻设置为下次事件发生点 排队系统通常采用离散型模拟模型 其中 发生系 统状态变化的事件有两个 一是有顾客到达 二 是服务员完成服务 将最近发生上述两种事件之 一的时刻设置为下次事件发生点 2 连续型模拟 因变量随时间的改变呈连续性变化 在大多数计算机模拟过程中 按固定的步长推进 模拟时间 通常需建立一系列的由系统状态变量组成的 状态方程组 以描述状态变量与模拟时间的关系 连续型模拟 因变量随时间的改变呈连续性变化 在大多数计算机模拟过程中 按固定的步长推进 模拟时间 通常需建立一系列的由系统状态变量组成的 状态方程组 以描述状态变量与模拟时间的关系 3 混合型模拟 因变量随时间的推移而作连续性的 变化并具有离散性的突变 如库存控制系统 混合型模拟 因变量随时间的推移而作连续性的 变化并具有离散性的突变 如库存控制系统 1 1 3 模拟的方式 终态模拟 在规定的时间 模拟的方式 终态模拟 在规定的时间T内进行模拟运行 时间达 到 内进行模拟运行 时间达 到T时 模拟终止 其性能指标明显取决于系统的 初始状态 稳态模拟 随着模拟时间的推移 系统的性能逐渐 趋于平稳 其目的是研究非终态系统长期运行条 件下的稳态性能 模拟时间的长短取决于能否获 得系统性能的优良估计 可由模拟输出的精度确 定 时 模拟终止 其性能指标明显取决于系统的 初始状态 稳态模拟 随着模拟时间的推移 系统的性能逐渐 趋于平稳 其目的是研究非终态系统长期运行条 件下的稳态性能 模拟时间的长短取决于能否获 得系统性能的优良估计 可由模拟输出的精度确 定 1 1 4 模拟的一般步骤模拟的一般步骤 明确问题 建立模型 正确描述待研究问题 明 确规定模拟的目的和任务 确定衡量系统性能或 模拟输出结果的目标函数 然后根据系统的结构 及作业规则 分析系统各状态变量之间的关系 以此为基础建立所研究的系统模型 明确问题 建立模型 正确描述待研究问题 明 确规定模拟的目的和任务 确定衡量系统性能或 模拟输出结果的目标函数 然后根据系统的结构 及作业规则 分析系统各状态变量之间的关系 以此为基础建立所研究的系统模型 收集和整理数据资料 模拟技术的正确运用 往 往由大量的输入数据作依靠 在随机模拟中 应 认真分析具体收集到的随机性数据资料 确定系 统中随机性因素的概率分布特性 以此为依据产 生模拟过程所必需的抽样数据 收集和整理数据资料 模拟技术的正确运用 往 往由大量的输入数据作依靠 在随机模拟中 应 认真分析具体收集到的随机性数据资料 确定系 统中随机性因素的概率分布特性 以此为依据产 生模拟过程所必需的抽样数据 编制程序 模拟运行 编制程序 模拟运行 分析模拟输出结果 模拟结果的统计特性 样本 均值 方差 置信区间等 灵敏性分析 选择 最优方案 分析模拟输出结果 模拟结果的统计特性 样本 均值 方差 置信区间等 灵敏性分析 选择 最优方案 注 模拟结果的统计分析模拟的输出结果是分布特 征未知的随机变量 每次运行的结果仅仅是对该 随机变量所有观察值总体的一次抽样 对总体的 代表性很差 虽然可以增加模拟运行的时间从而 增加抽样次数 但这些数据总是由一个 注 模拟结果的统计分析模拟的输出结果是分布特 征未知的随机变量 每次运行的结果仅仅是对该 随机变量所有观察值总体的一次抽样 对总体的 代表性很差 虽然可以增加模拟运行的时间从而 增加抽样次数 但这些数据总是由一个 种子种子 经 过一定的算法而获得的伪随机序列 它们是自相 关的 并不能构成统计上独立的随机样本 经 过一定的算法而获得的伪随机序列 它们是自相 关的 并不能构成统计上独立的随机样本 问题 如图 一列火车从A站开往B站 某人每天 赶往B站上这趟火车 问题 如图 一列火车从A站开往B站 某人每天 赶往B站上这趟火车 AB 火车运行方向火车运行方向 某人某人 他已了解到 他已了解到 1 火车从 火车从A站到站到B站的运行时间是均值为站的运行时间是均值为30分 钟 标准差为 分 钟 标准差为2分钟的随机变量 分钟的随机变量 思考 思考 请研究他能否赶上这趟火车 请研究他能否赶上这趟火车 1 2 随机模拟案例 赶上火车的概率随机模拟案例 赶上火车的概率 出发时刻午后出发时刻午后1 00 午后午后1 05 午后午后1 10 频率频率0 7 0 2 0 1 他到达他到达B 站的时刻的频率分布为 时刻午后 站的时刻的频率分布为 时刻午后1 28 午后午后1 30 午后午后1 32 午后午后1 34 频率频率0 3 0 4 0 2 0 1 他能否及时赶上火车 他能否及时赶上火车 2 火车在下午大约1点离开 火车在下午大约1点离开A站 离开时刻 的频率分布如下 站 离开时刻 的频率分布如下 明确问题 明确问题 他能及时赶上火车的概率是多少 他能及时赶上火车的概率是多少 i 分析法 用概率统计知识建立分析模型 求 分析法 用概率统计知识建立分析模型 求解 析解 解 析解 思考 思考 ii 模拟法 用概率统计知识建立模型 通过模拟 求 模拟法 用概率统计知识建立模型 通过模拟 求近似解近似解 即先建立模拟模型 然后通过计算机模拟得到 问题的近似解 在同样条件下多次试验 计算 他能及时赶上火车的频率 建模方向 思路 即先建立模拟模型 然后通过计算机模拟得到 问题的近似解 在同样条件下多次试验 计算 他能及时赶上火车的频率 建模方向 思路 问题分析 能及时赶上火车的充要条件是 其中 T 问题分析 能及时赶上火车的充要条件是 其中 T1 1 火车从A站出发的时刻 T 火车从A站出发的时刻 T2 2 火车的运行时间 T 火车的运行时间 T3 3 他到达B站的时刻 他到达B站的时刻 是什么变 量 如何 模拟 是什么变 量 如何 模拟 213 213 TTT TTT 即 ii 将午后 将午后1时记为时记为t 0 设火车运行时间 设火车运行时间T2 服从正态分布 服从正态分布 T2 N 30 22 基本假设 基本假设 i 假设 假设T1 T2 T3 都是相互独立的随机变量都是相互独立的随机变量 火车出发时刻火车出发时刻T1 1 和人到达B站时刻和人到达B站时刻T3 的分布 律分别为 的分布 律分别为 T1 分 0 5 10 P t 0 7 0 2 0 1 T3 分 28 30 32 34 P t 0 3 0 4 0 2 0 1 建立模型 为了简化计算 将下午建立模型 为了简化计算 将下午1点记为初始时 刻 得到随机变量 点记为初始时 刻 得到随机变量T1 1 和和T3 的分布律如下 能及时赶上火车的概率 的分布律如下 能及时赶上火车的概率 p P T3 T1 T2 如果如果r为在为在 0 1 均匀分布的随机数 为了模拟随 机变量 均匀分布的随机数 为了模拟随 机变量T1和和T3 可以通过如下方法 可以通过如下方法 19 0 10 9 07 0 5 7 00 0 1 r r r t 0 19 0 34 9 07 0 32 7 03 030 3 00 28 3 r r r r t 则则t1 和和t3 可分别 用来模拟随机变 量 可分别 用来模拟随机变 量T1 和和T3 主要变量说明 主要变量说明 n 模拟次数模拟次数 k 临时变量 存储当前累计模拟次数临时变量 存储当前累计模拟次数 count 存储赶上火车的次数存储赶上火车的次数 两种不同风格的算法描述 模拟算法设计 两种不同风格的算法描述 模拟算法设计 输入 输入 赶火车次数 天数 赶火车次数 天数 输出 输出 赶上火车的频率赶上火车的频率 第 1 步 输入模拟次数n 第 2 步 k 1 count 0 第 3 步 当k T3 count count 1 END 第 10 步 执行第3步 第 11 步 输出赶上火车频率p count n 算法1 分步骤描述 第 1 步 输入模拟次数n 第 2 步 k 1 count 0 第 3 步 当k T3 count count 1 END 第 10 步 执行第3步 第 11 步 输出赶上火车频率p count n 算法1 分步骤描述 i 初始化 输入模拟次数n count 0 ii 模拟n次 i 初始化 输入模拟次数n count 0 ii 模拟n次 for for i 1 to n 模拟随机变量T i 1 to n 模拟随机变量T1 1 T T2 2 T T3 3 分别赋给t1 t2 t3 分别赋给t1 t2 t3 if if t1 t2 t3 count count 1 t1 t2 t3 count count 1 end if end for end if end for app prb count n 算法2 伪代码描述 app prb count n 算法2 伪代码描述 n input 输入模拟次数 输入模拟次数 count 0 for i 1 n rt1 rand 模拟随机变量模拟随机变量t1 火车从 火车从A站出发的时刻 站出发的时刻 if rt1 0 7 else T1 10 end T2 30 randn 2 模拟随机变量模拟随机变量t2 火车的运行时间 火车的运行时间 模拟随机变量模拟随机变量t3 他到达 他到达B站的时刻 站的时刻 rt3 rand if rt3 0 3 else T3 34 end if T3 MAXP YN xj aj R bj aj gi X 0 i 1 2 n YN jMAXK YN 输出X Q 停止 Y N 在MATLAB软件包中编程 共需3个 文件 randlp m mylp m lpconst m 主程序为randlp m mylp m function z mylp x 目标函数 z 2 x 1 2 x 2 2 x 1 x 2 8 x 1 3 x 2 转化为求最小值问 题 lpconst m function lpc lpconst x 约束条件 If 3 x 1 x 2 10 0 5 约束条件的误差 为 0 5 lpc 1 else lpc 0 end randlp m function sol r1 r2 randlp a b n 随机模拟解非线性规划 debug 1 a 0 试验点下界 b 10 试验点上界 n 1000 试验点个数 r1 unifrnd a b n 1 n 1阶的 a b 均匀分布随机数矩阵 r2 unifrnd a b n 1 sol r1 1 r2 1 z0 inf for i 1 n x1 r1 i x2 r2 i lpc lpconst x1 x2 if lpc 1 z mylp x1 x2 if z z0 z0 z sol x1 x2 end end end 2 2 2 估算圆周率2 2 2 估算圆周率 2 2 3 估算定积分2 2 3 估算定积分 1 频率法1 频率法 2 平均值法2 平均值法 例例1 某港口提供有足够的泊位供船舶停靠 但现在 仅有一个可供装卸的泊位 船舶先到则先进行装 卸 如果船舶得不到及时装卸而造成的滞期费为 每小时 某港口提供有足够的泊位供船舶停靠 但现在 仅有一个可供装卸的泊位 船舶先到则先进行装 卸 如果船舶得不到及时装卸而造成的滞期费为 每小时100元 现要弄清该系统的性能 重点考 察船舶进入该港后等待装卸的滞留时间以及卸位 即装卸用的泊位 的利用率 从而进行经济效 益分析 元 现要弄清该系统的性能 重点考 察船舶进入该港后等待装卸的滞留时间以及卸位 即装卸用的泊位 的利用率 从而进行经济效 益分析 3 模拟模型案例模拟模型案例 到达间隔 小时 567 89101112131415161718 到达船舶 数 艘 136 791011111197654 首先 对进入该港口的首先 对进入该港口的100艘船进行实际调查 记录其活动情况 得到 这 艘船进行实际调查 记录其活动情况 得到 这100艘船到达港口的时间间隔和装卸时间的分布情况的频数和累积频 率分布 艘船到达港口的时间间隔和装卸时间的分布情况的频数和累积频 率分布 装卸时间 小时 910111213141516 装卸船舶数 艘 2022191610832 表1 100艘船到达港口的时间间隔频数表 表2 100艘船装卸时间频数表 到达间隔 56789101112131415161718 累积频率 0 010 040 100 170 260 360 470 580 690 780 850 910 961 00 装卸时间910111213141516 累积频率0 200 420 610 770 870 950 981 00 表3 船舶到达港口的时间间隔累积分布表 表4 船舶装卸时间累积分布表 设 一年内到达港口的船舶数为N 到港船舶滞留 总时间为T1 船舶平均滞留时间为T2 港口支付 滞留费为Y 装卸泊位空闲时间装卸泊位利用率S Step1 模拟船舶到达港口的时间间隔的分布P1 Step2 模拟船舶装卸所需时间的分布P2 Setp3 编写程序 为了比较准确地反映系统的性能 我们采用稳态 模拟方式 可以考察系统运行360天的情况 假 定港口每天24小时连续工作 因此模拟时间T设 置为8640小时 考虑到船舶到达港口的事件是影 响整个系统状态的主要因素 可以将模拟事件设 置为该事件的发生时刻 所用变量说明 t 一艘船到达港口的时间 tl 前一艘船驶离港口的时间 td 两艘船到达港口的时间间隔 ts 当前船舶装卸所需时间 tw t时刻所有已到达港口的船舶等待装卸时 间总和 tf t时刻装卸位已空闲时间总和 初始化数据 t tl tf tw 0 产生船舶到达间隔时间 td 设置模拟时间 t t td t 8640 打印输出 产生装卸服务时间ts t tl 统计装卸位空闲时间 tf tf t tl 统计船舶等候时间 tw tw tl t 设置船舶离港时间 Tl t ts 设置船舶离港时间 Tl tl ts 是 是 否 否 模拟 次数 到达船 舶数 到港船舶滞留 总时间 小时 船舶平均滞 留时间 小时 港口支付滞 留费 元 装卸泊位空 闲时间 小时 装卸泊位 利用率 1736748010 1674800035396 272243696 0543690051594 3737910912 3690190042695 473657587 8257580038196 5741750110 1275010034196 673968409 2668400042295 表5 某港口对船舶服务的模拟结果 经过6次模拟计算 装卸泊位的平均利用率为 95 3 但到达的船舶的却因得不到及时的服务 而造成平均每艘滞留9 295小时 每年到港船舶总 滞留6843小时 因此港口每年约需支付68万元的 滞留费 这显然是一笔不小的开支 为此 可修 改模拟模型 考虑增设一个装卸泊位 并重新进 行模拟运行 将这些数据提供给决策者一确定是 否需要再新建一个装卸泊位 练习 某公共汽车站每隔练习 某公共汽车站每隔30分钟到达一辆汽车 但 可能有 分钟到达一辆汽车 但 可能有 0 3 分钟的误差 此误差大小与前一辆汽 车的运行无关 汽车最多容纳 分钟的误差 此误差大小与前一辆汽 车的运行无关 汽车最多容纳50名旅客 到达该 汽车站时车内旅客人数服从 名旅客 到达该 汽车站时车内旅客人数服从 20 50 的均匀分布 到站下车的旅客人数服从 的均匀分布 到站下车的旅客人数服从 3 7 的均匀分布 每 名旅客下车的时间服从 的均匀分布 每 名旅客下车的时间服从 1 7 秒的均匀分布 旅 客按每 秒的均匀分布 旅 客按每30分钟到达分钟到达12个人的泊松分布到达汽车 站 单列排队等车 先到先上 如果某位旅客未 能上车 他将不再等候 旅客上车时间服从 个人的泊松分布到达汽车 站 单列排队等车 先到先上 如果某位旅客未 能上车 他将不再等候 旅客上车时间服从 4 12 秒的均匀分布 上下车的规则是 先下后 上 逐个上车 逐个下车 假设每天共发 秒的均匀分布 上下车的规则是 先下后 上 逐个上车 逐个下车 假设每天共发25 辆汽车 现在要求模拟一天汽车的运行情况 了 解一天中在站内等候汽车的总人数 能上车及不 能上车的人数 旅客排队时间分布情况 不能上 车人数的分布情况等 辆汽车 现在要求模拟一天汽车的运行情况 了 解一天中在站内等候汽车的总人数 能上车及不 能上车的人数 旅客排队时间分布情况 不能上 车人数的分布情况等 例2 露天矿用电铲采掘矿石 然后用卡车运送到卸 场 假设共有m辆卡车装运 有n台 n m 电铲 同时采掘供n辆卡车同时装卸 卸场有s个卸位 s0 1 x 5 x 1 y 5 y 1 for i 1 4 d sqrt x i 1 x i 2 y i 1 y i 2 x i x i v dt x i 1 x i d y i y i v dt y i 1 y i d plot x i y i hold on end end 离散系统模拟实例离散系统模拟实例 排队问题排队问题 排队论排队论主要研究随机服务系统的工作过程 在排队系统中 服务对象的到达时间和服务时间都是随机的 排 队论通过对每个个别的随机服务现象的统计研究 找出反映这些随机 现象平均特性的规律 从而为设计新的服务系统和改进现有服务系统 的工作提供依据 对于排队服务系统 顾客常常注意排队的人是否太多 等候的时间 是否长 而服务员则关心他空闲的时间是否太短 于是人们常用排队的 长度 等待的时间及服务利用率等指标来衡量系统的性能 单服务员的排队模型单服务员的排队模型 在某商店有一个售货员 顾客陆续来到 售货员逐个地接待顾客