航空路线建模

《航空路线建模》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、航空路线建模问题重述：某航空公司在6个城市C1,…,C6中都有分公司，从Ci到Cj的直达航班票价由下述矩阵的第i行、第j列元素给出（∞表示无直达航班），试计算从C1出发到其他5个城市的最廉价路线。问题分析：要求c1到c5的最廉价路线，即从c1出发到每个点的路径都最短。可用Dijkstra算法求固定起点的最短路问题。模型假设：1.假设飞机在飞行过程中速度不变2.假设飞机正常飞行，不会发生突发事件以及天气变化等建立模型：定义d为从v1到vj的当前“距离”Dijkstra算法的过程就是不断更新d(vj)，最终使得所有d(

2、vj)达到最小。W表示图G的带权邻接矩阵，d(vj)表示从v1到vj的只允许经过已选出顶点的最短路的权。（1）令d(vj)=w1j,S={v1},R=VS={v2,…,vn}（2）在R中寻找一个顶点vk，使得置S=S∪{vk}，R=VS。若R=Ø，终止算法。（3）修正d(vj)，对R中的每个vj，令转回（2）dC1C2C3C4C5C65035251035453525354535354545其模型图为：模型求解:求解的c1到c5的最短距离为25，c1到c6的最短距离为10；c1到c2的最短距离为35；c1到c4

3、最短距离为35；c1到c5的最短距离为25；c1到c3的最短距离为45。即其路线模型图如下：模型评价:该模型能得到最短距离的路线图，具有普遍性，该模型求解简单实用性强，考虑到一些天气等因素，飞机需要更换路线，此模型需考虑更多因素。