网络优化及实例.ppt

网络优化与优化网络优化与优化算法算法例：中国例：中国邮递员问题邮递员问题(CPP-Chinese Postman Problem)一一名名邮邮递递员员负负责责投投递递某某个个街街区区的的邮邮件件.如如何何设设计计一一条条最最短短的的投投递递路路线线(从从邮邮局局出出发发，经经过过投投递递区区内内每每条条街街道道至至少少一一次次，最最后后返返回回邮邮局局)？由由于于这这一一问问题题是是我我国国学学者者管管梅梅谷谷教教授授19601960年首先提出的，所以国际上称之为中国邮递员问题年首先提出的，所以国际上称之为中国邮递员问题.一、网络优化及实例一、网络优化及实例单向？双向？n欧拉把哥尼斯堡七桥问题转化为一个欧拉把哥尼斯堡七桥问题转化为一个图论上的问题：图论上的问题：七桥问题七桥问题答案答案的的是是否定的否定的因为图中没有偶度顶点有些问题目前找不到现成的软件n也没有快速求解最优解的方法也没有快速求解最优解的方法TSPTSP（Travel Sales Travel Sales Man ProblemMan Problem）问题）问题例例4 4设有城市集合设有城市集合，城市，城市到城市到城市的费用为的费用为求从指定城市出发，经过所有其他城市恰好求从指定城市出发，经过所有其他城市恰好一次，且使总费用最少的旅行路线。一次，且使总费用最少的旅行路线。TSPTSP问题可以通过枚举的方问题可以通过枚举的方法用计算机求解法用计算机求解n不同的路线共有不同的路线共有(n-1)！条！条枚举城市数与计算时间的关系 城市数城市数 24 25 26 27 28 29 30 31计算时间计算时间1s 24s 10m 4.3h 4.9d 136.5d10.8a 325a当城市个数增大到一定数量时枚举方法当城市个数增大到一定数量时枚举方法行不通行不通 !二、最优算法与近似算法二、最优算法与近似算法n有一些问题在计算复杂性上被称做有一些问题在计算复杂性上被称做NP困难问题困难问题,对这一类问题寻找快速的近似算法是十分有意义对这一类问题寻找快速的近似算法是十分有意义的。的。全国数学建模竞赛题中有一些全国数学建模竞赛题中有一些NPNP困难问题的困难问题的例子，需要用现有的软件结合编程进行计算，例子，需要用现有的软件结合编程进行计算，这一类近似算法的设计需要较宽的数学知识这一类近似算法的设计需要较宽的数学知识面和较强的创新能力面和较强的创新能力数学建模竞赛十分强调模型与数学建模竞赛十分强调模型与算法的创新性算法的创新性如：如：98年竞赛题年竞赛题B题是题是TSP问题问题的一个变形的一个变形n从县城出发分三个小组巡视受灾的地区各地的从县城出发分三个小组巡视受灾的地区各地的灾情，已知每个村镇所需要的停留时间以及行灾情，已知每个村镇所需要的停留时间以及行车速度，问如何设计各组的巡视路线才能以最车速度，问如何设计各组的巡视路线才能以最快的速度掌握整个地区全部的受灾情况快的速度掌握整个地区全部的受灾情况？灾情巡视路线灾情巡视路线(CUMCM-1998B)多人TSP问题的扩展考虑用一个考虑用一个 图来代替县城结点，图来代替县城结点，将问题转化为一个将问题转化为一个TSPTSP问题：问题：再将三点收缩成一点，就得到再将三点收缩成一点，就得到一个三个巡视组的一个三个巡视组的TSPTSP巡视路线巡视路线接下来的工作是要均衡各个巡视小组接下来的工作是要均衡各个巡视小组的工作时间的工作时间（十分复杂的工作！）（十分复杂的工作！）05年杭州电子科技大学校内竞赛题年杭州电子科技大学校内竞赛题B题题是一个网络优化问题是一个网络优化问题桥梁选址问题 设下图中每一个圆点代表一个区，连接各圆点的设下图中每一个圆点代表一个区，连接各圆点的直线代表公路，粗实线代表交通主干线，曲线代直线代表公路，粗实线代表交通主干线，曲线代表一条河流。随着城市经济发展表一条河流。随着城市经济发展,为了便利河两岸为了便利河两岸的交通，决定在适当的位置造桥。假设河流北侧的交通，决定在适当的位置造桥。假设河流北侧A到到D段有沿岸公路，河的南侧当前还没有修建沿段有沿岸公路，河的南侧当前还没有修建沿岸公路。试分别就以下问题讨论：岸公路。试分别就以下问题讨论：n问题一：问题一：河流为东西向的水平直线，各河流为东西向的水平直线，各区规模大致相同。区规模大致相同。1.总建设费用最低的桥梁位置和与之配套的总建设费用最低的桥梁位置和与之配套的公路设计方案；公路设计方案；2.以便捷交通为原则的最佳桥梁位置和公路以便捷交通为原则的最佳桥梁位置和公路设计方案。设计方案。问题二：河流为图中曲线，分别讨论总建设费问题二：河流为图中曲线，分别讨论总建设费用最小化和以便捷交通为原则的建设方案。用最小化和以便捷交通为原则的建设方案。问题三：如果计划建两座桥问题三：如果计划建两座桥,地址又该如何选择地址又该如何选择？问题四：如果各地的人口数不同，又该怎样选问题四：如果各地的人口数不同，又该怎样选择合理的桥梁位置？择合理的桥梁位置？ADn1.最小生成树算法最小生成树算法n2.最短路算法最短路算法n3.网络流算法网络流算法n4.匹配问题算法匹配问题算法常用网络优化算法有常用网络优化算法有复杂问题通常综合非线性优化和多目标规划复杂问题通常综合非线性优化和多目标规划1.1.计算机搜索算法计算机搜索算法2.2.计算机模拟计算机模拟常用计算机辅助算法有：常用计算机辅助算法有：常用的计算机搜索算法有遗传算法,模拟退火算法等,需要有一定的算法设计基础和基本的编程能力05年全国竞赛题B题:DVD的在线租赁n1.对对100个会员的订单和已有的个会员的订单和已有的DVD数量数量,如何分配才如何分配才可以尽可能满足要求可以尽可能满足要求?n某网站提供某网站提供DVD租赁服务租赁服务,根据以往数据根据以往数据,有有40%会员会员每月租赁一次每月租赁一次,60%会员每月租赁两次会员每月租赁两次.规定每次租赁规定每次租赁的的DVD数量为数量为3张张.建立以下问题的数学模型建立以下问题的数学模型:n2.经过网上调查经过网上调查,已有已有1000个会员的需求数据个会员的需求数据,对总数对总数n个会员个会员,应购买各种新应购买各种新DVD多少张才能以多少张才能以95%的概率满的概率满足需求足需求?n3.对给出的十万个会员数据及对给出的十万个会员数据及DVD数量数量,求具体的分配求具体的分配方案方案.n1.DVD租赁问题可以用整数规划求解租赁问题可以用整数规划求解n2.会员数据信息量大会员数据信息量大,Lingo软件可以与软件可以与Excel表链接表链接n3.随机数据可以利用概率统计知识进行预处理随机数据可以利用概率统计知识进行预处理,也可也可以建立随机规划模型以建立随机规划模型n4.会员满意度可以用计算机随机模拟方法估计会员满意度可以用计算机随机模拟方法估计n5.会员数任意大时会员数任意大时,整数规划不是一个快速算法整数规划不是一个快速算法,可以可以考虑建立一个诸如遗传算法或蚁群算法之类的快速考虑建立一个诸如遗传算法或蚁群算法之类的快速(近似近似)算法算法算法质量关键算法质量关键:1.精度精度 2.效能效能A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7铁路运价表里程300301350351400401450451500运价2023262932 钢管运输问题钢管运输问题（CUMCM-CUMCM-2000B)2000B)n常用解法常用解法:二次规划二次规划n先计算最小运费矩阵先计算最小运费矩阵两种运输方式（铁路公路）混合最短路问题两种运输方式（铁路公路）混合最短路问题是普通最短路问题的变种，需要自己设计算法是普通最短路问题的变种，需要自己设计算法 钢管运输问题钢管运输问题（CUMCM-CUMCM-2000B)2000B)fi表示钢厂表示钢厂i是否使用；是否使用；xij是从钢厂是从钢厂i运到节点运到节点j的钢管量的钢管量yj是从节点是从节点j向左铺设的钢管量；向左铺设的钢管量；zj是向右铺设的钢管量是向右铺设的钢管量 钢管运输问题钢管运输问题（CUMCM-CUMCM-2000B)2000B)LINDO/LINGO得到的结果比得到的结果比matlab得到的好得到的好cumcm2000b.lg4 算法设计中应该注意的问题算法设计中应该注意的问题1.1.线性规划是有效算法线性规划是有效算法,可以线性化的问可以线性化的问题不用非线性模型题不用非线性模型2.2.整数线性规划、二次规划及其他非线整数线性规划、二次规划及其他非线性规划模型除了可以利用数学软件求解性规划模型除了可以利用数学软件求解外外,讨论问题推广时应设计快速近似算法讨论问题推广时应设计快速近似算法3.3.一题多解讨论算法性能比较与分析一题多解讨论算法性能比较与分析应应大规模数据处理是近年竞赛题的倾向n如:n1.04年年A题题:奥运会临时超市网点设计奥运会临时超市网点设计n2.05年年A题题:长江水质的评价和预测长江水质的评价和预测n3.05年年B题题:DVD的在线租赁的在线租赁难度逐年增大计算机的应用能力是必要的内容计算机的应用能力是必要的内容