网络优化及实例PPT学习教案

1、会计学1网络优化及实例网络优化及实例例：中国邮递员问题例：中国邮递员问题(CPP-Chinese Postman Problem)一名邮递员负责投递某个街区的邮件一名邮递员负责投递某个街区的邮件. . 如何设计一条最短如何设计一条最短的投递路线的投递路线( (从邮局出发，经过投递区内每条街道至少一次从邮局出发，经过投递区内每条街道至少一次，最后返回邮局，最后返回邮局) )？由于这一问题是我国学者？由于这一问题是我国学者管梅谷管梅谷教授教授19601960年首先提出的，所以国际上称之为中国邮递员问题年首先提出的，所以国际上称之为中国邮递员问题. . 一、网络优化及实例一、网络优化及实例单向？双向

2、？第1页/共25页第2页/共25页七桥问题七桥问题答案答案的的是是因为图中没有偶度顶点第3页/共25页21 nI， TSPTSP（Travel Sales Travel Sales Man ProblemMan Problem）问题）问题例例4 4设有城市集合设有城市集合，城市，城市ij到城到城市市的费用为的费用为，ijcnji, 1,求从指定城市出发，经过所有其他城市恰好求从指定城市出发，经过所有其他城市恰好一次，且使总费用最少的旅行路线。一次，且使总费用最少的旅行路线。第4页/共25页枚举城市数与计算时间的关系 城市数城市数 24 25 26 27 28 29 30 31计算时间计算时间1

3、s 24s 10m 4.3h 4.9d 136.5d10.8a 325a当城市个数增大到一定数量时枚举方法当城市个数增大到一定数量时枚举方法行不通行不通 ! !第5页/共25页全国数学建模竞赛题中有一些全国数学建模竞赛题中有一些NPNP困难问题的困难问题的例子，需要用现有的软件结合编程进行计算，例子，需要用现有的软件结合编程进行计算，这一类近似算法的设计需要较宽的数学知识这一类近似算法的设计需要较宽的数学知识面和较强的创新能力面和较强的创新能力数学建模竞赛十分强调模型与数学建模竞赛十分强调模型与算法的创新性算法的创新性第6页/共25页第7页/共25页灾情巡视路线灾情巡视路线(CUMCM-199

4、8B)多人TSP问题的扩展第8页/共25页第9页/共25页接下来的工作是要均衡各个巡视小组接下来的工作是要均衡各个巡视小组的工作时间的工作时间（十分复杂的工作！）（十分复杂的工作！）第10页/共25页 设下图中每一个圆点代表一个区，连接各圆点的设下图中每一个圆点代表一个区，连接各圆点的直线代表公路，粗实线代表交通主干线，曲线代直线代表公路，粗实线代表交通主干线，曲线代表一条河流。随着城市经济发展表一条河流。随着城市经济发展,为了便利河两岸为了便利河两岸的交通，决定在适当的位置造桥。假设河流北侧的交通，决定在适当的位置造桥。假设河流北侧A到到D段有沿岸公路，河的南侧当前还没有修建沿段有沿岸公路，

5、河的南侧当前还没有修建沿岸公路。试分别就以下问题讨论：岸公路。试分别就以下问题讨论：第11页/共25页问题二：河流为图中曲线，分别讨论总建设费问题二：河流为图中曲线，分别讨论总建设费用最小化和以便捷交通为原则的建设方案。用最小化和以便捷交通为原则的建设方案。问题三：如果计划建两座桥问题三：如果计划建两座桥,地址又该如何选择地址又该如何选择？第12页/共25页AD第13页/共25页常用网络优化算法有常用网络优化算法有复杂问题通常综合非线性优化和多目标规划复杂问题通常综合非线性优化和多目标规划第14页/共25页常用计算机辅助算法有：常用计算机辅助算法有：常用的计算机搜索算法有遗传算法,模拟退火算法

6、等,需要有一定的算法设计基础和基本的编程能力第15页/共25页第16页/共25页算法质量关键算法质量关键: 1.精度精度 2. 效能效能第17页/共25页第18页/共25页A13258010103120124270108810706270302020304501043017506061942052016804803002202104205006003060195202720690520170690462160320160110290115011001200A2A3A4A5A6A7A8A9A10A11A12A13A14A15S1S2S3S4S5S6S7铁路运价表里程300301350351400

7、401450451500运价2023262932 钢管运输问题钢管运输问题（CUMCM-CUMCM-2000B)2000B)第19页/共25页第20页/共25页 钢管运输问题钢管运输问题（CUMCM-CUMCM-2000B)2000B)第21页/共25页 钢管运输问题钢管运输问题（CUMCM-CUMCM-2000B)2000B). 7,.,1, 1 , 0, 0.14,.,1.15,.,1,. 7,.,1,500. .)1 ()1(21 . 0)(151171151151,ifzyjbzyjzyxifSxftszzyyxcpMinijjjjjiijiijijijjjjjjiijijiLINDO/LINGO得到的结果比得到的结果比matlab得到的好得到的好cumcm2000b.lg4第22页/共25页 算法设计中应该注意的问题算法设计中应该注意的问题1. 1. 线性规划是有效算法线性规划是有效算法, ,可以线性化的可以线性化的问题不用非线性模型问题不用非线性模型2.2.整数线性规划、二次规划及其他非线整数线性规划、二次规划及其他非线性规划模型除了可以利用数学软件求解性规划模型除了可以利用数学软件求解外外, ,