数学建模第二次作业(3)
更新时间:2023-10-09 02:19:01 阅读量: 综合文库 文档下载
数
学 建 模
任意两个城市之间的最廉价路线
参与人员信息 :
2012 年 6 月 6 日
一、问题提出
某公司在六个城市C1、C2、C3、C4、C5、C6中都有分公司,从Ci到Cj的直达航班票价由下述矩阵的第i行、第j列元素给出(∞表示无直达航班),该公司想算出一张任意两个城市之间最廉价路线表,试做出这样的表来。
0 50 ∞ 40 25 10 50 0 15 20 ∞ 25
∞ 15 0 10 20 ∞
40 20 10 0 10 25 25 ∞ 20 10 0 55 10 25 ∞ 25 55 0
二 、问题分析
若网络中的每条边都有一个数值(长度、成本、时间等),则找出两节点(通
常是源节点和阱节点)之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一,可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。最短路问题,我们通常归属为三类:单源最短路径问题、确定起点终点的最短路径问题、全局最短路径问题———求图中所有的最短路径。
题中要求算出一张任意城市间的最廉价路线表,属于全局最短路问题,并且使得该公司总经理能够与各个子公司之间自由往返。(此两点为主要约束条件) Floyd算法,具体原理如下:
(1) 我们确定本题为全局最短路问题,并采用求距离矩阵的方法
根据路线及票价表建立带权矩阵W,并把带权邻接矩阵我w作为距离矩阵的初始值,即D(0)?(dij(0))v?v?W
(2)求路径矩阵的方法
在建立距离矩阵的同时可建立路径矩阵R,R?(rij)v?v,rij的含义是从vi到vj的最短路径要经过点号为rij的点。
(3)查找最短路径的方法
若rij(v)?p1,则点p1是点i到j的最短距离的中间点,然后用同样的方法再分头查找。
三、 模型假设:
1.各城市间的飞机线路固定不变 2.各城市间飞机线路的票价不改变 3.忽略乘客除票价以外的各项开销费用
4.不考虑雷雨云、低云、大风、雷暴、冰雹等主要天气因素对飞行的影响。
四、 模型建立
建立带权邻接矩阵:
根据飞机路线及票价表建立带权邻接矩阵, 在带权邻接矩阵中用插入顶点的方法依次构造出 6 个矩阵。
采用floyd算法步骤为:
Di,j:i到j的最短距离
Ri,j:i到j之间的插入点
输入带权邻接距阵 w
(1)赋初值:对所有i,j,wi,j?di,j,j?ri,j,k?1. (2)更新Di,j,Ri,j:对所有i,j若di,k?dk,j?di,j,则 di,k?dk,j?di,j,k?ri,j.
(3)若k?v,停止;否则k?1?k,转(2).
运行程序得:
D (1)
(2)(3) 、
、 D D
(4)
( 5)
、 D 、 D
D
(6)
,
使最后得到的矩阵 D ( 6 ) 为飞机的最廉价矩阵。
五、 模型求解结果
根据模型求解,分析得出任意两个城市之间最廉价线路及票价为:
C1→C2: 1→6→2;35
C1→C3:1→5→3,1→6→4→3;45 C1→C4:1→6→4,1→5→4﹔35 C1→C5∶1→5﹔25 C1→C6:1→6﹔10 C2→C3∶2→3﹔15 C2→C4∶2→4﹔20 C2→C5∶2→4→5﹔30 C2→C6∶2→5﹔25 C3→C4∶3→4﹔10
C3→C5∶3→5∶3→4→5﹔20 C3→C6∶3→4→6﹔35 C4→C5∶4→5﹔10 C4→C6∶4→6﹔25 C5→C6∶5→4→6﹔35
正在阅读:
数学建模第二次作业(3)10-09
DIY留学:去英国留学学费12-29
wps教案12-25
道路交通安全法10-15
人美版《美术》4年级上册14课 - 生活日用品的联想10-07
遗产学问答01-08
5S管理(3)资料03-22
优化PAPB参数提升LTE下载速率11-13
- 《江苏省环境水质(地表水)自动监测预警系统运行管理办法(试行)》
- 安乐死合法化辩论赛立论稿(浙大新生赛)
- 公共科目模拟试卷公务员考试资料
- 我国固定资产投资FAI对GDP的影响
- 大学生创新创业训练计划项目申请书大创项目申报表
- 完美版—单片机控制步进电机
- 2013资阳中考化学试题
- 18.两位数减一位数退位(397道)
- 工程量计算规则
- 二年级操行评语(下)
- 第3章 流程控制语句
- 浅基桥墩加固技术
- 课题研究的主要方法
- 5100软件说明书 - 图文
- 车间技术员年终总结
- 关于印发《中铁建工集团开展项目管理实验室活动方案》的通知
- 经典诵读结题报告
- 地下水动力学习题答案
- 2018年全国各地高考数学模拟试题平面解析几何试题汇编(含答案解
- 街道办事处主任2018年度述职述廉报告
- 数学建模
- 作业
- 新兴重大工程-20MW光伏电站中草药种植一体化项目可行性研究报告 - 图文
- 增城方言的研究+高湘
- 苏州大学文正学院2018年五年一贯制高职专转本招生简章 - 图文
- 中国古镇艺术风采纵览 - 图文
- windows下weblogic安装、建域文档
- 航天信息网上认证系统软件操作手册 - 图文
- 太钢制证中心制度
- 16年中职对口升学语文试题
- JGJ 128-2010脚手架(门式)安全技术规范 - 图文
- 江氏始祖像 - 图文
- 八字十神取象
- 考前指导
- 油务管理制度
- 基金从业资格考试证券投资基金基础知识 - --2017年基金从业考试《证券投资基金》计算题及答案(1)--(2)
- 金华市一中2018-2019学年高三上学期11月月考数学试卷含答案
- 小石潭记对比阅读
- 分析化学实验报告(武汉大学第五版)
- 钢铁专业英语
- 国际贸易计算题及案例分析(答案)
- 我院学生在2015年广东省省赛“现代物流方案设计与实施”中喜获佳绩