2015年全国研究生数学建模竞赛答案 - 图文(2)

用Hopfield网络求解优化问题的一般步骤： （1）用罚函数法写出问题的目标函数 设优化问题如下：

?min?(v1,v2,?,vN),i?1,2,?,k；k为约束数 ??约束：pi(v1,v2,?,vN)?0 则目标函数为I??(v1,v2,?,vN)???iF[p(v1,v2,?,vN)]，其中?i为足够大的常数，

i?1k取值可以互不相同。令I与前式中的E相等可定出各连接权Tij的值来。

（2）写出网络的动态方程

Hopfield网络是一个梯度系统，所以它满足

dui?E??对于常用的连续网络有dt?vidui?E(v1,v2,?,vN) ??Rdt?vi（3）选择合适的初值u1(0),u2(0),?,uN(0)，使网络按动态方程演化直到收敛为止。

2.2 用Hopfield网络求解旅行商问题（TSP问题）

对于N城市的TSP问题，任何一个城市在最终路径上的访问次序可用一个N维向量来表示，就需要N个神经元。如在5-TSP中，设城市1在第3个被访问，则对应的向量为V(1)=00100。N城市TSP问题需用N*N个神经元来实现，而每行每列都只能有一个1，其余为0，该阵称为换位矩阵。换位矩阵中1的和为N，所构造的函数极小值

对应于最短路径。

构造与TSP相对应的能量函数[1-3]：

ANE??2x?1?D?2x?1NN?i?1N?1BNVxiVxj???2i?1j?i?1xyN?x?1N?1CNVxiVyi?(??2x?1y?x?1N?Vi?1Nxi?N)2

??dy?1i?1NVxi(Vy,i?1?Vy,i?1)A、B、C、D为拉格朗日常数，均为正数。当解合法时前三项为0；当达到最优解时，

第四项最小，其值对应于最短路径。在Hopfield网络运行时，采用并行算法：

NNNduxiuxi???A?Vxj?B?Vyi?C(?dt?j?1y?1x?1j?iy?x?Vi?1Nxi?N)?D?dxy(Vy,i?1?Vy,i?1)y?1Nu1Vxi?g(uxi)?[1?tanh(xi)]?2u011?e?2uxiu0

τ=1.0；u0为符号函数的参量，u0越小，符号函数的离散化程度越高。在进行迭代前，要对uxi赋初值，不妨令uxi,init??0.5*u0*ln(N?1)*(1??)，δ是在（-0.1，0.1）均匀分

t?1t?uxi?布的随机数。在迭代时，uxiduxi*?t，δt为运算步长。 dt因为能量在极小值时变化最慢，所以将能量函数E变化小到一定程度作为结束标志，即?E?Min_value。如果超过了一定的迭代次数（如1500次）仍没有收敛，则强行终止。

2.3 旅游路线规划问题一的分析与求解

假设该旅游爱好者每年外出旅游次数为x次，每次旅游时间为y天。根据条件，该旅游爱好者每年有不超过30天的外出旅游时间，每年外出旅游的次数不超过4次，每次旅游的时间不超过15天，则有：

xy ≤ 30 x ≤ 4 y ≤ 15

问题一中旅游爱好者需要以最短的时间将201个5A景点全部游览过，则有必要考虑旅行过程中的耗时因素，主要有（1）每次从西安到某个景点的来回时间t1；（2）高速公路及过道的限速t2；（3）到达景点的时间及景点的参观时长t3。针对耗时因素t1，可近似考虑其与从西安出发的次数x成正相关关系，正相关系数为a，则有：

t1 = ax

要使得t1时长短，需要减小x的值，同时为了使每年可以去到尽量多的地方，需要该旅游爱好者每年安排30天出行，求得x=2，y=15。

则该旅行者需要每年外出旅游2次，每次15天，从而可以有效地减小t1的时间，缩短整个规划中的时长。

2.3.1 聚类分析思想

聚类分析指将物理或抽象对象的集合分组为由类似的对象组成的多个类的分析过程[4]。聚类分析就是通过在相似的基础上收集数据来分类，达到数据简化的目的。聚类分析包括两类方式，（1）层次聚类（Hierarchical Clustering），包括合并法、分解法、树状图；（2）非层次聚类，包括划分聚类、谱聚类。

201个5A级别的景点覆盖整个中国，如果直接对其进行数据分析和处理，工作量是非常大的。因此我们需要对其进行聚类分析，形成更少数量的点，便于下一步的规划与设计。

图2 全国201个5A景点一览图

从地图上可以看到，西安市位于中原地区，黄色五角星表示5A级别的景点，这些景点分布在西安市的四周，这在位置上有利于聚类分析的分类，采用合并法，现有两种分类方式，（1）按照省份分类；（2）按照地理位置分类，即相邻的景点划分一类。两类分类方法的优缺点如下：

（1）按照省份分类

优点：a. 分类方便，可直接通过省界线确定各区域；

b. 同一个省内交通方便，距离较近，可大大缩短旅游时间； c. 符合附件中景点的分类方式，数据处理较为方便； d. 符合现代人游玩的方式，可尽情享受省特色文化。

缺点：相邻省份的某些景点可能更加接近，按照省份分类反而会稍增耗时。

（2）按照地理位置分类

优点：相邻景点交通便利，耗时较短。

缺点：a. 数据庞大，分区复杂，工作量大；

b. 地图上相邻的某些景点之间交通可能并不发达，反而耗时更大； c. 不能充分感受省特色文化。

综上，为了简化数据的处理，为了更好地体验，问题一中采用两种分类结合的方式对中国的5A景点进行划分，以按省份分类为主，按地理位置分类为辅，考虑实际环境，综合各自的优势为一体，最终划分出20个区域，分别是：江苏、浙江、福建、江西、黑龙江、广东、云南、四川、安徽（江苏、陕西）、青海-甘肃（宁夏）、湖北（宁夏）、上海-山西（宁夏）、北京-天津（河北）、山东（河北）、吉林-辽宁-内蒙、湖南(重庆)、河南(陕西)、广西-海南、贵州（重庆）、新疆-西藏，其中符号“-”后的省份被完全包含到该区域中去，括号内的省份仅部分地区合并到该地区。以下所有问题的解决，都是以这20个区域为基础进行规划的。

2.3.2 求解的具体过程

由于全国的省份众多，这里不再一一说明。下面以旅游景点较多的浙江省为例进行

说明。

浙江省的旅游景点有：杭州西湖风景区、温州乐清市雁荡山风景区、舟山普陀山风景区、杭州淳安千岛湖风景区、嘉兴桐乡乌镇古镇旅游区、宁波奉化溪口－滕头旅游景区、金华东阳横店影视城景区、嘉兴南湖旅游区、杭州西溪湿地旅游区、绍兴市鲁迅故里－沈园景区、衢州市开化根宫佛国文化旅游区、湖州市南浔区南浔古镇景区。

为了减少计算的复杂性，提高计算结果的准确性，我们把在一个城市的多个景点合并成一个景点来进行计算，并将总游览时间作为该景点的游览时间。比如浙江省的杭州西湖风景区与杭州西溪湿地旅游区两者都在杭州市区，可以被当做一个景点来计算，当最后安排详细行程时再分拆成两个景点进行行程安排。另外由于该旅游爱好者计划在每一个省会城市至少停留24小时，以安排专门时间去游览城市特色建筑和体验当地风土人情，因此我们将每个省的省会当做一个景点来计算，并将游览时间定为8个小时。

由于旅游路线规划问题一需要求解的是旅游时间最优，查询各个景点的行车时间（资料来源：百度地图[5]）与游览时间（资料来源：附件1），建立如下图所示的各景点之间所花费时间的表格。表格中每个花费时间包括行车时间与将要游览景区的游览时间。其中左侧景区为出发地，上侧的景区为目的地。

表1 浙江省各景区间的花费时间表 杭州杭州西溪淳安湿地千岛旅游湖风区、西景区 湖 0 10.2 9.5 9.3 9.2 10.2 0 11.5 湖州市南浔区南浔古镇景区 5.5 7.5 0 嘉兴嘉兴桐乡南湖乌镇旅游古镇区 旅游区 5.3 7.4 5.2 7.2 金华东阳横店影视城景区 6.1 7.6 宁波奉化溪口－滕头旅游景区 6.25 8.05 衢州市开化根宫佛国 绍兴市鲁迅故里－沈园景区 温州乐清市雁荡山风景区 舟山普陀山风景区 浙江省景区 杭州西溪湿地旅游区，西湖 杭州淳安千岛湖风景区 湖州市南浔区南浔古镇景区 嘉兴南湖旅游区 嘉兴桐乡乌镇古镇旅游区 金华东阳横店影视城景区 7.3 6.7 8.6 8.4 5.45 12.6 11.7 7.25 13.65 13.5 6.6 5.5 13.1 12.05 12.1 11.4 13 11 5.05 4.67 7.33 6.67 0 4.9 4.9 0 7.3 6.6 8.75 6.65 6.05 7.3 0 5.75 7 6.6 5.75 0 8.1 11.4 5.05 11.2 4.67 8.75 6.17 7 8.1 0 7.9 9 10.1 11.6 7.33 6.65 5.65 10.7 11.85 5.75 7.9 0 8 11 10.04 13 14.05 12 11.25 0 13.05 宁波奉化溪口－滕10.25 12.05 6.67 6.05 头旅游景区 衢州市开化根宫佛国 绍兴市鲁迅故里－沈园景区 温州乐清市雁荡山风景区 11.3 10.7 8.6 8.4 5.5 8.1 9.45 11.25 6.6 12.6 13.65 9.1 6.17 5.65 5.75 9 6.7 7

舟山普陀山风景区 11.7 13.5 8.05 7.4 7 7.85 6.04 10.05 7.25 13.05 0

编写基于Hopfield网络的matlab语言的m文件[6]（具体程序请见附录一），输入上表数据，运行得出浙江省内的最优路线方案如下矩阵（程序结果vv矩阵的第2~12列）。

杭州西溪湿地旅游区，西湖 杭州淳安千岛湖风景区 嘉兴南湖旅游区

湖州市南浔区南浔古镇景区 嘉兴桐乡乌镇古镇旅游区 金华东阳横店影视城景区 衢州市开化根宫佛国

0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0

宁波奉化溪口－滕头旅游景区 0 0 0 0 0 0 0 1 0 0 0 绍兴市鲁迅故里－沈园景区 温州乐清市雁荡山风景区 舟山普陀山风景区

矩阵为一个换位矩阵，矩阵每一列仅有一个1，代表每次游览的城市。从第1列到第11列分别给出了依次游览的城市顺序。TSP问题将会回到起点，因此第11列的游览景区结束后将会回到第1列的游览景区。上表对应的游览景区顺序如下：

湖州市南浔区南浔古镇景区→嘉兴桐乡乌镇古镇旅游区→嘉兴南湖旅游区→杭州西溪湿地旅游区，西湖→绍兴市鲁迅故里－沈园景区→金华东阳横店影视城景区→舟山普陀山风景区→宁波奉化溪口－滕头旅游景区→温州乐清市雁荡山风景区→衢州市开化根宫佛国→杭州淳安千岛湖风景区→湖州市南浔区南浔古镇景区

在地图上标明各景区(黄色五角星)和游览路线(红色直线)后，如下图所示。由图可知整个游览过程在地图上基本成一个环装，说明游览过程是合理的。其中宁波奉化溪口－滕头旅游景区这一个景区似乎不太合理，但结合景区间的公路情况我们可以知道，从金华东阳横店影视城景区去往舟山普陀山风景区的公路是途径宁波奉化溪口－滕头旅游景区的，而舟山普陀山风景区前往温州乐清市雁荡山风景区也会途径宁波奉化溪口－滕头旅游景区，因此舟山普陀山风景区和宁波奉化溪口－滕头旅游景区的前后顺序不会增加游览的总时间。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库2015年全国研究生数学建模竞赛答案 - 图文(2)在线全文阅读。