0815运输优化模型参考1

《0815运输优化模型参考1》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运输问题摘要本文根据运输公司提供的提货点到各个客户点的路程数据，利用线性规划的优化方法与动态优化模型——最短路径问题进行求解，得到相关问题的模型。针对问题一，我们采用Dijkstra算法，将问题转化为线性规划模型求解得出当运送员在给第二个客户卸货完成的时，若要他先给客户10送货，此时尽可能短的行使路线为：，总行程85公里。针对问题二，我们首先利用prim算法求解得到一棵最小生成树：再采用Dijkstra算法求得客户2返回提货点的最短线路为故可得到一条理想的回路是：后来考虑到模型的推广性，将问题看作是哈密顿回路

2、的问题，建立相应的线性规划模型求解，最终找到一条满足条件的较理想的的货车送货的行车路线：。针对问题三，我们首先直接利用问题二得一辆车的最优回路，以货车容量为限定条件，建立相应的规划模型并设计一个简单的寻路算法，最终可为公司确定合理的一号运输方案:两辆车全程总和为295公里（见正文）；然后建立线性规划模型得出二号运输方案：两辆车全程总和为290公里（见正文）；最后再进一步优化所建的线性规划模型，为运输公司献上一个最优的决策即三号运输方案：车号行车路线线路的长度该车负责的客户一号车135公里2，3，4，5，8二号

3、车145公里6，7，9，10两辆车全程总和为280公里。针对问题四，我们首先用Dijkstra算法确定提货点到每个客户点间的最短路线，然后结合一些限定条件建立一个目标模型，设计一个较好的解决方案进行求解可得到一种很理想的运输方案：车号行车路线车号行车路线一号车三号车二号车四号车该方案得到运输总费用是645元。18关键字：Dijkstra算法,prim算法,哈密顿回路问题重述某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离（单位公里）用下面矩阵中的位置上的数表示

4、（其中表示两个客户之间无直接的路线到达）。1、运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。2、现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。3、现因资源紧张，运输公司没有大货车可以使用，

5、改用两辆小的货车配送货物。每辆小货车的容量为50个单位，每个客户所需要的货物量分别为8，13，6，9，7，15，10，5，12，9个单位，请问两辆小货车应该分别给那几个客户配送货物以及行使怎样的路线使它们从提货点出发最后回到提货点所行使的距离之和尽可能短？对所设计的算法进行分析。4、如果改用更小容量的车，每车容量为25个单位，但用车数量不限，每个客户所需要的货物量同第3问，并假设每出一辆车的出车费为100元，运货的价格为1元/公里（不考虑空车返回的费用），请问如何安排车辆才能使得运输公司运货的总费用最省？18

6、问题1【模型分析与假设】运送员在给第二个客户卸完货后，即从此处赶到第十个客户处，路程越短越好，是一个最短路径问题，为此我们采用Dijkstra算法，考虑到建模的方便我们将问题转化为线性规划模型进行求解。下面是一些变量的假设与说明：1．为0，1变量，其值为1代表行车路线经过第j个客户，为0则代表不经过。2．为题中给出的邻接矩阵对应位置的值。3．为了表达的方便，将邻接矩阵的第一行与第二行互换,第一列与第二列互换。（因为求的是客户2至客户10的最短线路，而非提货点至客户10）同时将矩阵中数据0或用一个足够大的数99

7、9代替。（这是因为目标函数是求最小值）【模型建立与求解】建立问题的模型(1)是：将其转化为lingo代码（见附录[1]）后，求解可得以下结果：18Globaloptimalsolutionfoundatiteration:19Objectivevalue:85.00000VariableValueReducedCostX(1,3)1.00000030.00000X(3,8)1.00000025.00000X(8,9)1.00000010.00000X(9,10)1.00000020.00000至此可以知道，运

8、送员应该走的最好路线是:总行程为85公里。【模型检验与评价】该模型是基于Dijkstra算法的基础上转化为线性规划模型来求最短路径的模型,优点是实现较简单,也容易求解；但有个令人不是很满意的地方就是其模式固定,要求任两个客户点间最短距离时,需将其一客户的位置与提货点互换,另一个客户的位置则需与客户10的位置互换,将其看成原始的提货点到客户10最短距离的模型进行求解，这样较为烦琐,有待改进。问题2【模