第四章-网络优化与petri网课件

第4章网络优化与Petri网4.1网络流与截集4.2最大流问题及其解法4.3最小费用流算法4.4Petri网2023/7/27重庆邮电大学理学院1从某种意义上说，现代社会是一个由计算机信息网络、通信网络、运输服务网络、能源和物质分派网络等各种网络所组成的复杂的网络系统。网络优化就是研究如何有效地计划、管理和控制这个网络系统，使之发挥出最大的社会和经济效益

。2023/7/27重庆邮电大学理学院2网络优化是运筹学中的一个重要分支，所研究的问题涉及经济管理、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。在现实生活中，诸如最短路问题、运输问题、指派问题、中国邮递员问题、旅行商问题等都是网络优化的问题。由于多数网络优化问题是以网络上的流为研究对象，因此，在图论中一般只涉及网络流问题。2023/7/27重庆邮电大学理学院34.1网络流与截集

2023/7/27重庆邮电大学理学院42023/7/27重庆邮电大学理学院5

2023/7/27重庆邮电大学理学院6

2023/7/27重庆邮电大学理学院7

2023/7/27重庆邮电大学理学院8

2023/7/27重庆邮电大学理学院9

2023/7/27重庆邮电大学理学院102023/7/27重庆邮电大学理学院11

2023/7/27重庆邮电大学理学院12

2023/7/27重庆邮电大学理学院13

2023/7/27重庆邮电大学理学院144.2最大流及其算法就只有一个发点和一个收点的网络而言，最大流问题就是在一个有容量的网络中从发点到收点找出一条可以运送最大数量的单位流量的路径，而且不得超过弧的容量。2023/7/27重庆邮电大学理学院15最大流问题的算法是由Ford和Fulkerson于1957最早提出的，其基本概念比较简单，即从某个初始流开始，重复地增加流的值到不能再改进为止，则最后所得的流将是一个最大流。为此，不妨将每条边上的流量设置为0作为初始流量。为了增加给定流量的值，我们必须找出从发点到收点的一条路并沿这条路增加流量。

2023/7/27重庆邮电大学理学院16

2023/7/27重庆邮电大学理学院17

2023/7/27重庆邮电大学理学院18

2023/7/27重庆邮电大学理学院19

2023/7/27重庆邮电大学理学院20

2023/7/27重庆邮电大学理学院21定理

2023/7/27重庆邮电大学理学院22定理定理2（最大流最小截定理）在任何网络中，最大流的流量等于最小截集的容量。证明略2023/7/27重庆邮电大学理学院23定理定理3（整数流定理）在任何网络中，如果网络所有的弧容量都是整数，则存在整数最大流。证明略2023/7/27重庆邮电大学理学院24定理

2023/7/27重庆邮电大学理学院25定理

2023/7/27重庆邮电大学理学院26

2023/7/27重庆邮电大学理学院27算法思想

2023/7/27重庆邮电大学理学院28最大流算法2023/7/27重庆邮电大学理学院29例4.2.1用标号法求图4.2.2(a)所示的容量网络的最大流。2023/7/27重庆邮电大学理学院302023/7/27重庆邮电大学理学院312023/7/27重庆邮电大学理学院322023/7/27重庆邮电大学理学院332023/7/27重庆邮电大学理学院342023/7/27重庆邮电大学理学院352023/7/27重庆邮电大学理学院36

2023/7/27重庆邮电大学理学院37

2023/7/27重庆邮电大学理学院384.3最小费用流算法前面所考虑的最大流问题是在一个有容量的网络中，怎样从发点向收点运送最大可能的流量问题。然而，在很多网络中，除了容量，还涉及到费用问题。因此，本节我们将讨论不仅要使网络上的流达到最大或者达到要求的预定值，而且还要使运输流的费用最小，即最小费用流问题。2023/7/27重庆邮电大学理学院39

2023/7/27重庆邮电大学理学院402023/7/27重庆邮电大学理学院412023/7/27重庆邮电大学理学院422023/7/27重庆邮电大学理学院432023/7/27重庆邮电大学理学院442023/7/27重庆邮电大学理学院452023/7/27重庆邮电大学理学院462023/7/27重庆邮电大学理学院472023/7/27重庆邮电大学理学院482023/7/27重庆邮电大学理学院492023/7/27重庆邮电大学理学院50Klein算法2023/7/27重庆邮电大学理学院512023/7/27重庆邮电大学理学院522023/7/27重庆邮电大学理学院532023/7/27重庆邮电大学理学院542023/7/27重庆邮电大学理学院552023/7/27重庆邮电大学理学院562023/7/27重庆邮电大学理学院57二、最小费用路算法2023/7/27重庆邮电大学理学院582023/7/27重庆邮电大学理学院59最小费用路算法2023/7/27重庆邮电大学理学院602023/7/27重庆邮电大学理学院612023/7/27重庆邮电大学理学院622023/7/27重庆邮电大学理学院632023/7/27重庆邮电大学理学院64三、原始-对偶算法2023/7/27重庆邮电大学理学院652023/7/27重庆邮电大学理学院662023/7/27重庆邮电大学理学院672023/7/27重庆邮电大学理学院682023/7/27重庆邮电大学理学院69算法步骤：2023/7/27重庆邮电大学理学院702023/7/27重庆邮电大学理学院712023/7/27重庆邮电大学理学院722023/7/27重庆邮电大学理学院734.4Petri网简介2023/7/27重庆邮电大学理学院742023/7/27重庆邮电大学理学院75二、Petri网的定义2023/7/27重庆邮电大学理学院762023/7/27重庆邮电大学理学院772023/7/27重庆邮电大学理学院782023/7/27重庆邮电大学理学院792023/7/27重庆邮电大学理学院802023/7/27重庆邮电大学