数学建模--运输问题

运输 摘要 问题 本文主要研究的是货物运输的最短路径问题，利用图论中的 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）输入权矩阵D(0) D。 (k)（2）计算D(k)(d ij ) nn (k 1,2,3,,n) (k)(k1)(k1)k1)其中d ij  min[d ij ,d ik d( jk ] (n)(n)（3）D(n)(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