《数学建模--运输问题》由会员分享，可在线阅读，更多相关《数学建模--运输问题（11页珍藏版）》请在金锄头文库上搜索。
1、.运输问题摘要本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo编程求解出最终结果。关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进展分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进展编程求解，运行得到结果：2-3-8-9-10总路程为85公里。关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用
2、最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：1-5-7-6-3-4-8-9-10-2；然后利用问题一的Floyd算法编程，能求得从客户2到客户1提货点的最短路线是：2-1，路程为50公里。即最短路线为：1-5-7-6-3-4-8-9-10-2-1。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进展编程求解，求解出的回路与Kruskal算法求出的回路一致。关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条
3、线路客户总需求量在50个单位以内即可。因此我们在问题二模型的根底上进展改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进展优化。得到优化结果为：第一辆车：1-5-2-3-4-8-9-1，第二辆车：1-7-6-9-10-1，总路程为280公里。关于问题四，在问题一的根底上我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进展求解可得到一种很理想的运输方案。根据matlab运行结果分析得出4条最优路线分别为：1-5-2，1-4-
4、3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。关键词： Floyd算法 Kruskal算法 整数规划 旅行商问题 一、问题重述*运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离单位公里用下面矩阵中的位置上的数表示其中表示两个客户之间无直接的路线到达。1、 运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送货，送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线假定上述矩阵中给出了所有可能的路线选择。2、 现运输公司派了一辆大的货车为这10个客户配送货物，假定这
5、辆货车一次能装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进展分析。3、 现因资源紧张，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小货车的容量为50个单位，每个客户所需要的货物量分别为8，13，6，9，7，15，10，5，12，9个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎样的路线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？对所设计的算法进展分析。4、 如果改用更小容量的车，每车容量为25个单位，但用车数量不限，每个客户所需要的货物量同第3问，并假设每出一辆车的出车
6、费为100元，运货的价格为1元/公里不考虑空车返回的费用，请问如何安排车辆才能使得运输公司运货的总费用最省？二、问题分析关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进展分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进展编程求解。关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是寻找一条最短的行车路线。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：；然后利用问题一的Fl
7、oyd算法和程序，能求得从客户2到客户1提货点的最短路线是：，路程为50公里。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文又根据路程最短建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进展编程求解。关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此我们在问题二模型的根底上进展改进，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进展优化。关于问题四，我们首先用Ma
8、tlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进展求解可得到一种很理想的运输方案。三、模型假设1.假设客户级别平等；2.假设不考虑装卸车费用；3.假设货车不发生意外事故；4.假设运输过程中货物无损失；四、符号说明不同的客户；从客户到客户的距离；总路程；五、模型的建立与求解问题一是要找出从客户2到客户10的最短路径，本文利用Floyd算法对此文进展求解。为计算方便，令网络的权矩阵为的距离。Floyd算法根本步骤为：1输入权矩阵。2计算 其中 3中元素就是到的最短路长。在本文计算中，对Floyd算法进展编程程序见附录1，利用Matl
9、ab软件进展求解。运行结果如下：a = 0 40 55 40 25 55 30 55 50 70 50 0 30 45 35 50 45 55 65 85 55 30 0 15 55 30 50 25 35 55 40 45 15 0 45 30 50 20 30 50 25 15 45 45 0 35 10 30 40 55 55 50 30 30 35 0 25 50 35 55 30 25 50 50 10 25 0 30 40 60 30 45 25 20 30 25 30 0 10 30 20 40 30 40 35 15 25 45 0 20 35 20 10 25 20 40 3
10、0 35 30 0path = 1 5 4 4 5 7 7 5 9 9 1 2 3 3 5 6 5 3 3 3 4 2 3 4 8 6 7 8 8 8 1 3 3 4 5 6 8 8 8 8 1 2 2 4 5 7 7 8 8 10 7 2 3 4 7 6 7 4 9 9 1 5 3 8 5 6 7 8 8 10 9 5 3 4 5 9 7 8 9 9 1 10 10 4 7 6 7 8 9 10 1 2 3 3 5 3 5 3 9 10请输入起点2请输入终点10 2 3 8 9 10由运行结果可以得出运货员从客户2到客户10的最短路径是：总路程为85公里。运输公司为这10个客户配送货物问题实
11、际上是寻找一条最短的行车路线。当不考虑送货员返回提货点的时候，本文利用最小生成树问题中的Kruskal算法结合题中所给的邻接矩阵，很快可以得到无回路的最短路线。Kruskal算法根本步骤：每步从未选的边中选取边，使它与已选边不够成圈，且是未选边中的最小权边，知道选够条边为止。利用最小生成树问题中的Kruskal算法结合题中所给的邻接矩阵，很快可以得到以下最小生成树：这两棵生成树不同之处就在于从客户6到达客户8的路径不一样，而实际路程经过计算后是一样的，路线的总行程为175公里。利用问题一的Floyd算法和程序，能求得从客户2到客户1提货点的最短路线是，路程为50公里。这样该回路，即最短的行车路
12、线为：行车路线总行程为225公里。以最小生成树法解决此问题速度快，结果较准确，但是只适合数目较少时，不适宜推广，因此本文又根据路程最短建立整数规划模型。为了更好的防止子巡回的产生，根据哈米尔顿回路，须附加一个约束条件：当访问客户i后必须要有一个即将访问确实切客户；访问客户j前必须要有一个刚刚访问过确实切客户。依次设立约束条件。利用Lingo求解模型局部结果附录2：Global optimal solution found. E*tended solver steps: 0 Total solver iterations: 86 Variable Value Reduced Cost由此可得，行程路线最短的回路：总路程为225公里。用两辆容量为50单位的小货车运货，在每个客户所需固定货物量的情况下，要使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内。此问与问题二有相似之处都要考虑回到提货点的情形,因此本文在模型2的根底上进展改进, 重新建立相应的整数线性规划模型。目标函数：利用Lingo求解模型局部结果附录3：Global optimal solution found. Objective value: 155.0000 Objective bound: 155.0000 E*tended solver steps:
