《運(yùn)籌學(xué)》 課件 第7-11章 圖與網(wǎng)絡(luò)-存儲(chǔ)論

第7章圖與網(wǎng)絡(luò)17/16/2024CONTENTS2目錄7/16/20247.1

圖與網(wǎng)絡(luò)的基本概念7.2

樹7.3

最短路問題7.4

最大流問題7.5

最小費(fèi)用流問題7.6

中國(guó)郵遞員問題7.7

網(wǎng)絡(luò)計(jì)劃37/16/202418世紀(jì)，歐洲有一個(gè)風(fēng)景秀麗的小城哥尼斯堡（今俄羅斯加里寧格勒）。那里的普萊格爾河上有七座橋，將河中的兩個(gè)島和河岸連結(jié)。城中的居民經(jīng)常沿河過橋散步，于是提出了一個(gè)問題：一個(gè)人怎樣才能一次走遍七座橋，每座橋只走過一次，最后回到出發(fā)點(diǎn)？大家都試圖找出問題的答案，但是誰(shuí)也解決不了這個(gè)問題………這就是哥尼斯堡七橋問題。

哥尼斯堡七橋問題47/16/2024LeonhardEuler(1707-1783)瑞士數(shù)學(xué)家他把這個(gè)難題進(jìn)行了轉(zhuǎn)換：把二岸和小島縮成點(diǎn)，橋化為邊，于是“七橋問題”就等價(jià)于下圖（B）中所畫圖形的一筆畫問題了。哥尼斯堡七橋問題經(jīng)過研究，歐拉發(fā)現(xiàn)了一筆畫的規(guī)律：i)能一筆畫的圖形必須是連通圖ii)全部由偶點(diǎn)組成的連通圖只有兩個(gè)奇點(diǎn)其余均為偶點(diǎn)的連通圖哥尼斯堡七橋問題57/16/202467/16/20241857年，英國(guó)數(shù)學(xué)家Hamiltion發(fā)明了一種游戲。他用一個(gè)實(shí)心正12面體象征地球，正12面體的20個(gè)頂點(diǎn)分別表示世界上20座名城，要求游戲者從任一城市出發(fā)，尋找一條可經(jīng)由每個(gè)城市一次且僅一次再回到原出發(fā)點(diǎn)的路，也稱“環(huán)球旅行”問題。圖與網(wǎng)絡(luò)哈密頓圈問題有位農(nóng)夫，攜帶一匹狼、一只羊和一挑草要過一條小河。河中只有一條小船，一次擺渡農(nóng)夫只能帶狼、羊、草中的一樣。當(dāng)農(nóng)夫不在場(chǎng)時(shí)，狼要吃羊，羊要吃草。試問農(nóng)夫怎樣才能將這三樣?xùn)|西擺渡到河對(duì)岸。至少要擺渡幾次？農(nóng)夫過河77/16/2024用M、W、S、G分別代表人、狼、羊、草。①[M,W,S,G][?]②[M,W][S,G]③[M,S][W,G] ④[M,G][W,S]⑤[M,W,S][G] ⑥[M,W,G][S]⑦[W,S,G][M] ⑧[M,S,G][W]上面組合中②、④、⑦是不允許的。去掉這三個(gè)組合中的六個(gè)狀態(tài)，那么可能的狀態(tài)有10個(gè)。按照狀態(tài)中是否有人存在，將它們分為兩組，如圖所示。[M,W,S,G]V16VV72VV38VV49VV510V[M,S][W,G][

][G

][S

][W

][M,W,S][M,W,G][M,S,G]87/16/2024農(nóng)夫過河中國(guó)郵遞員問題(ChinesePostmanProblem,CPP):

一個(gè)郵遞員負(fù)責(zé)一個(gè)地區(qū)的信件投遞，他每天要從郵局出發(fā)，走遍該地區(qū)所有街道，最后返回到郵局，問如何安排送信的路線使所走路程最短？旅行售貨商問題(TravelingSalesmanProblem,TSP):賣貨郎走遍一個(gè)區(qū)域內(nèi)的所有村莊一次，使得所走路程最短?要在若干個(gè)城市之間架設(shè)電網(wǎng)(或鋪設(shè)管道),如何選擇一個(gè)聯(lián)系所有城市的電網(wǎng)(管網(wǎng)結(jié)構(gòu))?在一個(gè)已有的道路網(wǎng)絡(luò)(管網(wǎng)、通信網(wǎng)絡(luò)等)，已知每條線路(管道)的容量，網(wǎng)絡(luò)上可通行的最大流量是多少？…………97/16/2024更多實(shí)用意義的問題實(shí)際應(yīng)用7.1圖與網(wǎng)絡(luò)的基本概念自然界和人類社會(huì)中，大量的事物以及事物之間的關(guān)系可以用圖形來描述。電路網(wǎng)絡(luò)、城市規(guī)劃、交通運(yùn)輸、物資調(diào)配……我們生活在一個(gè)網(wǎng)絡(luò)社會(huì)中，從某種意義上說，現(xiàn)代社會(huì)是一個(gè)由各種網(wǎng)絡(luò)所組成的復(fù)雜的網(wǎng)絡(luò)系統(tǒng)。計(jì)算機(jī)信息網(wǎng)絡(luò)電話通信網(wǎng)絡(luò)運(yùn)輸服務(wù)網(wǎng)絡(luò)能源和物資分派網(wǎng)絡(luò)……01圖與網(wǎng)絡(luò)的基本概念7.1圖與網(wǎng)絡(luò)基本概念117/16/2024VS平面幾何中的圖關(guān)心圖中有多少個(gè)點(diǎn)

關(guān)心點(diǎn)與點(diǎn)之間有無(wú)連線這里研究的圖是反映對(duì)象之間關(guān)系的一種工具從形形色色的具體實(shí)際問題中抽象而來

研究其共同的性質(zhì)、規(guī)律和方法7.1圖與網(wǎng)絡(luò)基本概念127/16/2024137/16/20247.1.1圖與子圖頂點(diǎn)/節(jié)點(diǎn)

(Vertex)物理實(shí)體、事物、概念一般用

vi

表示邊

(Edge)節(jié)點(diǎn)間的連線，表示有關(guān)系一般用

eij

表示圖

(Graph)節(jié)點(diǎn)和邊的集合一般用

G(V,E)表示點(diǎn)集

V={v1,v2,…,vn}邊集

E={eij}

無(wú)向圖，有向圖147/16/2024邊都沒有方向的圖稱為無(wú)向圖，即

eij=eji或

(vi,vj)=(vj,vi)當(dāng)邊都有方向時(shí)，稱為有向圖，即在有序?qū)?/p>

(vi,vj)中，vi表示始點(diǎn)，vj表示終點(diǎn)在有向圖中，有向邊又稱為弧，用

aij表示，i,j的順序是不能顛倒的，圖中弧的方向用箭頭標(biāo)識(shí)圖中既有邊又有弧，稱為混合圖7.1.1圖與子圖環(huán)多重邊注：有向圖中兩點(diǎn)之間有不同方向的兩條邊，不是多重邊。

簡(jiǎn)單圖，多重圖一個(gè)邊的兩個(gè)端點(diǎn)如果相同，稱為環(huán)兩個(gè)點(diǎn)之間如果多于一條邊，稱為多重邊不含環(huán)和多重邊的圖稱為簡(jiǎn)單圖；含有多重邊的圖稱為多重圖01圖與網(wǎng)絡(luò)的基本概念157/16/20247.1.1圖與子圖

完全圖，偶圖一個(gè)簡(jiǎn)單圖中，若任意兩點(diǎn)之間均有邊相連，則稱為完全圖

n個(gè)頂點(diǎn)的完全圖，邊數(shù)有n(n-1)/2條若圖的頂點(diǎn)能分成兩個(gè)互不相交的非空集合

V1和V2，使在同一集合中的任意兩個(gè)頂點(diǎn)均不相鄰，稱為偶圖（二分圖，bipartition）V1V2167/16/20247.1.1圖與子圖無(wú)向圖中，與節(jié)點(diǎn)v關(guān)聯(lián)的邊數(shù)，稱為該節(jié)點(diǎn)的次或度，記為deg(v)，或d(v)對(duì)任意節(jié)點(diǎn)v，若度數(shù)d(v)為奇數(shù)，則稱此節(jié)點(diǎn)為奇點(diǎn)，若度數(shù)d(v)為偶數(shù)，則稱此節(jié)點(diǎn)為偶點(diǎn)次為1的點(diǎn)稱為懸掛點(diǎn)，所關(guān)聯(lián)的邊稱為懸掛邊次為0的點(diǎn)稱為孤立點(diǎn)有向圖中，由節(jié)點(diǎn)指向外的弧的數(shù)目稱為正次數(shù)，記為d+，指向該節(jié)點(diǎn)的弧的數(shù)目稱為負(fù)次數(shù)，記為d–177/16/2024

頂點(diǎn)的次（度，vertexdegree）7.1.1圖與子圖

頂點(diǎn)的次（度，vertexdegree）

定理1：圖G=(V,E)中，所有點(diǎn)的次之和是邊數(shù)的2倍：

其中m=|E|為邊數(shù)。

定理2：任何圖中，奇點(diǎn)的個(gè)數(shù)必為偶數(shù)。定理3：有向圖中，所有頂點(diǎn)的入次之和等于所有頂點(diǎn)的出次之和。01圖與網(wǎng)絡(luò)的基本概念187/16/20247.1.1圖與子圖

子圖設(shè)有圖

G＝(V,E)和圖

G’＝(V’,E’),若

G

和

G’滿足：若V’

V，E’

E，則稱G’是G的子圖

Subgraph,記為

G’

G；特別,若V’＝V，E’

E，則稱G’是G的生成子圖(支撐圖)

SpanningSubgraph;197/16/20247.1.1圖與子圖207/16/20247.1.2賦權(quán)圖與圖聯(lián)系在一起的，通常還有與點(diǎn)或邊有關(guān)的某些數(shù)量指標(biāo)，我們常稱之為“權(quán)”，權(quán)可以代表距離、費(fèi)用、通過能力（容量）等等。這種點(diǎn)或邊帶有某種數(shù)量指標(biāo)的圖稱為賦權(quán)圖（weightedgraph）權(quán)矩陣weightedmatrix867452493v1v5v4v2v3v1v2v3v4v5v1v2v3v4v5217/16/20247.1.2賦權(quán)圖鄰接矩陣adjacentmatrixv1v2v4v3v5v6若G為無(wú)向圖，則鄰接矩陣為對(duì)稱矩陣。v1v2v3v4v5v6v1v2v3v4v5v67.1.2賦權(quán)圖227/16/2024關(guān)聯(lián)矩陣incidencematrixv1v2v4v3v5v6e1e2e3e4e5e6e7e8e9e10v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10

A

每一列元素和等于2

A每一行元素和等于對(duì)應(yīng)頂點(diǎn)的次數(shù)237/16/20247.1.2賦權(quán)圖

鏈，圈，道路，回路設(shè)G

=

(V,

E)

是一個(gè)無(wú)向圖，考慮圖G中邊的序列：[v0,v1],[v1,v2],[v2,v3],…,[vk-1,vk]，簡(jiǎn)單地記為(v0,v1,v2,v3,…,vk-1,vk)，在這個(gè)序列中，任意一條邊的終點(diǎn)都是下一條邊的始點(diǎn)，稱此邊的序列為圖的一條鏈link若一條鏈中v0＝vk，則稱為圈loop對(duì)有向圖,可以類似地定義鏈和圈對(duì)有向圖G=(V,E)，當(dāng)鏈（圈）上邊的方向相同時(shí)，稱為道路path（回路circuit）01圖與網(wǎng)絡(luò)的基本概念7.1.3鏈，路，圈與回路247/16/2024連通圖(Connectedgraph)：在一個(gè)圖中，每一對(duì)頂點(diǎn)之間至少存在一條鏈否則為不連通圖257/16/2024

連通圖7.1.3鏈，路，圈與回路7.2樹

樹的定義：連通且不含圈的無(wú)向圖多級(jí)輻射制的電信網(wǎng)絡(luò)、管理的指標(biāo)體系、家譜、分類學(xué)、組織結(jié)構(gòu)等都是典型的樹圖ExploitingSection開發(fā)部Programming規(guī)劃發(fā)展部GeneralWorker’s總工辦Property物業(yè)部Engineering工程部MaterialPurchasing材料采購(gòu)部FinancingSection財(cái)務(wù)部Multioffice綜合辦公室董事會(huì)Directorate監(jiān)事會(huì)Intendancy副總經(jīng)理DeputyGeneralManager總經(jīng)理GeneralManager經(jīng)營(yíng)部門ManagementDepartment職能部門FunctionDepartment某公司組織結(jié)構(gòu)圖7.2.1樹的概念277/16/2024連通、無(wú)圈；設(shè)頂點(diǎn)數(shù)為|V|=n，邊數(shù)為|E|=m，那么m=n-1;任意兩點(diǎn)之間有且僅有一條鏈；去掉任意一條邊，就不連通；增加任意一條邊，就得到一個(gè)且僅一個(gè)圈；287/16/20247.2.1樹的概念設(shè)G＝(V,E)是一個(gè)連通的無(wú)向圖，若G的某個(gè)生成子圖是一棵樹，則稱該樹為G的生成樹(支撐樹)SpanningTree，記為TG。圖(c)是上圖(a)的生成子樹，而圖(d)所示的樹T3，則不是圖(a)的生成子樹。圖(b)是(a)的生成子圖但不是生成樹。7.2.2圖的支撐樹297/16/2024定理：圖G有生成樹（支撐樹）的充要條件是圖G是連通的。如何找到一棵生成樹？破圈法：每次去掉圈中的一條邊，其去掉的邊的總數(shù)為m－(n－1)；避圈法：每次選取G中的一條邊，該邊不能與已經(jīng)選取的邊構(gòu)成回路，此時(shí)，選取的邊的總數(shù)為(n－1)。307/16/20247.2.2圖的支撐樹求右圖(a)中的生成子樹。317/16/20241.破圈法：7.2.2圖的支撐樹求右圖(a)中的生成子樹。327/16/20242.避圈法：7.2.2圖的支撐樹破圈法337/16/20247.2.2圖的支撐樹在架設(shè)電話線，鋪設(shè)自來水或暖氣管道的工程設(shè)計(jì)中會(huì)遇到如下的優(yōu)化問題：如何相互連通，由使得總線路長(zhǎng)度最短？例：某居民區(qū)五棟樓的分布如圖。每條邊旁的數(shù)字表示水塔與各樓間的距離。試求最短的管道鋪設(shè)方案。最小支撐樹問題7.2.3最小支撐樹問題347/16/2024設(shè)有一個(gè)連通圖G=(V,E)，每一邊

eij=[vi,vj]有一個(gè)非負(fù)權(quán)

w(eij)=wij(wij≥0)如果T=(V,E’)，是

G的一個(gè)支撐樹，稱E’中所有邊的權(quán)之和為支撐樹

T

的權(quán)，記為

w(T)如果支撐樹

T*的權(quán)

w(T*)是

G的所有支撐樹的權(quán)中最小者，則稱

T*是

G的最小支撐樹（最小生成樹），即357/16/20247.2.3最小支撐樹問題求G的最小生成樹的方法有二：避圈法Kruskal破圈法該算法是克魯斯克爾(Kruskal)于1956年將構(gòu)造生成樹的避圈法推廣到求最小生成樹的結(jié)果，其要點(diǎn)是，在與已選取的邊不構(gòu)成圈的邊中選取最小者。避圈法：367/16/20247.2.3最小支撐樹問題7.3最短路問題例

已知如圖所示的單行線交通網(wǎng)，每弧旁的數(shù)字表示這條單行線的距離?，F(xiàn)在某人要從

v1出發(fā)，通過這個(gè)交通網(wǎng)到達(dá)

v8

，求使總距離最短的旅行線路。387/16/2024v1v7v2v5616321v32v4v610310v8v924623403最短路問題7.3.1最短路問題概述例

已知如圖所示的單行線交通網(wǎng)，每弧旁的數(shù)字表示這條單行線的距離。現(xiàn)在某人要從

v1出發(fā)，通過這個(gè)交通網(wǎng)到達(dá)

v8

，求使總距離最短的旅行線路。397/16/20241+10+2+4=176+1+6=133+2+1+3+4=133+2+10+10+6=31可行路線有多條！哪一條最短？v1v7v2v5616321v32v4v610310v8v924623403最短路問題7.3.1最短路問題概述給定一個(gè)賦權(quán)有向圖D=(V,A),對(duì)每一弧a=(vi

,

vj

)相應(yīng)地有權(quán)w(a)=wij給定D中的兩個(gè)頂點(diǎn)

vs和

vt，設(shè)

P是D中從

vs到

vt的一條路，定義路P的權(quán)是P中所有弧的權(quán)之和，即w(P)最短路問題就是要在所有從vs到vt的可行路中，求一條權(quán)最小的路記P0是從vs到vt的最短路，路P0的權(quán)為從vs到vt的距離，記為d(vs

,

vt

)

407/16/20247.3.1最短路問題概述——求無(wú)負(fù)權(quán)網(wǎng)絡(luò)最短路的最好方法之一基本原理：v1

v4

v6

v5

v7如果這是v1到達(dá)v7的最短路，那么也是v1到達(dá)該路徑上任意點(diǎn)的最短路。Dijkstra算法逐點(diǎn)求最短路03最短路問題7.3.2Dijkstra算法417/16/2024對(duì)每個(gè)節(jié)點(diǎn)，用兩種標(biāo)號(hào)：T和P（表示從始點(diǎn)到該節(jié)點(diǎn)的距離）T是目前路徑的距離(TentativeLabel)P是最短距離(PermanentLabel)開始時(shí)，令始點(diǎn)有P=0，記P標(biāo)號(hào)，其它節(jié)點(diǎn)有T=M/∞不斷改進(jìn)T值，當(dāng)其最小時(shí)，將其改為P標(biāo)號(hào)當(dāng)所有的標(biāo)號(hào)都為P時(shí)，找到最短路427/16/20247.3.2Dijkstra算法標(biāo)號(hào)過程分為兩步：437/16/2024Step1.修改T標(biāo)號(hào)。Step2.產(chǎn)生新的P標(biāo)號(hào)。原則：在現(xiàn)有的T標(biāo)號(hào)中將值最小者改為P標(biāo)號(hào)。03最短路問題7.3.2Dijkstra算法v1

v7的最短路徑？447/16/20247.3.2Dijkstra算法-例題03最短路問題457/16/20247.3.2Dijkstra算法-例題467/16/20247.3.2Dijkstra算法-例題03最短路問題477/16/20247.3.2Dijkstra算法-例題487/16/20247.3.2Dijkstra算法-例題497/16/20247.3.2Dijkstra算法-例題=12507/16/20247.3.2Dijkstra算法-例題517/16/20247.3.2Dijkstra算法-例題使用雙標(biāo)號(hào)527/16/20247.3.2Dijkstra算法-例題Ford算法算例537/16/20247.3.2Dijkstra算法-例題Dijkstra算法提供了從網(wǎng)絡(luò)圖中某一點(diǎn)到其它點(diǎn)的最短路。但實(shí)際問題中往往要求網(wǎng)絡(luò)任意兩點(diǎn)之間的最短距離，用Dijkstra算法就要對(duì)每個(gè)點(diǎn)分別計(jì)算，很麻煩。Floyd算法（基于權(quán)矩陣）n個(gè)頂點(diǎn)：的元素就是vi到vj的最短路權(quán)。7.3.3Floyd算法547/16/2024例：求圖中各點(diǎn)之間的最短距離557/16/2024v1v2v3v4v5v10512∞v25010∞2v323028v42∞604v5∞24405242121026348D(0)v1v2v5v4v37.3.3Floyd算法-例題v1v2v3v4v5v10512∞v25010∞2v323028v42∞604v5∞2440D(0)v1v2v3v4v5v10512∞v250672v323028v427304v5∞2440D(1)D(2)D(3)v1v2v3v4v5v105127v250672v323025v427304v572440v1v2v3v4v5v104126v250672v323025v426304v56244003最短路問題567/16/20247.3.3Floyd算法-例題D(3)v1v2v3v4v5v104126v250672v323025v426304v562440D(4)v1v2v3v4v5v104126v250672v323025v426304v562440D(5)v1v2v3v4v5v104126v250662v323025v426304v562440577/16/20247.3.3Floyd算法-例題587/16/20247.3.4旅行銷售商的問題在線路優(yōu)化中，從起始節(jié)點(diǎn)開始，要選擇一條合適的路徑經(jīng)過所有已知的節(jié)點(diǎn)各一次，并最后回到起始節(jié)點(diǎn)，要求所走距離最短。這一問題就是著名的旅行銷售商問題(TSP,TravelingSalesmanProblem，也稱貨郎擔(dān)問題）它可以抽象地?cái)⑹鋈缦拢簭囊粋€(gè)起始點(diǎn)出發(fā)到達(dá)所有要求服務(wù)的n個(gè)點(diǎn)，而且只到達(dá)一次，再回到起始點(diǎn)（即哈密爾頓回路）。已知任意兩點(diǎn)i、j間的距離dij，要求在所有可供考慮的路線中選擇路徑最短的旅行路線597/16/2024TSP的數(shù)學(xué)模型如下：這里

xij=1表示從

i直接去

j，否則

xij=0。第3個(gè)約束條件，式（7.6）保證路徑無(wú)子回路(subtour)，其中參數(shù)

ui為連續(xù)變量(i=1,2,…,n)，也可以取整數(shù)值7.3.4旅行銷售商的問題607/16/2024求解TSP問題的一種著名啟發(fā)式算法——最近插入法（closestinsertionalgorithm），它是由Rosenkrantz和Stearnes等人在1977年提出的一種TSP算法,步驟為：找到d1m最小的節(jié)點(diǎn)vm，形成一個(gè)子回路T={v1,vm,v1}在剩下的節(jié)點(diǎn)中，尋找一個(gè)離上子回路中某一節(jié)點(diǎn)最近的節(jié)點(diǎn)vk；在子回路中找到一條弧(i,j)，使得dik+dkj-

dij最小，然后將節(jié)點(diǎn)vk插入到節(jié)點(diǎn)vi，vj之間，用兩條新的弧(i,k)，(k,j)代替原來的弧(i,j)，并將節(jié)點(diǎn)vk加入到子回路中；重復(fù)2、3步驟，直到所有的節(jié)點(diǎn)都加入子回路中。

此時(shí)的回路就演變成了TSP的一個(gè)解（哈密爾頓回路）。最近插入法可以方便地用計(jì)算機(jī)求解。7.3.4旅行銷售商的問題617/16/2024求解TSP問題時(shí)，對(duì)于小型問題還可以求得最優(yōu)解，最簡(jiǎn)單的方法是枚舉法。但是對(duì)于大型問題，由于枚舉法的例舉次數(shù)為(n-1)!次，它的數(shù)量是非常龐大的！整數(shù)規(guī)劃的分枝定界法也可以解決部分TSP問題，但也只能是小規(guī)模的求解。如果模型中去掉“無(wú)子回路”的約束，它就是線性的指派問題（LAP）了，可以用匈牙利算法求出最優(yōu)解。因此先求出TSP對(duì)應(yīng)的LAP問題，可以為TSP問題提供一個(gè)下界，再用分枝定界法求解?？傊?，TSP模型是一個(gè)非線性規(guī)劃NP-Hard問題，對(duì)于大規(guī)模問題無(wú)法獲得最優(yōu)解，只有通過啟發(fā)式算法獲得近似解。啟發(fā)式算法不僅可以用于各種復(fù)雜的TSP問題，也適用于中小規(guī)模問題7.3.4旅行銷售商的問題7.4最大流問題

對(duì)網(wǎng)絡(luò)流的研究是在容量網(wǎng)絡(luò)上進(jìn)行的容量網(wǎng)絡(luò)是指網(wǎng)絡(luò)上的每一條弧(vi,vj)都有一個(gè)最大的通過能力，稱為該弧的容量

c(vi,vj)，

cij在網(wǎng)絡(luò)圖中通常規(guī)定一個(gè)發(fā)點(diǎn)（s）和一個(gè)收點(diǎn)（t），其余為中間點(diǎn)網(wǎng)絡(luò)最大流是指從發(fā)點(diǎn)到收點(diǎn)間允許通過的最大流量對(duì)有多個(gè)發(fā)點(diǎn)或收點(diǎn)的網(wǎng)絡(luò)，另虛設(shè)一個(gè)總發(fā)點(diǎn)或總收點(diǎn)容量網(wǎng)絡(luò)637/16/20247.4.1網(wǎng)絡(luò)流的基本概念流與可行流流是加在網(wǎng)絡(luò)各條弧上的一組負(fù)載量對(duì)加在弧

(vi,vj)上的負(fù)載量記作

f(vi,vj),

fij若網(wǎng)絡(luò)上所有的

fij

=0，則這個(gè)流稱為零流滿足容量限制條件和平衡條件的一組流為可行流容量限制條件：對(duì)所有弧有

0≤fij

≤cij中間點(diǎn)平衡條件：

∑

fij－∑fji＝0(i≠s,t)若以

W

表示網(wǎng)絡(luò)中從s

t的流量，則有647/16/2024

收發(fā)點(diǎn)平衡條件7.4.1網(wǎng)絡(luò)流的基本概念任何網(wǎng)絡(luò)上一定存在可行流（零流就是可行流）所謂求網(wǎng)絡(luò)最大流，是指滿足容量限制條件和中間點(diǎn)平衡條件下，使

W

值達(dá)到最大這是一個(gè)線性規(guī)劃問題，但圖論方法更簡(jiǎn)單657/16/20247.4.1網(wǎng)絡(luò)流的基本概念割：將容量網(wǎng)絡(luò)中的發(fā)點(diǎn)和收點(diǎn)分開，并使發(fā)點(diǎn)到收點(diǎn)的流中斷的一組邊的集合667/16/2024v1s8(8)2(0)9(4)5(4)7(5)v3v2v49(9)6(1)t10(8)5(5)KKKK將網(wǎng)絡(luò)上的點(diǎn)分割成V和V’兩個(gè)集合，且有s∈V,t∈V’。邊的集合

(V,V’)={(v3,t),(v4,v3),(v2,v4)}是一個(gè)割。7.4.1網(wǎng)絡(luò)流的基本概念v1s8(8)2(0)9(4)5(4)7(5)v3v2v49(9)6(1)t10(8)5(5)割集容量是指所有始點(diǎn)在V，終點(diǎn)在V’的弧的容量之和7+8=159+5+7=219+9=185+9=14KK割集有多個(gè)，其中割集容量最小者稱為最小割。677/16/20247.4.1網(wǎng)絡(luò)流的基本概念若用

f(V,V’)表示通過割(V,V’)中所有V

V’方向弧的流量的總和

f(V’,V)表示通過割(V,V’)中所有V’

V方向弧的流量的總和從s

t的流量實(shí)際上等于通過割的從V

V’的流量減去V’

V的流量，即W

=f(V,V’)－f(V’,V)7.4.2求解網(wǎng)絡(luò)最大流的基本原理687/16/2024若用W*代表網(wǎng)絡(luò)中從s

t的最大流，C*(V,V’)代表網(wǎng)絡(luò)中最小的一個(gè)割的容量，則W*=C*(V,V’)割集是從s

t

的必經(jīng)之路任何一個(gè)可行流的流量不會(huì)超過任一割集的容量W≤C(V,V’)

——

最大流-最小割定理MaxW≤Min

C(V,V’)

697/16/20247.4.2求解網(wǎng)絡(luò)最大流的基本原理如果在網(wǎng)絡(luò)的發(fā)點(diǎn)和收點(diǎn)之間存在一條鏈，那么在這條鏈上所有指向?yàn)椤鞍l(fā)點(diǎn)到收點(diǎn)”的弧稱為前向弧，記為m+所有指向?yàn)橄喾吹幕》Q為后向弧，記為m－在所有的前向弧上，流量

<容量；在所有的后向弧上，流量

>0；則稱這條鏈為增廣鏈(不飽和鏈)前向弧，后向弧增廣鏈如果707/16/20247.4.2求解網(wǎng)絡(luò)最大流的基本原理顯然f’仍然是一個(gè)可行流，但比原來的可行流f在s

t方向上增大了一個(gè)正的q

值因此只有當(dāng)網(wǎng)絡(luò)上找不到增廣鏈時(shí)，s

t的流才不可能再增大

當(dāng)有增廣鏈存在時(shí)，找出再令717/16/20247.4.2求解網(wǎng)絡(luò)最大流的基本原理定理：可行流

f為最大流的充分必要條件是當(dāng)且僅當(dāng)網(wǎng)絡(luò)不存在增廣鏈給出一初始可行流，例如尋找增廣鏈，若存在，則通過該增廣鏈調(diào)整、增加網(wǎng)絡(luò)流若不存在增廣鏈，則網(wǎng)絡(luò)流不可再增加。求得最大流727/16/20247.4.2求解網(wǎng)絡(luò)最大流的基本原理標(biāo)號(hào)算法Ford-Fulkerson

1.首先給發(fā)點(diǎn)標(biāo)號(hào)(

0,δs)737/16/2024使這個(gè)點(diǎn)得到標(biāo)號(hào)的前一個(gè)點(diǎn)的代號(hào)。因s是發(fā)點(diǎn)，故記為0δs

是從上一標(biāo)號(hào)點(diǎn)到這個(gè)標(biāo)號(hào)點(diǎn)的流量的最大允許調(diào)整值。因s是發(fā)點(diǎn)，不允許調(diào)整，故

δs=+∞7.4.3求解網(wǎng)絡(luò)最大流的標(biāo)號(hào)法2.列出與已標(biāo)號(hào)點(diǎn)相鄰的所有未標(biāo)號(hào)點(diǎn)：(1)考慮從標(biāo)號(hào)點(diǎn)

i出發(fā)的所有弧(i,j)，如果fij=cij，不給點(diǎn)j標(biāo)號(hào)若fij<cij對(duì)j標(biāo)號(hào)，記為(+vi,δj

),其中δj

=min{δi

,cij-fij}(2)考慮所有指向點(diǎn)i的弧(j,i)，如果fji=0，不給點(diǎn)j標(biāo)號(hào)若fji>0

對(duì)j標(biāo)號(hào)，記為(-vi,δj

),其中δj

=min{δi

,fji}747/16/2024如果某未標(biāo)號(hào)點(diǎn)k

有兩個(gè)以上相鄰的標(biāo)號(hào)點(diǎn)，為減少迭代次數(shù)，可按(1)(2)分別計(jì)算出δk

值，并取其中最大一個(gè)標(biāo)記。7.4.3求解網(wǎng)絡(luò)最大流的標(biāo)號(hào)法3.重復(fù)第2步，可能出現(xiàn)兩種結(jié)局：(1)標(biāo)號(hào)過程中斷，點(diǎn)

t得不到標(biāo)號(hào)，說明該網(wǎng)絡(luò)中不存在增廣鏈，給定的流量即為最大流記已標(biāo)號(hào)點(diǎn)的集合為V，未標(biāo)號(hào)點(diǎn)集合為V’(V,V’)即為網(wǎng)絡(luò)的最小割(2)點(diǎn)t得到標(biāo)號(hào)，這時(shí)可用反向追蹤法在網(wǎng)絡(luò)中找出一條從s

t的由標(biāo)號(hào)點(diǎn)及相應(yīng)弧連接而成的增廣鏈4.修改流量。設(shè)圖中原有可行流為

f，令757/16/20247.4.3求解網(wǎng)絡(luò)最大流的標(biāo)號(hào)法5.抹掉圖上所有標(biāo)號(hào)。重復(fù)第1到第4步，直到圖中找不出任何增廣鏈，即第3步中的(1)為止，這時(shí)網(wǎng)絡(luò)圖中的流量即為最大流。767/16/2024v1s8(8)2(0)9(4)7(5)v3v2v49(9)6(1)t10(8)5(5)5(4)7.4.3求解網(wǎng)絡(luò)最大流的標(biāo)號(hào)法v1s8(8)2(0)9(4)5(4)7(5)v3v2v49(9)6(1)t10(8)5(5)(0,∞)(s,2)(v2,2)(v1,2)(v3,1)(v4,1)增廣鏈7(6)5(3)9(5)6(0)10(9)777/16/2024標(biāo)號(hào)法算例v1s8(8)2(0)v3v2v49(9)t5(5)(0,∞)(s,1)(v2,1)(v1,1)重復(fù)上述標(biāo)號(hào)過程7(6)5(3)9(5)6(0)10(9)已再無(wú)增廣鏈，故可行流即為最大流W*=14KK787/16/2024標(biāo)號(hào)法算例7.5最小費(fèi)用流問題給定網(wǎng)絡(luò)

G=(V,A,C,d)和經(jīng)過網(wǎng)絡(luò)的流量

W(f)=v，求流在網(wǎng)絡(luò)上的最佳分布，使總費(fèi)用最小。807/16/20247.5.1最小費(fèi)用流的問題定義增廣鏈費(fèi)用，最小費(fèi)用增廣鏈。對(duì)于最小費(fèi)用可行流，沿最小費(fèi)用增廣鏈調(diào)整流，可使流增加，并保持流費(fèi)用最小。給定初始最小費(fèi)用可行流，求最小費(fèi)用增廣鏈，若存在，則沿該增廣鏈調(diào)整網(wǎng)絡(luò)流，直到達(dá)到給定的網(wǎng)絡(luò)流或不存在增廣鏈為止，后一種情況為最小費(fèi)用最大流。若給定網(wǎng)絡(luò)流超過最大流，則不可能實(shí)現(xiàn)。817/16/20247.5.2求解最小費(fèi)用流的賦權(quán)圖法生成最小費(fèi)用可行流的剩余網(wǎng)絡(luò)：將飽和弧反向?qū)⒎秋柡头橇懔骰〖右环聪蚧×懔骰〔蛔兯星跋蚧〉臋?quán)為該弧的費(fèi)用，后向弧的權(quán)為該弧費(fèi)用的相反數(shù)剩余網(wǎng)絡(luò)又叫長(zhǎng)度網(wǎng)絡(luò)最小費(fèi)用增廣鏈對(duì)應(yīng)剩余網(wǎng)絡(luò)的最短路827/16/20247.5.2求解最小費(fèi)用流的賦權(quán)圖法837/16/20247.5.2求解最小費(fèi)用流的賦權(quán)圖法第1次剩余網(wǎng)絡(luò)最短路847/16/2024賦權(quán)圖法-算例第1次調(diào)整網(wǎng)絡(luò)流857/16/2024賦權(quán)圖法-算例第2次剩余網(wǎng)絡(luò)最短路867/16/2024賦權(quán)圖法-算例第2次調(diào)整網(wǎng)絡(luò)流877/16/2024賦權(quán)圖法-算例第3次剩余網(wǎng)絡(luò)最短路887/16/2024-2賦權(quán)圖法-算例第3次調(diào)整網(wǎng)絡(luò)流897/16/2024賦權(quán)圖法-算例剩余網(wǎng)絡(luò)已不存在最短路907/16/2024賦權(quán)圖法-算例917/16/2024賦權(quán)圖法-算例

7.6中國(guó)郵遞員問題937/16/20247.6中國(guó)郵遞員問題一個(gè)郵遞員送信，要走完負(fù)責(zé)投遞的全部街道，完成任務(wù)后回到郵局，應(yīng)該按照怎樣的線路走，所走的路程最短。這是我國(guó)學(xué)者管梅谷1962年提出的問題，在國(guó)際上通稱為中國(guó)郵遞員問題。這一問題的介紹首先要從圖論中最早的哥尼斯堡七橋問題開始947/16/20247.6.1哥尼斯堡七橋問題與歐拉圖連通圖G中，若存在一條鏈，經(jīng)過每條邊一次且僅一次，則稱這條鏈為歐拉鏈（Eulerpath）。若存在一條圈，經(jīng)過每條邊一次且僅一次，則稱這條回路為歐拉圈（Eulercircuit）。定理1：無(wú)向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中無(wú)奇點(diǎn)推論

連通多重圖G有歐拉圈，當(dāng)且僅當(dāng)G恰有兩個(gè)奇點(diǎn)根據(jù)定理來檢查哥尼斯堡七橋問題，從圖(B)中可以看到d(A)=3,d(B)=3,d(C)=5,d(D)=3，有四個(gè)奇點(diǎn)，所以不是歐拉圖，即這樣的走法不存在957/16/20247.6.2中國(guó)郵遞員問題定義定義：給定一個(gè)連通圖G，每邊有非負(fù)權(quán)l(xiāng)(e)，要求一條回路過每邊至少一次，且滿足總權(quán)最小。此種問題為中國(guó)郵遞員問題。由定理知，如果G沒有奇點(diǎn)，則是一個(gè)歐拉圖，顯然按歐拉回路走就是滿足要求的過每邊至少一次且總權(quán)最小的回路。

如果G中有奇點(diǎn)，要求連續(xù)走過每邊至少一次，必然有些邊不止一次走過，這相當(dāng)于在圖G中對(duì)某些邊增加一些重復(fù)邊，使所得到的新圖G*沒有奇點(diǎn)且滿足總路程最短。967/16/2024由于總路程的長(zhǎng)短完全取決于所增加的重復(fù)邊的長(zhǎng)度，所以中國(guó)郵路問題也可以轉(zhuǎn)為如下問題在連通圖G=(V,E)中，求一個(gè)邊集E1∈E，把G中屬于E1的邊均變?yōu)槎剡叺玫綀DG*=G+E1，使其滿足G*無(wú)奇點(diǎn)，且最小。定理2

已知圖G*=G+E1無(wú)奇點(diǎn)，則最小的充要條件為：(1)每條邊最多重復(fù)一次；(2)對(duì)圖G中每個(gè)初等圈來講，重復(fù)邊的長(zhǎng)度和不超過圈長(zhǎng)的一半。7.6.2中國(guó)郵遞員問題定義977/16/2024定理2的證明，給出了中國(guó)郵路問題的一種算法，稱為“奇偶點(diǎn)圖上作業(yè)法”，它的思路是：先對(duì)一個(gè)有奇點(diǎn)的圖增加重復(fù)邊轉(zhuǎn)變?yōu)椴缓纥c(diǎn)的歐拉圖，這樣的重復(fù)邊方案為可行方案，然后再尋求對(duì)重復(fù)邊總長(zhǎng)減少的改進(jìn)方案，最后找到使總長(zhǎng)最短的可行方案就是所求的解。下面舉例說明這個(gè)算法求解下圖所示網(wǎng)絡(luò)的中國(guó)郵路問題。圖a圖b7.6.2中國(guó)郵遞員問題的求解7/16/202498第1步：確定初始可行方案先檢查圖中是否有奇點(diǎn)，如無(wú)奇點(diǎn)則已是歐拉圖，找出歐拉回路即可。如有奇點(diǎn)，由前知奇點(diǎn)個(gè)數(shù)必為偶數(shù)個(gè)，所以可以兩兩配對(duì)。每對(duì)點(diǎn)間選一條路，使這條路上均為二重邊。圖中有四個(gè)奇點(diǎn)v2,v4,v6,v8（空心點(diǎn)表示），將v2與v4，v6與v8配對(duì)，聯(lián)結(jié)v2與v4的路有好幾條，任取一條，如｛v2,v3,v6,v9,v8,v7,v4｝，類似地，對(duì)v6與v8?。鹶6,v3,v2,v1,v4,v7,v8｝。得到圖b，已是歐拉圖。對(duì)應(yīng)這個(gè)可行方案，重復(fù)邊的總長(zhǎng)為2l23+2l36+l69+l98+2l87+2l74+l41+l12=517.6.2中國(guó)郵遞員問題的求解7/16/202499第2步：調(diào)整可行方案，使重復(fù)邊最多為一次去掉[v2,v3]，[v3,v6]，[v4,v7]，[v7,v8]各兩條，得到圖c，重復(fù)邊總長(zhǎng)度下降為：l12+l14+l69+l98=21第3步：檢查圖中每個(gè)初等圈是否滿足定理7.10條件(2)。如不滿足則進(jìn)行調(diào)整，直至滿足為止。檢查圖c，發(fā)現(xiàn)圈｛v1,v2,v5,v4,v1｝總長(zhǎng)度為24，而重復(fù)邊的長(zhǎng)為14，大于該圈總長(zhǎng)度的一半，可以作一次調(diào)整，以[v2,v5]，[v5,v4]代替[v1,v2]，[v1,v4]，得到圖d，重復(fù)邊總長(zhǎng)度下降為：l25+l43+l69+l98=17再檢查圖d，圈｛v3,v6,v9,v8,v5,v2,v3｝總長(zhǎng)度為24，而重復(fù)邊長(zhǎng)為13。再次調(diào)整得圖e，重復(fù)邊總長(zhǎng)度為15。檢查圖e，條件(1),(2)均滿足，得到最優(yōu)方案7.6.2中國(guó)郵遞員問題的求解7/16/2024100圖c圖d圖e圖中任一歐拉回路即為最優(yōu)郵遞路線。7.6.2中國(guó)郵遞員問題的求解7.7網(wǎng)絡(luò)計(jì)劃網(wǎng)絡(luò)計(jì)劃起源與發(fā)展1917年，亨利·甘特發(fā)明了著名的甘特圖GanttChart（也稱橫道圖），使項(xiàng)目經(jīng)理按日歷制作任務(wù)圖表，用于日常工作安排1956年，美國(guó)杜邦公司將關(guān)鍵路徑法（CPM）應(yīng)用于設(shè)備維修，使維修停工時(shí)間由125小時(shí)銳減為7小時(shí)

1958年，美國(guó)海軍特種計(jì)劃局在北極星導(dǎo)彈設(shè)計(jì)中，應(yīng)用計(jì)劃評(píng)審技術(shù)（PERT），將項(xiàng)目任務(wù)之間的關(guān)系模型化，使設(shè)計(jì)完成時(shí)間縮短了2年

1962年美國(guó)國(guó)防部規(guī)定：以后承包有關(guān)工程的單位都應(yīng)采用網(wǎng)絡(luò)計(jì)劃技術(shù)來安排計(jì)劃前言7/16/202410260年代初，我國(guó)著名數(shù)學(xué)家華羅庚教授將此技術(shù)介紹到中國(guó)，并把它稱為“統(tǒng)籌法”國(guó)內(nèi)外應(yīng)用網(wǎng)絡(luò)計(jì)劃的實(shí)踐表明，它具有一系列優(yōu)點(diǎn)

特別適用于生產(chǎn)技術(shù)復(fù)雜，工作項(xiàng)目繁多、且聯(lián)系緊密的一些跨部門的工作計(jì)劃新產(chǎn)品研制開發(fā)、大型工程項(xiàng)目、生產(chǎn)技術(shù)準(zhǔn)備、設(shè)備大修等計(jì)劃、資源安排、工作流程以下主要介紹CPM。編制網(wǎng)絡(luò)計(jì)劃包括繪制網(wǎng)絡(luò)圖，計(jì)算時(shí)間參數(shù)，確定關(guān)鍵路線及網(wǎng)絡(luò)優(yōu)化等環(huán)節(jié)網(wǎng)絡(luò)計(jì)劃起源與發(fā)展7/16/2024103前言網(wǎng)絡(luò)計(jì)劃與橫道計(jì)劃的比較簡(jiǎn)單、清晰、形象、易懂、使用方便；施工過程施工進(jìn)度（天）2468101214161820支模10人綁鋼筋15人澆混凝土10人優(yōu)點(diǎn)：可以直接在圖中進(jìn)行各項(xiàng)資源需要量統(tǒng)計(jì)。102510勞動(dòng)力動(dòng)態(tài)消耗圖1047/16/2024前言不能直接反映各施工過程之間相互聯(lián)系、相互制約的邏輯關(guān)系不能明確指出那些工作是關(guān)鍵工作，那些工作不是關(guān)鍵工作不能計(jì)算各工作的時(shí)間參數(shù)，看不到計(jì)劃的潛力不能應(yīng)用計(jì)算機(jī)進(jìn)行調(diào)整和優(yōu)化缺點(diǎn)：網(wǎng)絡(luò)計(jì)劃與橫道計(jì)劃的比較1057/16/2024前言1213456支模1綁鋼筋1澆混凝土1446支模2綁鋼筋2澆混凝土2426施工過程施工進(jìn)度（天）2468101214161820支模10人綁鋼筋15人澆混凝土10人網(wǎng)絡(luò)計(jì)劃與橫道計(jì)劃的比較1067/16/2024前言1213456支模1綁鋼筋1澆混凝土1446支模2綁鋼筋2澆混凝土2426能全面而明確地反映各施工過程之間相互聯(lián)系、相互制約的邏輯關(guān)系；通過時(shí)間參數(shù)的計(jì)算，能夠找出關(guān)鍵施工過程和關(guān)鍵線路，便于管理者抓住主要矛盾；通過時(shí)間參數(shù)的計(jì)算，可以對(duì)網(wǎng)絡(luò)計(jì)劃進(jìn)行調(diào)整和優(yōu)化；優(yōu)點(diǎn)：網(wǎng)絡(luò)計(jì)劃與橫道計(jì)劃的比較1077/16/2024前言7.7.1網(wǎng)絡(luò)圖繪制網(wǎng)絡(luò)圖繪制1網(wǎng)絡(luò)圖的構(gòu)成2網(wǎng)絡(luò)圖的基本畫法3繪制網(wǎng)絡(luò)圖的基本原則1087/16/2024網(wǎng)絡(luò)圖是由作業(yè)、事項(xiàng)（節(jié)點(diǎn)）和路線三大部分組成作業(yè)（工作、工序、活動(dòng)），箭線表示，一般箭線之上表示工作名稱，之下表示工作時(shí)間1097/16/2024作業(yè)一般分為兩種：消耗一定的時(shí)間與資源的工作――實(shí)工作，用實(shí)箭線表示既不消耗時(shí)間也不消耗資源的工作――虛工作，虛設(shè)的工作，只表示前后工作之間的邏輯關(guān)系，用虛箭線表示“雙代號(hào)表示法”網(wǎng)絡(luò)圖的構(gòu)成

事項(xiàng)，節(jié)點(diǎn)表示，表示前面工作結(jié)束和后面工作開始的時(shí)間點(diǎn)，表示工作結(jié)束和開始的瞬間，既不消耗時(shí)間也不消耗資源1213456支模1綁鋼筋1澆混凝土1446支模2綁鋼筋2澆混凝土2426起始節(jié)點(diǎn)終點(diǎn)節(jié)點(diǎn)中間節(jié)點(diǎn)1107/16/2024網(wǎng)絡(luò)圖的構(gòu)成1213456支模1綁鋼筋1澆混凝土1446支模2綁鋼筋2澆混凝土2426節(jié)點(diǎn)的編號(hào):從左到右，由小到大；箭尾編號(hào)小于箭頭編號(hào),即i＜j

；編碼可以不連續(xù)，但不可以重復(fù)。1117/16/2024網(wǎng)絡(luò)圖的構(gòu)成

路線，網(wǎng)絡(luò)圖中，從起始節(jié)點(diǎn)開始，沿箭線方向連續(xù)通過一系列節(jié)點(diǎn)和箭線，最后到達(dá)終點(diǎn)節(jié)點(diǎn)的若干條通道，稱為路線124AC5B2D4E5G3F56351①→②→④→⑥（8天）①→②→③→④→⑥（10天）①→②→③→⑤→⑥（9天）①→③→④→⑥（14天）①→③→⑤→⑥（13天）1127/16/2024網(wǎng)絡(luò)圖的構(gòu)成第四條線路耗時(shí)最長(zhǎng)（14天），對(duì)整個(gè)工程的完工起著決定性的作用，稱為關(guān)鍵線路；其余線路均稱為非關(guān)鍵線路。處于關(guān)鍵線路上的各項(xiàng)工作稱為關(guān)鍵工作。關(guān)鍵工作完成的快慢將直接影響整個(gè)計(jì)劃工期的實(shí)現(xiàn)。關(guān)鍵線路上的箭線常采用粗線、雙線或其它顏色的箭線突出表示。

位于非關(guān)鍵線路上的工作除關(guān)鍵工作外，都稱為非關(guān)鍵工作，它們都有機(jī)動(dòng)時(shí)間(即時(shí)差)；非關(guān)鍵工作也不是一成不變的，它可以轉(zhuǎn)化成關(guān)鍵工作；利用非關(guān)鍵工作的機(jī)動(dòng)時(shí)間可以科學(xué)地、合理地調(diào)配資源和對(duì)網(wǎng)絡(luò)計(jì)劃進(jìn)行優(yōu)化。

1137/16/2024網(wǎng)絡(luò)圖的構(gòu)成1147/16/2024網(wǎng)絡(luò)圖的基本畫法在一個(gè)大的工程項(xiàng)目中，各作業(yè)之間的關(guān)系是很復(fù)雜的，有的按順序進(jìn)行，有的同時(shí)進(jìn)行，有的需要在幾項(xiàng)作業(yè)完成后才能開始，有的交叉進(jìn)行，等等。為了表示這些不同的情況，引入四種不同的表示法作業(yè)的串聯(lián)：表示按時(shí)間的先后次序進(jìn)行的作業(yè)之間的關(guān)系。必須完成的作業(yè)稱為先行作業(yè)（緊前作業(yè)），繼這些作業(yè)之后開始的稱為緊后作業(yè)。例如在下圖中，作業(yè)G完成之后H才能開始，則G是H的緊前作業(yè)，H是G的緊后作業(yè)。1157/16/2024作業(yè)的并聯(lián)：表示兩個(gè)或兩上以上的作業(yè)同時(shí)進(jìn)行的關(guān)系，如圖7.21作業(yè)B,C是在作業(yè)A之后平行進(jìn)行的。則A為B,C的緊前作業(yè)，或者說B,C為A的緊后作業(yè)。3和4之間的虛作業(yè)表示E的緊前作業(yè)是B,C，只有在B,C都完成后E才能開始。網(wǎng)絡(luò)圖的基本畫法1167/16/2024作業(yè)的交叉：兩個(gè)及以上的作業(yè)，部分地交錯(cuò)進(jìn)行時(shí)，要用作業(yè)的交叉表示，如圖所示。作業(yè)的合并：把兩個(gè)及以上的作業(yè)簡(jiǎn)化合并成一個(gè)更大的作業(yè)稱為作業(yè)的合并，合并后的作業(yè)時(shí)間，按原圖中兩個(gè)結(jié)點(diǎn)之間的最長(zhǎng)路線計(jì)算。網(wǎng)絡(luò)圖的基本畫法網(wǎng)絡(luò)圖只能一個(gè)開始節(jié)點(diǎn)，一個(gè)終止節(jié)點(diǎn)網(wǎng)絡(luò)圖應(yīng)從左向右延伸，編號(hào)應(yīng)從小到大，且不重復(fù)。箭頭事項(xiàng)編號(hào)大于箭尾事項(xiàng)編號(hào)不能出現(xiàn)循環(huán)路線（即不允許有回路）236541繪制網(wǎng)絡(luò)圖的基本原則1177/16/2024兩事項(xiàng)間只能有一項(xiàng)作業(yè)改為箭線的首尾都必須有節(jié)點(diǎn)131211配砂造型14131211造型配砂2配砂1

1187/16/2024繪制網(wǎng)絡(luò)圖的基本原則網(wǎng)絡(luò)圖要布局規(guī)整、條理清晰、重點(diǎn)突出。繪制網(wǎng)絡(luò)圖時(shí)，應(yīng)盡量采用水平箭線和垂直箭線而形成網(wǎng)格結(jié)構(gòu)，盡量減少斜箭線，使網(wǎng)絡(luò)圖規(guī)整、清晰。其次，應(yīng)盡量把關(guān)鍵工作和關(guān)鍵線路布置在中心位置，盡可能把密切相連的工作安排在一起，以突出重點(diǎn)，便于使用。1197/16/20241234EBDACF（a）有交叉和斜向箭線的網(wǎng)絡(luò)圖1234EFDCAB（b）調(diào)整后的網(wǎng)絡(luò)圖繪制網(wǎng)絡(luò)圖的基本原則ABABCABCABCACB序號(hào)工作之間的邏輯關(guān)系網(wǎng)絡(luò)圖中的表示方法說明1A工作完成后進(jìn)行B工作A工作制約著B工作的開始，B工作依賴著A工作2A、B、C三項(xiàng)工作同時(shí)開始

A、B、C三項(xiàng)工作稱為平行工作3A、B、C三項(xiàng)工作同時(shí)結(jié)束A、B、C三項(xiàng)工作稱為平行工作4有A、B、C三項(xiàng)工作。只有A完成后，B、C才能開始A工作制約著B、C工作的開始，B、C為平行工作5有A、B、C三項(xiàng)工作。C工作只有在A、B完成后才能開始C工作依賴著A、B工作，A、B為平行工作1207/16/2024繪制網(wǎng)絡(luò)圖的基本原則BACDACBDiDA1B1A2A3B2B3ADBCE6有A、B、C、D四項(xiàng)工作。只有當(dāng)A、B完成后，C、D才能開始通過中間節(jié)點(diǎn)i正確地表達(dá)了A、B、C、D工作之間的關(guān)系7有A、B、C、D四項(xiàng)工作。A完成后C才能開始，A、B完成后D才能開始D與A之間引人了邏輯連接（虛工作），從而正確地表達(dá)了它們之間的制約關(guān)系8有A、B、C、D、E五項(xiàng)工作。A、B完成后C才能開始，B、D完成后E才能開始虛工作i-j反映出C工作受到B工作的制約；虛工作i-k反映出E工作受到B工作的制約9有A、B、C、D、E五項(xiàng)工作。A、B、C完成后D才能開始，B、C完成后E才能開始虛工作反映出D工作受到B、C工作的制約10A、B兩項(xiàng)工作分三個(gè)施工段，平行施工每個(gè)工種工程建立專業(yè)工作隊(duì)，在每個(gè)施工段上進(jìn)行流水作業(yè)，虛工作表達(dá)了工種間的工作面關(guān)系A(chǔ)CBE

i

j

k1217/16/2024繪制網(wǎng)絡(luò)圖的基本原則任務(wù)分解(WorkBreakdownStructure,WBS)繪制網(wǎng)絡(luò)圖節(jié)點(diǎn)編號(hào)作業(yè)分析表網(wǎng)絡(luò)圖的繪制實(shí)例1227/16/2024試探性繪制法：試探1237/16/2024網(wǎng)絡(luò)圖的繪制實(shí)例試探性繪制法：修改1247/16/2024網(wǎng)絡(luò)圖的繪制實(shí)例流程圖過渡繪制法：流程圖1257/16/2024網(wǎng)絡(luò)圖的繪制實(shí)例流程圖過渡繪制法：加事項(xiàng)1267/16/2024網(wǎng)絡(luò)圖的繪制實(shí)例流程圖過渡繪制法：去方框1277/16/2024網(wǎng)絡(luò)圖的繪制實(shí)例流程圖過渡繪制法：修改1287/16/2024網(wǎng)絡(luò)圖的繪制實(shí)例網(wǎng)絡(luò)圖繪制，只是用網(wǎng)絡(luò)的形式表達(dá)出了工作之間的邏輯關(guān)系。還必須通過計(jì)算求出工期，得到一定的時(shí)間參數(shù)計(jì)算網(wǎng)絡(luò)圖中有關(guān)的時(shí)間參數(shù)，主要目的是找出關(guān)鍵路線，為網(wǎng)絡(luò)計(jì)劃的優(yōu)化、調(diào)整和執(zhí)行提供明確的時(shí)間概念時(shí)間參數(shù)：工序所需時(shí)間、事項(xiàng)最早、最遲的時(shí)間、工序的最早、最遲時(shí)間及時(shí)差7.7.2網(wǎng)絡(luò)圖的時(shí)間參數(shù)計(jì)算1297/16/2024完成一項(xiàng)工序所需時(shí)間確定，只給出一個(gè)時(shí)間值CPM在影響工序因素較多，作業(yè)時(shí)間難以準(zhǔn)確估計(jì)時(shí)，采用三點(diǎn)時(shí)間PERTa—最快可能完成時(shí)間m—最可能完成時(shí)間b—最慢可能完成時(shí)間1307/16/2024確定型概率型作業(yè)時(shí)間的確定事項(xiàng)（節(jié)點(diǎn)）的最早時(shí)間——tE(j)表示以j為始點(diǎn)的各工序最早可能開始的時(shí)間，也表示以j為終點(diǎn)的各工序均完成的最早可能時(shí)間起始節(jié)點(diǎn)的最早開始時(shí)間為0，即tE(1)=0

tE(j)=max{tE(i)+t(i,j)}i,j

分別代表箭尾和箭頭事件從起始節(jié)點(diǎn)開始,正向計(jì)算1317/16/2024i節(jié)點(diǎn)時(shí)間參數(shù)及計(jì)算事項(xiàng)（節(jié)點(diǎn)）最遲時(shí)間——tL(i)表示在不影響任務(wù)總工期的條件下，以i為始點(diǎn)的各工序最遲必須開始時(shí)間，或以i為終點(diǎn)的各工作的最遲必須完成時(shí)間一般將任務(wù)的最早完工時(shí)間作為任務(wù)的總工期

tL(n)=tE(n)

n為終點(diǎn)事項(xiàng)

tL(i)=min{tL(j)–t(i,j)}i,j

分別代表箭尾和箭頭事件從終點(diǎn)節(jié)點(diǎn)開始,反向計(jì)算，即從編號(hào)大到小順序1327/16/2024j節(jié)點(diǎn)時(shí)間參數(shù)及計(jì)算計(jì)算各事項(xiàng)的最早時(shí)間和最遲時(shí)間。1337/16/2024節(jié)點(diǎn)時(shí)間參數(shù)及計(jì)算-例題時(shí)間參數(shù)的圖上計(jì)算法1347/16/2024節(jié)點(diǎn)時(shí)間參數(shù)及計(jì)算-例題工序的最早可能開工時(shí)間——tES(i,j)任何一個(gè)工序都必須在其所有緊前工序全部完成后才能開始工序的最早可能完工時(shí)間——tEF(i,j)表示工作按最早開工時(shí)間開始所能達(dá)到的完工時(shí)間tES(1,j)=0tES(i,j)=max{tES(k,i)+t(k,i)}tEF(i,j)=tES(i,j)+t(i,j)tES(i,j)=tE(i)1357/16/2024EarlyFinishEarlyStarttEF(i,j)=tE(i)+

t(i,j)作業(yè)時(shí)間參數(shù)及計(jì)算

工序的最遲必須開工時(shí)間——tLS(i,j)表示工序(i,j)在不影響整個(gè)任務(wù)如期完成的前提下，必須開始的最晚時(shí)間工序的最遲必須完工時(shí)間——tLF(i,j)表示工作(i,j)按最遲時(shí)間開工，所達(dá)到的完工時(shí)間tLF(i,n)=tL(n)=tE(n)tLS(i,j)=min{tLS(j,k)-t(i,j)}tLF(i,j)=tLS(i,j)+t(i,j)tLF(i,j)=tL(j)1367/16/2024LateFinishLateStarttLS(i,j)=tL(i)

-

t(i,j)作業(yè)時(shí)間參數(shù)及計(jì)算作業(yè)時(shí)間和事項(xiàng)時(shí)間的關(guān)系1377/16/2024ijETESEFETLTLTLFLStij+tij=－

tij=作業(yè)時(shí)間參數(shù)及計(jì)算工序的時(shí)差或工序的機(jī)動(dòng)時(shí)間工序總時(shí)差R(i,j)，在不影響總工期的情況下，最早開始（或結(jié)束）時(shí)間可以推遲的時(shí)間R(i,j)=tLF(i,j)-tEF(i,j)=tLS(i,j)-tES(i,j)總時(shí)差為0的作業(yè)是關(guān)鍵作業(yè)，開始和結(jié)束的時(shí)間沒有一點(diǎn)機(jī)動(dòng)的余地由關(guān)鍵作業(yè)構(gòu)成的路線是關(guān)鍵路線，它是時(shí)間最長(zhǎng)的路線1387/16/2024

時(shí)差-總時(shí)差作業(yè)時(shí)間參數(shù)及計(jì)算時(shí)差-單時(shí)差工序單時(shí)差——r(i,j)

表示不影響緊后工序最早開始時(shí)間的條件下，工序最早結(jié)束時(shí)間可以推遲的時(shí)間

r(i,j)=tES(j,k)–tEF(i,j)

tES(j,k)為工序(i,j)的緊后工序的最早開始時(shí)間單時(shí)差為0，總時(shí)差不一定為0總時(shí)差為0，單時(shí)差一定為01397/16/2024作業(yè)時(shí)間參數(shù)及計(jì)算時(shí)差-總時(shí)差與單時(shí)差的關(guān)系1407/16/2024作業(yè)時(shí)間參數(shù)及計(jì)算計(jì)算各作業(yè)的最早時(shí)間、最遲時(shí)間和時(shí)差。1417/16/2024作業(yè)時(shí)間參數(shù)及計(jì)算-例題時(shí)間參數(shù)的表上計(jì)算法1427/16/2024作業(yè)時(shí)間參數(shù)及計(jì)算-例題網(wǎng)絡(luò)計(jì)劃優(yōu)化工期優(yōu)化費(fèi)用優(yōu)化資源優(yōu)化7.7.3網(wǎng)絡(luò)優(yōu)化1437/16/2024該作業(yè)每天所需勞動(dòng)力該作業(yè)時(shí)間工期限定,資源平衡問題1447/16/2024關(guān)鍵路線作業(yè)總時(shí)差作業(yè)時(shí)間各工作都按最早開始時(shí)間開始1457/16/2024工期限定,資源平衡問題工期不變，就是關(guān)鍵工作時(shí)間不能調(diào)整，即不調(diào)整關(guān)鍵路線上的作業(yè)資源不平衡將導(dǎo)致資源不足利用時(shí)差，調(diào)整非關(guān)鍵路線上工作的開始時(shí)間，使資源實(shí)現(xiàn)平衡1467/16/2024工期限定,資源平衡問題1477/16/2024工期限定,資源平衡問題1487/16/2024工期限定,資源平衡問題某工程按作業(yè)最早開工期安排的日程網(wǎng)絡(luò)圖如下：若每天最多只有10人工作，試問如何安排才能使總工期最短？資源有限,工期最短1497/16/2024調(diào)整方案一1507/16/2024資源有限,工期最短調(diào)整方案二1517/16/2024資源有限,工期最短工程項(xiàng)目的成本費(fèi)用是和時(shí)間進(jìn)度有關(guān)的。

投入的資源愈多，作業(yè)時(shí)間也愈短反之，成本費(fèi)用可能低些，但作業(yè)時(shí)間會(huì)加長(zhǎng)綜合考慮費(fèi)用優(yōu)化主要有以下兩個(gè)方面：

工程周期給定，如何安排各項(xiàng)作業(yè)，使整個(gè)工程的直接費(fèi)用降低如果有一筆準(zhǔn)備用來加快工程進(jìn)度的追加費(fèi)用，如何安排才能使工程總周期縮短最多?；蛘哒f，如果要求工程縮短一定時(shí)間，如何安排才能使追加的費(fèi)用最小網(wǎng)絡(luò)計(jì)劃中的費(fèi)用優(yōu)化1527/16/2024工期-費(fèi)用關(guān)系曲線費(fèi)用工期總成本直接費(fèi)用間接費(fèi)用最短工期優(yōu)化工期正常工期1537/16/2024網(wǎng)絡(luò)計(jì)劃中的費(fèi)用優(yōu)化從正常工時(shí)每縮短一個(gè)單位時(shí)間所需增加的費(fèi)用成本斜率1547/16/2024網(wǎng)絡(luò)計(jì)劃中的費(fèi)用優(yōu)化ij特急工時(shí)正常工時(shí)成本斜率1557/16/2024網(wǎng)絡(luò)計(jì)劃中的費(fèi)用優(yōu)化工期=11天第一步求關(guān)鍵路線1567/16/2024網(wǎng)絡(luò)計(jì)劃中的費(fèi)用優(yōu)化第二步選擇(2,3)縮短工期1577/16/2024工期=10天增加費(fèi)用1網(wǎng)絡(luò)計(jì)劃中的費(fèi)用優(yōu)化-例題第三步按第II方案縮短工期1587/16/2024工期=9天累計(jì)增加費(fèi)用1+2=3網(wǎng)絡(luò)計(jì)劃中的費(fèi)用優(yōu)化-例題再按方案III縮短工期1597/16/2024工期=8天累計(jì)增加費(fèi)用3+3=6網(wǎng)絡(luò)計(jì)劃中的費(fèi)用優(yōu)化-例題第四步按第I、II方案縮短工期1607/16/2024工期=4天累計(jì)增加費(fèi)用6+16=22網(wǎng)絡(luò)計(jì)劃中的費(fèi)用優(yōu)化-例題縮短(1,2)與(3,4)，并調(diào)整(2,3)1617/16/2024工期=3天增加費(fèi)用22+5=27網(wǎng)絡(luò)計(jì)劃中的費(fèi)用優(yōu)化-例題總費(fèi)用最小的優(yōu)化一般還應(yīng)考慮間接費(fèi)用——工期縮短，總的間接費(fèi)用減少如果直接費(fèi)用的增加超過了間接費(fèi)用的減少，那么此時(shí)就不應(yīng)再縮短工期了例如，上例中，間接費(fèi)用率為：4.5/天，則因?yàn)樽詈笠徊恐苯淤M(fèi)率5/天>4.5/天，因此最后一步的工期不能縮短，工期應(yīng)為4天，此時(shí)可節(jié)省費(fèi)用3.5+2.5+1.5+4*0.5=9.5。1627/16/2024網(wǎng)絡(luò)計(jì)劃中的費(fèi)用優(yōu)化-例題當(dāng)網(wǎng)絡(luò)圖中工作很多，關(guān)鍵路線又不止一條時(shí)，靠觀察來確定縮短工時(shí)所需直接費(fèi)用增加最少的方案比較困難。此時(shí)可用求網(wǎng)絡(luò)最大流的標(biāo)號(hào)法來解決。

問題可轉(zhuǎn)化為：在全部以關(guān)鍵工序組成的網(wǎng)絡(luò)上，每邊容量取該工作的成本斜率（若該工作已不能縮短工時(shí)，容量標(biāo)為+∞），求網(wǎng)絡(luò)的最大流。當(dāng)求出最大流時(shí)，所得的最小割就是增加直接費(fèi)用最小的方案！1637/16/2024網(wǎng)絡(luò)計(jì)劃中的費(fèi)用優(yōu)化-例題2024/7/16第8章決策論164CONTENTS目錄8.1決策的概念與分類8.2確定型決策分析8.3不確定型決策分析8.4風(fēng)險(xiǎn)型決策分析8.5多準(zhǔn)則決策分析8.6

效用函數(shù)8.7行為決策理論2024/7/161658.1決策的概念與分類2024/7/16一個(gè)人駐足路口，選擇一條路線，其目的是為了達(dá)到渴望的目標(biāo)，或者避免不愉快的結(jié)果。決策的目的就是趨利避害。決策為什么如此重要？何謂決策？背景8.1.1

決策的概念1672024/7/16新中國(guó)成立之初是否出兵朝鮮背景1978年關(guān)于改革開放的重大決策國(guó)家的重大決策1682024/7/16背景俄羅斯與烏克蘭歐羅斯與歐盟歐羅斯與美國(guó)美國(guó)出兵伊拉克美國(guó)打擊伊斯蘭國(guó)恐怖勢(shì)力國(guó)家的重大決策1692024/7/16背景三峽工程是否要建？一直爭(zhēng)議不斷高鐵建設(shè)采用何種技術(shù)？南京長(zhǎng)江上修建大橋、建隧道？一些重大工程的決策1702024/7/16背景通俗地說就是從可選方案中選出一個(gè)方案以解決問題或達(dá)到某種目的；我們常常為達(dá)到某一特定的目標(biāo)尋找行動(dòng)的準(zhǔn)則或措施。為了回答涌現(xiàn)在我們周圍一個(gè)又一個(gè)的“怎么辦”也常常作出決擇，這種貌似簡(jiǎn)單的活動(dòng)，實(shí)質(zhì)上就是決策。什么是決策？1712024/7/16背景決策是人們?cè)谡J(rèn)識(shí)客觀世界的基礎(chǔ)上為了能動(dòng)地改造世界所開展的一種思維和選擇活動(dòng)；決策是多方案的選擇活動(dòng)，如果僅僅有一個(gè)候選方案，就不存在方案的選擇問題，因此每個(gè)決策問題都至少應(yīng)該有兩個(gè)備選方案；決策是一個(gè)過程，包括確定行動(dòng)目標(biāo)，分析環(huán)境條件與約束，選擇滿意的行動(dòng)方案；決策的目的是通過尋找并執(zhí)行最優(yōu)的方案達(dá)到最佳的效益。決策的核心1722024/7/16背景決策主體或決策者（Subject）決策信息集（InformationSet）規(guī)則集（RuleSet）狀態(tài)集（StateSet）時(shí)間（Time）決策環(huán)境（Environment）方案集（AlternativeSet）效用集（UtilitySet）決策包含8個(gè)主要要素1732024/7/16背景按照決策的狀態(tài)集分為確定型決策、不確定型決策和風(fēng)險(xiǎn)型決策按照決策過程重復(fù)的程度分為程序化決策和非程序化決策按照決策的內(nèi)容和層次分為戰(zhàn)略決策、戰(zhàn)術(shù)決策和執(zhí)行層的決策按照決策的階段數(shù)分為單階段決策和多階段決策8.1.2決策分類1742024/7/16背景如何做決策？8.1.3決策過程1752024/7/16176是去風(fēng)光綺麗的杭州還是去迷人的海邊北戴河或者是山水甲天下的桂林假期來臨，你選擇去哪兒旅行？2024/7/16背景確定一個(gè)旅游目的地，或把3個(gè)目的地進(jìn)行排序即為決策。其中可供選擇的旅游目的地“杭州”，“北戴河”，“桂林”稱為方案，或備選方案。你會(huì)根據(jù)諸如景色、費(fèi)用、居住、飲食、旅途條件等一些準(zhǔn)則去反復(fù)比較哪三個(gè)候選地點(diǎn)。假期來臨，你選擇去哪兒旅行？1772024/7/16為什么覺得難以選擇？標(biāo)題數(shù)字等都可以通過點(diǎn)擊和重新輸入進(jìn)行更改。添加標(biāo)題物理學(xué)經(jīng)濟(jì)學(xué)慣性被看做異常的、不能預(yù)料的行為粘性盡可能地和以前一樣消費(fèi)決策科學(xué)決策時(shí)不關(guān)心結(jié)果并具有重復(fù)之前選擇的傾向一是判別好壞的標(biāo)準(zhǔn)多了，難以權(quán)衡.二是對(duì)幾個(gè)目的地的不熟悉，信息不充分，難以準(zhǔn)確判定.特別是十一黃金周，人多帶來許多不確定.如果不是一個(gè)人出行，還要兼顧他人的意愿.。。。。。？多目標(biāo)不確定群決策1782024/7/16類似的決策問題標(biāo)題數(shù)字等都可以通過點(diǎn)擊和重新輸入進(jìn)行更改。添加標(biāo)題物理學(xué)經(jīng)濟(jì)學(xué)慣性被看做異常的、不能預(yù)料的行為粘性盡可能地和以前一樣消費(fèi)決策科學(xué)決策時(shí)不關(guān)心結(jié)果并具有重復(fù)之前選擇的傾向我們常常面臨著這樣的選擇：購(gòu)物：價(jià)廉物美測(cè)評(píng)：如學(xué)生對(duì)教師的評(píng)估，多項(xiàng)指標(biāo)買房：選擇要考慮環(huán)境、價(jià)格、距離等因素。。。。

1792024/7/16你如何做選擇的？標(biāo)題數(shù)字等都可以通過點(diǎn)擊和重新輸入進(jìn)行更改。添加標(biāo)題物理學(xué)經(jīng)濟(jì)學(xué)慣性被看做異常的、不能預(yù)料的行為粘性盡可能地和以前一樣消費(fèi)決策科學(xué)決策時(shí)不關(guān)心結(jié)果并具有重復(fù)之前選擇的傾向直覺、經(jīng)驗(yàn)請(qǐng)教別人抓鬮搜集資料、分析1802024/