第四章-網(wǎng)絡(luò)優(yōu)化與petri網(wǎng)課件

第4章網(wǎng)絡(luò)優(yōu)化與Petri網(wǎng)4.1網(wǎng)絡(luò)流與截集4.2最大流問題及其解法4.3最小費用流算法4.4Petri網(wǎng)2023/7/27重慶郵電大學理學院1從某種意義上說，現(xiàn)代社會是一個由計算機信息網(wǎng)絡(luò)、通信網(wǎng)絡(luò)、運輸服務(wù)網(wǎng)絡(luò)、能源和物質(zhì)分派網(wǎng)絡(luò)等各種網(wǎng)絡(luò)所組成的復(fù)雜的網(wǎng)絡(luò)系統(tǒng)。網(wǎng)絡(luò)優(yōu)化就是研究如何有效地計劃、管理和控制這個網(wǎng)絡(luò)系統(tǒng)，使之發(fā)揮出最大的社會和經(jīng)濟效益

。2023/7/27重慶郵電大學理學院2網(wǎng)絡(luò)優(yōu)化是運籌學中的一個重要分支，所研究的問題涉及經(jīng)濟管理、交通運輸、計算機科學與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域。在現(xiàn)實生活中，諸如最短路問題、運輸問題、指派問題、中國郵遞員問題、旅行商問題等都是網(wǎng)絡(luò)優(yōu)化的問題。由于多數(shù)網(wǎng)絡(luò)優(yōu)化問題是以網(wǎng)絡(luò)上的流為研究對象，因此，在圖論中一般只涉及網(wǎng)絡(luò)流問題。2023/7/27重慶郵電大學理學院34.1網(wǎng)絡(luò)流與截集

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最大流及其算法就只有一個發(fā)點和一個收點的網(wǎng)絡(luò)而言，最大流問題就是在一個有容量的網(wǎng)絡(luò)中從發(fā)點到收點找出一條可以運送最大數(shù)量的單位流量的路徑，而且不得超過弧的容量。2023/7/27重慶郵電大學理學院15最大流問題的算法是由Ford和Fulkerson于1957最早提出的，其基本概念比較簡單，即從某個初始流開始，重復(fù)地增加流的值到不能再改進為止，則最后所得的流將是一個最大流。為此，不妨將每條邊上的流量設(shè)置為0作為初始流量。為了增加給定流量的值，我們必須找出從發(fā)點到收點的一條路并沿這條路增加流量。

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（最大流最小截定理）在任何網(wǎng)絡(luò)中，最大流的流量等于最小截集的容量。證明略2023/7/27重慶郵電大學理學院23定理定理3（整數(shù)流定理）在任何網(wǎng)絡(luò)中，如果網(wǎng)絡(luò)所有的弧容量都是整數(shù)，則存在整數(shù)最大流。證明略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)所示的容量網(wǎng)絡(luò)的最大流。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最小費用流算法前面所考慮的最大流問題是在一個有容量的網(wǎng)絡(luò)中，怎樣從發(fā)點向收點運送最大可能的流量問題。然而，在很多網(wǎng)絡(luò)中，除了容量，還涉及到費用問題。因此，本節(jié)我們將討論不僅要使網(wǎng)絡(luò)上的流達到最大或者達到要求的預(yù)定值，而且還要使運輸流的費用最小，即最小費用流問題。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網(wǎng)簡介2023/7/27重慶郵電大學理學院742023/7/27重慶郵電大學理學院75二、Petri網(wǎng)的定義2023/7/27重慶郵電大學理學院762023/7/27重慶郵電大學理學院772023/7/27重慶郵電大學理學院782023/7/27重慶郵電大學理學院792023/7/27重慶郵電大學理學院802023/7/27重慶郵電大學