最短路径问题.doc

最短路径问题摘要在图论当中，任意两点间的最短路径问题，运用Dijkstra算法，Flord算法，匈牙利算法等都可以就解决这类相关问题,本文主要就是运用图论相关知识，来分析问题的。在问题一中，需要为货车司机选择一条从地点1到地点11的最短时间问题，其实际归结为求一个两点间最短路径问题，运用运筹学中的网络模型相关知识，建立了一个一个0-1线性模型，并最终求的其结果，最短时间为21，货车司机的运输路线为。运用Floyd算法解决问题二，并且运用Matlab软件编程，Floyd算法与Matlab软件编程所得出的结果一致，最后得出了一个最短航程表，及任意两点间的最短航程图。本文的最大亮点在于将问题二进行更深一步的拓展，从问题实际出发，从公司的差旅费用最小出发，利用Mtlab软件编程的出了公司到个城市间差旅费用最小图，从而更能为公司节省成本。C1C2C3C4C5C6C1051.561.5503416C254.8024324840C366240163254.5C450321601638.5C5344827.516050C614.835.550.334.348.80 任意城市间差旅费用最小 其次是本文结果的准确性，问题一运用Lingo软件编程，和WinQSB软件，所得出结果都是一致的，问题二更是运用Floyd算法，Matlab软件编程，WinQSB软件，大大地保证了结果的准确性，并且十分恰当地运用WinQSB软件将作图功能，把每一提的最短路径都清晰的描绘出来，更加直观地将结果展现出来。关键字：Matlab Lingo WinQSB Floyd算法 0-1规划 一、 问题重述问题一需要解决的问题是在一个城市交通网络中（图一），如何从地点1找到一条时间最短路径通往地点11，在这个城市交通网络中，有单向道，也有双向道，即如何处理一个有向图与无向图结合的图论问题，并且是一个两点间的最短路径问题：10237411659813512210615887993227图（一）问题二阐述的是某公司员工往来于六个城市间，给出了这六个城市间的直达航班票价（表二），需要为这家公司提供出这六个城市间任意两点间的最小航班费用表表（二）二、问题分析4.1问题一的分析：实际问题是货车运输问题，货车运输从起点1到终点11，一般情况下，不存在货物往回运输，所以地点1到地点8是可以看成是一个单向道，即8指向1，同样的地点8也是指向地点9的。假设货物到达地点9时，货物要运送到终点，则地点9只能指向地点10，同理货物到达地顶点点7，只能是往地点6的方向运输。如果货物到达地点5时，货物只有经过5 6 9 10 11，才是最短的，所以在这里地点5指向地点6.同理3指向5，得出图（二），这样按照时间耗费的目的，将一个有向图与无向图结合的图，转化为一个单纯的有向图，这将有利于问题的分析。 图（二）4.2问题二的分析；通过题目给出的六个城市间的直达航班票价（表二），可以将其绘成无向图（图三），可以将其转换成一个图轮问题，即求一个具有六个顶点无向图的任意两点间的最短路径问题，这里用到图论当中的Flord算法。 图（三）三、基本假设1、货车在各路段中所花时间数据属实。2、货车在行驶中是按匀速行驶3、货运车在路途中无意外发生，无需返回原地。4、假设天气等一些客观因素不影响交通运输。5、飞机航班不存在延误现象。6、公司员工转机过程中不存在逗留现象。四、符号说明1、：货车从地点到地点所花的时间：2、：货车司机是否选择地点到地点，； 3、公司员工选择从城市到城市的航班，；4、，插入点；5、：插入点后的路径；五、模型的建立与求解6.1 问题1的模型建立与求解6.1.1跟据已得出的分析再加上题目所给的已知条件，可以得出其赋全矩阵（表（三）：v1v2v3v4v5v6v7v8v9v10v11v10878v203v30565v401112v560210v6203v790v809v9702v10202v110表（三）建立如下0-1规划数学模型：运用Lingo软件输入一个线性规划程序（见附录（一），分析得出如下结果：formtotimetimev1v888v8v9917v9v10219v10v11221v1v11=21v1v2=8v1v3=11v1v4=16v1v5=17v1v6=16v1v7=7v1v8=8v1v9=17v1v10=19表（四）6.1.2模型一的结果分析: 利用WinQSB软件中的Network model,选择Short Path problem,输入问题一的赋权矩阵（表 ）输入如下数据：图（三）得出结果表（见附录三），并得出如下直观图： 图（四）图四中可以看出的最短路径为21，所以模型一的最优解可以得到验证为，所以货车司机应选路线最短，所花时间最短为21。6.2 问题2的模型建立与求解 6.2.1由问题2的分析，可利用图论方法、Floyd算法及WinQSB软件求解该问题, 由问题中所给的各个节点的坐标进行如下的Floyd算法步骤： 以及得出每次插入点的路径变化（见附录表（三），得出六个城市间的任意两点间的最短路径表和最终选择路径矩阵：C1C2C3C4C5C6C103545352510C235015203025C345150102035C435201001025C525302010035C610253525350 最短航程图由Matlab编程（见附录五）运行得出的结果与Floyd算法一致、 6.2.2问题二的结果分析 利用WinQSB软件求得这6个城市间的任意两点最短航程见（附录四），并得出直观图：六、模型二的扩展在问题二该公司员工出差途中，在搭乘航班过程所使用的总时间，都算作公司损失时间，此时公司差旅费用=每小时员工正常创造价值航班总时间+票价。公司员工搭乘航班时间是航班总飞行时间是与飞机飞行时间和员工转乘时间有关，计算公司员工出差从地到地，公司差旅费用最少。员工在六个城市C1,C2,C3,C4,C5,C6个机场等待重新登机起飞所等待的时间（机场估算），如下： 假设：航程越长飞行时间越长票价越贵，这三者间存在联系，查找数据得两个城市之间飞行时间（机场估算），如下：航班飞行时间=航班飞行总时间=飞机飞行时间+员工重新登机时间。公司员工为公司创造价值每小时（=30）元（公司估计值）。公司差旅费用=员工为公司创造价值航班总时间+票价。通过计算得：公司差旅费用=票价+飞行总时间，根据此矩阵的出如下图形：利用Matlab软件编程求解（程序见附录七），整理结果得出任意城市差旅费用最小表（四），并利用WinQSB软件得出如下任意城市间差旅费用最小图：C1C2C3C4C5C6C1051.561.5503416C254.8024324840C366240163254.5C450321601638.5C5344827.516050C614.835.550.334.348.80任意城市间差旅费用最小表（四）任意城市间差旅费用最小图 七、模型的评价问题一的模型评价运用了Lingo编程、利用WinQSB软件验证，大大地减少了计算量，同时提高了计算的准确性。模型一求最短路径问题，将问题按实际常理出发，将一个有向与无向结合的图，转化为一个单一的有向图，使得问题变得简化易解，将模型建立为一个线性规划问题，该模型有利于解决一些解决常见的最短路问题，并且其Lingo程序只需改动相关数据便可适用于常见的求最短路问题。问题二的模型评价采用了Floyd算法并利用Matlab软件编程，再利用WinQSB软件，确保了结果的准确性，并以图表的形式，更加直观清晰地展示出每一个城市到任意城市的最短路径。针对问题二，从实际问题出发，对问题进行了拓展，求出了公司差旅费用最小矩阵，更加有利于为公司节省最大费用。但由于渠道不畅，对于拓展内容的相关数据的可靠性还有待核实，但这并不会减掉模型拓展内容的丰富性，并不会抹掉其内在的，实质性魅力。八、参考文献1 熊伟，运筹学，第二版，北京：机械工业出版社，2011。2 薛毅，数学建模基础，第二版，北京：科学出版社，2011。3 魏巍, Matlab应用数学工具箱技术手册，北京：国防工业出版社，2004。4 姜启源 谢金星 叶俊，数学模型，第三版：高等教育出版社，2007。5 韩中庚 宋明武 邵广纪，数学建模竞赛获奖论文精选与点评，北京：科学出版社，2007。九、附录附录一（问题一中的Lingo程序）： model: ! vij表示选择从地点i到地点j； ! eij表示从地点i到地点j货车司机所花时间； objmin=v12*e12+v17*e17+v18*e18+v23*e23+v34*e34+v37*e37+v35*e35 +v411*e411+v45*e45+v511*e511+v56*e56+v69*e69+v76*e76+v89*e89 +v910*e910+v95*e95+v1011*e1011; av12+v17+v18=1; bv18-v89=0; cv17+v37-v76=0; dv12-v23=0; ev23-v34-v37-v35=0; fv34-v411-v45=0; gv35+v45+v95-v56-v511=0; hv76+v56-v69=0; lv89+v69-v95-v910=0; nv910-v1011=0; ov411+v511+v1011=1; bin(v12);bin(v17);bin(v18); bin(v76);bin(v89);bin(v35); bin(v37);bin(v23);bin(v34); bin(v45);bin(v411);bin(v511); bin(v56);bin(v69);bin(v95); bin(v910);bin(v1011);data: e12=8;e23=3;e34=5; e411=12;e37=5;e17=7; e18=8;e45=1;e35=6; e76=9;e56=2;e511=10; e89=9;e910=2;e1011=2; e95=7;e69=3; enddataend附录二（问题一中的Lingo程序的运行结果）： Feasible solution found. Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0Variable ValueV12 0.000000V17 0.000000V18 1.000000V89 1.000000V37 0.000000V76 0.000000V23 0.000000V34 0.000000V35 0.000000V411 0.000000V45 0.000000V95 0.000000V56 0.000000V511 0.000000V69 0.000000V910 1.000000V1011 1.000000E12 8.000000E23 3.000000E34 5.000000E411 12.00000E37 5.000000E17 7.000000E18 8.000000E45 1.000000E35 6.000000E76 9.000000E56 2.000000E511 10.00000E89 9.000000E910 2.000000E1011 2.000000E95 7.000000E69 3.000000Row Slack or SurplusA 0.000000B 0.000000C 0.000000D 0.000000E 0.000000F 0.000000G 0.000000H 0.000000L 0.000000N 0.000000O 0.000000附录三问题一在WinQSB软件中运行的结果：附录四 问题二在WinQSB软件中运行的结果，任意两点间的最短航程表 到各个城市的最短航程到各个城市的最短航程到各个城市的最短航程到各个城市的最短航程到各个城市的最短航程到各个城市的最短航程 附录五问题二在进行Floydj算法进行插值时，每次插值所发生的选择路径的变化： 附录六问题二用Matlab软件编程程序与运行结果： clear n=6; a=zeros(n); a(1,2)=50;a(1,4)=40;a(1,5)=25;a(1,6)=10; a(2,3)=15;a(2,4)=20;a(2,6)=25;a(3,4)=10;a(3,5)=20; a(4,5)=10;a(4,6)=25; a(5,6)=55; a=a+a; M=max(max(a)*n2; %M为充分大的正实数 a=a+(a=0)-eye(n)*M; path=zeros(n); for k=1:nfor 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, path a = 0 35 45 35 25 10 35 0 15 20 30 25 45 15 0 10 20 35 35 20 10 0 10 25 25 30 20 10 0 35 10 25 35 25 35 0path = 0 6 5 5 0 0 6 0 0 0 4 0 5 0 0 0 0 4 5 0 0 0 0 0 0 4 0 0 0 1 0 0 4 0 1 0 附录七问题二的拓展用Matlab软件编程程序与运行结果： n=6; a=zeros(n); a(1,2)=69.5;a(1,4)=61;a(1,5)=34;a(1,6)=16; a(2,1)=71;a(2,3)=24;a(2,4)=32;a(2,6)=40; a(3,2)=24;a(3,4)=16;a(3,5)=32; a(4,1)=53.5;a(