




版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
网络优化与优化算法网络优化及实例例:中国邮递员问题(CPP-ChinesePostmanProblem)一名邮递员负责投递某个街区的邮件.如何设计一条最短的投递路线(从邮局出发,经过投递区内每条街道至少一次,最后返回邮局)?由于这一问题是我国学者管梅谷教授1960年首先提出的,所以国际上称之为中国邮递员问题.一、网络优化及实例单向?双向?网络优化及实例欧拉把哥尼斯堡七桥问题转化为一个图论上的问题:给定一个图,问是否存在点不重的环游?网络优化及实例七桥问题答案的是否定的因为图中没有偶度顶点网络优化及实例有些问题目前找不到现成的软件也没有快速求解最优解的方法TSP(TravelSalesManProblem)问题例4设有城市集合,城市到城市的费用为求从指定城市出发,经过所有其他城市恰好一次,且使总费用最少的旅行路线。网络优化及实例
TSP问题可以通过枚举的方法用计算机求解不同的路线共有(n-1)!条枚举城市数与计算时间的关系
城市数2425262728293031计算时间1s24s10m4.3h4.9d136.5d10.8a325a当城市个数增大到一定数量时枚举方法行不通
!网络优化及实例二、最优算法与近似算法有一些问题在计算复杂性上被称做NP困难问题,对这一类问题寻找快速的近似算法是十分有意义的。全国数学建模竞赛题中有一些NP困难问题的例子,需要用现有的软件结合编程进行计算,这一类近似算法的设计需要较宽的数学知识面和较强的创新能力数学建模竞赛十分强调模型与算法的创新性网络优化及实例如:98年竞赛题B题是TSP问题
的一个变形从县城出发分三个小组巡视受灾的地区各地的灾情,已知每个村镇所需要的停留时间以及行车速度,问如何设计各组的巡视路线才能以最快的速度掌握整个地区全部的受灾情况?网络优化及实例灾情巡视路线(CUMCM-1998B)多人TSP问题的扩展网络优化及实例考虑用一个图来代替县城结点,
将问题转化为一个TSP问题:网络优化及实例再将三点收缩成一点,就得到
一个三个巡视组的TSP巡视路线
接下来的工作是要均衡各个巡视小组的工作时间(十分复杂的工作!)网络优化及实例05年杭州电子科技大学校内竞赛题B题
是一个网络优化问题桥梁选址问题
设下图中每一个圆点代表一个区,连接各圆点的直线代表公路,粗实线代表交通主干线,曲线代表一条河流。随着城市经济发展,为了便利河两岸的交通,决定在适当的位置造桥。假设河流北侧A到D段有沿岸公路,河的南侧当前还没有修建沿岸公路。试分别就以下问题讨论:网络优化及实例问题一:河流为东西向的水平直线,各区规模大致相同。1.总建设费用最低的桥梁位置和与之配套的公路设计方案;2.以便捷交通为原则的最佳桥梁位置和公路设计方案。问题二:河流为图中曲线,分别讨论总建设费用最小化和以便捷交通为原则的建设方案。问题三:如果计划建两座桥,地址又该如何选择?网络优化及实例问题四:如果各地的人口数不同,又该怎样选择合理的桥梁位置?AD网络优化及实例1.最小生成树算法2.最短路算法3.网络流算法4.匹配问题算法常用网络优化算法有复杂问题通常综合非线性优化和多目标规划网络优化及实例1.计算机搜索算法
2.计算机模拟常用计算机辅助算法有:常用的计算机搜索算法有遗传算法,模拟退火算法等,需要有一定的算法设计基础和基本的编程能力网络优化及实例05年全国竞赛题B题:DVD的在线租赁1.对100个会员的订单和已有的DVD数量,如何分配才可以尽可能满足要求?某网站提供DVD租赁服务,根据以往数据,有40%会员每月租赁一次,60%会员每月租赁两次.规定每次租赁的DVD数量为3张.建立以下问题的数学模型:2.经过网上调查,已有1000个会员的需求数据,对总数n个会员,应购买各种新DVD多少张才能以95%的概率满足需求?3.对给出的十万个会员数据及DVD数量,求具体的分配方案.网络优化及实例1.DVD租赁问题可以用整数规划求解2.会员数据信息量大,Lingo软件可以与Excel表链接3.随机数据可以利用概率统计知识进行预处理,也可以建立随机规划模型4.会员满意度可以用计算机随机模拟方法估计5.会员数任意大时,整数规划不是一个快速算法,可以考虑建立一个诸如遗传算法或蚁群算法之类的快速(近似)算法算法质量关键:1.精度
2.
效能网络优化及实例网络优化及实例A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7铁路运价表里程≤300301~350351~400401~450451~500…运价2023262932…
钢管运输问题(CUMCM-2000B)网络优化及实例网络优化及实例常用解法:二次规划先计算最小运费矩阵两种运输方式(铁路/公路)混合最短路问题是普通最短路问题的变种,需要自己设计算法
钢管运输问题(CUMCM-2000B)网络优化及实例fi表示钢厂i是否使用;xij是从钢厂i运到节点j的钢管量yj是从节点j向左铺设的钢管量;zj是向右铺设的钢管量
钢管运输问题(CUMCM-2000B)LINDO/LINGO得到的结果比matlab得到的好cumcm2000b.lg4网络优化及实例
算法设计中应该注意的问题1.线性规划是有效算法,可以线性化的问题不用非线性模型2.整数线性规划、二次规划及其他非线性规划模型除了可以利用数学软件求解外,讨论问题推广时应设计快速近似算法3.一题多
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 星际通信调制解调技术研究-洞察分析
- 法定代表人资格证明书
- 应急演练方案范例(2篇)
- 毕业设计实习报告
- 双创双争实施方案例文(3篇)
- 坦克吊工安全职责(2篇)
- 火工材料仓管员安全技术操作规程(4篇)
- 机关值班工作管理制度模版(2篇)
- 服装年度总结
- 有志者事竟成演讲稿
- 甲醇-水溶液连续精馏塔设计
- 山钢钢板材质单
- 容积升校准记录表1份
- 煤矿公司掘进巷道贯通管理办法
- 技工学校毕业生登记表
- 降低故障工单回复不合格率
- 可涂色简笔画打印(共20页)
- 灯光架介绍及使用说明
- 十一学校行动纲要
- GB 1886.6-2016 食品安全国家标准 食品添加剂 硫酸钙(高清版)
- 关于房屋征收及土地收储过程中的税收政策(仅供参考)
评论
0/150
提交评论