网络优化及实例ppt课件.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.会员数任意大时,整数规划不是一个快速算法,可以考虑建立一个诸如遗传算法或蚁群算法之类的快速(近似)算法A1常用解法:二次规划

先计算最小运费矩阵
两种运输方式（铁路／公路）混合最短路问题
是普通最短路问题的变种，需要自己设计算法fi表示钢厂i是否使用；xij是从钢厂i运到节点j的钢管量
yj是从节点j向左铺设的钢管量；zj是向右铺设的钢管量算法设计中应该注意的问题
1.线性规划是有效算法,可以线性化的问题不用非线性模型
2.整数线性规划、二次规划及其他非线性规划模型除了可以利用数学软件求解外,讨论问题推广时应设计快速近似算法
3.一题多解讨论算法性能比较与分析
应大规模数据处理是近年竞赛题的倾向