数学建模讲义 第8章图论与网络模型.ppt

《数学建模讲义 第8章图论与网络模型.ppt》由会员分享，可在线阅读，更多相关《数学建模讲义 第8章图论与网络模型.ppt（13页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、文法系文法系 高等数学教研室高等数学教研室数学建模多媒体课件第6章 图与网络模型最短路径问题最短路径问题例：求以下带权图从V0到V6最短路径。l邻接矩阵Ml权值表示两点之间的长度求最短路已有成熟的算法：迪杰斯特拉（Dijkstra）算法。具体可见数据结构或者图论方面的参考书。数学规划方法，用Lingo解决：起点多一条边出去终点多一条边进入其他点进入的边数等于出去的边数最大流问题最大流问题例：求以下带权有向图从V1到V4的最大流。权值权值表示两点之间的流量限制表示两点之间的流量限制14231213710085求最大流已有成熟的算法：标号法求最大流已有成熟的算法：标号法 （Ford-Fulkers

2、on算法算法）。具体可见图论。具体可见图论方面的参考书。方面的参考书。数学规划方法，用数学规划方法，用Lingo解决：解决：l除去源点和汇点的流量等于网络总流量之外，除去源点和汇点的流量等于网络总流量之外，其他点所有流入的流量和流出的流量相等。其他点所有流入的流量和流出的流量相等。14231213710085最小生成树问题最小生成树问题例：求以下带权图的最小生成树。求最小生成树已有成熟的算法：求最小生成树已有成熟的算法：primprim算法算法和和KruskalKruskal算法算法。具体可见图论方面的参。具体可见图论方面的参考书。考书。数学规划方法，用数学规划方法，用Lingo解决：解决：根

3、根至少有一条边连接到其他点至少有一条边连接到其他点除根外除根外,每个点只有一条边进每个点只有一条边进入入旅行商旅行商(TSP)问题问题一名推销员准备前往若干城市推销产品，一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？城市恰好一次，最后返回驻地）？旅行商问题图论中没有成熟的算法，有改旅行商问题图论中没有成熟的算法，有改良圈算法良圈算法，但几乎不能找到最优解。，但几乎不能找到最优解。数学规划方法，用数学规划方法，用Lingo解决：解决：

4、每个点只有一条边出去每个点只有一条边进入除起点和终点外，不构成回路。只能在有哈密顿回路的情况下。关键路径问题关键路径问题如下图，某个项目由如下图，某个项目由4个作业（边）完成，每项个作业（边）完成，每项作业需要一定时间（边的权值）完成，并且每项作业需要一定时间（边的权值）完成，并且每项作业都需要在一定的状态（顶点）下才能开始，作业都需要在一定的状态（顶点）下才能开始，即要完成所有先行作业（所有进入该顶点的边）。即要完成所有先行作业（所有进入该顶点的边）。求完成这个项目的最短时间。求完成这个项目的最短时间。无回路有向赋权图中的最长路径：关键路径。无回路有向赋权图中的最长路径：关键路径。14231

5、2137100关键路径问题图论中已有成熟的算法，具体可见数据结构或者图论方面的参考书。数学规划方法，用Lingo解决：设xi是作业i的开始时间。目标：最后一个作业的开始时间最小。142312137100关键路径问题关键路径问题为了得到每个作业的最早开工时间和最迟为了得到每个作业的最早开工时间和最迟开工时间，可更改模型如下：开工时间，可更改模型如下：全部作业的开始时间最小l当sij0时，说明对应的作业的开始时间可以推迟sij，从而得到每个作业i的最迟开工时间。l关键路径还可以看成最长路，用求最短路径的方法来求解。142312137100图论其他问题图论其他问题图的遍历：深度优先，广度有限平面图,着色问题二分图树：二叉树，二叉树遍历，编码，表达式