建模需要思想也需要数学训练和手上功夫B题综合评述

第1 9 卷 建模 专辑 工 程 数学 学报 1 9 s p p 加 月 J OURNAL OF ENGI NEERI NG M ATHEM ATI C S F e b 2 0 0 2 文章编号 1 0 0 5 3 0 8 5 2 0 0 2 0 5 0 1 0 7 0 6 建模需 要 思想 也需要数 学训 练和 手 上功 夫 B题综合评 述 刘 宝 光 北 京理 工 大学 北京 1 0 0 0 8 1 摘要 本 文对 于 2 O O 1年 全 国太学 生教 学 建横 竞赛 B题 的解答 从模 型框 架 模型 建立 和 模型 求解 等 三千 方面 鲭出评 述 美 键 词 公 交车 调度 敦 学规 划模 型 目标规 划 分 粪 号 A MS 2 0 0 0 9 0 C 0 8 中舶 分类 号 Tb l 1 4 1 文献标 识 码 A 1 模型框架 正 如题 目的标题所 示 这是一个 公交车调 度问题 题 目给定 了限制条件 和 目标 要求在 一 定统计数 据资料 的基础 上 构建 理论模 型并据 以实现 调度 应 当指 出 构建 明确 完整 的数 学模型 是本题懈案要求 的一个本质性的方面 事实上 每一天 在全国各地 都有无数的车 队调 度在作 这 类 问题 他 们遵 守各 自的约束 追 求各 自的 目标 用 他们 习惯 了的方 法调度 车 辆 指挥 着 全国各地 公交车 的运行 他们 不见得都有 多高深 的数学修养 所 给 出的调 度方案也 不见 得都是合 理 的优 良的 本题 的意义 并 非要参赛者 习作普通 的车 队调度 而是 要求对这 一 问题用数学方法作更深一层次的探讨 这次有 占相当比例的答 卷没有完成明确 完整的模型 的建立 只从数 据 出发 凭某 种直 观方法给 出一个可行 的调度 方案 应 当说 这是不符 合题 目要 求 的 因而都不在 得奖 者之列 考察题 意最 直接 的想法 会是 建立 数学规划模 型 在培 出 了数学 模 型 的答卷 中 恐 怕有 七 成 以上是用 的各种 不同 的数学规划模 型 模 型的变量 既然题 目要求 设计 调度方案 最 自然 的 就是 发 车 时 刻 系列 T 1 T2 但 这一 变量 其 维数 m 很高 而且是不定 的 这 会 为使 用某 些成 熟 的优 化数 值 方法 求解带来 麻烦 一种适 当的简 化方法是 将 全天 分作若干 时段 在 每一类时 段中等 间距发车 这 时 模型 的变量可取 作各 类时段 的发 车 时问间距 从 而可建立有 确定 的低 维数 的数学规划模 型 例如 将 全天分为 平峰 时段和 高峰时段 分别 间距 f 1 和 t 2 分 钟发一班 车 则 可得 到 以 f 2 为变量 的 2维 模 型 题 目称 调度 方案应 满足 四项要 求 若 记 i为乘 客候车时 间 为早 高峰 时乘客候 车时 间 为 车辆载 客人数 则要 求为 a 1 O分 钟 b 5分 钟 c 5 0 d P 1 2 0 维普资讯 更多数学建模资料请关注微店店铺 数学建模学习交流 1 0 8 工程教学学报 第 1 9卷 按照题 目所列 的乘 车人数 统计数据 严格 满足这 四项要 求 的调 度方 案 是不 存 在 的 而题 目只 是 限定 为 硬性 约 束 不 应 违反 其他 三条 使用 一 般 不要 措 词 即是 说 可 以违反 但应 使 违反程度 尽可能低 这很 自然 导 向使 用 目标 规 划 g o a l p r o g r a mmi n g 而且粗 看 起来 如 下模 型是合理 的 rai n 1 f 5 1 0 2 r 5 3 p 5 0 4 1 2 0 5 1 z 6 n t 2 s s 0 7 然而 由于约 束 2 和 3 要对 每个乘 客成立 约 束 4 和 5 要 对 每辆 车 每个路 段 指相邻 二车 站 间 的道路 区段 成立 这 一模 型只有观 赏意 义 是难 以处 理 的 将 和 r换 作 所有乘 客 的最 大候车 时间 换作各 车各路 段的最小 载客数 便 真 的是作成 了三个 约束 但 此时 f和 作 为 1 2 的函数难 以给 出表 达 不仅 如此 因为 和 r是 以分钟为单 位 的等候时 间数 是车 上的人数 二者 是不可 比较的 所 以会 给权 因子 的设 置带 来 困难 这样 的模型 在答 卷 中有 为 数极少 如上述 这 一模型 实际上 是不 能操作 的 必 须另外想 变通 的方 法 一 种作法 是计算 两种 时段 中超 时候 车 1 0 r 5 的乘 客数 在各 段乘 客总数 中所 占的百 分 比 作为 l t 2 的 函数 计算 载 客人 数 p 2 t2左侧相邻 T 值 为 Tf 则 规定 T 1 L 1 等等 或按其他 规则 此处 不赘述 设 以 1 2 标 记车站 从 J一1站到 J站 的站 问行车 时间 包 括 J站 的停车时 间 记 为 J 2 3 n 第 班车驶 离 站 的时 刻记 作 T 则有 i 1 J 2 3 1 1 2 2 这便 给 出了每一班 车 的行 车时 刻表 为了求 g 2 和 p 2 需 要计 算 每 班 车驶 离各 站 时 车上 的乘 客 数 1 2 m J 1 2 一1 而为 了计算 g 1 1 2 和 g 2 l 2 需要 计算 每个乘 客的候 车时间 这 些都要 从乘 客流 的统计数 据出发 首先 对 每一 车站 J引人 乘客来站 的时 间密度 即单位 时 间来 站乘 客数 记 以函数 J 1 2 一1 统 计数 据恰 好 给出每隔 6 0分钟一个 点上 的平 均密度 值 据此 或用插 值或用 拟台 总可 以得 出 f 的一 个近似 表示 这里最 简单 的是用 阶梯 函数 作分 段线性 插 值得一 折线 函数也很 简单好用 答 卷上 对此一细 节的处理花样 繁 多 有 的甚 至作 了长篇 幅 的讨论 其 实 这 在整个 解案 中不过是 一个 细节 下 功夫过大则 势必 舍本 逐 末 类 似 可建 立乘 客离 站的时 间密 度函数 c f 2 3 虽说乘 客来 站是 分散 的 离站 是成批 的 但 统计数 据中并未 反映这一 区别 因而在计算 中也就作 完全一样 的处 理 乘 客等 候 时间 的计 算较 为 曲折 这里使用将乘 客 按等 候 时间长 短 分类 统 计 的方 法 为 此 设第 班车 到 达 站 时 站 上 已 等 候 过 h辆 车 而 仍 未 能 上 车 的 乘 客 数 为 以下 将 和 1 2 一1 k 1 2 m 用 对 k和 二 重递推 的方式表述 出来 注 意 对 任 意 的 当 0 因 为 j 0 为 时 间 段 0 J 出 1 其 中的 T D 1 理解 作 题 目所讨 论 的全天 的开始 时间 即 To To 5 6 0 j 1 2 一 l 的来 客数 所 以有 1 3 1 4 维普资讯 1 1 0 工程数学学报 第 1 9卷 对 于 k 1 根据 1 3 式 对 任意 的 J l 0 为 已知 以下证 明 对 于任 意 k 若 对任意 k一1 任意 J h 为 已知 则 可 以导 出 1 2 n 一1和 1 h 1 2 n 一1 h k 我 们 假 设 乘 客 按 先 到 先 上 车 的 队 列 原则 乘 车 记 h 为 站 上等待最 久 的乘 客 的候车趟数 即 h ma xI h l 0 我们规 定 0 0 L 0 O o 依 次对 于 1 2 一1 记 n 目 m a x I 1 一l 吐 t d t 0 1 5 一l 即第 k班车 到达j站 乘 客下车后 车 上仍 留下 的乘 客数 这 里 的 仍如 1 4 式 此 时 可容 纳的乘 客上车数 上 界 1 2 0一 1 6 这 时有 m i n 1 2 0 n w j h 1 7 0 h l J m a x h l h 0 或使 w k j r l 1 8 1 8 式 的意思是按候车趟数从多到少依次累加 h k j 一1 直到苜次出现大 于 6 则停 止 累加 以累加 到的最后 的 最 小的 一个 h作为 l 如果 直加至 目 0 仍不 大于 则 h l O o 然后 若 h l J 0 则 l 1 0 否则 h 1 一 1 h 1 2 l j一1 1 9 十 1 H 一1 一 一 2 0 1 0 则如 1 3 式 现 在可 以建 立模 型 8 一 1 0 中的各个 函数 了 利用 P 有 1 l 5 0 g 3 t l t 2 且 厂 2 注意 P L 的构 造过程 已保证 了约束条件 9 式 的成立 因而无须再 求 函数 1 2 该约 束 在建 成 的模 型 中也不再 出现 为求 g l 和 g 2 注意 到至 时刻 站上 已候 辆车 而仍 未能上 车 的乘 客 的等候 时间满足 一 L 一 f或 一 L 一 一 I j 以保守 的原则取其 下限 则有 l 一L一 5 1 2 2 2 2 3 维普资讯 建 模专 辑 建模 需 要 思想 也需 要数 学训 练 和手 上 功 夫 三个 函数 都是百 分率 数 值 上有 良好 的可 比性 可 以简 单地 取 其 加 权 和作 为单 一 目标 函 数 题 目中没有关 于优先权 及权重 的规定 可 以认为公交 公 司利 益与乘 客利益等 权 并且 表现 乘 客利益的二 函数 g 和 g 2等权 这样便有 2 1 g 3 1 2 2 4 2 5 可 以以此作为求 解 2的规 划模型 三个 函数 的 表述 是该 题 目的最 具 难度 之点 构 想 一个 如上一 段 所述 的模 型框架 并不很 难 要 表述 出这 些 函数从 而完成 模型 的建 立 却是 对参赛 者 的数 学训 练 和手 上功 夫 的考验 这 次 的答卷 中有 表现极好 的 但 是不 多 从这一 现象是否可 以提 出一个 问题 近一些年来 在教学 中很注意 思想性 的方面 学生 在这一方 面也确 实有很大提 高 但 对于 实际的手上 功夫 的训练却 渐趋弱化 固然技术 的进步代 替了许 多手上的操作 但同时却 派生 出许 多新 的需 要人工操作 的 事 情 即如本题 不 是计算技 术 如今 天的进步 也就不会 提 出这样 的题 目 在教学上 应 当如何 适 应情况 的这 种变化 呢 3 模 型求解 此次 的答 卷 中 模 型建立与其 后的求解计算 两相 脱节 者所 在 多有 这 是 不好 的 建立 了模 型 而 又不用 它 去寻解案 那 么建 模 又是 为了什么呢 所 建 的模 型难 解 不 会解 那 就 应 当再 进 一 步抽 象 再引 入新 的假设 以简 化模 型 直到你能够 处理 它 为止 包 括 引 出理 论结果 或数值 求 解 前面两段 中 我们先是 作等 间隔发车 的假设 以便将 一个有不确 定 的高维数 的问题 变为一 个 2维问题 然后 又将本 应是面 向各单个乘客 和单 个车路段 的 目标要 求 集总化为 三个百分率 函数 这些 都是 为了使得做 成 的模型 能够作求解处 理 模 型 2 4 一 2 5 是 容 易求解 的 作 为一 个非线性规划 问题 只有 2 维 且 约束 极为简单 除 非 目标 函数 的求值 不 能实现 总 可 以用 某种直 接方法 不 涉及求 导 数 求得 近 似解 上 段 中函 数 和 h 的二 重递推式 的表述 实际上就 给 出了对 给定 的 I 2 值求 这些 函数 值 的算法 2 1 2 2 和 2 3 式则表示 如何用这些 函数 值完 成 目标 函数求 值 运算 而实 际上 2 1 式 的分子是 台条 件的 的个数 的计 数器 2 2 和 2 3 式 的分 子是 台条件 f h 值 的累加 因此 g 1 g 2 和 g 3 的计算 可以放人到为产生 P 和 的对 k和J的 2 重循 环 中 随产生 随累加 以免去对这些 不再有用 的 和 h 的存储 使用 参赛 者熟 知的 Ma t t a b语言 容易 作成给 定 f 2 值 后产生 目标 函数值 的程序段 再 使用 Ma t t a b的优化工 具 箱 的程 序即可 完成求解 这 当 中或许 要为 t 2 设 一个合理 的上界 或 许要 通 过 随机 搜索选一 个好 一点 的初 始点 都是容 易做到 的事情 有的答卷 中选用 遗 传算 法求 解 此模 型 单从 其 目标 函数构 成复 杂 可 以求值而 难于求导 或作其他处理 等特点 这 一选择 就是 正确 的 另外要 指 出一点 如果 将 函数 g 3和 g 进一 步分拆成两 项 即分 别单 独计算平 峰时段 和高 峰 时段的载 客数不 到 5 0的车路段百 分率和候 车超 时乘客的百分 率 并且对 两种时段 的交接 点 处 的情况作适 当处理 目标 函数就 可 以化 为可 分离 的形式 即 f 2 f l 1 2 2 这 时就 可 以分 别求解两 个一维 问题 f 1 t 1 1 0 2 2 0 1 4 0 知 维普资讯 1 1 2 工程数学学报 第 1 9卷 比如分 别为 f 1 和 2 设 定合理 的上 界 就可 以用 0 6 1 8 方 法求 解 其 关键 的运算还是 目标 函数 和 的求 值 设 得解为 和 f 如果 f 则 f 就是所 求之解 4结束语 作 者认为 这个 题 目的难 点在 于 目标 函数 的具体 表述 如 本 文第 2段 如 果 判定建 立此 表述 的难度是适 当的 那 么这个题 目是选得很 好 的 事实 上 尽 管漂 亮 的答 卷不 多 怛众 多答 卷上对 于这样一 个活 生生 的相 当复杂 的实 际 问题 表 现 出分 析的 思 路是舍 理 的 也很 有深 度 为解决 问题 表现 的思路 也很 广 不足 之处 从总体上说 相对 于完成表 述 显得数 学训练和手 上功 夫欠 缺些 或难 度太 了些 相 对于 三天集 中时间 或 的确 是训 练 差 了些 或二 者兼有 以供 讨论 建模 是重要 的 在各 类 信息 系统平 台 日趋完善 的今 天 如何从 中发现 知识 如何优 化决策 人们 祈求建模 而建 模不光要 有思想 也 要 靠人 工完成 表 述 这要 求 数 学训 练和 手上 功 夫 致谢 本文参 考 了大量 的参 赛者 的答 卷 和 全 国及 北 京眷 区两级 阅卷组 的评 论 意见 并特 别 引用 了供题 者所提供 的参考答 案 谨在 此一井致