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

1、资料收集于网络如有侵权请联系网站删除谢谢数学建模任意两个城市之间的最廉价路线参与人员信息：2012年6月6日精品文档资料收集于网络如有侵权请联系网站删除谢谢一、问题提出某公司在六个城市 C1、C2、C3、 C4、C5、C6 中都有分公司，从 Ci 到 Cj 的直达航班票价由下述矩阵的第 i 行、第 j 列元素给出（表示无直达航班） ，该公司想算出一张任意两个城市之间最廉价路线表，试做出这样的表来。0 5040251050 015 20 25 150 1020402010010 25252010055102525550二 、问题分析若网络中的每条边都有一个数值 ( 长度、成本、时间等 ) ，则找

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

3、离矩阵的初始值，即 D (0)(dij (0) )v vW（ 2）求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R ，R(rij ) v v ，rij 的含义是从 vi 到 v j的最短路径要经过点号为rij 的点。（ 3）查找最短路径的方法若 rij ( v)p1 ，则点 p1 是点 i 到 j 的最短距离的中间点，然后用同样的方法再分头查找。三、 模型假设：1. 各城市间的飞机线路固定不变2. 各城市间飞机线路的票价不改变3. 忽略乘客除票价以外的各项开销费用4. 不考虑雷雨云、低云、大风、雷暴、冰雹等主要天气因素对飞行的影响。精品文档资料收集于网络如有侵权请联系网站删除谢谢四、模型建

4、立建立带权邻接矩阵：根据飞机路线及票价表建立带权邻接矩阵， 在带权邻接矩阵中用插入顶点的方法依次构造出 6 个矩阵。采用 floyd算法步骤为 :D i , j : i 到 j 的最短距离Ri , j ： i 到 j 之间的插入点输入带权邻接距阵w(1)赋初值：对所有 i, j , wi , jdi, j , jri , j , k1.(2)更新 Di , j , Ri, j : 对所有 i , j若 di, kdk, jdi , j ，则di ,kdk , j di, j , kri, j .(3)若 kv , 停止；否则 k1k ，转（ 2）.运行程序得：D(1)精品文档资料收集于网络如有侵权请联系网站删除谢谢DD(2)(3)、精品文档资料收集于网络如有侵权请联系网站删除谢谢D(4)、D（5）、精品文档资料收集于网络如有侵权请联系网站删除谢谢D（6），使最后得到的矩阵D ( 6 ) 为飞机的最廉价矩阵。五、模型求解结果根据模型求解，分析得出任意两个城市之间最廉价线路及票价为：C1 C2: 1 62；35C1 C3:153,1 643;45C1 C4:164，15435C1 C51525C1 C6:1610C2 C32315C2 C42420C2 C5245 30C2 C62525C3 C43410C3 C53