生活中的数学建模

数 学 建 模 从 自 然 走 向 理 性 之 路 2/40 【 本 讲 简 介 】 数 学 建 模 无 处 不 在 。 在 我 们 的 生 活 中 处 处 可 以 看 到数 学 模 型 的 影 子 ， 本 讲 介 绍 发 生 在 我 们 身 边 的 几 个 数 学建 模 案 例 ： 人 行 走 时 步 长 多 大 最 省 力 ？ 雨 中 行 走 如 何 使淋 雨 量 最 小 ？ 道 路 越 多 越 通 畅 吗 ？ 有 奖 销 售 时 的 抽 奖 策略 问 题 ， “ 非 诚 勿 扰 ” 女 生 的 最 佳 选 择 ,网 络 文 章 流 行度 预 测 ,招 聘 时 的 稳 定 匹 配 等 。 3/40 行走步长问题 问 题 人 在 匀 速 行 走 时 步 长 多 大 最 省 劲 ？ 设 人 的 体 重 为 M ， 腿 重 为 m ， 腿 长 为 l ， 速 度 为v （ 固 定 ） ， 单 位 时 间 步 数 为 n ， 步 长 为 x （ v = n x ） 。 4/40 5/40 考 虑 人 行 走 时 所 消 耗 的 能 量 的 两 个 部 分 ： 一 部 分抬 高 人 体 重 心 ， 转 化 为 势 能 ， 另 一 部 分 转 化 为 两 腿 转动 的 动 能 （ 全 身 运 动 的 平 动 能 是 常 数 ， 与 步 长 无 关， 故 不 考 虑 ） 。 下 面 分 别 计 算 之 。 1. 重 心 升 高 所 需 的 能 量 记 一 步 中 重 心 升 高 为 ， 则 6/40 2 1 22 1 22 222 co s(1 sin )(1 )4(1 )88l ll l xl l lxl l lxl 7/40 于 是 ， 单 位 时 间 重 心 升 高 所 需 做 功 为 2. 腿 运 动 所 需 的 能 量 将 人 行 走 时 腿 的 运 动 视 为 均 匀 直 杆 （ 腿 ） 绕 腰 部 的转 动 ， 则 在 单 位 时 间 内 所 需 动 能 为 28 8nMgx MgvW nMg xl l 势 212W I n 动 8/40 其 中 转 动 惯 量 ， 角 速 度 ,故所 以 人 行 走 时 单 位 时 间 所 做 的 功 为 213I ml v l 2 32 21 12 3 6 6v n mvW ml n mvl x 动 3M8 6gv m vW W W W x Wl x 动平平势 9/40 令 解 得 为 检 验 此 结 果 的 合 理 性 ， 带 入 具 体 数 值 ， 假 定 M/m = 4， l = 1 米 , g = 9.8米 /秒 2 , v =1.5米 /秒计 算 得 到 n = 5.4步 /秒 x = 0.28米结 果 与 实 际 情 形 差 异 太 大 ! 0dWdx 24 33 4mlv Mgx nMg ml 10/40 有 人 将 腿 的 转 动 改 为 脚 的 直 线 运 动 ， 且 将 腿 的 质 量全 部 算 在 脚 上 ， 这 样 得 到 的 结 果 大 约 是 每 秒 步 ， 是 否合 理 ？ 建 模 小 结 ： 本 问 题 的 关 键 点 在 于 腿 部 运 动 的 合 理 描 述 ，模 型 改 进 的 方 向 来 自 于 对 结 果 的 细 致 分 析 。3M 1(13.3 )8 6gv mvW x C xl x x 11/40 雨中行走问题 问 题 考 虑 人 在 雨 中 沿 一 直 线 行 走 ， 雨 速 已 知 ， 问 人行 走 的 速 度 多 大 才 能 使 淋 雨 量 最 小 ？ 单 位 时 间 淋 雨 量 最 小 ： 雨 从 头 顶 上 落 下 。 但 这 样 做 要 付 出 时 间 代 价 ， 值 不 值 就 要 看 具 体 降 雨量 情 况 与 风 的 情 况 而 定 了 。 淋 雨 量 单 位 时 间 淋 雨 量 淋 雨 时 间 跑 得 越 快 淋 雨 量 越 小 ？ 12/40 设 人 行 走 速 度 (U,0,0) (U0) ，雨 速 (Vx, Vy, Vz)， 行 走 距 离 为 S，将 人 视 为 长 方 体 ， 前 、 侧 、 顶 的面 积 之 比 为 1:L:T。 13/40 单 位 时 间 淋 雨 量 为 C |U-Vx|, |0-Vy|, |0-Vz| 1, L , T C（ | U-Vx | + |Vy| L + |Vz| T ） C（ | U-Vx | + A ） (其 中 A = |Vy| L + |Vz| T) 总 淋 雨 量 为 R(U)= S/U C (|U-Vx| + A ) 为 简 便 计 ， 考 虑 R(U)= S/U (|U-Vx| + A ) 14/40 因 此 ， 雨 中 行 走 问 题 抽 象 成 数 学 问 题 ： 已 知 S , Vx ,A, 求 U为 何 值 时 R(U)达 最 小 值 ？ 下 面 分 几 种 情 况 讨 论 。 （ 1） Vx 0 时 （ 即 风 从 背 面 吹 来 ） ( )( )( ) ( )( ) xx xxx xS V AS V U A S U VU UR U S A VS U V A S U VU U 22( ) ,( ) ,x xx xS V A U VdR US A VdU U VU 16/40 结 论 当 A Vx 时 ， 取 U = Vx ， 其 他 情 况 下 ， U 应 尽 可 能 大 。 建 模 小 结 ： 决 定 淋 雨 量 大 小 有 两 个 因 素 ： 淋 雨 时 间及 单 位 时 间 淋 雨 量 ,忽 略 后 者 将 导 致 错 误 结 论 。 17/40 道路越多越通畅吗？ 18/40 布 雷 斯 悖 论 ( Braesss paradox ) 19/40 数 学 家 研 究 结 论 ： 如 果 一 个 交 通 网 络 上 每 一 条 路 的通 行 时 间 都 与 这 条 路 上 的 车 子 数 量 成 线 性 关 系 ， 这 个 交通 网 络 就 一 定 存 在 一 个 纳 什 均 衡 点 。 它 可 能 导 致 全 体 不利 的 情 况 发 生 ， 即 出 现 布 雷 斯 悖 论 现 象 。 真 实 案 例 1： 德 国 ,斯 图 加 特 市 ,1969 年 。 真 实 案 例 2： 美 国 ， 纽 约 ， 1990年 世 界 地 球 日 。 真 实 案 例 3： 韩 国 ， 清 溪 川 。 20/40 某 人 可 获 得 一 笔 奖 金 x , x由 他 在 区 间 0,1 中任 意 地 抽 取 。 如 果 他 满 意 ， 可 以 领 取 x 奖 金 而 不 再 抽取 ； 如 果 他 不 满 意 ， 可 以 放 弃 这 个 x 而 重 新 抽 取 。 这个 抽 取 过 程 可 重 复 3 次 , 第 三 次 抽 取 后 不 得 放 弃 。 问 他 应 该 采 取 何 种 策 略 以 期 获 得 最 多 奖 金 ？ 有奖销售抽奖策略 21/40 设 该 抽 奖 人 采 取 的 策 略 为 ： 其 中 X1 , X2 , X3 均 为 在 0,1上 均 匀 分 布 的 随 机 变量 。 该 人 目 标 为 获 得 的 奖 金 H 的 期 望 达 最 大 值 。 1 12 1 23 1 2X X aH X X a X bX X a X b 22/40 计 算 期 望 ： 令则 H = g(X1,X2,X3), 根 据 期 望 计 算 公 式 有1 11 2 3 2 1 23 1 2( , , ) x x ag x x x x x a x bx x a x b 1 2 3 1 2 3 1 2 30 11,2,3 2 2 2 2( , , ) ( , , )1 (1 ) 1 (1 )2 2 2 2ixiEH g x x x p x x x dx dx dxa a b ab a a ab ab 23/40 以 下 我 们 换 一 种 方 法 计 算 获 利 期 望 。 条 件 期 望 方 法 第 一 次 抽 奖 的 获 奖 期 望 为 第 二 次 抽 奖 的 获 奖 期 望 为 1 1 1 12( ) ( )1 1(1 ) 2 2EH P X a E X X aa aa 2 1 2 2 1 22( , ) ( , )1 (1 )(1 ) 2 2EH P X a X b E X X a X bb a ba b 24/40 第 三 次 抽 奖 的 获 奖 期 望 为 所 以 3 1 2 3 1 2( , ) ( , )12 2EH P X a X b E X X a X babab 1 2 32 22 21 1 1(1 ) (1 )2 2 21 12J EH EH EH EHa a b aba a ab ab 25/40 令 解 得 ： a = 5/8 , b = 1/2 最 大 期 望 奖 金 为 ： 最 优 停 止 问 题 ， 例 如 “ 不 可 召 回 的 秘 书 招 聘 问 题 ” 。 21 1 2 02 1 2 02J a b ba J a bb 89 0.7128EH 26/40 非诚勿扰女生的”最优选择”总 共 面 试 n人 ， 不 选 择 前 k人 ， 从 第 k+1人 起 ， 一旦 有 比 前 面 更 优 秀 的 男 生 ， 则 选 择 。策略 如 何 确 定 K， 使 选 到 最 中 意 男 生 的 概 率 最 大 ？ 对 于 某 个 固 定 的 k， 能 选 到 最 佳 男 生 的 总 概 率 为 ： 1 11 1( ) 1 1n ni k i kk kP k n i n i 27/4011( ) lnxP k x dt x xt 1/e 大 约 等 于 37%， 即 k/n 37% 37%法 则 ！ 按 此 策 略 ， 找 到 最 中 意 男 生 的 概 率 也 是 37%！ 用 x 来 表 示 k/n 的 值 ， 并 且 假 设 n 充 分 大 ， 则 上 述公 式 可 以 近 似 表 示 为 积 分 形 式 ： ( ln ) 1 ln 0d x x xdx 1/x e 建 模 小 结 ： 生 活 中 处 处 有 数 学 建 模 的 身 影 。 28/40 【 问 题 】 “ 如 何 在 一 篇 文 章 被 发 出 前 就 判 断 它 会 否 流 行 ” The Pulse of News in Social Media: Forecasting Popularity【 基 本 思 路 】l 确 定 文 章 内 容 的 关 键 因 素 。l 统 计 这 些 关 键 因 素 取 不 同 值 时 对 文 章 流 行 度 的 影 响 ， 并 将 各 取 值赋 以 不 同 分 值 。 l 利 用 统 计 方 法 建 立 并 优 化 “ 内 容 关 键 因 素 ” 对 “ 流 行 度 ” 影 响 程度 的 数 值 模 型 。 l 利 用 模 型 预 测 某 篇 文 章 在 推 特 上 的 流 行 度 。网络文章流行度预测 29/40 4个 判 断 的 关 键 要 素 ：1、 信 息 类 别 30/40 2、 客 观 程 度 用 软 件 判 断 样 本 标 题 及 摘 要 的 客 观 程 度 ， 并 为 其 设 定 分值 0 或 者 1。3、 提 及 的 人 物 和 地 名4、 新 闻 来 源 31/40 预 测 模 型 ：其 中 ：T 流 行 度 （ t-density）S 信 息 来 源 的 t-density 分 值C 信 息 类 别 的 t-density 分 值Ent max 文 中 提 及 的 人 名 或 地 名 中 的 最 大 t-density值 结论： 来 自 可 靠 的 信 息 源 、 提 及 名 人 并 且 谈 论 流 行 话 题建 模 启 示 ： 对 建 立 评 价 类 模 型 具 有 典 型 意 义 。 32/40 假 设 在 一 个 n男 n女 的 联 谊 会 上 配 对 跳 舞 ， 每 个 人 都按 自 己 的 喜 好 程 度 对 所 有 异 性 排 一 个 顺 序 ， 没 有 并 列 ，例 如 ：【 问 题 】 是 否 存 在 一 个 稳 定 的 配 对 ？ 如 果 存 在 ， 是 否 唯 一 ？ 如 何 求 ？稳定匹配问题及算法A B C Dw x x yx z w xy w y zz y z w w x y zD B D CC A C BA D B AB C A D 33/40 稳 定 匹 配（Stable matching）：每 个 人 当 前的 配 对 对 象 恰 好 是 他 （ 她 ） 在 当 前 现 实 中 的 最 优 选 择 。 不 稳 定 匹 配 ： 存 在 这 样 的 一 个 男 生 和 一 个 女 生 ， 他们 都 认 为 对 方 比 自 己 当 前 的 配 对 对 象 更 优 。A B C Dw x x yx z w xy w y zz y z w w x y zD B D CC A C BA D B AB C A D(A,w), (B,x), (C,y), (D,z) (A,z), (B,x), (C,w), (D,y) 34/40 罗 伊 德 沙 普 利(Lloyd Shapley)美 国 著 名 数 学 家 和 经 济 学 家2012年 因 在 稳 定 配 对 和 市 场设 计 方 面 的 贡 献 获 诺 贝 尔 经济 学 奖 1923年 6月 2日 35/40 Gale-Shapley算 法 ： 第 一 轮 ： 每 位 男 生 向 各 自 最 中 意 的 女 生 发 出 邀 请 ，然 后 每 个 女 生 在 向 其 发 出 邀 请 的 男 生 中 选 择 自 己 最 中 意的 ； 第 二 轮 ， 尚 未 配 对 的 男 生 向 其 第 二 喜 欢 的 女 生 （ 不管 该 女 生 是 否 已 配 对 ） 发 出 邀 请 ， 然 后 每 个 女 生 在 向 其发 出 邀 请 的 男 生 以 及 上 一 轮 已 选 择 的 男 生 中 选 择 一 个 最中 意 的 ； 第 三 轮 ， 36/40第 一 轮 ： (A,w) (B,x) (C,x) (D,y), x拒 绝 C第 二 轮 ： (A,w) (B,x) (C,w) (D,y), w拒 绝 A第 三 轮 ： (A,x) (B,x) (C,w) (D,y), x拒 绝 A第 四 轮 ： (A,y) (B,x) (C,w) (D,y), y拒 绝 A第 五 轮 ： (A,z) (B,x) (C,w) (D,y) A B C Dw x x yx z w xy w y zz y z w w x y zD B D CC A C BA D B AB C A D 37/40 几 个 问 题 ：1、 算 法 是 否 能 在 有 限 步 结 束 ？ 是 的 。 由 于 每 一 个 男 生 最 多 发 出 n次 邀 请 ， 必 然 能 够 邀请 到 女 生 ， 所 以 算 法 在 有 限 轮 后 会 结 束 。2、 选 择 先 后 对 双 方 是 否 有 区 别 ？ 是 的 。 对 先 选 的 一 方 有 利 。3、 稳 定 配 对 是 否 唯 一 ？ 未 必 。 见 上 面 例 子 。4、 算 法 得 到 的 配 对 是 否 稳 定 ？ 是 的 。A B C Dw x w yx y y xy z z wz w x z w x y zA A B DB C A CC B D BD D C A 38/40 5、 算 法 在 多 对 一 时 （ 例 如 ： 企 业 与 求 职 者 ， 研 究 生 导 师与 研 究 生 等 ） 是 否 有 效 ？ 是 的 。6、 算 法 是 否 能 够 预 防 欺 诈 行 为 得 逞 ？ 否 。 思 考 题 ： 2n个 男 生 分 宿 舍 ， 每 间 宿 舍 住 两 人 ， 每 个 人 对 其 他 人 成为 自 己 的 舍 友 有 一 个 优 先 排 序 ， 能 否 应 用 Shapley算 法求 稳 定 匹 配 ？ 为 什 么 ？ 39/40 2.1、 建 立 更 合 理 的 模 型 ， 改 进 “ 行 走 步 长 问 题 ” 模 型 。2.2、 教 材 P37 第 3题 。作 业 ： 数 学 建 模 从 自 然 走 向 理 性 之 路