最短路径最少费用数学建模论文

最短路径最少费用数学建模论文PAGEPAGE1摘要现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，即高质量高速度的完成送货任务，针对本案例，我们采用了大量的科学分析方法，并进行了反复验证，得出如下结果：问题1：根据所给问题与数据，我们将题目中给出的城市，及其之间的线路可看成一个赋权连通简单无向图，采用了求这个图最小生成树的办法，求出最优线路.在此基础上，我们通过观察分析计算对上述结果进行修正，然后我们再采用穷举法对问题结果进行验证，结果相吻合。最终得到如下路线：北京香港湖南海南广西重庆河南云南西藏新疆青海甘肃宁夏江苏福建上海台湾上海黑龙江内蒙古黑龙江吉林北京。（最短时间为61小时）问题2：由于题中有货物重量与体积限制，货机一次最多只能载50件产品，考虑19个城市的总需求为114，这就估算出至少需要返回2次，采用逆向求解的方法，相当于3架货机同时送货，要设计线路使总共花费的时间最短，尽量使送货任务均衡，最大限度不超过50件货物，最后得出结果为：北京吉林黑龙江内蒙古新疆西藏云南河南北京重庆广西海南湖南香港北京重庆青海甘肃宁夏江苏福建上海台湾上海北京。（总的时间为71.77777）（其中红色表示只路过不送货）问题3：要求问题1，2的花费最少，只需对前两个模型做进一步优化即可，经过优化计算我们得到如下结果：问题1的最少花费为584250（元），路线如下：北京香港湖南海南广西重庆河南云南西藏新疆青海甘肃宁夏江苏福建上海台湾上海黑龙江内蒙古黑龙江吉林北京问题2的最少花费为711750（元），线路如下：北京吉林黑龙江内蒙古新疆西藏云南河南北京重庆广西海南湖南香港北京重庆青海甘肃宁夏江苏福建上海台湾上海北京。关键词：关键字：最短路径送货线路优化赋权连通简单无向图Excel最小生成树§1问题的重述一、问题背景现今社会网络越来越普及，网购已成为一种常见的消费方式，随之物流行业也渐渐兴盛，每个工厂为了自身的发展需要以最快的速度及时将产品送达所需单位，现有实业公司，该实业公司专业生产某专用设备产品，专用设备产品每件重达5吨（其长5米，宽4米，高6米），该实业公司库房设在北京，所有货物均由一货机送货，该机种飞机翼展88.40米（机身可用宽20米），机长84米（可用长50米），机高18.2米（可用14米），最多可装载250吨货物，起飞全重达600吨，平均速度为900停靠费用=5000元×该省市的消费指数.二、相关数据1、各个城市间的通路和权数1、上图1描述了中国各个省市之间的航班以及权重以图中标注为准；A6A17，A7A16，A8A18，A8A19，A9A10，A9A14，A9A18，A9A19，A13A15，A138、W：V中点之间的权（2）的集合，则G=（V，E，W）表示赋权连通简单无向图9、M：V中点之间的权（3）的集合，则F=（V，E，M）表示赋权连通简单无向图10、G（V，E）：赋权连通图；11、Gi：G（V，E）的第i个子图；12、Li：为子图Gi中的最佳回路；13、：为边e的权；14、：为点的点权；15、：的各边的大小；§5模型的建立与求解依据问题的要求及相关假设，建立相应的模型并进行求解：一、问题一的模型建立与求解1、模型Ⅰ最小生成树模型根据题目意思，两城市之间的时间=权（1）*100/速度+2（单位：小时）例如北京到新疆A1A5权（1）是4.5555556表3线路权（1）权（2）（时间）线路权（1）权（2）（时间）A1A5234.5555556A5A1282.888888889A1A6214.3333333A5A14204.222222222A1A1082.8888889A5A15224.444444444A1A13204.2222222A6A732.333333333A1A15123.3333333A6A1722.222222222A1A17244.6666667A7A1622.222222222A1A1993A8A1842.444444444A2A562.6666667A8A1932.333333333A2A1382.8888889A9A1022.222222222A2A1142.4444444A9A14113.222222222A3A1122.2222222A9A18153.666666667A3A18103.1111111A9A19173.888888889A4A5113.2222222A13A15123.333333333A4A12123.3333333A13A1672.777777778A4A15153.6666667A19A2042.444444444定义V为A1，A2，A3，A4，A5，A6，A7，A8，A9，A10，A11，A12，A13，A14，A15，A16，A17，A18，A19，A20的集合，定义E为A1A5，A1A6，A1A10，A1A13，A1A15，A1A17，A1A19，A2A5，A2A11，A2A13，A3A11，A3A18，A4A5，A4A12，A4A15，A5A12，A5A14，A5A15，A6A7，A6A17，A7A16，A8A18，A8A19，A9A10，A9A14，A9A18，A2、模型I求解根据最小生成树的求法可以求出改图G的最小生成树如图2沿着最小生成树的路线相对较短，为：A1—A19—A20—A19—A8—A18—A3—A11—A2—A5—A12—A5—A4—A5—A2—A13—A16—A7—A6—A17—A15—A1—A10—A9—A14—A9—A10—A1经过观察上面下划线的部分并A5—A12—A5—A4—A5—A2—A13—A16不是最短的，经计算这个路线A5—A12—A4—A15—A13—A16比上一段的要短，故用它替换上一段，这里经过了A15，那从A17可直接到A1，不用再经过A15，故A7—A6—A17—A15—A1这段可用A7—A6—A17—A1来替换，A1—A19—A20—A19—A8—A18—A3—A11—A2—A5—A12—A4—A15—A13—A16—A7—A6—A17—A1—A10—A9—A14—A9—A10—A1，由于这条路径最后一段，A20，和A9都重走了，故可对路径进行重组，依据线路最短和经过两次的城市最少的原则，经过综合分析，得出最优的路径为A1—A17—A6—A7—A16—A13—A15—A4—A12—A5—A2—A11—A3—A18—A8—A19—A20—A19—A9—A14—A9—A10—A1。可以将相邻两点的权（2）相加，和为总时间，经过计算上述线路所花时间是61小时，为最短时间.二、问题二的模型建立与求解1、建立模型把各个城市间的航线示意图抽象为一赋权连通图，在权图G中，对应的示意图中各个货物需求地，表示北京，对应图中的航线，边权对应示意图中的航线长。建立的数学模型如下：，，，，求G中回路，使得满足：（1）；（2）；（3）=min（目标为总距离最短）；或=min（目标为飞行所用时间最少）。2、模型求解由分析得此货机至少要回去取货二次，相当于把图G分成三个子图，在每个子图中寻找最佳回路。因为最小生成树包括图G中的所有顶点，而且最小树的边权是相邻两点之间是的距离，它描述顶点之间的相近程度，故可利用最小生成树进行初步分块。根据最小生成树求解Kruskal算法，找到图的最小生成树如下图3：

现要对已经得到的最小生成树进行分解，以获得三个子图G，使得分解的每一组的各个城市需求和不超过50件货物，并且尽量使每一组的线路最短。从而根据最小生成树的分解方法把图G（V，E）划分为三个子图，分别在中寻找最佳航线。依据寻找最优回路的有效优化规则：扩环策略、增环策略、换枝策略，寻找最优的分块结果，在，中分别寻找一条从北京出发，遍历V并回到北京的最短路线。在G（V，E）中求三条从北京O出发并回到北京O的路，依据的步骤如下，做出G和O之间的最短路；以O与G连通的路径及原图G的最优树在中保留的边为基础，进行增环扩环调整，使最后尽可能形成一个环路。三条环路如下图4所示：线路如下：北京吉林黑龙江内蒙古新疆西藏云南河南北京(时间为88/9+8*2=25.777778)北京重庆广西海南湖南香港北京(时间58/9+6*2=18.444444)北京重庆青海甘肃宁夏江苏福建上海台湾上海北京。(时间68/9+10*2=27.555556)总的时间为25.777778+18.444444+27.555556=71.77777三、问题三的模型建立与求解根据题目和假设，假设两城市之间运输的价格=权（1）*2500+平均指数*5000（单位：价格）北京到新疆A1A5权（1）是23，北京的指数为1.9，上海为1.2，则先求出平均指数（1.9+1.2）/2=1.5北京到新疆A1A5关于时间的运输价格的权为23*2500+1.55*5000=65250（小时），其他各城市间的权（3）表4线路权（1）平均消费指数权（3）（价格）线路权（1）平均消费指数权（3）（价格）A1A5231.5565250A5A1281.125500A1A6211.6560750A5A14201.256000A1A1081.5527750A5A15221.2561250A1A13201.758500A6A731.5515250A1A15121.638000A6A1721.613000A1A17241.8569250A7A1621.4512250A1A1991.8531750A8A1841.5517750A2A561.1520750A8A1931.716000A2A1381.326500A9A1021.2511250A2A1141.216000A9A14111.2533750A3A1121.17510875A9A18151.444500A3A18101.27531375A9A19171.5550250A4A5111.2533750A13A15121.437000A4A12121.1535750A13A1671.3524250A4A15151.344000A19A2041.8519250针对问题一根据最小生成树的求法根据权（3）求出改图G的最小生成树如图5所示：沿着最小生成树的路线相对较短，为：A1—A19—A20—A19—A8—A18—A3—A11—A2—A5—A12—A5—A4—A5—A2—A13—A16—A7—A6—A17—A15—A1—A10—A9—A14—A9—A10—A1经过观察上面下划线的部分并A5—A12—A5—A4—A5—A2—A13—A16不是最短的，经计算这个路线A5—A12—A4—A15—A13—A16比上一段的要短，故用它替换上一段，这里经过了A15，那从A17可直接到A1，不用再经过A15，故A7—A6—A17—A15—A1这段可用A7—A6—A17—A1来替换，A1—A19—A20—A19—A8—A18—A3—A11—A2—A5—A12—A4—A15—A13—A16—A7—A6—A17—A1—A10—A9—A14—A9—A10—A1，由于这条路径最后一段，A20，和A9都重走了，故可对路径进行重组，依据线路最短和经过两次的城市最少的原则，经过综合分析，得出最优的路径为A1—A17—A6—A7—A16—A13—A15—A4—A12—A5—A2—A11—A3—A18—A8—A19—A20—A19—A9—A14—A9—A10—A1。可以将相邻两点的权（3）相加，和为总花费，最少为584250元。针对问题二把各个城市间的航线示意图抽象为一赋权连通图，在权图G中，对应的示意图中各个货物需求地，表示北京，对应图中的航线，边权对应示意图中的航线长，将航线长及在各个城市停留的时间都转化相应的花费即权（3）。建立的数学模型如下：，，，，求G中回路，使得满足：（1）；（2）；（3）=min（目标为总花费最少）；或=min（目标为飞行总的花费最少）。2、模型求解由分析得此货机至少要回去取货二次，相当于把图G分成三个子图，在每个子图中寻找最佳回路。现要对已经得到的最小生成树进行分解，以获得三个子图G，使得分解的每一组的各个城市需求和不超过50件货物，并且尽量使每一组的线路最短。从而根据最小生成树的分解方法把图G（V，E）划分为三个子图，分别在中寻找最佳航线。依据寻找最优回路的有效优化规则：扩环策略、增环策略、换枝策略，寻找最优的分块结果，在，中分别寻找一条从北京出发，遍历V并回到北京的最短路线。在G（V，E）中求三条从北京O出发并回到北京O的路，依据的步骤如下，做出G和O之间的最短路；以O与G连通的路径及原图G的最优树在中保留的边为基础，进行增环扩环调整，使最后尽可能形成一个环路。线路如下：北京吉林黑龙江内蒙古新疆西藏云南河南北京重庆广西海南湖南香港北京重庆青海甘肃宁夏江苏福建上海台湾上海北京。总的费用为711750（元）§7模型的评价与推广一、模型的优缺点1、优点：〔1〕.本文的三个问题，给出了在各种约束条件下的最短时间以及最少花费的计算方法，具有较强的实用性和通用性，可用于日常生活中；〔2〕.在忽略其他条件限制的最短时间问题中，我们采用最小生成树方法进行求解，并用了枚举法进行验证，经过大量的计算使结果更准确，更符合实际情况，从而达到解决实际问题的目的；〔3〕.采用枚举法对问题结果进行验证，使计算结果更加准确，更符合实际；〔4〕.对于加入了省辖市需求量的问题当中，我们在第一问的基础上，计算出北京到各个城市间的最短距离，并再次利用最小生成树的方法，进行计算验证得出结果，解决实际问题。〔5〕.在本题目的最后一问当中，给出了计算在货物体积和重量等多个限制条件下的最优化解法，采用最小生成树算法解决了这个与实际问题非常接近的问题，具有很好的实际意义。2、缺点：〔1〕.本题中为使问题便于研究，我们做了许多假设，这或许对模型的实际意义产生影响；〔2〕.本问题并非线性优化问题，加之节点过多，需要到量的精密计算，多次重复因此很难做到求出的结果就是最优解，只是相对较优的结果；〔3〕.本为题所建立的模型，本省舍弃了某些因素的影响的结果，但会使所求结果与实际生活产生偏差。七．模型的推广本文依据所研究的问题建立了三个模型，这三种模型对于许多数学问题的解决方法和途径都有一定的帮助。第一问中利用最小生成树的方法来解决的，此种优化方法可用来指导现实生活中所遇到的许多问题，如：旅游最短线路问题、货物运送问题、邮递问题以及管道输水等等一些实际问题。求解这些问题可以参考最小生成树方法，再利用枚举法经过大量的计算可得出非常接近最优解。第二问中是加入了限制条件的运货最优问题，利用赋权连通图，并根据寻找最优回路的有效优化规则：扩环策略、增环策略、换枝策略，寻找到最优的分块，再利用最小生成树方法求解在有需求量约束的前提下最短线路的模型，然后综合比较得出符合要求的较优的线路。在日常生活中，可以利用该模型来求解与最优树和最大流量有关的实际问题。在第一问和第二问的基础上所延伸出来的第三个问题也可以采用该算法解决实际问题。这类问题在实际生活中随处可看见，且都可以应用这些模型进行解决。在将实际问题抽象为具体数学问题的时候，根据数学建模的思想以及步骤，会做出一定的假设，因此会导致一定的误差，因此不同的实际问题，要根据具体情况认真考虑，得出最优的设计方案，对于解决实际问题具有很重要的意义参考文献[1]李庆扬，关治，白峰衫.数值计算原理.北京：清华大学出版社,2000；[2]刘来福，曾文艺.数学模型与数学建模（第二版）.北京：北京师范大学出版社，2002；[3]蔡锁章.数学建模原理与方法.北京：海洋出版社，2000；[4]王勇，池洁，物流配送路线及配送时间的优化分析2010-6-4；[5]吴群妹，实际配送中多个配送点闭回路最短路径的选取，2010-6-4；[6]郭亚军,综合评价理论与方法[M].北京：科学出版社,2002；[7]池洁，李莉，物流中配送区域与配送路线的网络优化法，2010-6-4；源程序