数学建模第二次作业(3)Word文件下载.doc
- 文档编号:831489
- 上传时间:2023-04-29
- 格式:DOC
- 页数:7
- 大小:122.49KB
数学建模第二次作业(3)Word文件下载.doc
《数学建模第二次作业(3)Word文件下载.doc》由会员分享,可在线阅读,更多相关《数学建模第二次作业(3)Word文件下载.doc(7页珍藏版)》请在冰点文库上搜索。
一、问题提出
某公司在六个城市C1、C2、C3、C4、C5、C6中都有分公司,从Ci到Cj的直达航班票价由下述矩阵的第i行、第j列元素给出(∞表示无直达航班),该公司想算出一张任意两个城市之间最廉价路线表,试做出这样的表来。
050∞402510
5001520∞25
∞1501020∞
40201001025
25∞2010055
1025∞25550
二、问题分析
若网络中的每条边都有一个数值(长度、成本、时间等),则找出两节点(通常是源节点和阱节点)之间总权和最小的路径就是最短路问题。
最短路问题是网络理论解决的典型问题之一,可用来解决管路铺设、线路安装、厂区布局和设备更新等实际问题。
最短路问题,我们通常归属为三类:
单源最短路径问题、确定起点终点的最短路径问题、全局最短路径问题———求图中所有的最短路径。
题中要求算出一张任意城市间的最廉价路线表,属于全局最短路问题,并且使得该公司总经理能够与各个子公司之间自由往返。
(此两点为主要约束条件)
Floyd算法,具体原理如下:
(1)我们确定本题为全局最短路问题,并采用求距离矩阵的方法
根据路线及票价表建立带权矩阵,并把带权邻接矩阵我w作为距离矩阵的初始值,即
(2)求路径矩阵的方法
在建立距离矩阵的同时可建立路径矩阵,,的含义是从到的最短路径要经过点号为的点。
(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)为飞机的最廉价矩阵。
五、模型求解结果
根据模型求解,分析得出任意两个城市之间最廉价线路及票价为:
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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 第二次 作业