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

《数学建模讲义 第8章图论与网络模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、去源点和汇点的流量等于网络总流量之外，其他点所有流入的流量和流出的流量相等。14231213710085最小生成树问题例：求以下带权图的最小生成树。求最小生成树已有成熟的算法：prim算法和Kruskal算法。具体可见图论方面的参考书。数学规划方法，用Lingo解决：根至少有一条边连接到其他点除根外,每个点只有一条边进入旅行商(TSP)问题一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？旅行商问题图论中没有成熟的算法，有改良圈算法，

3、但几乎不能找到最优解。数学规划方法，用Lingo解决：每个点只有一条边出去每个点只有一条边进入除起点和终点外，不构成回路。只能在有哈密顿回路的情况下。关键路径问题如下图，某个项目由4个作业（边）完成，每项作业需要一定时间（边的权值）完成，并且每项作业都需要在一定的状态（顶点）下才能开始，即要完成所有先行作业（所有进入该顶点的边）。求完成这个项目的最短时间。无回路有向赋权图中的最长路径：关键路径。142312137100关键路径问题图论中已有成熟的算法，具体可见数据结构或者图论方面的参考书。数学规划方法，用Lingo解决：

4、设xi是作业i的开始时间。目标：最后一个作业的开始时间最小。142312137100关键路径问题为了得到每个作业的最早开工时间和最迟开工时间，可更改模型如下：全部作业的开始时间最小当sij>0时，说明对应的作业的开始时间可以推迟sij，从而得到每个作业i的最迟开工时间。关键路径还可以看成最长路，用求最短路径的方法来求解。142312137100图论其他问题图的遍历：深度优先，广度有限平面图,着色问题二分图树：二叉树，二叉树遍历，编码，表达式