2016数学建模提高班专题六网络优化模型及案例分析资料

《2016数学建模提高班专题六网络优化模型及案例分析资料》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2016数学建模提高班——网络优化模型及案例分析专题梦想点燃激情，激情成就未来赵承业2016/5/7内部资料，版权所有，请勿外传，侵权必究内容提要从农夫怎样过河谈起图是一种思考问题的方法最短路问题最小生成树问题旅行商问题Matlab的图论工具箱从农夫怎样过河谈起农夫过河独木桥一般过河问题的解决策略选课问题农夫过河4农夫过河摆渡人F狼W羊G菜C5南岸状态：16种，其中WG,GC,WGC，从而FC,FW,F为不允许状态，FWGCFWGFWCFGCFGOCGWWC10个允许状态：农夫过河6FWGCFWGFWCFGCFGOCGWWC寻求图中从顶点“FWGC”到

2、顶点“O”的最短路径，这样的路径有几条？求出最优的渡河方案。想语言描述时未显示的关系跃然纸上农夫过河7FWGCFWGFWCFGCFGOCGWWCFWGCFWGFWCFGCFGOCGWWC农夫过河8独木桥9一般过河问题的解决策略多少种状态状态如何转换花的时间怎么计算最后求什么10选课问题学校要为一年级的研究生开设六门基础数学课：统计(S)，数值分析(N)，图论(G)，矩阵论(M)，随机过程(R)和数理方程(P)。按培养计划，注册的学生必须选修其中的一门以上，你作为教务管理人员，要设法安排一个课表，使每个学生所选的课程，在时间上不会发生冲突。11选课问题

3、12选课问题为什么会出现时间上的冲突？时间冲突的本质是什么？如何表示课程在时间上冲突？如果把一门课程看成图中的顶点，那么连接两点的边表示什么？13SNGRPM‡完成上述表示课程冲突关系的线图直观、清晰地表达已知信息的方式14图是一种思考问题的方法图有两个基本要素--顶点和边顶点表示事物边表示两个事物之间的关系增加第三个要素--边的权值可以表示关系深浅、大小、重要等程度用图来思考问题本质是考虑事物之间的联系15图是一种思考问题的方法图可以画出来v1v2v5v6v7v4v3abjkcghidfe16图是一种思考问题的方法图也可以用矩阵来表示，最常用的是邻接

4、矩阵v1v2v5v6v7v4v3abjkcghidfe17邻接矩阵的优点：容易理解容易转换为具体的图便于计算机编程计算图是一种思考问题的方法18最短路问题固定起点的最短路每对顶点之间的最短路选址问题固定起点的最短路最短路是一条路径，且最短路的任一段也是最短路．假设在u0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树．因此,可采用树生长的过程来求指定顶点到其余顶点的最短路．2021算法步骤：22TOMATLAB(road1)23241234567825每对顶点之间的最短路1．求距离矩阵的方法2．求路径矩阵的方法3．查找最短路

5、路径的方法（一）算法的基本思想（三）算法步骤26算法的基本思想27算法原理——求距离矩阵的方法28算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R．即当k被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．)(nR29ij算法原理——查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：30算法步骤31TOMATLAB(road2(floyd))32选址问题--中心问题TOMATLAB(road3(floyd))33S(v1)=10,S(v2)=7,S(v3)=6,

6、S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处.34选址问题--重心问题35最小生成树问题树图最小生成树Kruskal算法Prim算法赵根赵明赵亮赵丽赵雷赵虹赵雨赵霞赵云赵梅赵松树图——直观形象的表示工具类似于自然界中的树形象地表示家族37树：没有圈的连通图树中任意两点间有唯一路径。树的边数恰好为顶点数减1。树图——直观形象的表示工具38城市电信局有许多业务如收费，营业，112，114等，希望在全市范围实现计算机联网服务，共享各种资源。一个主要关心的问题是：用数据通讯线把一组站点联结起来

7、，而不允许通讯线在非站点处相交，如何连接可使通讯线的花费最小？引例：计算机网络的线路设计3912345869157103引例：计算机网络的线路设计最经济的网络不应该有任何封闭的回路。40引例：计算机网络的线路设计生成树或支撑树(spanningtree)：G的子图且是树，其顶点集等于G的顶点集；12345869157103如何简便地得到左图的生成树？它应有几条边？想41确定应在哪些站点之间铺设通讯线路，是否可看作是在相应的加权图中构造最小费用的生成树的问题？引例：计算机网络的线路设计42最小生成树最大生成树引例：计算机网络的线路设计想1)一个完全图

8、Kn有多少不同的生成树？2)如何求其最小生成树?4310个顶点的完全图，其不同的生成树就有一亿