数学建模第二次作业3_第1页
数学建模第二次作业3_第2页
数学建模第二次作业3_第3页
数学建模第二次作业3_第4页
数学建模第二次作业3_第5页
已阅读5页，还剩2页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

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

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

3、的最短路径要经过点号为的点。（3）查找最短路径的方法若，则点是点到的最短距离的中间点，然后用同样的方法再分头查找。三、 模型假设： 1.各城市间的飞机线路固定不变 2.各城市间飞机线路的票价不改变 3.忽略乘客除票价以外的各项开销费用 4.不考虑雷雨云、低云、大风、雷暴、冰雹等主要天气因素对飞行的影响。 四、 模型建立 建立带权邻接矩阵： 根据飞机路线及票价表建立带权邻接矩阵， 在带权邻接矩阵中用插入顶点的方法依次构造出 6 个矩阵。 采用floyd算法步骤为:到的最短距离：到之间的插入点 输入带权邻接距阵 (1) 赋初值：对所有(2) 更新,:对所有,若，则 ,.(3) 若,停止；否则，转（2）. 运行程序得： D (1) D (2) 、 D(3)、 D (4) 、 D（ 5）、 D（6），使最后得到的矩阵 D ( 6 ) 为飞机的最廉价矩阵。 五、 模型求解结果 根据模型求解，分析得出任意两个城市之间最廉价线路及票价为： C1C2: 162；35 C1C3:153,1643;45 C1C4:164，15435 C1C51525 C1C6:1610 C2C32315 C2C42420 C2C524530 C2C62525

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论