《2010东北三省数学建模》由会员分享，可在线阅读，更多相关《2010东北三省数学建模（33页珍藏版）》请在金锄头文库上搜索。
1、2010东北三省数学建模 B题：走遍全中国,周游先生退休后想到各地旅游。计划走遍全国的省会城市、直辖市、香港、澳门、台北。请你为他按下面要求制定出行方案： 1按地理位置（经纬度）设计最短路旅行方案； 2如果2010年5月1日周先生从哈尔滨市出发，每个城市停留3天，可选择航空、铁路（快车卧铺或动车），设计最经济的旅行互联网上订票方案； 3 要综合考虑省钱、省时又方便，设定你的评价准则，建立数学模型，修订你的方案； 4对你的算法作复杂性、可行性及误差分析； 5关于旅行商问题提出对你自己所采用的算法的理解及评价。,针对最短路问题的分析,蒙特卡罗算法：随机性模拟算法 通过仿真来实现检验模型的正确性 图
2、论：解决优化问题（lindo 和 lingo）实现最短路 连续离散化的方法：将连续的数据离散化 计算机只认离散数据 离散化后进行差分代替微分 求和代替积分 最优化理论三大非经典算法,非对称的旅行商问题，因为我们知道旅行商问题解决的是对称距离下所求的最短路径问题，但是要知道考虑到现实的综合后不可能每一个路程都是对称的，而非对称的旅行商问题恰好能够解决这样的问题。与此同时我们运用节约算法这样大大方便的解决了我们需要讨论的问题。,最终我们运用模拟退火原理获得旅行商路径优化问题的全局最优解。目的想要达到在空间上，即两点之间的最短距离求出那个路径是最短的。但是这个只是不考虑其他一切因素，只单纯考虑地是平
3、的。可是虽然满足了最短的距离但是花费并没有考虑在内，即忽略所有其他因素。,模拟退火算法（ Metropolis 准则）,假设在原始状态时，系统受到某种扰动而使其状态变为新状态，由此对应，系统的能量也从原始能量改变为新能量，系统由原始状态变为新状态的接受概率：,物理退火过程和模拟退火算法的 相似关系,针对TSP问题我们来了解一下具体的模拟退火算法原理过程：,对于上述旅行商问题（s,j） , 用模拟退火算法求解其基本步骤如下 步骤一：,步骤二、三、四,在模拟退火过程中,给定温度下状态(解)的转移可以视为是一个马尔可夫链。,最短路径,针对最经济模型的分析,周游先生退休后想到各地旅游，计划从哈尔滨出发
4、，走遍全国的省会城市、直辖市、香港、澳门、台北， 然后再回到他的出发地。各城镇之间的旅程票价是已知的, 应安排其旅行路线, 才能使他经过每个城市恰好一次, 且使总的旅行花费的路费最少。,最省钱的路径,旅网的拓扑结构指的是组成网络的基本单元之间的相互连接关系，网络的衔接结构包括任何一个基本单元和其他基本单元之间的关系和整个网络之间的关系所呈现的路线特性。 旅游低碳是指旅行商在综合考虑省钱、省时因素，所最终达到让旅行商满意的状态。该项指标对于整个旅网线路的选择有着较大的意义。 旅游网络领域内很多是解决最短路的问题，对低碳的研究还处于表面阶段。该模型提出旅网拓扑低碳评价准则，利用该准则界定旅网中的关
5、键线路，与此该准则也可以评价整个网络的低碳评价准则。,该指标是在通信网络领域提出的，由于它基于网络拓扑结构（节点和节点之间的连线关系）进行解决问题，且在不同网络之间具有可比性，满足旅网拓扑低碳评价准则的要求，该准则作为旅网低碳标准分析的基础。划分区域的方法进行求解：华东地区，华北地区，西南地区，西北地区，华南地区，华中地区，东北地区，台北地区。,全国路网关键路线图,在一定层次考虑权重，得出各个地区的关键性路段是： （1）西宁-兰州-银川（2）南宁-广州-澳门-香港 （3）贵阳-重庆-昆明-成都（4）北京-天津-石家庄-太原 （5）济南-合肥-南昌-福州 （6）哈尔滨-长春-沈阳,而得出了这些关键性路段后，针对实际情况，进而推导出一条较优的路线，而这条路线就是我们解决周游先生问题的优化答案。 这条较优路线是： 哈尔滨长春沈阳北京天津石家庄太原济南合肥南昌福州台北福州杭州上海南京武汉长沙香港澳门广州南宁海口昆明贵阳重庆成都拉萨兰州乌鲁木齐兰州西宁银川西安郑州呼和浩特哈尔滨总计走行： =210 小时32分乘坐交通工具的花费为： =11165 元人民币最优路径图,
