c?400?40?80?55?70?645（元）
5.4.3模型的检验
由以上分析可得若派出四辆车，则最小费用为645元，但是问题当中没有对时间进行限制，因此，我们也可假设只雇用一辆车，按以上运输方案进行运输，如下表所得; 车号 行车路线 路线总长度 货物需求量 一号车 40 20 V1?V5?V2 一号车 一号车 一号车 V1?V4?V3?V8 80 55 70 20 25 21 V1?V7?V6 V1?V9?V10 则最小费用为c=100+40+80+55+70=345(元)；
6.模型评价
6.1模型的优点
本文从模型建立来看，无论是理论值还是实际值都比较接近，而且我们从模型的假设到模型的创新，以及方法运用上都是合理的，因此可以说明本文实际运用性比较强，可以与用于其他问题的研究和求解。
首先，该模型是基于Dijkstra算法的基础上转化为线性规划模型来求最短路径的模型,优点是实现较简单,也容易求解；
其次，虽然我们猜想模型很简单，但它是解决本问题的关键，也是我们建模思路的切入点，通过这个模型的建立与求解我们逐渐发现问题的所在，故而引导我们对自己所建的模型一步一步地优化，最终得到一个非常理想的运输方案
最后，我们设计的解决方案是以Dijkstra算法为基础，以小车容量为约束条件得出的一种解决问题的方法，从模型分析可以看出我们没有必要去考虑以加车的方法来换取短路线的方案，因此直接根据客户的总需货量可以知道，至少需要4辆小车来送货。从得出的运输方案来看，这种办法确实是可行了，且并不会很差。
6.2模型的缺点
首先本文有个令人不是很满意的地方就是其模式固定,要求任两个客户点间最短距离时,需将其一客户的位置与提货点互换,另一个客户的位置则需与客户10的位置互换,将其看成原始的提货点到客户10最短距离的模型进行求解，这样较为烦琐,有待改进。
其次，本文模型也存在不少问题，例如我们没有用一个统一的模型来同时得出两辆车的最优路线，这是我们觉得比较郁闷的地方，我们将慢慢地对其不断改进与完善。
6.3模型的推广
最短路径问题在交通网络结构的分析，交通运输线路(公路、铁路、河流航运线、航空线、管道运输线路等)的选择，通讯线路的建造与维护，运输货流的最小成本分析，城公共交通网络的规划等，都有直接应用的价值。
在很多目标信息引导系统的设计中．需要获得最优化路径引导信息。例如，在日益增多的高层建筑、大型公共建筑(超级市场、博物馆、医院、游乐场等)场台的火灾事故现场救生疏导系统，需要根据现场情况动态地为逃生者实时提供最短的安全通道指引信息；而当这些场合发生盗窃、抢劫等突发犯罪事件时，安全监控系统如能为警方实时提供通向罪犯所处位置最短搜索路径信息．则可以达到迅速制止犯罪的目的。在设计一个大型高层建筑火灾事故现场救生疏导系统时，将图论中Dijkstra算法应用于目标信息引导系统的设计中，通过Dijkstra算法，首先计算出任一指定位置点距各疏导出口的最短路径树，进而通过编制辅助方向指示箭头程序．动态地将火灾事故现场救生疏导路径引导图加以显示，从而达到优化目标引导路径的目的．
7.参考文献
【1】卜月华 图论及其应用 南京：东南大学出版社，2000 【2】最短路问题在运输网络中的应用 李玲 2006
【3】戴文舟. 交通网络中最短路径算法的研究 [D ]. 重庆大学硕士学位论文 ,2004.
【4】荣玮.基于道路网的最短路径算法的研究与实现.武汉理工大学硕士学位论文[D],2005. 【5】朱建青 ,张国梁.数学建模方法M. 郑州大学出版社. 【6】杨民助 ,运筹学M. 西安交通大学出版社.
【7】殷剑宏 ,吴开亚.图论及其算法M. 中国科学技术出版社. 【8】王朝瑞.图论M. 国防工业出版社.
【9】姚思瑜.数学规划与组合优化M. 浙江大学出版社.
【10】秦裕瑗 ,秦明复.运筹学简明教材M. 高等教育出版社.
8.附录
附录一 求解问题一
n=9; a=zeros(n);
a(1,2)=30;a(1,4)=35;a(1,5)=50;a(1,7)=60;
a(2,3)=15;a(2,5)=30;a(2,6)=50;a(2,7)=25;a(2,9)=60;
a(3,4)=45;a(3,5)=30;a(3,6)=55;a(3,7)=20;a(3,8)=40;a(3,9)=65; a(4,5)=60;a(4,6)=10;a(4,7)=30;a(4,9)=55; a(5,6)=25;a(5,7)=55;a(5,8)=35; a(6,7)=30;a(6,8)=45;a(6,9)=60; a(7,8)=10;a(8,9)=20;
a=a+a'; M=max(max(a))*n^2; %M为充分大的正实数 a=a+((a==0)-eye(n))*M; path=zeros(n); for k=1:n for i=1:n
for j=1:n
if a(i,j)>a(i,k)+a(k,j) a(i,j)=a(i,k)+a(k,j); path(i,j)=k; end end end end a, path a =
0 30 45 35 50 45 55 65 85 30 0 15 55 30 50 25 35 55 45 15 0 45 30 50 20 30 50 35 55 45 0 35 10 30 40 55 50 30 30 35 0 25 45 35 55 45 50 50 10 25 0 30 40 60 55 25 20 30 45 30 0 10 30 65 35 30 40 35 40 10 0 20 85 55 50 55 55 60 30 20 0
path =
0 0 2 0 0 4 2 7 8 0 0 0 7 0 0 0 7 8 2 0 0 0 0 7 0 7 8 0 7 0 0 6 0 0 7 0 0 0 0 6 0 0 8 0 8 4 0 7 0 0 0 0 7 0 2 0 0 0 8 0 0 0 8 7 7 7 7 0 7 0 0 0 8 8 8 0 8 0 8 0 0
附录二
求解问题二的程序 MODEL: SETS:
CUSTOMERS / 1.. 10/: U; LINK( CUSTOMERS, CUSTOMERS):DIST,X; ENDSETS DATA: 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) <= N-1- (N - 2) * X(1,K);U( K) >=1+(N-2)*X(K, 1)); END