【精品】22组A题论文

《【精品】22组A题论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、旅游中国摘要本文研究A题中在考虑省钱省时等因素条件下如何走遍中国大陆省会城市、直辖市及否港、澳门、台北，总共34个城市，并建立数学模型，制定出最佳的旅行方案。对于问题1,首先通过查阅资料得到地球的半径和经纬度，通过MATLAB⑴算出两地之间的实际距离。然后将省会之间的距离看成权值，把问题转化为求解图论中的旅行售货员⑵问题，用LINGO⑶解出其最短路程为1579.2km,最佳旅行路线为：西安一郑州一石家庄一太原一呼和浩特一哈尔滨一长春一沈阳一北京->天津济南合肥->南京->上海杭州台北->福州南昌武汉长沙->广州香港—澳门

2、海口南宁昆明〜贵阳〜重庆—成都〜拉萨—乌鲁木齐—西宁一兰州一银川一西安。对于问题2,首先我们通过查询资料得出全国所有省会Z间的火车、动车以及飞机票价，由于在三种出行方式（硬卧、动车、飞机）屮，硬卧比其它两种出行方式的花费小，所以我们选择换卧作为首要考虑的出行方式。其次，在实际屮两地之间存在没有直达列车的情况，在求解过程屮选择FOLYD算法得到最佳转车方案。然后利用问题一的混合整数线性规划模型中的LINGO程序进行求解，得到最小花费为:10108.00元，相应的最佳旅行路线为：西安一拉萨一西宁一兰州一银川->呼和浩特一北京

3、一沈阳一长春一哈尔滨一天津一济南一南京->合肥—南吕一福州f杭州f上海〜澳门f台北f香港一广州f海口f长沙f南宁f昆明f贵阳f成都f重庆f乌鲁木齐f重庆f武汉f广州f右家庄f太原f西安。对于问题3,木题要求我们综合考虑省钱省时和方便。在问题二省钱的基础上考虑省时问题，由此建立多H标规划模型，给出省钱和省时的均衡度，统一对火车快车、动车、飞机的票价矩阵以及所对应的时间矩阵进行标准化，分别乘以7组权重系数并求和，得到在7组权重系数下三种出行方式所对应的“方便系数”矩阵，对其进行最优化处理得到最小“方便系数”矩阵，最后然后利用

4、问题一的混合整数线性规划模型中的LINGO程序进行求解得到7组权重系数下的最佳旅行路线。模型所用的LINGO程序在求解时采用的是分枝定界法，数据量（城市数冃）小丁•20时，所耗费时间（运算次数）与变量数呈多项式分布；当数据量（城市数目）大于20时，所耗费时间（运算次数）与变量数呈指数分布。我们在求解时最多耗时为25分36秒，分枝数为87817,对于本题34个变量算法基本可行。关键词：旅行售货员LINGO最短路线多冃标规划1问题重述西安秦先生准备到中国所有的省会城市直辖市以及港澳台旅游，请你为他设计出行方案:1.按照地理位

5、置（经纬度）设计出行方案。2.如果2011年9月1日秦先生从西安市出发，每个城市停留3天，可选择航空、铁路（快车卧铺、动车），设计最经济的旅行互联网上订票方案。3.要综合考虑省钱、省时乂方便，设定你的评价准则，建立数学模型，修订你的方案。4.对你的算法作复杂性、可行性及误差分析。5.关于旅行薛问题提出对你自己所采用的算法的理解及评价。2模型假设1.假设两城市之间的距离可以用两点之间的直线距离来表示。2•假设在旅行过程屮所坐交通T具会准时出发准时到达。3.假设在旅行途中所用交通工具的票价在旅途中稳定不变。4.假设地球是一个

6、均匀的球体，计算得两点之间的具体距离可靠。3符号说明X,从第i城市到下一城市j5第i城市到下一城市j的路程Z总路程pk.pd.pf分别表示标准化过的火车快车，动车，飞机票价矩阵tk.td.tf分別表示乘坐火车快车，动车，飞机到达34个城市中任意两个城市之间所需时间4问题分析4.1问题1的分析本题从西安出发用坐火车、飞机和动车的方式走遍大陆，要求在旅行过程中必须经过每一个省会城市，且走过的路程最短。将所给城市的经纬度转换成为一个坐标，由此可以把每一个城市看作一个点，将城市之间的距离看作权值，所给问题就转化为一个图论问题，即

7、从给定点西安出发走遍图上每一・个点后又冋到西安，在这过程中所走距离最短。4.2问题二的分析本题中要求设计岀走遍全国省会城训所需最经济的互联网订票方案，即求花费最小的订票方案。首先，对比于上题的最短路径问题我们发现两者有相似之处，因此我们将两地之间的花费等价于两地之间的路程，然后只需要求得从给定点西安出发，走遍图上每一点后又冋到西安，在这过程中所用的最短路程，即可求出旅行所需最小花费。由此用问题一相同的方法，将全国省会城市看作一点，将两点之间所需花费看作权，把问题乂转化为一个图论问题。其本质还是一个最佳推销员问题。其次，与

8、第一问题不相同的是，第一问题屮，通过经纬度我们可以得到所有线路的完全图，而此问题屮，通过互联网我们得到全国省会城市有的有直达火车,有的却没有，所以全国各省会之间构成的就不是一个完全图（见附表4）。凶•匕，采用FLOYD算法得到城市之间的完全图（见附表5）。4.3问题三的分析本题中需要设计一个走遍全国省时、省钱又方便的