数学建模【图与网络模型(图的基本概念与数据结构、最短路 | 您所在的位置:网站首页 › 图论与网络优化 › 数学建模【图与网络模型(图的基本概念与数据结构、最短路 |
🚀【MOOC数学建模与实验---学习笔记---整理汇总表】🚀 🌈【学习网址:MOOC---郑州轻工业大学---数学建模与实验】🌈 【第1、2章】【概述、软件介绍】【第3章】【数据处理方法】【第4章】【规划模型】【第5章】【图与网络模型】【第6章】【微分方程模型】【第7章】【统计模型】【第8章】【系统评价决策模型】【各个章节---作业题解析】目 录 5.1 图的基本概念与数据结构 5.1.1 图的基本概念 5.1.2 图与网络的数据结构 1.邻接矩阵表示法 2.稀疏矩阵表示法 5.2 最短路问题 5.2.1 问题描述 例5.2.1 求c1到其他城市的最短路 5.2.2 两指定顶点间的最短路径模型 例5.2.1 求c1到其他城市的最短路 5.2.3 每对顶点间的最短路径 例5.2.1 求c1到其他城市的最短路 5.3 最小生成树问题 5.3.1 生成树 5.3.2 最小生成树 1.Prim算法 2. Kruskal算法 5.4 网络最大流问题 5.4.1 基本概念 1.网络与流 2.可行流与最大流 3.增广路 5.4.2 求解最大流问题 例5.4.1 求从城市v1到城市v6的最大流 5.4.3 最小费用最大流问题 例5.4.2(续例5.4.1) 5.5 Matlab图论工具箱 5.5.1 Matlab图论工具箱命令介绍 1、graphallshortestpaths 求图中所有顶点对之间的最短距离 2、graphshortestpath 求图中指定的一对顶点间的最短距离和最短路径 3、graphminspantree 在图中找最小生成树 4、graphmaxflow 计算有向图的最大流 5.5.2 应用举例 例5.5.1 求有向图5.5.1中v1到v7的最短路径及长度. 例5.5.2 求有向图5.5.2中从1到8的最大流. 5.6 渡河问题 1.问题描述 2.问题分析 3.模型建立 4.模型求解 5.结果分析 6.模型应用 5.7 钢管的订购与运输 1.问题描述 2.符号假设 3.模型的建立与求解 (一)运费矩阵的计算模型 (二)总费用的数学规划模型 (三)模型求解 4.结果分析 5.1 图的基本概念与数据结构图与网络模型:建模中常用来描述的离散型模型。比如:交通问题、通讯问题、优化问题。 5.1.1 图的基本概念
哥尼斯堡七桥问题 A B C D 四个城市 ------ 不重复、不遗漏地一次走完七座桥,最后回到出发点。 18世纪初普鲁士的哥尼斯堡,有一条河穿过,河上有两个小岛,有七座桥把两个岛与河岸联系起来。有个人提出一个问题:一个步行者怎样才能不重复、不遗漏地一次走完七座桥,最后回到出发点。后来大数学家欧拉把它转化成一个几何问题——一笔画问题。他不仅解决了此问题,且给出了连通图可以一笔画的充要条件是:奇点的数目不是0 个就是2 个(连到一点的数目如是奇数条,就称为奇点,如果是偶数条就称为偶点,要想一笔画成,必须中间点均是偶点,也就是有来路必有另一条去路,奇点只可能在两端,因此任何图能一笔画成,奇点要么没有要么在两端)。 七桥所成之图形中,没有一点含有偶数条数,因此上述的任务无法完成。 图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型,借助于图论的概念、理论和方法,可以对该模型求解。哥尼斯堡七桥问题就是一个典型的例子。 1847年,德国物理学家克希霍夫为了给出电网络方程而引进了“树”的概念。哈密尔顿于1859年提出“周游世界”游戏,用图论的术语,就是如何找出一个连通图中的生成圈。近几十年来,由于计算机技术和科学的飞速发展,大大地促进了图论研究和应用,图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、运筹学、生物遗传学、心理学、经济学、社会学等学科中。
节点:图中的点。 点集:节点的集合。 边集:边的集合。 e22:环 v1、v3:回路
在Matlab中无向图和有向图邻接矩阵的使用上有很大差异。 对于有向图,只要写出邻接矩阵,直接使用Matlab的命令sparse命令,就可以把邻接矩阵转化为稀疏矩阵的表示方式。对于无向图,由于邻接矩阵是对称阵,Matlab中只需使用邻接矩阵的下三角元素,即Matlab只存储邻接矩阵下三角元素中的非零元素。稀疏矩阵只是一种存储格式。Matlab中,普通矩阵使用sparse命令变成稀疏矩阵,稀疏矩阵使用full命令变成普通矩阵。图论常见问题:最短路问题、最小生成树问题、最大流问题。 5.2.1 问题描述最短路问题就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。 有些问题,如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题,也可以归结为求最短路的问题。 因此这类问题在生产实际中得到广泛应用。 例5.2.1 求c1到其他城市的最短路设计城市c1到其他城市间的票价最便宜路线图 5.2.2 两指定顶点间的最短路径模型
迪杰斯特拉算法:先找到到临近节点的最短距离,然后一步步向远处延伸。 (1)初始步 (2)循环步 (3) i = |V| - 1 :V的度-1 例5.2.1 求c1到其他城市的最短路(1)求c1到其他城市的最短边。w16=10,最短。c1到c6,距离最短,将c6纳入S1中。将c6并入S1中。目标:S1、S1补集之间最短路 c1到c2、c3、c4、c5;c6到c1到c2、c3、c4、c5 (2)c1到c5、c6到c2,距离最短(权重最小)。将c1、c2、c5、c6并入S中。 (3)c5到c4,距离最短。找S2到S2补之间的最短路,保证不重复,避免重复搜索。 (4)c4到c3,距离最短。 1号城市🏙:...2号城市🏙:c16 -> c62:c1到c6 -> c6到c2【10+25=35】3号城市🏙:c15 -> c54 -> c43【25+10+10=45】4号城市🏙:c15 -> c54【25+10=35】5号城市🏙:c15【25】6号城市🏙:c16【10】 5.2.3 每对顶点间的最短路径计算赋权图中各对顶点之间的对短路径,显然可以调用Dijkstra算法,即每次以不同顶点作为起点,反复执行n-1次这样的操作, 但这种算法比较费时。另一种解决该问题的方法是由R.W.Floyd提出的,称为Floyd算法。
if a(i, j) > a(i, k) +a(k, j) a(i, j) = a(i, k) +a(k, j):城市i到城市j,间接连线 2-5 --> 4-7 --> 3-7 --> 1-2 --> 4-5 不能有回路,直到找到6条边。 网络最大流问题是网络的一个基本问题。许多系统包含了流量问题,例如交通系统有车流量,金融系统有现金流,控制系统有信息流等。许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。 5.4.1 基本概念 1.网络与流发点:从该点出发。 C={ (1) 对于发点vs: 对于收点vt:考虑有向弧(流量有方向) 在流量限制下,求最大流量(信息传输量、最大运输量)。 线性规划模型 目标函数:max v(f)---流量v(f)达到最大 发点:流出量v(f)收点:流入量-v(f)中间点:流出量-流入量=0 3.增广路
[dist] = graphallshortestpaths(G, ..., 'Directed', DirectedValue, ...) [dist] = graphallshortestpaths(G, ..., 'Weights', WeightsValue, ...) G是代表一个图的N*N稀疏矩阵,矩阵中的非零值代表一条边的权值;DirectedValue属性表示图是否为有向图,false代表无向图,true代表有向图,默认为true。WeightsValue是矩阵G中边的自定义权值列向量,该属性可以使我们使用零权值。输出[dist]是一个N*N的矩阵,每一个元素代表两点之间最短距离,对角线上的元素总为零,不在对角线上的零表示起点和终点的距离为零,inf值表示没有路径。 2、graphshortestpath 求图中指定的一对顶点间的最短距离和最短路径 graphshortestpath调用格式[dist, path] = graphshortestpath(G, S, T, 'Directed', Directedvalue) G表示图的下三角稀疏矩阵;S是最短路的起点;T是最短路终点;Directed为有向图或无向图标志,Directedvalue是属性值,false(或 0)代表无向图,true(或1)代表有向图,默认为true。dist为得到的最短距离;path为得到的最短路径。 3、graphminspantree 在图中找最小生成树 graphminspantree调用格式[Tree, pred] = graphminspantree(G) [Tree, pred] = graphminspantree(G, R) [Tree, pred] = graphminspantree(..., 'Method' ,MethodValue, ...) [Tree, pred] = graphminspantree(..., 'Weights', WeightsValue, ...) 该函数用来寻找一个无环的节点集合,连接无向图的全部节点,并且总的权值最小。Tree是一个代表生成树的稀疏矩阵,pred是包含 最小生成树的前驱节点的向量。G是无向图,R代表根节点,取值为1到节点数目,Method可以选择‘Kruskal’ , ’Prim’算法。 4、graphmaxflow 计算有向图的最大流 graphmaxflow调用格式[MaxFlow,FlowMatrix,Cut]=graphmaxflow(G,SNode,TNode) [...] = graphmaxflow(G, SNode, TNode, ...'Capacity', CapacityValue, ...) [...] = graphmaxflow(G, SNode, TNode, ...'Method', MethodValue, ...) G是N*N的稀疏矩阵,表示有向图,SNode和TNode都是G中的节点,分别表示起点和终点,CapacityValue为每条边自定义容量的列向量;MethodValue 可以取 ‘ Edmonds ’ 和 ‘ Goldberg ’ 算 法。输 出 MaxFlow表示最大流,FlowMatrix是表示每条边数据流值的稀疏矩阵,Cut表示连接SNode到TNode的逻辑向量,如果有多个解时,Cut 是一个矩阵。若只有一个解,Cut表示逻辑向量。 5.5.2 应用举例 例5.5.1 求有向图5.5.1中v1到v7的最短路径及长度.
解:Matlab图论工具箱求解最大流的命令graphmaxflow,只能解决权重都为正值,且两个顶点之间不能有两条弧的问题,图5.5.2中顶点 3、4之间有两条弧,可在顶点4和顶点3之间加入一个虚拟的顶点9,并添加两条弧,删除顶点4到顶点3的权重为2的弧,加入的两条弧的容量都是2。
z值:属性值向量,表示该网络流有唯一的最大流。 5.6 渡河问题图模型应用:渡河问题。 1.问题描述某人带狼、羊以及蔬菜渡河,一小船除需人划外,每次只能载一物过河。而人不在场时,狼要吃羊,羊要吃菜,问此人应如何过河? 2.问题分析人或物的状态有两个:河此岸或河对岸。 在同一岸边,人不在场时,不能将狼和羊、羊和蔬菜放同一岸。 该问题可用图论中的最短路算法进行求解。 用四维向量 通过穷举法可列出所有可行的状态: (1,1,1,1),(1,1,1,0),(1,1,0,1),(1,0,1,1),(1,0,1,0), (0,1,0,1),(0,1,0,0),(0,0,1,0),(0,0,0,1),(0,0,0,0). 每次渡河可改变现有状态为另一状态。 3.模型建立构造赋权图G=(V,E,W),顶点集合 问题变为在图G中寻找一条由初始状态(1,1,1,1)出发,经过最小次数转移到最终状态(0,0,0,0)的转移过程,即求从顶点
邻接矩阵 由于摆渡一次就改变现有状态,为此引入一个四维状态转移向量,用它来反映摆渡情况。用1表示渡河,用0表示未渡河。如 (1,1,0,0)表示人带狼渡河。状态转移只有4种情况,用如下向量表示:(1,0,0,0),(1,1,0,0),(1,0,1,0),(1,0,0,1) 邻接矩阵 定义状态向量与转移向量之间的运算为: 0+0=0,1+0=1,0+1=1,1+1=0 第一个数字代表状态;第二个数字代表转移【对岸、未渡河->对岸;此岸、未渡河->此岸;对岸、渡河->此岸;此岸、渡河->对岸】 根据定义,如果某一可行状态加上转移向量得到的新向量还是可行状态,则这两个可行状态对应的顶点之间就存在一条边。用计算机编程时,可以利用普通向量的”异或”运算实现。 ^ 逻辑异或 a^b,a和b结果不同为true,相同为false 4.模型求解用Matlab程序求解该最短路问题,如下 % clc,clear % 10行4列向量 每行是一可行状态 a=[1 1 1 1;1 1 1 0;1 1 0 1;1 0 1 1;1 0 1 0; 0 1 0 1;0 1 0 0;0 0 1 0;0 0 0 1;0 0 0 0]; b=[1 0 0 0;1 1 0 0;1 0 1 0;1 0 0 1]; %每行是一转移状态 w=zeros(10); %邻接矩阵初始化 for i=1:9 %i表示第一个状态 for j=i+1:10 %j表示另一个状态 上三角矩阵 for k=1:4 % k表示渡河情况 % 可行状态、转移状态之间的运算 a(j,:):其它的可行状态 if strfind(xor(a(i,:),b(k,:)),a(j,:)) %xor 表示异或运算 w(i,j)=1; % 如果运算结果是其它的某一可行状态,令对应的w(i,j)=1,否则为0 end end end end w=w'; %变成下三角矩阵 c=sparse(w); %构造稀疏矩阵 [x,y,z]=graphshortestpath(c,1,10,'Directed',0) %为无向图 h=view(biograph(c,[],'ShowArrows','off','ShowWeights','off')) %画无向图 Edges=getedgesbynodeid(h); %提取 h 中的边集x = 7:需要渡河7次; y:转移情况(1->6->3...); z:每个路径点的前驱节点 5.结果分析图G的状态转移关系见图5.6.2,根据求解结果,可得完成过河需要渡河7次,顶点的状态转移顺序为1,6,3,7,2,8,5,10。 即第1次,人带羊到对岸;第2次,人返回此岸;第3次,人带菜到对岸;第4次,人带羊到此岸;第5次,人带狼到对岸;第6次,人到此岸;第7次,人带羊到对岸。状态情况转移图 10个顶点,Node 1~Node 10,连接矩阵 6.模型应用该问题的求解方法可以推广到类似背景,不同条件下问题的一般决策过程。例如,n个人,m个物在限定条件下调度问题,可通过调整状态向量和转移向量,类似求解方法来完成。 5.7 钢管的订购与运输 1.问题描述要铺设一条 为方便计算,1km主管道钢管 称为 1单位钢管。 一家钢厂如果承担制造这种钢管,至少需要生产500个单位。钢厂在指定期限内能生产该钢管的最大数量为 1000km以上每增加1km~100km运价增加5万元。公路运输费为1单位钢管每千米0.1万元(不足整千米部分按整千米计算)。钢管可由铁路、公路运往铺设地点(不只是运到 (1)请制定一个主管道钢管的订购与运输计划,使总费用最小(给 出总费用)。 (2)请就(1)的模型分析:哪家钢厂钢管的销价的变化对购运计划和总费用影响最大,哪家钢厂的钢管的产量的上限的变化对购运计划和总费用的影响最大,并给出相应的数字结果。 2.符号假设设 根据问题所给的数据,可以先计算从供应点 (一)运费矩阵的计算模型 (1)计算铁路任意两点间的最小运输费用 由于铁路运费不是连续的,故不能直接构造铁路费用赋权图,用Floyd算法来计算任意两点间的最小运输费用。但可以首先构造铁路距离赋权图,用Floyd算法计算任意两点间的最短铁路距离值,再依据表5.7.2中的铁路运价,求出任意两点间的最小铁路运输费用。 钢厂节点S1~S7,管道节点A1~A15,火车站位置B1~B17:一共39个节点 邻接矩阵W1 0.1:单位公路里程的运价 纵坐标:钢厂节点S1~S7; 横坐标:管道节点A1~A15 xij对i求和:第i个钢厂到第j个节点的运输量。 xij:第i个钢厂到第j个节点的运输量。 下限 500;上限 si (三)模型求解 |
CopyRight 2018-2019 实验室设备网 版权所有 |