[所有分类]东北大学数学建模-图论模型朱和贵.ppt

[所有分类]东北大学数学建模-图论模型朱和贵.ppt

  1. 1、本文档共136页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[所有分类]东北大学数学建模-图论模型朱和贵

此问题包含两方面:a)对顶点分组, b)在每组中 求(单个售货员)最佳旅行售货员回路. 因单个售货员的最佳旅行售货员回路问题不存 存在多项式时间内的精确算法. 故多售货员的最佳旅行售货员回路问题 也不 而图中节点数较多,为53个,我们只能去寻求 一种较合理的划分准则,对图1进行粗步划分后,求 出各部分的近似最佳旅行售货员回路的权,再进一 进一步进行调整,使得各部分满足均衡性条件3). 从O点出发去其它点,要使路程较小应尽量走 O点到该点的最短路. 故用软件包求出O点到其余顶点的最短路. 这些最短路构成一棵O为树根的树. 将从O点出发的树枝称为干枝. 从O点出发到其它点共有6条干枝,它们的名称 分别为①,②,③,④,⑤,⑥. 在分组时应遵从准则: 准则1 尽量使同一干枝上及其分枝上的点分在同一组. 准则2 应将相邻的干枝上的点分在同一组; 准则3 尽量将长的干枝与短的干枝分在同一组. 由上述分组准则,我们找到两种分组形式如下: 分组1:(⑥,①),(②,③),(⑤,④) 分组2:(①,②),(③,④),(⑤,⑥) 分组1极不均衡,故考虑分组2. 分组2:(①,②),(③,④),(⑤,⑥) 对分组2中每组顶点的生成子图,用算法一求出近似最优解及相应的巡视路线. 在每个子图所构造的完全图中,取一个尽量包含上图中树上的边的H圈作为其第2)步输入的初始圈. 分组2的近似解 因为该分组的均衡度 . 所以此分法的均衡性很差. 为改善均衡性,将第Ⅱ组中的顶点C,2,3,D,4 分给第Ⅲ组(顶点2为这两组的公共点),重新分 分组后的近似最优解见表2. 因该分组的均衡度 所以这种分法的均衡性较好. 问题二 当巡视人员在各乡(镇)、村的停留 停留时间一定,汽车的行驶速度一定,要在24小时内 完成巡视,至少要分几组及最佳旅行的巡视路线. 由于T=2小时,t=1小时,V=35公里/小时,需访问 的乡镇共有17个,村共有35个. 计算出在乡(镇)及 村的总停留时间为17 2+35=69小时,要在24小时 内完成巡回,若不考虑行走时间,有: 69/i24(i为 分的组数). 得i最小为4,故至少要分4组. 由于该网络的乡(镇)、村分布较为均匀,故有可 能找出停留时间尽量均衡的分组,当分4组时各组停 停留时间大约为69/4=17.25小时,则每组分配在路 路途上的时间大约为24-17.25=6.75小时.而前面讨 论过,分三组时有个总路程599.8公里的巡视路线, 分4组时的总路程不会比599.8公里大太多,不妨以 599.8公里来计算.路上约用599.8/35=17小时,若平 均分配给4个组,每个组约需17/4=4.25小时6.75小 小时,故分成4组是可能办到的. 现在尝试将顶点分为4组.分组的原则:除遵从 前面准则1、2、3外,还应遵从以下准则: 准则4 尽量使各组的停留时间相等. 用上述原则在下图上将图分为4组,同时计算 各组的停留时间,然后用算法一算出各组的近似最 最佳旅行售货员巡回,得出路线长度及行走时间, 从而得出完成巡视的近似最佳时间. 用算法一计 计算时,初始圈的输入与分三组时同样处理. 这4组的近似最优解见表3. 表3符号说明:加有底纹的表示前面经过并停留过, 此次只经过不停留;加框的表示此点只经过不停留. 可看出,表3分组的均衡度很好,且完全满足24小时完成巡视的要求 该分组实际均衡度 4.62% 谢 谢 * * 实际问题中,一个网络会出现下面两种情况: ⑴ 发点和收点都不止一个。 解决的方法是再虚设一个发点vs和一个收点vt ,发点vs到所有原发点边的容量都设为无穷大, 所有原收点到收点vt 边的容量都设为无穷大。 ⑵ 网络中除了边有容量外,点也有容量。 解决的方法是将所有有容量的点分成两个点,如点v有容量Cv ,将点v分成两个点v和v,令 C(vv ) = Cv . 行 遍 性 问 题 一、中 国 邮 递 员 问 题 二、推 销 员 问 题 三、建模案例:最佳灾情巡视路线 (一) 欧 拉 图 (二) 中 国 邮 递 员 问 题 (一) 哈 密 尔 顿 图 (二) 推 销 员 问 题 V7 e3 v1 v2 v3 v4 e1 e2 e4 e5 V5 V6 e6 e7 e8 e9 割边 G的边e是割边的充要条件是e不含在G的圈中. 割边的定义:设G连通,e E(G),若从G中删除边e后,

文档评论(0)

skvdnd51 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档