南阳师范学院

2012年第四届数学建模竞赛论文

答卷编号：（队伍编号）

论文题目：任意两个城市之间最廉价路线

参赛队员：

1.姓名：王亚萍 学院：物理与电子工程学院 班级：10.2电话：15236071551 2.姓名:赵玉洁 学院：物理与电子工程学院 班级：10.1电话：15236079102 3.姓名：王菲 学院：数学与统计学院 班级：10.3 电话：15236057605

任意两个城市之间最廉价路线

摘要 关键词

一、问题重述

某公司在六个城市C1，C2，C3，C4，C5，C6都有分公司，从Ci到Cj的直达航班票价由下述矩阵的第i行, 第j列元素给出(?表示无直达航班), 请帮助该公司算出一张任意两个城市之间最廉价路线表格.城市间直达航班票价矩阵已给出（相关数据查看原题）。

二、问题分析

根据题意可知任意两个城市之间的直达航班票价在往返之间是相同的，且是求任意两城市间的最短路问题，因此我们运用图论的知识中floyd算法来求解。

三、模型假设

1﹑假设每个城市间的票价是不随节日或其他影响而改变。

2﹑假设该公司人员从一个城市到另一城市乘坐飞机过程中不返航。

3﹑假设每个城市机场正常运营，各个航班不因天气变化或其他什么原因而延误。

四、符号说明及概念引入

DDRR?0?:表示城市间直达航班票价矩阵，即初始带权的邻接矩阵 ：表示第n次插值后所得的距离矩阵 :表示初始的城市间的路径矩阵 ：第n次插值后所得的路径矩阵

?n??0??n?五、模型的建立与求解

1）解题过程： 把六个城市

C1，C2，C3，C4，C5，C6从C到C的直达航

ij班票价由下述矩阵的第i行, 第j列元素给出

城市间直达航班票价矩阵转化为如图一的带权图：

则

?0?50????0?D=??40?25??10?1?1??1?0?R=??1?1??15001520?25222222333?1501020?33344440201001025??4?4??56?56??56?425?20100555510??25????25?55??0?666初始带权的邻接矩阵为

，初始的城市间的路径矩阵为

，

5由Floyd算法：求任意两顶点间的最短路.

d(i,j)：i到j的距离．

r(i,j)：i到j之间的插入点． 输入: 带权邻接矩阵

(1) (2)

赋初值：对所有i,j, d(i,j)?w(i,j), r(i,j)?j, k

W?(w(i,j))v?v

?1.

更新d(i,j), r(i,j): 对所有i,j，若d(i,k)+d(k,j)

?d(i,k)+d(k,j), r(i,j)?k

，停止．否则k

(3)

若k=

??k+1，转(2)．

得

?0?50????1?插入C1后，得D=??40?25??10???0??50?652??插入C2后，得D=?==?40??25?10??500152075==?1501020?65==40201001025402010010252575==2010035==255001520752510??25????，R?1?=25??35==??0???1?1??1??1?1???1??1??1?2?==?1??1?1??2222==33333322221223333==4444444444445==1555==1216??6?6??，6??1==??6??515551

25752010035150102040==10??25?40??2?==?，R=25??35??0??==26??6?2?==? ?6?1??6???0?50???3??65插入C3后，得D=?40?25???10500152035==65150102040402010010252535==2010035(k?1)25(k?1)10??25?40??，R?3?=25??35??0??1?1??2??1?1???12222==23333244444453==5551326??6?2?? 6??1??6?插入C4后， dij

?0??50?50?4??==D=??40?25??10?500152030==(k)?min{dij,dik(k?1)?dkj},

50==402010010252530==1501020==20==1003525?4?35==10??25??35??4?R=?25?35?==?0???1??1?4?==??1?1??1?2222====434444==5==4333或445或4551或4==4244==??6??4?==?，其中6?1或4?==?6??6R35和R53的值均有两个，即两种情况都可以，以下情况相同。

?4?插入C5后，得

?0??50?45?5?D=?==?35?==?25??10?5001520302545==35==2530201003515010203520100102510??25?35??R?5?=25??35??0???1??1?5?==?5?==?1??1?222242==5==5545或4551或43333或44444446??6?4?? 6??1或4??6??插入C6后，得

?0??35==??6??45D=??35??25?10?35==45150102035352010010252530201003501520302510??25??35??6??R=25??35?0???1??6==??5或6?5??1??1==653333或445或644444==545或4551或4222426??6??4? 6??1或4??6?2）结果分析:

由于一个城市到另一个城市是无向的，因而在此我们就考虑一个方向。 由第六次插值后所得的距离矩阵D??和城市间的路径矩阵R??可得以下结果：

661>从C1?C2的最短路：C1?C6?C2，即从C1到C2需要经过C6，如图（加粗的边即是从一顶点到另一顶点所要经过的边，以下图像相同）：

2>从C1?C3的最短路：C1?C5?C3，即从C1到C3需要经过C5，如图：

3>从C1?C4的最短路：C1?C5?C4或C1?C6?C4，即从C1到C4需要经过C5或从C1到C4需要经过C6,如图:

4>从C1?C5的最短路：C1?C5,如图:

5>从C1?C6的最短路：C1?C6,如图:

6>从C2?C3的最短路：C2?C3,如图:

7>从C2?C4的最短路：C2?C4,如图:

8>从C2?C5的最短路：C2?C4?C5, 即从C2到C5需要经过C4,如图:

9>从C2?C6的最短路：C2?C6,如图:

10>从C3?C4的最短路：C3?C4,如图:

11>从C3?C5的最短路：C3?C5或C3?C4?C5,如图:

12>从C3?C6的最短路：C3?C4?C6,即从C3到C6需要经过C4,如图:

13>从C4?C5的最短路：C4?C5,如图:

14>从C4?C6的最短路：C4?C6,如图:

15>从C5?C6的最短路：C5?C4?C6或C5?C1?C6,如图: