网络优化及实例.ppt

,网络优化与优化算法,例：中国邮递员问题(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.以便捷交通为原则的最佳桥梁位置和公路设计方案。,问题二：河流为图中曲线，分别讨论总建设费用最小化和以便捷交通为原则的建设方案。,问题三：如果计划建两座桥,地址又该如何选择？,问题四：如果各地的人口数不同，又该怎样选择合理的桥梁位置？,A,D,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.效能,铁路运价表,钢管运输问题（CUMCM-2000B),常用解法:二次规划先计算最小运费矩阵两种运输方式（铁路公路）混合最短路问题是普通最短路问题的变种，需要自己设计算法,钢管运输问题（CUMCM-2000B),fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量,钢管运输问题（CUMCM-2000B),LINDO/LINGO得到的结果比matlab得到的好,算法设计中应该注意的问题1.线性规划是有效算法,可以线性化的问题不用非线性模型2.整数线性规划、二次规划及其他非线性规划模型除了可以利用数学软件求解外,讨论问题推广时应设计快速近似算法3.一题多解讨论算法性能比较与分析应,大规模数据处理是近年竞赛题的倾向,如:1.04年A题:奥运会临时超市网点设计2.05年A题:长江水质的评价和预测3.05年B题:DVD的在线租赁,难,度逐年增大,计算机的应用能力是必要的内容,