网络优化及实例.ppt

例：中国邮递员问题(CPP-ChinesePostmanProblem)一名邮递员负责投递某个街区的邮件.如何设计一条最短的投递路线(从邮局出发，经过投递区内每条街道至少一次，最后返回邮局)？由于这一问题是我国学者管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题.欧拉把哥尼斯堡七桥问题转化为一个图论上的问题：七桥问题有些问题目前找不到现成的软件TSP问题可以通过枚举的方法用计算机求解二、最优算法与近似算法如：98年竞赛题B题是TSP问题的一个变形灾情巡视路线(CUMCM-1998B)考虑用一个图来代替县城结点，将问题转化为一个TSP问题：再将三点收缩成一点，就得到一个三个巡视组的TSP巡视路线05年杭州电子科技大学校内竞赛题B题是一个网络优化问题问题一：河流为东西向的水平直线，各区规模大致相同。1.总建设费用最低的桥梁位置和与之配套的公路设计方案；2.以便捷交通为原则的最佳桥梁位置和公路设计方案。问题四：如果各地的人口数不同，又该怎样选择合理的桥梁位置？1.最小生成树算法2.最短路算法3.网络流算法4.匹配问题算法1.计算机搜索算法2.计算机模拟05年全国竞赛题B题:DVD的在线租赁1.DVD租赁问题可以用整数规划求解2.会员数据信息量大,Lingo软件可以与Excel表链接3.随机数据可以利用概率统计知识进行预处理,也可以建立随机规划模型4.会员满意度可以用计算机随机模拟方法估计5.会员数任意大时,整数规划不是一个快速算法,可以考虑建立一个诸如遗传算法或蚁群算法之类的快速(近似)算法常用解法:二次规划先计算最小运费矩阵两种运输方式（铁路／公路）混合最短路问题是普通最短路问题的变种，需要自己设计算法fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量算法设计中应该注意的问题1.线性规划是有效算法,可以线性化的问题不用非线性模型2.整数线性规划、二次规划及其他非线性规划模型除了可以利用数学软件求解外,讨论问题推广时应设计快速近似算法3.一题多解讨论算法性能比较与分析应大规模数据处理是近年竞赛题的倾向