数学建模航班最廉路线问题

更新时间：2023-03-16 23:08:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

数学建模大赛官网推荐度：
相关推荐

航班最廉路线问题

建模背景：

某航空公司在6个城市C1,…,C6中都有分公司，从Ci到Cj的直达航班票价由下述矩阵的第i行、第j列元素给出。现有矩阵A给出不同机场直达航班票的票价（ ∞ 表示无直达航班），试计算从C1出发到其他5个城市的最廉价路线。

?0?50???A???40?25??10402510?01520?25??1501020???201001025??2010055??25?25550? 50?模型的分析与假设：

1、航空票价不受其他因素影响。

2、最廉价的路线表示为固定起点的最短路问题.

模型的建立：

由上述矩阵，可画出如下的图形，图上的权即为票价

最廉价路线问题可以转化为求C1到各点的最短路线问题，所以通过dijkstra算法可以得到：

C1 0 C2 50 35 C2 35 35 C2 35 C2 C3 C4 40 35 C4 35 35 C4 35 35 C4 35 C5 25 25 C5 25 C5 C5 C6 10 C6 C6 C6 ? 75 C3 75 45 C3 45 45 C3 45 45 C1 C1 C1 得到的最终结果： C1 0 C2 35 C3 45 C4 35 C5 25 C6 10 即：建立集合P=｛C1｝，T={C2,C3,C4,C5,C6} 第一次：P=｛C1,C6，C5｝，T={C2,C3,C4}

dT(C2)?35 dT(C3)?45 dT(C4)?35

所以MinC1→C2：C1→C6→C2=35 MinC1→C4：C1→C6→C4=35 或者 C1→C6→C5→C4=35

第二次：P=｛C1,C6，C5，C2，C4｝，T={C3} dT(C3)?45

所以MinC1→C3：C1→C6→C5→C3=45 第三次：P=｛C1,C6｝，T={C2,C3,C4,C5}

dT(C2)?35 dT(C3)?? dT(C4)?35,dT(C5)?25

所以MinC1→C5:C1→C5=25

第四次：dT(C2)?50 dT(C3)?? dT(C4)?40,dT(C5)?25,dT(C6)?10 所以P=｛C1,C6｝

所以MinC1→C6：C1→C6=10 所以，画出最短路线的图：

所以上图即

为所求解。

本文来源：https://www.bwwdw.com/article/iuuv.html

相关文章：