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

第4章 网络优化与Petri网4.1 4.1 网络流与截集网络流与截集4.2 4.2 最大流问题及其解法最大流问题及其解法4.3 4.3 最小费用流算法最小费用流算法4.4 Petri4.4 Petri网网2024/8/7重庆邮电大学 理学院 1从某种意义上说，现代社会是一个由计算机信息网络、通信网络、运输服务网络、能源和物质分派网络等各种网络所组成的复杂的网络系统。网络优化就是研究如何有效地计划、管理和控制这个网络系统，使之发挥出最大的社会和经济效益。2024/8/7重庆邮电大学 理学院 2网络优化是运筹学中的一个重要分支，所研究的问题涉及经济管理、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。在现实生活中，诸如最短路问题、运输问题、指派问题、中国邮递员问题、旅行商问题等都是网络优化的问题。由于多数网络优化问题是以网络上的流为研究对象，因此，在图论中一般只涉及网络流问题。2024/8/7重庆邮电大学 理学院 34.1 4.1 网络流与截集网络流与截集2024/8/7重庆邮电大学 理学院 42024/8/7重庆邮电大学 理学院 52024/8/7重庆邮电大学 理学院 62024/8/7重庆邮电大学 理学院 72024/8/7重庆邮电大学 理学院 82024/8/7重庆邮电大学 理学院 92024/8/7重庆邮电大学 理学院 102024/8/7重庆邮电大学 理学院 112024/8/7重庆邮电大学 理学院 122024/8/7重庆邮电大学 理学院 132024/8/7重庆邮电大学 理学院 144.2 最大流及其算法就只有一个发点和一个收点的网络而言，最大流问最大流问题题就是在一个有容量的网络中从发点到收点找出一条可以运送最大数量的单位流量的路径，而且不得超过弧的容量。2024/8/7重庆邮电大学 理学院 15最大流问题的算法是由Ford和Fulkerson于1957最早提出的，其基本概念比较简单，即从某个初始流开始，重复地增加流的值到不能再改进为止，则最后所得的流将是一个最大流。为此，不妨将每条边上的流量设置为0作为初始流量。为了增加给定流量的值，我们必须找出从发点到收点的一条路并沿这条路增加流量。2024/8/7重庆邮电大学 理学院 162024/8/7重庆邮电大学 理学院 172024/8/7重庆邮电大学 理学院 182024/8/7重庆邮电大学 理学院 192024/8/7重庆邮电大学 理学院 202024/8/7重庆邮电大学 理学院 21定理2024/8/7重庆邮电大学 理学院 22定理定理定理2（最大流最小截定理）（最大流最小截定理）在任何网络中，最大流的流量等于最小截集的容量。证明略2024/8/7重庆邮电大学 理学院 23定理定理定理3（整数流定理）（整数流定理）在任何网络中，如果网络所有的弧容量都是整数，则存在整数最大流。证明略2024/8/7重庆邮电大学 理学院 24定理2024/8/7重庆邮电大学 理学院 25定理2024/8/7重庆邮电大学 理学院 262024/8/7重庆邮电大学 理学院 27算法思想2024/8/7重庆邮电大学 理学院 28最大流算法2024/8/7重庆邮电大学 理学院 29例例4.2.1 用标号法求图4.2.2(a)所示的容量网络的最大流。2024/8/7重庆邮电大学 理学院 302024/8/7重庆邮电大学 理学院 312024/8/7重庆邮电大学 理学院 322024/8/7重庆邮电大学 理学院 332024/8/7重庆邮电大学 理学院 342024/8/7重庆邮电大学 理学院 352024/8/7重庆邮电大学 理学院 362024/8/7重庆邮电大学 理学院 372024/8/7重庆邮电大学 理学院 384.3 最小费用流算法前面所考虑的最大流问题是在一个有容量的网络中，怎样从发点向收点运送最大可能的流量问题。然而，在很多网络中，除了容量，还涉及到费用问题。因此，本节我们将讨论不仅要使网络上的流达到最大或者达到要求的预定值，而且还要使运输流的费用最小，即最小费用流问题。2024/8/7重庆邮电大学 理学院 392024/8/7重庆邮电大学 理学院 402024/8/7重庆邮电大学 理学院 412024/8/7重庆邮电大学 理学院 422024/8/7重庆邮电大学 理学院 432024/8/7重庆邮电大学 理学院 442024/8/7重庆邮电大学 理学院 452024/8/7重庆邮电大学 理学院 462024/8/7重庆邮电大学 理学院 472024/8/7重庆邮电大学 理学院 482024/8/7重庆邮电大学 理学院 492024/8/7重庆邮电大学 理学院 50Klein算法算法2024/8/7重庆邮电大学 理学院 512024/8/7重庆邮电大学 理学院 522024/8/7重庆邮电大学 理学院 532024/8/7重庆邮电大学 理学院 542024/8/7重庆邮电大学 理学院 552024/8/7重庆邮电大学 理学院 562024/8/7重庆邮电大学 理学院 57二、最小费用路二、最小费用路算法算法2024/8/7重庆邮电大学 理学院 582024/8/7重庆邮电大学 理学院 59最小费用路算法最小费用路算法2024/8/7重庆邮电大学 理学院 602024/8/7重庆邮电大学 理学院 612024/8/7重庆邮电大学 理学院 622024/8/7重庆邮电大学 理学院 632024/8/7重庆邮电大学 理学院 64三、原始三、原始-对偶对偶算法算法2024/8/7重庆邮电大学 理学院 652024/8/7重庆邮电大学 理学院 662024/8/7重庆邮电大学 理学院 672024/8/7重庆邮电大学 理学院 682024/8/7重庆邮电大学 理学院 69算法步骤：算法步骤：2024/8/7重庆邮电大学 理学院 702024/8/7重庆邮电大学 理学院 712024/8/7重庆邮电大学 理学院 722024/8/7重庆邮电大学 理学院 734.4 Petri网网简介简介2024/8/7重庆邮电大学 理学院 742024/8/7重庆邮电大学 理学院 75二、二、Petri网的定义网的定义2024/8/7重庆邮电大学 理学院 762024/8/7重庆邮电大学 理学院 772024/8/7重庆邮电大学 理学院 782024/8/7重庆邮电大学 理学院 792024/8/7重庆邮电大学 理学院 802024/8/7重庆邮电大学 理学院 812024/8/7重庆邮电大学 理学院 82三、三、Petri网的运行网的运行规则规则2024/8/7重庆邮电大学 理学院 832024/8/7重庆邮电大学 理学院 842024/8/7重庆邮电大学 理学院 852024/8/7重庆邮电大学 理学院 86四、四、Petri网的网的性能性能2024/8/7重庆邮电大学 理学院 872024/8/7重庆邮电大学 理学院 882024/8/7重庆邮电大学 理学院 892024/8/7重庆邮电大学 理学院 902024/8/7重庆邮电大学 理学院 91