数学建模--运输问题

运输 摘要 问题 本文主要研究的是货物运输的最短路径问题，利用图论中的 Floyd 算法、Kruskal 算法，以及整数规划的方法建立相关问题的模型，通过 matlab，lingo 编程求解出最终 结果。 关于问题一，是一个两客户间最短路程的问题，因此本文利用 Floyd 算法对其进行 分析。考虑到计算的方便性，首先，我们将两客户之间的距离输入到网络权矩阵中；然 后，逐步分析出两客户间的最短距离；最后，利用Matlab 软件对其进行编程求解，运行 得到结果2-3-8-9-10 总路程为 85 公里。 关于问题二，运输公司分别要对10 个客户供货，必须访问每个客户，实际上是一个 旅行商问题。首先，不考虑送货员返回提货点的情形，本文利用最小生成树问题中的 Kruskal 算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线-9-10-2；然 后利用问题一的 Floyd 算法编程， 能求得从客户 2 到客户 1 （提货点） 的最短路线是 2-1， 路程为 50 公里。即最短路线为-9-10-2-1。但考虑到最小生成树法局限于顶点数较少 的情形，不宜进一步推广，因此本文建立以路程最短为目标函数的整数规划模型；最后， 利用 LINGO 软件对其进行编程求解，求解出的回路与 Kruskal 算法求出的回路一致。 关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只 要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此 我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并 设计一个简单的寻路算法，对于模型求解出来的结果，本文利用 Kruskal算法结合题中所 给的邻接矩阵进行优化。得到优化结果为第一辆车-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个客户的路线距离（单位公里）用下面矩阵中的i, j i, j 1,,10位置上的数 表示（其中表示两个客户之间无直接的路线到达） 。 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 算法，结合题中所给的邻接矩阵，很快可以得到回路的最短路线 v 1  v 5  v 7  v 6  v 3  v 4  v 8  v 9  v 10  v 2 ；然后利用问题一的 Floyd 算法和程 序，能求得从客户 2 到客户 1（提货点）的最短路线是v 2  v 1 ，路程为 50 公里。但考 虑到最小生成树法局限于顶点数较少的情形，不宜进一步推广，因此本文又根据路程最 短建立以路程最短为目标函数的整数规划模型；最后，利用 LINGO 软件对其进行编程求 解。 关于问题三，是在每个客户所需固定货物量的情况下，使得行程之和最短。这样只 要找出两条尽可能短的回路，并保证每条线路客户总需求量在50个单位以内即可。因此 我们在问题二模型的基础上进行改进，以货车容量为限定条件，建立相应的规划模型并 设计一个简单的寻路算法，对于模型求解出来的结果，本文利用 Kruskal算法结合题中所 给的邻接矩阵进行优化。 关于问题四，我们首先用 Matlab 软件编程确定提货点到每个客户点间的最短路线， 然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一 种很理想的运输方案。 三、模型假设 1.假设客户级别平等； 2.假设不考虑装卸车费用； 3.假设货车不发生意外事故； 4.假设运输过程中货物无损失； 四、符号说明 v ij 不同的客户i 1.210; j 1.210； lij从客户v i 到客户v j 的距离； c ij 从第i个客户到第j个客户的距离； a j 第j个客户所需的货物量； z 总路程； 五、模型的建立与求解 问题一模型的建立与求解 问题一是要找出从客户 2 到客户 10 的最短路径， 本文利用 Floyd 算法对此文进行求 解。 为计算方便，令网络的权矩阵为D  d ij nn ,l ij为vi到vj 的距离。 Floyd 算法基本步骤为 （1）输入权矩阵D0 D。 k（2）计算Dkd ij nn k 1,2,3,,n kk1k1k1其中d ij  min[d ij ,d ik d jk ] nn（3）Dnd ij 就是v i 到v j 的最短路长。 nn 中元素d ij 在本文计算中n 10，对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