Question

数学建模——运输问题

题目：某运输公司为10个客户配送货物，假定提货点就在客户1所在的位置，从第i个客户到第j个客户的路线距离用下面矩阵中的（i,j）(i,j=1,L,10) 位置上的数表示（其中10000 表示两个客户之间无直接的路线到达）。 0 55 10000 45 25 10000 30 10000 50 10000 55 0 30 10000 35 50 10000 60 10000 10000 10000 30 0 15 10000 30 50 25 10000 60 45 10000 45 0 45 30 55 20 40 65 25 15 10000 45 0 60 10 30 10000 55 10000 50 30 30 60 0 25 55 35 10000 30 10000 50 10000 10 25 0 30 45 60 10000 60 25 20 30 55 30 0 10 10000 20 10000 10000 40 10000 15 25 45 0 20 35 20 10 45 20 10000 60 10000 30 0 1、 运送员在给第二个客户卸货完成的时候，临时接到新的调度通知，让他先给客户10送货，已知送给客户10的货已在运送员的车上，请帮运送员设计一个到客户10的尽可能短的行使路线（假定上述矩阵中给出了所有可能的路线选择）。 2、 现运输公司派了一辆大的货车为这10个客户配送货物，假定这辆货车一次能装满10个客户所需要的全部货物，请问货车从提货点出发给10个客户配送完货物后再回到提货点所行使的尽可能短的行使路线？对所设计的算法进行分析。

Answer 1

第1问：
运用
Dijkstra算法
，可以等到从客户2到客户10最短的距离是90
路线是：客户2--〉客户3--〉客户10
距离：30+60=90