第4章网络优化与Petr网
第4章 网络优化与Petri网
4.1网络流与截集 42最大流问题及其解法 ·4.3最小费用流算法 4.4Peti网
• 4.1 网络流与截集 • 4.2 最大流问题及其解法 • 4.3 最小费用流算法 • 4.4 Petri网
从某种意义上说,现代社会是一个由计算 机信息网络、通信网络、运输服务网络、 能源和物质分派网络等各种网络所组成的 复杂的网络系统。网络优化就是研究如何 有效地计划、管理和控制这个网络系统, 使之发挥出最大的社会和经济效益。 2021/12/10 重庆邮电大学 理学院
• 从某种意义上说，现代社会是一个由计算 机信息网络、通信网络、运输服务网络、 能源和物质分派网络等各种网络所组成的 复杂的网络系统。网络优化就是研究如何 有效地计划、管理和控制这个网络系统， 使之发挥出最大的社会和经济效益 。 2021/12/10 重庆邮电大学 理学院 3
网络优化是运筹学中的一个重要分支,所研 究的问题涉及经济管理、交通运输、计算机 科学与信息技术、通讯与网络技术等诸多领 域。在现实生活中,诸如最短路问题、运输 问题、指派问题、中国邮递员问题、旅行商 问题等都是网络优化的问题。 由于多数网络优化问题是以网络上的流为研 究对象,因此,在图论中一般只涉及网络流 问题。 重庆邮电大学 理学院
• 网络优化是运筹学中的一个重要分支，所研 究的问题涉及经济管理、交通运输、计算机 科学与信息技术、通讯与网络技术等诸多领 域。在现实生活中，诸如最短路问题、运输 问题、指派问题、中国邮递员问题、旅行商 问题等都是网络优化的问题。 • 由于多数网络优化问题是以网络上的流为研 究对象，因此，在图论中一般只涉及网络流 问题。 重庆邮电大学 理学院 4
4.1网络流与截集 定义4.1.1设有向连通图D=<V,E>满足 (1)图D中包含两个特定的顶点S和t,其中S只有出孤而没 有入弧(即入度为0),S称为发点或源;t只有入弧而没有出 弧(即出度为0),t称为收点或汇;D中的其余点既有出弧 又有入弧,称为中间点。 (2)在D的弧集E上定义非负函数C,称为容量函数,对任 意弧已=<vv>∈E(有时把<vv>简写成<i,j>) 称C(e)=C(<,v>)=Cu为弧的容量 此时,称有向图D构成一个网络,记为N=<V,E,C>。 2021/12/10 重庆邮电大学 理学 院
4.1 网络流与截集 2021/12/10 重庆邮电大学 理学 院 5