数学模型课程设计.doc

数学模型课程设计 课程设计 论文 任务书课程设计 论文 任务书 学 院理 学 院专 业信息与计算科学 学生姓名杨阳班级学号0609010224 课程名称数学模型课程设计 课 程 设 计 论文 题目 垃圾运输问题 设计要求 技术参数 1 建模 要求思路清晰 处理恰当 构思新颖 2 分析 数学应用合理恰当 应用知识综合 内容丰富 3 结论 要有一定的广度 深度 实用程度 4 表达 文字通顺 语言流畅 论述简洁 推理严谨 设计任务 用所学过的数学建模知识 上网查阅相关资料 对现实生活中的某一个实际问题 建立数学模 型 分析并解决提出的问题 可结合自己解决的问题展开 并以 MATLAB 或者其他数学软件为 工具 对所建模型进行求解 程序源码要在附录中给出 论文篇幅要在 15 页以上 计划与进度安排 第一周 第一阶段 上网查阅相关资料 第二阶段 建立模型 第二周 第三阶段 模型求解及优化 第四阶段 撰写论文 指导教师 签字 年 月 日 专业负责人 签字 年 月 日 主管院长 签字 年 月 日 数学模型课程设计 I 摘要 该题我们的主要解题思路分三阶段 第一阶段 我们先根据题设条件和基本假设画出该题的图 第二阶段 我们根据图和点的位置关系结合题设 归纳出一些最基本的确 定路线的原则 在仔细分析该题后 我们认为该题为一个单目标规划题 我们先抛开空 载费用 若要把所有的垃圾运回垃圾处理站 这部分有效工的费用为 1 8 Xi Yi Xi 为垃圾点 Xi 到原点的距离 Yi 为垃圾点的垃圾量 是 恒定不变的 只要我们能保证空载路线最小 则所花的时间和费用都最小 因 此解题的关键在于找出一个调度方案 使空载行驶的线路最小 第三阶段则是编制程序阶段 采用计算机模拟搜索的计算方法 搜索出 运输车投入辆数以及运输车最佳调配方案 使得在不考虑铲车的情况下运营费 用最低 总运营费用为运输车空载费与实际运输费之和 问题的解答如下 第一问 求得所需总费用为 2345 4 元 所需总时间为 22 5 小时 路线分配图见正文 第二问 求得需 3 辆铲车 铲车费用为 81 6 元 分配图及运输车调度表见正文 第三问 运营总费用为 2325 8 其中 8 吨 6 吨 4 吨载重量的运输车各需 5 2 3 辆 路线分配图见正文 关键词 单目标优化 计算机搜索 数学模型课程设计 II 目录 一 问题重述一 问题重述 1 二 问题分析二 问题分析 1 三 名词解释三 名词解释 2 四 模型建立与求解四 模型建立与求解 3 4 1 模型假设 3 4 2 参数说明 3 4 3 模型的建立 4 4 4 模型的求解 5 五 模型评价与推广五 模型评价与推广 20 5 1 模型评价 20 5 2 模型推广 20 六 参考文献六 参考文献 20 七 附件七 附件 21 数学模型课程设计 1 一 问题重述一 问题重述 某城区有 36 个垃圾集中点 每天都要从垃圾处理厂 第 37 号节点 出发将垃圾运回 现有一种载重 6 吨的运输车 每个垃圾点需要用 10 分钟的 时间装车 运输车平均速度为 40 公里 小时 夜里运输 不考虑塞车现象 每台车每日平均工作 4 小时 运输车重载运费 1 8 元 吨公里 运输车和装 垃圾用的铲车空载费用 0 4 元 公里 并且假定街道方向均平行于坐标轴 请你给出满意的运输调度方案以及计算程序 问题 1 运输车应如何调度 需要投入多少台运输车 每台车的调度方案 运营费用 2 铲车应如何调度 需要多少台铲车 每台铲车的行走路线 运营费用 3 如果有载重量为 4 吨 6 吨 8 吨三种运输车 又如何调度 垃圾点地理坐标数据表见附录一 二 问题分析二 问题分析 垃圾运输问题最终可以归结为最优路径搜索问题 但注意到此图为 森林而不是树 不能直接套用 Krusal Prim 等现成算法 于是根据具体问题设 计出随机下山法 用计算模拟搜索 可以搜寻到令人满意的可行解 先注意到两点的情况 设两点分别为A x1 y1 B x2 y2 主要有以下两种情况 一 A B明显有先后次序 递减状态 如图 1 数学模型课程设计 2 不妨设x1 x2 y1 y2 不难看出A在B的后方 即A比B远 对于前方参考点O 要将A B对应垃圾点的垃圾全部取回再返回 O 一共有三种方式 1 O A O O B O 单独运输 这种情况下 总的路程消费等于空载运行费用 0 4 元 公 里 与装载时运行费用 1 8 元 公里吨 的总和 所需的总时间等于车辆所走 过的总路程与速度 40 公里 小时 的比值再加上在 A B 两点停留的时间 每个 垃圾点上停留了 10 分钟 1 6 小时 于是有 2 O A B O 先远点再近点 即先空载至最远处 装完 A 点垃圾后再返回至 B 再回 O 点 有 3 O B A O 先近点在远点 即先装 B 点垃圾 然后载着 B 点的垃圾奔至 A 点 再回 O 点 有 比较以上三种情况 远近点的遍历顺序 可以看出 先远后近 绝对比 先近后远 在花费钱的数量上要少的多 省出 1 8 A B 2 Tb这部分的钱主 数学模型课程设计 3 要是车载着B点的垃圾奔到 A 点再返回 B 点 而又注意到两者的时间花费是相 等的 所以在其余同等的情况下选择 先远后近 考虑到时间上单独运输比其 余的两种运输要大的多 多一一倍 而且花费的钱仍不比 先远后近 省 还 多了 0 4 B 所以一般情况下 不采用单独运输 三 名词解释三 名词解释 A 表示 A 点到原点的距离 恒正 B 表示 B 点到原点的距离 恒正 A B 表示 A B 两点之间的距离 恒正 Ta 表示 A 点所在地的垃圾量 cost 运费 time 时间消耗 装的足够多 运输车当前的载重离限载不大于 0 55 吨 垃圾点的最小垃圾量 序数号 所在点的编号 四 模型建立与求解四 模型建立与求解 4 1 模型假设 模型假设 1 车辆在拐弯时的时间损耗忽略 2 车辆在任意两站点中途不停车 保持稳定的速率 3 只要平行于坐标轴即有街道存在 4 无论垃圾量多少 都能在十分钟内装上运输车 5 每个垃圾站点的垃圾只能由一辆运输车运载 6 假设运输车 铲车从 A 垃圾站到 B 垃圾站总走最短路线 7 任意两垃圾站间的最短路线为以两垃圾站连线为斜边的直角三角形的两直 角边之和 8 建设在运输垃圾过程中没有新垃圾入站 9 假设铲车 运输车载工作途中不发生意外也不遇到意外 数学模型课程设计 4 10 各垃圾站每天的垃圾量相对稳定 4 2 参数说明 参数说明 A 表示 A 点到原点的距离 恒正 B 表示 B 点到原点的距离 恒正 A B 表示 A B 两点之间的距离 恒正 Ta 表示 A 点所在地的垃圾量 4 3 模型的建立 模型的建立 先注意到两点的情况 设两点分别为A x1 y1 B x2 y2 主要有以下两种情况 二 A B明显有先后次序 递减状态 如图 1 图 不妨设x1 x2 y1 y2 不难看出A在B的后方 即A比B远 对于前方参考点O 要将A B对应垃圾点的垃圾全部取回再返回 O 一共有三种方式 1 O A O O B O 单独运输 这种情况下 总的路程消费等于空载运行费用 0 4 元 公 里 与装载时运行费用 1 8 元 公里吨 的总和 所需的总时间等于车辆所走 数学模型课程设计 5 过的总路程与速度 40 公里 小时 的比值再加上在 A B 两点停留的时间 每个 垃圾点上停留了 10 分钟 1 6 小时 于是有 1 TbBBTaAACost 8 14 08 14 0 2 26140 22 BATime 2 O A B O 先远点再近点 即先空载至最远处 装完 A 点垃圾后再返回至 B 再回 O 点 有 TbBTaAA TbTaBTaBAACost 8 18 14 0 8 18 14 0 3 261402 ATime 4 3 O B A O 先近点在远点 即先装 B 点垃圾 然后载着 B 点的垃圾奔至 A 点 再回 O 点 有 TbBATbBTaAB TbTaATbBABCost 28 18 18 14 0 8 18 14 0 5 261402 ATime 6 比较以上三种情况 远近点的遍历顺序 可以看出 先远后近 绝对比 先近后远 在花费钱的数量上要少的多 省出 1 8 A B 2 Tb这部分的钱主 数学模型课程设计 6 要是车载着B点的垃圾奔到 A 点再返回 B 点 而又注意到两者的时间花费是相 等的 所以在其余同等的情况下选择 先远后近 考虑到时间上单独运输比其 余的两种运输要大的多 多一一倍 而且花费的钱仍不比 先远后近 省 还 多了 0 4 B 所以一般情况下 不采用单独运输 二 A B两点没有明显先后顺序 并邻状态 如图 2 图 还是一共有三种情况 1 O A O O B O 单独运输 这种情况下 跟 A B 两点有先后顺序中的情况完全相同 即有 7 TbBBTaAACost 8 14 08 14 0 8 26140 22 BATime 2 O A B O TbBTaAA TbTaBTaBAACost 8 18 14 0 8 18 14 0 9 26140 BBAATime 数学模型课程设计 7 10 3 O B A O 8 18 14 0TbTaATbBABCost 11 26140 BBAATime 12 相比之下 清晰可见并邻状态下的单独运输所花的费用最少 所以在不要 求时间的情况下对于并邻两点 采用单独运输的方式最节约钱 用式与 式相减除以 1 8 得到如下判断式 ABTbTaTbTaBA 上式 0 时 选 O B A O 上式 0 时 任意选上述两路线 三 两点选择趋势的讨论 如图 3 图 数学模型课程设计 8 由图中看到B C两点没有明显的先后顺序 属于并邻点 因为当运输车载 重行驶时费用会成倍的增长 比其空载时所花费用要大的多 所以排除 A B C或A C B这样的一次经过 3 点的往返路线 仅选择 B C 中的某一点 与 A 完成此次运输 将另一点留到下次 那么A点选择B还是C呢 不妨假设 B C 即 B 点离原点的距离比C点的更远 因为A在B C之后 所以也就是B点离A点更近 这样 此次的运输我们更趋向于选择A B 因为 就这三点而论 A无论是选B还是C 三点的垃圾总要运完 所以花费的钱是 一样的 但选择A B后 下次运输车运C点垃圾时就无需跑的更远 四 关于垃圾点的垃圾是否一次清除的讨论 以 6 吨车例 由假设 2 知 每天的垃圾必须清除完毕 全部运往 37 点 这里说的一次 清除问题不是指一天 而是指当一辆运输车已经装载了足够多的垃圾 不能完 全清理下一个垃圾点的时候 车在下一个站点 停还是不停 的问题 例如 一辆运输车选择了 30 26 18 35 20 的路线 即先将空车开往 30 清理装 载 30 点的垃圾 然后依次到 26 18 35 20 它从 20 返回时车已经装载了 5 8 吨垃圾 仍可以装 0 2 吨 小于垃圾点垃圾量的最小值 0 5 称这种情况为 装的足够多 在 20 点下方仍有不少的点 但肯定不能将下面的任意点的 垃圾装完 那么此车是直接返回 37 点呢 还是继续装直至车装满为止呢 我们判断前者更好 就是车在装的足够多的情况下应该直接返回原点 37 点 这是因为对于下一垃圾点 假设为 A 点 内的垃圾而言 无论是一次装完 还是分两次装完 将它们运回所花费用是恒定的 等于 1 8 Ta A 整体而 言 两者花费的钱是相等的 但分两次装要多花 10 分钟的装车时间 所以选 择前者 综上所述 得出搜索的基本原则 数学模型课程设计 9 1 在两点递减的情况下 不采用单独运输 2 在其余同等的情况下选择 先远后近 3 不要求时间的情况下对于并邻两点 采用单独运输的方式最节约钱 一般情况下用式s jg i j1 w 1 j sum w 4 j m j else continue end end w 5 m 1 j1 j1 1 while 1 js 0 q 40 for k 1 36 if q w 2 m w 2 k w 3 m w 3 k js 1 jg i j1 w 1 k i3 k else continue end end w 5 i3 1 sum sum w 4 i3 j1 j1 1 m i3 数学模型课程设计 18 if w 2 i3 0 zcost 0 allcost 0 n 0 for u1 1 11 for u2 1 11 if jg u1 u2 0 n jg u1 u2 else continue end zcost zcost w 4 n 1 8 w 2 n w 3 n end n jg u1 1 kcost kcost 0 4 w 2 n w 3 n end allcost zcost kcost zcost kcost i 1 11 time i time 1 0 n1 0 n2 0 n3 0 for u4 1 11 for u5 1 11 if jg u4 u5 0 n1 jg u4 u5 n2 n2 1 else continue end end n3 jg u4 1 time 1 u4 w 2 n3 w 3 n3 2 40 end n2 time 附录三附录三 源码源码 数学模型课程设计 19 clear x 3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25 9 9 30 0 y 2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 16 7 20 15 12 0 t 1 50 1 50 0 55 1 20 0 85 1 30 1 20 2 30 1 40 1 50 1 10 2 70 1 80 1 80 0 60 1 50 0 80 1 50 0 80 1 40 1 20 1 80 1 40 1 60 1 60 1 00 2 00 1 00 2 10 1 20 1 90 1 30 1 60 1 20 1 50 1 30 0 00 r 1 37 plot x y r for ii 1 37 k int2str ii k strcat P k text x ii y ii k end w r x y t a 1 11 point 30 28 36 24 34 20 19 14 22 11 31 3 5 21 15 2 9 8 1 22 10 6 a point 3 0 s 80 p 80 k 2 j1 0 j2 0 m 1 b 1 11 pai b pai 1 0 for j 1 11 if s w 2 point 1 j w 3 point 1 j else continue end end j1 j point 3 j1 1 pai 1 point 1 j1 while m w 2 point 1 i w 3 point 1 i w 2 point 2 j1 w 3 point 2 j1 数学模型课程设计 20 else continue end j2 i point 3 j2 1 pai k point 1 j2 k k 1 end j1 j2 m m 1 end pai 附录三附录三 结果结果 pai 31 30 28 36 24 34 20 19 14 22 11 附录四 clear x 3 1 5 4 0 3 7 9 10 14 17 14 12 10 7 2 6 11 15 19 22 21 27 15 15 20 21 24 25 28 5 17 25 9 9 30 0 y 2 5 4 7 8 11 9 6 2 0 3 6 9 12 14 16 18 17 12 9 5 0 9 19 14 17 13 20 16 18 12 16 7 20 15 12 0 t 1 50 1 50 0 55 1 20 0 85 1 30 1 20 2 30 1 40 1 50 1 10 2 70 1 80 1 80 0 60 1 50 0 80 1 50 0 80 1 40 1 20 1 80 1 40 1 60 1 60 1 00 2 00 1 00 2 10 1 20 1 90 1 30 1 60 1 20 1 50 1 30 0 00 i 1 37 a 1 37 plot x y r for ii 1 37 k