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

2、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域。在現(xiàn)實(shí)生活中，諸如最短路問題、運(yùn)輸問題、指派問題、中國(guó)郵遞員問題、旅行商問題等都是網(wǎng)絡(luò)優(yōu)化的問題。 由于多數(shù)網(wǎng)絡(luò)優(yōu)化問題是以網(wǎng)絡(luò)上的流為研究對(duì)象，因此，在圖論中一般只涉及網(wǎng)絡(luò)流問題。2022-4-10重慶郵電大學(xué) 理學(xué)院 34.1 4.1 網(wǎng)絡(luò)流與截集網(wǎng)絡(luò)流與截集2022-4-10重慶郵電大學(xué) 理學(xué)院 42022-4-10重慶郵電大學(xué) 理學(xué)院 52022-4-10重慶郵電大學(xué) 理學(xué)院 62022-4-10重慶郵電大學(xué) 理學(xué)院 72022-4-10重慶郵電大學(xué) 理學(xué)院 82022-4-10重慶郵電大學(xué) 理學(xué)院 92022-4-10重慶郵電大學(xué) 理學(xué)院 102022-4-

3、10重慶郵電大學(xué) 理學(xué)院 112022-4-10重慶郵電大學(xué) 理學(xué)院 122022-4-10重慶郵電大學(xué) 理學(xué)院 132022-4-10重慶郵電大學(xué) 理學(xué)院 142022-4-10重慶郵電大學(xué) 理學(xué)院 154.2 最大流及其算法 就只有一個(gè)發(fā)點(diǎn)和一個(gè)收點(diǎn)的網(wǎng)絡(luò)而言，最大流問最大流問題題就是在一個(gè)有容量的網(wǎng)絡(luò)中從發(fā)點(diǎn)到收點(diǎn)找出一條可以運(yùn)送最大數(shù)量的單位流量的路徑，而且不得超過弧的容量。2022-4-10重慶郵電大學(xué) 理學(xué)院 16 最大流問題的算法是由Ford和Fulkerson于1957最早提出的，其基本概念比較簡(jiǎn)單，即從某個(gè)初始流開始，重復(fù)地增加流的值到不能再改進(jìn)為止，則最后所得的流將是一個(gè)最

4、大流。為此，不妨將每條邊上的流量設(shè)置為0作為初始流量。為了增加給定流量的值，我們必須找出從發(fā)點(diǎn)到收點(diǎn)的一條路并沿這條路增加流量。2022-4-10重慶郵電大學(xué) 理學(xué)院 172022-4-10重慶郵電大學(xué) 理學(xué)院 182022-4-10重慶郵電大學(xué) 理學(xué)院 192022-4-10重慶郵電大學(xué) 理學(xué)院 202022-4-10重慶郵電大學(xué) 理學(xué)院 212022-4-10重慶郵電大學(xué) 理學(xué)院 22定理2022-4-10重慶郵電大學(xué) 理學(xué)院 23定理 定理定理2（最大流最小截定理）（最大流最小截定理） 在任何網(wǎng)絡(luò)中，最大流的流量等于最小截集的容量。 證明略2022-4-10重慶郵電大學(xué) 理學(xué)院 24定理

5、 定理定理3（整數(shù)流定理）（整數(shù)流定理）在任何網(wǎng)絡(luò)中，如果網(wǎng)絡(luò)所有的弧容量都是整數(shù)，則存在整數(shù)最大流。 證明略2022-4-10重慶郵電大學(xué) 理學(xué)院 25定理2022-4-10重慶郵電大學(xué) 理學(xué)院 26定理2022-4-10重慶郵電大學(xué) 理學(xué)院 272022-4-10重慶郵電大學(xué) 理學(xué)院 28算法思想2022-4-10重慶郵電大學(xué) 理學(xué)院 29最大流算法2022-4-10重慶郵電大學(xué) 理學(xué)院 30 例例4.2.1 用標(biāo)號(hào)法求圖4.2.2(a)所示的容量網(wǎng)絡(luò)的最大流。2022-4-10重慶郵電大學(xué) 理學(xué)院 312022-4-10重慶郵電大學(xué) 理學(xué)院 322022-4-10重慶郵電大學(xué) 理學(xué)院 3

6、32022-4-10重慶郵電大學(xué) 理學(xué)院 342022-4-10重慶郵電大學(xué) 理學(xué)院 352022-4-10重慶郵電大學(xué) 理學(xué)院 362022-4-10重慶郵電大學(xué) 理學(xué)院 372022-4-10重慶郵電大學(xué) 理學(xué)院 382022-4-10重慶郵電大學(xué) 理學(xué)院 394.3 最小費(fèi)用路算法 前面所考慮的最大流問題是在一個(gè)有容量的網(wǎng)絡(luò)中，怎樣從發(fā)點(diǎn)向收點(diǎn)運(yùn)送最大可能的流量問題。然而，在很多網(wǎng)絡(luò)中，除了容量，還涉及到費(fèi)用問題。因此，本節(jié)我們將討論不僅要使網(wǎng)絡(luò)上的流達(dá)到最大或者達(dá)到要求的預(yù)定值，而且還要使運(yùn)輸流的費(fèi)用最小，即最小費(fèi)用流問題。2022-4-10重慶郵電大學(xué) 理學(xué)院 402022-4-10

7、重慶郵電大學(xué) 理學(xué)院 412022-4-10重慶郵電大學(xué) 理學(xué)院 422022-4-10重慶郵電大學(xué) 理學(xué)院 432022-4-10重慶郵電大學(xué) 理學(xué)院 442022-4-10重慶郵電大學(xué) 理學(xué)院 452022-4-10重慶郵電大學(xué) 理學(xué)院 462022-4-10重慶郵電大學(xué) 理學(xué)院 472022-4-10重慶郵電大學(xué) 理學(xué)院 482022-4-10重慶郵電大學(xué) 理學(xué)院 492022-4-10重慶郵電大學(xué) 理學(xué)院 502022-4-10重慶郵電大學(xué) 理學(xué)院 51Klein算法算法2022-4-10重慶郵電大學(xué) 理學(xué)院 522022-4-10重慶郵電大學(xué) 理學(xué)院 532022-4-10重慶郵電大

8、學(xué) 理學(xué)院 542022-4-10重慶郵電大學(xué) 理學(xué)院 552022-4-10重慶郵電大學(xué) 理學(xué)院 562022-4-10重慶郵電大學(xué) 理學(xué)院 57二、最小二、最小費(fèi)用費(fèi)用路路算法算法2022-4-10重慶郵電大學(xué) 理學(xué)院 582022-4-10重慶郵電大學(xué) 理學(xué)院 59最小最小費(fèi)用費(fèi)用路路算法算法2022-4-10重慶郵電大學(xué) 理學(xué)院 602022-4-10重慶郵電大學(xué) 理學(xué)院 612022-4-10重慶郵電大學(xué) 理學(xué)院 622022-4-10重慶郵電大學(xué) 理學(xué)院 632022-4-10重慶郵電大學(xué) 理學(xué)院 64三、原始三、原始-對(duì)偶對(duì)偶算法算法2022-4-10重慶郵電大學(xué) 理學(xué)院 652

9、022-4-10重慶郵電大學(xué) 理學(xué)院 662022-4-10重慶郵電大學(xué) 理學(xué)院 672022-4-10重慶郵電大學(xué) 理學(xué)院 682022-4-10重慶郵電大學(xué) 理學(xué)院 69算法步驟：算法步驟：2022-4-10重慶郵電大學(xué) 理學(xué)院 702022-4-10重慶郵電大學(xué) 理學(xué)院 712022-4-10重慶郵電大學(xué) 理學(xué)院 722022-4-10重慶郵電大學(xué) 理學(xué)院 734.4 Petri網(wǎng)網(wǎng)簡(jiǎn)介簡(jiǎn)介2022-4-10重慶郵電大學(xué) 理學(xué)院 742022-4-10重慶郵電大學(xué) 理學(xué)院 75二、二、 Petri網(wǎng)的定義網(wǎng)的定義2022-4-10重慶郵電大學(xué) 理學(xué)院 762022-4-10重慶郵電大學(xué) 理學(xué)院 772022-4-10重慶郵電大學(xué) 理學(xué)院 782022-4-10重慶郵電大學(xué) 理學(xué)院 792022-4-10重慶郵電大學(xué) 理學(xué)院 802022-4-10重慶郵電大學(xué) 理學(xué)院 812022-4-10重慶郵電大學(xué) 理學(xué)院 82三、三、 Petri網(wǎng)的運(yùn)行網(wǎng)的運(yùn)行規(guī)則規(guī)則2022-4-10重慶郵電大學(xué) 理學(xué)院 832022-4-10重慶郵電大學(xué) 理學(xué)院 842022-4-10重慶郵電大學(xué) 理學(xué)院