数学建模运输问题

-运输问题摘要本文主要研究的是货物运输的最短路径问题，利用图论中的Floyd算法、Kruskal算法，以及整数规划的方法建立相关问题的模型，通过matlab，lingo编程求解出最终结果。关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进展分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进展编程求解，运行得到结果：2-3-8-9-10总路程为85公里。关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是一个旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的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算法求出的回路一致。关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在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-3-8，1-7-6，1-9-10。最短总路线为245公里，最小总费用为645。关键词： Floyd算法 Kruskal算法 整数规划 旅行商问题 一、问题重述某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离单位公里用下面矩阵中的位置上的数表示其中表示两个客户之间无直接的路线到达。1、 运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送货，送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线假定上述矩阵中给出了所有可能的路线选择。2、 现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进展分析。3、 现因资源紧，运输公司没有大货车可以使用，改用两辆小的货车配送货物。每辆小货车的容量为50个单位，每个客户所需要的货物量分别为8，13，6，9，7，15，10，5，12，9个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎样的路线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？对所设计的算法进展分析。4、 如果改用更小容量的车，每车容量为25个单位，但用车数量不限，每个客户所需要的货物量同第3问，并假设每出一辆车的出车费为100元，运货的价格为1元/公里不考虑空车返回的费用，请问如何安排车辆才能使得运输公司运货的总费用最省？二、问题分析关于问题一，是一个两客户间最短路程的问题，因此本文利用Floyd算法对其进展分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然后，逐步分析出两客户间的最短距离；最后，利用Matlab软件对其进展编程求解。关于问题二，运输公司分别要对10个客户供货，必须访问每个客户，实际上是寻找一条最短的行车路线。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的Kruskal算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线：；然后利用问题一的Floyd算法和程序，能求得从客户2到客户1提货点的最短路线是：，路程为50公里。但考虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文又根据路程最短建立以路程最短为目标函数的整数规划模型；最后，利用LINGO软件对其进展编程求解。关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以即可。因此我们在问题二模型的根底上进展改良，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进展优化。关于问题四，我们首先用Matlab软件编程确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进展求解可得到一种很理想的运输方案。三、模型假设1.假设客户级别平等；2.假设不考虑装卸车费用；3.假设货车不发生意外事故；4.假设运输过程中货物无损失；四、符号说明不同的客户；从客户到客户的距离；总路程；五、模型的建立与求解5.1问题一模型的建立与求解5.1.1模型的建立问题一是要找出从客户2到客户10的最短路径，本文利用Floyd算法对此文进展求解。为计算方便，令网络的权矩阵为的距离。Floyd算法根本步骤为：1输入权矩阵。2计算 其中 3中元素就是到的最短路长。5.1.2模型的求解在本文计算中，对Floyd算法进展编程程序见附录1，利用Matlab软件进展求解。运行结果如下：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 30 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公里。5.2问题二模型的建立与求解5.2.1模型的建立运输公司为这10个客户配送货物问题实际上是寻找一条最短的行车路线。当不考虑送货员返回提货点的时候，本文利用最小生成树问题中的Kruskal算法结合题中所给的邻接矩阵，很快可以得到无回路的最短路线。Kruskal算法根本步骤：每步从未选的边中选取边，使它与已选边不够成圈，且是未选边中的最小权边，知道选够条边为止。利用最小生成树问题中的Kruskal算法结合题中所给的邻接矩阵，很快可以得到以下最小生成树：这两棵生成树不同之处就在于从客户6到达客户8的路径不一样，而实际路程经过计算后是一样的，路线的总行程为175公里。利用问题一的Floyd算法和程序，能求得从客户2到客户1提货点的最短路线是，路程为50公里。这样该回路，即最短的行车路线为：行车路线总行程为225公里。以最小生成树法解决此问题速度快，结果较准确，但是只适合数目较少时，不适宜推广，因此本文又根据路程最短建立整数规划模型。为了更好的防止子巡回的产生，根据哈米尔顿回路，须附加一个约束条件：当访问客户i后必须要有一个即将访问确实切客户；访问客户j前必须要有一个刚刚访问过确实切客户。依次设立约束条件。5.2.2模型的求解利用Lingo求解模型局部结果附录2：Global optimal solution found. Objective value: 225.0000 Objective bound: 225.0000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 86 Variable Value Reduced CostX( 1, 5) 1.000000 25.00000X( 2, 1) 1.000000 50.00000X( 3, 4) 1.000000 15.00000X( 4, 8) 1.000000 20.00000X( 5, 7) 1.000000 10.00000X( 6, 3) 1.000000 30.00000X( 7, 6) 1.000000 25.00000X( 8, 9) 1.000000 10.00000X( 9, 10) 1.000000 20.00000X( 10, 2) 1.000000 20.00000由此可得，行程路线最短的回路：总路程为225公里。5.3问题三模型的建立与求解5.3.1模型的建立用两辆容量为50单位的小货车运货，在每个客户所需固定货物量的情况下，要使得行程之和最短。这样只要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以。此问与问题二有相似之处都要考虑回到提货点的情形,因此本文在模型2的根底上进展改良, 重新建立相应的整数线性规划模型。目标函数：5.3.2模型的求解利用Lingo求解模型局部结果附录3：Global optimal solution found. Objective value: 155.0000 Objective bound: 155.0000 Infeasibilities: 0.2220446E-15 Extended solver steps: 0 Total solver iterations: 224Variable Value Reduced CostX( 1, 5) 1.000000 25.00000X( 2, 3) 1.000000 30.00000X( 3, 6) 1.000000 30.00000X( 5, 2) 1.000000 15.00000X( 6, 7) 1.000000 25.00000X( 7, 1) 1.000000 30.00000Global optimal solution found. Objective value: 135.0000 Objective bound: 135.0000 Infeasibilities: 0.2220446E-15 Extended solver steps: 0 Total solver iterations: 224Variable Value Reduced CostX( 1, 4) 1.000000 40.00000X( 4, 8) 1.000000 20.00000X( 5, 1) 1.000000 25.00000X( 8, 9) 1.000000 10.00000X( 9, 10) 1.000000 20.00000X( 10, 5) 1.000000 20.00000由此可得，两辆车的行车路线及路程：第一辆车：，包含的客户有2,3,6,7，运货总量为44，路程为155公里。第二辆车：，包含的客户有4,8，9,10,5运货总量为42单位，路程为135公里。总路程为290公里。5.3.3模型的优化对于模型求解出来的结果，本文利用Kruskal算法结合题中所给的邻接矩阵进展优化。从起始点处，进展分析，用两辆小的货车配送货物，为了尽可能的减少两辆车的重复路线，到、的路程最短，让两辆车分开运货，先根据货物承载量50的限制让其中的一辆车走完路程，再让另一辆车走剩余城市的最短路线，这样走出两条运货路线：第一种情况：第一辆车：，包含的客户有5,2,3,4,8，从模型1可解得，从回到的最短路线是，运货总量为40单位，路程为145公里。第二辆车：，包含的客户有7,6,9,10，运货总量为46，路程为135公里。这种情况下总路程为280公里。第二种情况：第一辆车：，包含的客户有7,6,3,4,8，从模型1可解得，从回到的最短路线是，运货总量为45单位，路程为150公里。第二辆车：，包含的客户5,2,9,10，运货总量为41单位，路程为160。这种情况下总路程为310公里。 对这两种情况比照，分析，可以看出第一种情况优于第二种情况。因此选择第一种情况的路线。5.4问题四模型的建立与求解题目要求我们运费最省，所以要考虑到需要的车最少，以及每辆车行驶的路程最短，而且还要保证送到每个客户手中。根据客户总需求量和货车的容量，所以，公司可派4辆货车去送货。在此，我们假设：从提货点1到各客户点最短路为从提货点1到各客户点的最短路程提货点1到各客户点路径客户所需要货物量的总和运用matlab程序见附录4可得：从中可以发现：，所以我们要继续对其进展分析：首先为了保证送到每个客户手里，所以必须走，那样就可以删除；然后考虑到货车的路程最短，所以要走，删除；最后，就只能走1-4-3-8路线。图1 四辆货车路线图经过计算可得下表：表1：4辆车的情况表每辆车的路线每辆车的路程每辆车所载的货物量1-5-240201-4-3-880201-7-655251-9-107021 所以，可得到目标函数：六、模型的评价与推广6.1模型的评价6.1.1模型的优点 1在整个模型的建立过程中，本文考虑的比拟全面客观，使模型具有较强的说服力，结果更合理。 2根据问题的特点，综合运用了多个软件，如lingo、matlab等等，使得在解决问题的过程中，更方便简单。6.1.2模型的缺点 这种寻路方法有其局限性，只适用于一些顶点较少的情况，顶点多，寻找起来较为麻烦。6.2模型的推广 模型的建立比拟客观，在现实中也可以广泛的应用，与现实情况严密相连；比方：最优路径问题与哈密顿回路问题，这些在现实中应用围已经很广了。七、参考文献1 胡运权，运筹学教程第四版，：清华大学，2012。2 朱道元，数学建模案例精选，：科学，2005。3 启源，金星。叶俊数学模型：高等教育出版杜，2004。I4 吴祈宗运筹学与最优化方法fM：机械工业，2003。附录附录1： clear;clc;M=10000;%不能直接到达是将距离赋值给Ma(1,:)=0,50,M,40,25,M,30,M,50,M;a(2,:)=50,0,30,M,35,50,M,60,M,M;a(3,:)=M,30,0,15,M,30,50,25,M,60;a(4,:)=40,M,15,0,45,30,55,20,40,65;a(5,:)=25,15,M,45,0,60,10,30,M,55;a(6,:)=M,50,30,30,60,0,25,55,35,M;a(7,:)=30,M,50,M,10,25,0,30,45,60;a(8,:)=M,60,25,20,30,55,30,0,10,M;a(9,:)=20,M,M,40,M,15,25,45,0,20;a(10,:)=35,20,10,45,20,M,60,M,30,0;%建立a矩阵path=zeros(length(a); %建立一个与矩阵a同大小的全零矩阵for i=1:10 for j=1:10 path(i,j)=j; %用path矩阵记录走过的点end end for k=1:10 for i=1:10 for j=1:10 if a(i,j)a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=path(i,k); % floyd算法 end end endenda, pathi1=input(请输入起点);i2=input(请输入终点); disp(i1); while i1=i2 i1=path(i1,i2);disp(i1); end;附录2：MODEL:SETS: CUSTOMERS / 1. 10/: U; LINK( CUSTOMERS, CUSTOMERS): DIST,X; ENDSETSDATA: DIST = 0 50 100000 40 25 100000 30 100000 50 100000 50 0 30 100000 35 50 100000 60 10000 100000 100000 30 0 15 100000 30 50 25 100000 60 40 10000 15 0 45 30 55 20 40 65 25 15 100000 45 0 60 10 30 100000 55 100000 50 30 30 60 0 25 55 35 1000000 30 100000 50 100000 10 25 0 30 45 60 100000 60 25 20 30 55 30 0 10 100000 20 100000 100000 40 100000 15 25 45 0 20 35 20 10 45 20 100000 60 100000 30 0;ENDDATA N = SIZE( CUSTOMERS);MIN = SUM( LINK: DIST * X);FOR( CUSTOMERS( K):SUM( CUSTOMERS( I)| I #NE# K: X( I, K) = 1;SUM( CUSTOMERS( J)| J #NE# K: X( K, J) = 1;FOR( CUSTOMERS( J)| J #GT# 1 #AND# J #NE# K: U( J) = U( K) + X ( K, J) - ( N - 2) * ( 1 - X( K, J) + ( N - 3) * X( J, K) ); );FOR( LINK: BIN( X);FOR( CUSTOMERS( K)| K #GT# 1: U( K) = 1 + ( N - 2) * X( K, 1) );END Global optimal solution found. Objective value: 225.0000 Objective bound: 225.0000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 86 Variable Value Reduced Cost N 10.00000 0.000000 U( 1) 0.000000 0.000000 U( 2) 9.000000 0.000000 U( 3) 4.000000 0.000000 U( 4) 5.000000 0.000000 U( 5) 1.000000 0.000000 U( 6) 3.000000 0.000000 U( 7) 2.000000 0.000000 U( 8) 6.000000 0.000000 U( 9) 7.000000 0.000000 U( 10) 8.000000 0.000000 DIST( 1, 1) 0.000000 0.000000 DIST( 1, 2) 50.00000 0.000000 DIST( 1, 3) 100000.0 0.000000 DIST( 1, 4) 40.00000 0.000000 DIST( 1, 5) 25.00000 0.000000 DIST( 1, 6) 100000.0 0.000000 DIST( 1, 7) 30.00000 0.000000 DIST( 1, 8) 100000.0 0.000000 DIST( 1, 9) 50.00000 0.000000 DIST( 1, 10) 100000.0 0.000000 DIST( 2, 1) 50.00000 0.000000 DIST( 2, 2) 0.000000 0.000000 DIST( 2, 3) 30.00000 0.000000 DIST( 2, 4) 100000.0 0.000000 DIST( 2, 5) 35.00000 0.000000 DIST( 2, 6) 50.00000 0.000000 DIST( 2, 7) 100000.0 0.000000 DIST( 2, 8) 60.00000 0.000000 DIST( 2, 9) 10000.00 0.000000 DIST( 2, 10) 100000.0 0.000000 DIST( 3, 1) 100000.0 0.000000 DIST( 3, 2) 30.00000 0.000000 DIST( 3, 3) 0.000000 0.000000 DIST( 3, 4) 15.00000 0.000000 DIST( 3, 5) 100000.0 0.000000 DIST( 3, 6) 30.00000 0.000000 DIST( 3, 7) 50.00000 0.000000 DIST( 3, 8) 25.00000 0.000000 DIST( 3, 9) 100000.0 0.000000 DIST( 3, 10) 60.00000 0.000000 DIST( 4, 1) 40.00000 0.000000 DIST( 4, 2) 10000.00 0.000000 DIST( 4, 3) 15.00000 0.000000 DIST( 4, 4) 0.000000 0.000000 DIST( 4, 5) 45.00000 0.000000 DIST( 4, 6) 30.00000 0.000000 DIST( 4, 7) 55.00000 0.000000 DIST( 4, 8) 20.00000 0.000000 DIST( 4, 9) 40.00000 0.000000 DIST( 4, 10) 65.00000 0.000000 DIST( 5, 1) 25.00000 0.000000 DIST( 5, 2) 15.00000 0.000000 DIST( 5, 3) 100000.0 0.000000 DIST( 5, 4) 45.00000 0.000000 DIST( 5, 5) 0.000000 0.000000 DIST( 5, 6) 60.00000 0.000000 DIST( 5, 7) 10.00000 0.000000 DIST( 5, 8) 30.00000 0.000000 DIST( 5, 9) 100000.0 0.000000 DIST( 5, 10) 55.00000 0.000000 DIST( 6, 1) 100000.0 0.000000 DIST( 6, 2) 50.00000 0.000000 DIST( 6, 3) 30.00000 0.000000 DIST( 6, 4) 30.00000 0.000000 DIST( 6, 5) 60.00000 0.000000 DIST( 6, 6) 0.000000 0.000000 DIST( 6, 7) 25.00000 0.000000 DIST( 6, 8) 55.00000 0.000000 DIST( 6, 9) 35.00000 0.000000 DIST( 6, 10) 1000000. 0.000000 DIST( 7, 1) 30.00000 0.000000 DIST( 7, 2) 100000.0 0.000000 DIST( 7, 3) 50.00000 0.000000 DIST( 7, 4) 100000.0 0.000000 DIST( 7, 5) 10.00000 0.000000 DIST( 7, 6) 25.00000 0.000000 DIST( 7, 7) 0.000000 0.000000 DIST( 7, 8) 30.00000 0.000000 DIST( 7, 9) 45.00000 0.000000 DIST( 7, 10) 60.00000 0.000000 DIST( 8, 1) 100000.0 0.000000 DIST( 8, 2) 60.00000 0.000000 DIST( 8, 3) 25.00000 0.000000 DIST( 8, 4) 20.00000 0.000000 DIST( 8, 5) 30.00000 0.000000 DIST( 8, 6) 55.00000 0.000000 DIST( 8, 7) 30.00000 0.000000 DIST( 8, 8) 0.000000 0.000000 DIST( 8, 9) 10.00000 0.000000 DIST( 8, 10) 100000.0 0.000000 DIST( 9, 1) 20.00000 0.000000 DIST( 9, 2) 100000.0 0.000000 DIST( 9, 3) 100000.0 0.000000 DIST( 9, 4) 40.00000 0.000000 DIST( 9, 5) 100000.0 0.000000 DIST( 9, 6) 15.00000 0.000000 DIST( 9, 7) 25.00000 0.000000 DIST( 9, 8) 45.00000 0.000000 DIST( 9, 9) 0.000000 0.000000 DIST( 9, 10) 20.00000 0.000000 DIST( 10, 1) 35.00000 0.000000 DIST( 10, 2) 20.00000 0.000000 DIST( 10, 3) 10.00000 0.000000 DIST( 10, 4) 45.00000 0.000000 DIST( 10, 5) 20.00000 0.000000 DIST( 10, 6) 100000.0 0.000000 DIST( 10, 7) 60.00000 0.000000 DIST( 10, 8) 100000.0 0.000000 DIST( 10, 9) 30.00000 0.000000 DIST( 10, 10) 0.000000 0.000000 X( 1, 1) 0.000000 0.000000 X( 1, 2) 0.000000 50.00000 X( 1, 3) 0.000000 100000.0 X( 1, 4) 0.000000 40.00000 X( 1, 5) 1.000000 25.00000 X( 1, 6) 0.000000 100000.0 X( 1, 7) 0.000000 30.00000 X( 1, 8) 0.000000 100000.0 X( 1, 9) 0.000000 50.00000 X( 1, 10) 0.000000 100000.0 X( 2, 1) 1.000000 50.00000 X( 2, 2) 0.000000 0.000000 X( 2, 3) 0.000000 30.00000 X( 2, 4) 0.000000 100000.0 X( 2, 5) 0.000000 35.00000 X( 2, 6) 0.000000 50.00000 X( 2, 7) 0.000000 100000.0 X( 2, 8) 0.000000 60.00000 X( 2, 9) 0.000000 10000.00 X( 2, 10) 0.000000 100000.0 X( 3, 1) 0.000000 100000.0 X( 3, 2) 0.000000 30.00000 X( 3, 3) 0.000000 0.000000 X( 3, 4) 1.000000 15.00000 X( 3, 5) 0.000000