数学建模-网络流.pdf

网络流 授课教师：陈六新 2023/4/19 1 重庆邮电大学 理学院 陈六新 ß 从某种意义上说，现代社会是一个由计算 机信息网络、通信网络、运输服务网络、 能源和物质分派网络等各种网络所组成的 复杂的网络系统。网络优化就是研究如何 有效地计划、管理和控制这个网络系统， 使之发挥出最大的社会和经济效益。 2023/4/19 2 重庆邮电大学 理学院 陈六新 ß 由于多数网络优化问题是以网络上的流为 研究对象，因此，在图论中一般只涉及网 络流问题。 2023/4/19 3 重庆邮电大学 理学院 陈六新 网络流与截集 ß   2023/4/19 4 重庆邮电大学 理学院 陈六新 2023/4/19 5 重庆邮电大学 理学院 陈六新 ß   2023/4/19 6 重庆邮电大学 理学院 陈六新 ß     2023/4/19 7 重庆邮电大学 理学院 陈六新 ß     2023/4/19 8 重庆邮电大学 理学院 陈六新 ß   2023/4/19 9 重庆邮电大学 理学院 陈六新 ß   2023/4/19 10 重庆邮电大学 理学院 陈六新 2023/4/19 11 重庆邮电大学 理学院 陈六新   2023/4/19 12 重庆邮电大学 理学院 陈六新 ß   2023/4/19 13 重庆邮电大学 理学院 陈六新 最大流及其算法 ß 就只有一个发点和一个收点的网络而言，最大流问 题就是在一个有容量的网络中从发点到收点找出一 条可以运送最大数量的单位流量的路径，而且不得 超过弧的容量。 • 最大流问题的算法是由Ford和Fulkerson于1957最早提 出的，其基本概念比较简单，即从某个初始流开始， 重复地增加流的值到不能再改进为止，则最后所得的 流将是一个最大流。为此，不妨将每条边上的流量设 置为0作为初始流量。为了增加给定流量的值，我们 必须找出从发点到收点的一条路并沿这条路增加