重庆邮电大学理学院：《图论及其应用》课程PPT教学课件_第4章 网络优化与Petri网

第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=满足 (1)图D中包含两个特定的顶点S和t,其中S只有出孤而没 有入弧(即入度为0),S称为发点或源;t只有入弧而没有出 弧(即出度为0),t称为收点或汇;D中的其余点既有出弧 又有入弧,称为中间点。 (2)在D的弧集E上定义非负函数C,称为容量函数,对任 意弧已=∈E(有时把简写成) 称C(e)=C()=Cu为弧的容量 此时,称有向图D构成一个网络,记为N=。 2021/12/10 重庆邮电大学 理学 院

4.1 网络流与截集 2021/12/10 重庆邮电大学 理学 院 5

图411所示的就是一个网络,其中孤上的数值为该孙容量 3 图41.1网络 2021/12/10 重庆邮电大学 理学 6 院

图 4.1.1 所示的就是一个网络，其中弧上的数值为该弧的容量。 图 4.1.1 网络2 4 37 2 61 51 2021/12/10 重庆邮电大学 理学 院 6

·对于任意一个有多个收、发点的网络N,可以在 上添加两个顶点S和t得到新的网N′,其中用容量 为∽的弧把S连接到V中每一个发点,用容量为∞的 弧把V中每一个收点连接到t,这时分别称和为超 级发点或超级源和超级收点或超级汇。 如图4.1.2,其中图(a)表示有三个发点两个收点的网 络,囹(b)表示添加了超级发点和超级收点的网络。 S 6 4 S (a) 图412超级发点与超级收点 021/12/10 理学院 7

2021/12/10 重庆邮电大学 理学院 7 5 5 4 2 6 4 3 3 2 (b) 图 4.1.2 超级发点与超级收点 (a) 4 2 6 4 3 3 2

定义412设N=是一个网络。称定义在弧集EA非负 函数F为网络N=上的流 对于弧e=∈E,F(e)=F(v,v>)称为弧e=∈E上的流量,记作同,即F(e)=F()=F1 ·称ΣeνF(即ΣvevF,下同)是流入j的流量或j的流入量; ·称Σ ey Fii是流出j的流量或j的流出量; 若Fj=Cj,即弧的流量已经达到它的容量,则称弧 在流F下是饱和的,否则称弧是不饱和的。 若流F满足 1)Fi≤Cij(称为限制条件或相容条件); (2)对于既不是源也不是汇的每个顶点,Σ ey Fi=∑evF (称为守恒条件或平衡条件,其中除非另有说明,总是对所 有步,而且如果不是边,则设F=0)。 中网络的一个可行流。 202l/12/10 重庆邮电大学 理学院 8

2021/12/10 重庆邮电大学 理学院 8

定理Ⅰ给定网络N=的一个流,其 为S,收点为t,则流出发点S流量等于流入收点t的 流量,即∑evFt=∑ i∈ VSi o 定义3给定网络N=的一个流,其发点 为S,收点为t,称值∑∈vFsi=∑evFt为流F的值, 记作V(F)。如图41.1中V(F)=10 图41.1网络 021/12/10 重 ""、 哩学院

2021/12/10 重庆邮电大学 理学院 9 图 4.1.1 网络 2 4 3 7 2 6 1 5 1

网络流研究中的一个基本问题是求网络N的一个 可行流F,而且还希望使得F达到最大值,即使 行流F成为网络N的最大流 般地,可能存在几个具有相同最大值的流。为 了给出一个求最大流的算法。下面我们再来介绍 网络的截集。 021/12/10 重庆邮电大学 理学院

2021/12/10 重庆邮电大学 理学院 10