数学建模第二次作业(3)

1、数学建模任意两个城市之间的最廉价路线参与人员信息：2022 年6月_6_日、问题提出某公司在六个城市 C1、C2、C3 C4 C5 C6中都有分公司，从 Ci到Cj的 直达航班票价由下述矩阵的第i行、第j列元素给出表示无直达航班，该 公司想算出一张任意两个城市之间最廉价路线表，试做出这样的表来。厂0 508 40 25 10、50 0 15 20258 15 0 10 20 840 20 10 0 10 25258 20 10 0 5510 2(8 25 55 0/二、问题分析假设网络中的每条边都有一个数值(长度、本钱、时间等)，那么找出两节点(通 常是源节点和阱节点)之间总权和最小的路径就是

2、最短路问题。最短路问题是网 络理论解决的典型问题之一，可用来解决管路铺设、线路安装、厂区布局和设备 更新等实际问题。最短路问题，我们通常归属为三类：单源最短路径问题、确定 起点终点的最短路径问题、全局最短路径问题求图中所有的最短路径。题中要求算出一张任意城市间的最廉价路线表，属于全局最短路问题，并且使得该公司总经理能够与各个子公司之间自由往返。此两点为主要约束条件 Floyd算法，具体原理如下：(1)我们确定此题为全局最短路问题，并采用求距离矩阵的方法根据路线及票价表建立带权矩阵W，并把带权邻接矩阵我 w作为距离矩阵 的初始值，即 D(0) (dij(0)vv W2求路径矩阵的方法在建立距离矩

3、阵的同时可建立路径矩阵 R，R (rij)vv , ©的含义是从v到Vj 的最短路径要经过点号为厲的点。3查找最短路径的方法假设昇 P1，那么点p是点i到j的最短距离的中间点，然后用同样的方法 再分头查找。三、模型假设：1. 各城市间的飞机线路固定不变2. 各城市间飞机线路的票价不改变4.不考虑雷雨云、低云、大风、雷暴、冰雹等主要天气因素对飞行的影响。四、模型建立建立带权邻接矩阵：根据飞机路线及票价表建立带权邻接矩阵，在带权邻接矩阵中用插入顶点的方法依次构造出6个矩阵。采用floyd算法步骤为：Di,j: i到j的最短距离Ri,j : i到j之间的插入点输入带权邻接距阵 w赋初值：对

4、所有i,j,w,jdi,j, j n,j,k 1.更新D,j, R,j:对所有i, j假设di,k dk,jdi,j，那么di ,k dk,jdi, j , kri,j .假设k v,停止；否那么k 1 k，转2.运行程序得：050InE402&10soC15207525Inf01020Inf4020100ID2525201035LQInf益35Q12315&12a41&123斗5&12345B1345112341&0506540251050C152D7S25551吁010£QAQ10201001025257E20la3510254025350

5、12£501162152151112Z416Du -Q506540IQ50015203525閒1510£04040201001025埜35ECllan芻10254025350DK =211I224q4斗435516616Du =050SO40E5105001520mo255015010£0354020100ID25戏30201003510253525350R =£445&12?44B4234吕4I2345& =0SO<53S2510500152030254呂1501020貼555010010252530201

6、0a3510253525350251244t122斗23344446441650453525IQ0IE203025150Id20352C1001025302010035為3525350o503525to2555&234-4B23454234564345124115D6使最后得到的矩阵D 6为飞机的最廉价矩阵。五、模型求解结果根据模型求解，分析得出任意两个城市之间最廉价线路及票价为:C1 f C2: 1 f 62; 35C1 f C3:1 f 5f 3,1 f 6f 4f 3;45C1 f C4:1 f 6f 4, 1f 5f 4 ； 35C1 f C5： 1f 5 ； 25C1 f C6:1 f 6 ； 10C2 f C3： 2f 3 ； 15C2 f C4： 2f 4 ； 20C2 f C5： 2f 4f 5 ； 30C2 f C6： 2f 5 ； 25C3 f C4： 3f 4 ； 10C3 f C5 :