運(yùn)籌學(xué)課件（第十一講）-網(wǎng)絡(luò)最大流的基本概念

運(yùn)籌學(xué)課程網(wǎng)絡(luò)最大流的基本概念（1）網(wǎng)絡(luò)與流實(shí)例容量網(wǎng)絡(luò)的特點(diǎn)分析（1）每條弧上的流量必須是非負(fù)的且不能超過(guò)該弧的最大通過(guò)能力(即該弧的容量)；（2）起點(diǎn)發(fā)出的流的總和(稱為流量)，必須等于終點(diǎn)接收的流的總和；（3）各中間點(diǎn)流入的流量之和必須等于從該點(diǎn)流出的流量之和，即流入的流量之和與流出的流量之和的差為0，也就是說(shuō)各中間點(diǎn)只起轉(zhuǎn)運(yùn)作用，它既不產(chǎn)出新的物資，也不得截留過(guò)境的物資．網(wǎng)絡(luò)最大流的基本概念（2）可行流的基本概念網(wǎng)絡(luò)最大流的基本概念（3）可行流的討論（1）可行流總是存在的（2）（3）上面實(shí)例所給出的運(yùn)輸方案，是否為可行流最大流的基本概念網(wǎng)絡(luò)最大流的基本概念（4）實(shí)例網(wǎng)絡(luò)最大流的基本概念（5）截集與截量的基本概念截集概念截集特點(diǎn)（1）（2）截量截量的性質(zhì)分析（1）（2）（3）最大流量最小截量定理實(shí)例：求從v1到v6的最大流網(wǎng)絡(luò)最大流的基本概念（6）增廣鏈的基本概念實(shí)例：尋找圖中增廣鏈網(wǎng)絡(luò)最大流的基本概念（7）最大流與增廣鏈定理在容量網(wǎng)絡(luò)D中，可行流f*是最大流的充分必要條件是不存在關(guān)于f*的增廣鏈證明：必要性實(shí)例：

計(jì)算網(wǎng)絡(luò)最大流的標(biāo)號(hào)法求解思路在容量網(wǎng)絡(luò)中，若給定一個(gè)可行流f，只要判斷網(wǎng)絡(luò)中有無(wú)關(guān)于f的增廣鏈，如果有則進(jìn)行改進(jìn)f，得到一個(gè)新的流量增大的可行流，如果沒(méi)有增廣鏈，則得到了最大流。求解步驟（1）標(biāo)號(hào)過(guò)程（2）調(diào)整過(guò)程我們的目標(biāo)是盡快找到一條從起點(diǎn)vs到終點(diǎn)vt的增廣鏈，所以沒(méi)必要在中途多停留，即對(duì)已標(biāo)號(hào)的vi，每次只檢查一個(gè)相鄰點(diǎn)vj，再給vj標(biāo)號(hào)，沒(méi)有必要檢查vi的所有相鄰點(diǎn)，這樣一次可改進(jìn)一條增廣鏈，只到?jīng)]有增廣鏈為止實(shí)例1實(shí)例2求從1出發(fā)到5的最大流實(shí)例第十一章網(wǎng)絡(luò)計(jì)劃概述網(wǎng)絡(luò)計(jì)劃方法是一種項(xiàng)目管理技術(shù)，合理安排項(xiàng)目的時(shí)間進(jìn)度，以及人力、物力、財(cái)力等資源。美國(guó)是網(wǎng)絡(luò)計(jì)劃技術(shù)的發(fā)源地，并廣泛應(yīng)用。20世紀(jì)50年代末，錢學(xué)森將將網(wǎng)絡(luò)計(jì)劃技術(shù)引入我國(guó)，并在航天領(lǐng)域應(yīng)用。華羅庚在我國(guó)的網(wǎng)絡(luò)計(jì)劃方法推廣普及等方面做出杰出貢獻(xiàn)。網(wǎng)絡(luò)計(jì)劃圖（1）基本概念工作（作業(yè)、工序）在項(xiàng)目中，消耗時(shí)間和資源的行動(dòng)。用有方向的箭頭表示事件（時(shí)間節(jié)點(diǎn)、Milestone)標(biāo)志工作（作業(yè)、工序）的開始或結(jié)束的點(diǎn)，本身不消耗資源。用圈或正方形表示，使工作兩端的連接點(diǎn)。網(wǎng)絡(luò)計(jì)劃圖有工作（弧）和事件（節(jié)點(diǎn)）所組成的有向圖路線從項(xiàng)目的最初事件到項(xiàng)目的最終事件、有各項(xiàng)工作連貫組成的的一條路工作名稱或代號(hào)持續(xù)時(shí)間或消耗資源i工作名稱或代號(hào)持續(xù)時(shí)間或消耗資源j網(wǎng)絡(luò)計(jì)劃圖（2）畫網(wǎng)絡(luò)計(jì)劃圖的注意事項(xiàng)（1）從左到右，從上到下畫。一項(xiàng)工作箭頭處的事件標(biāo)號(hào)，必須大于箭尾處事件標(biāo)號(hào)（2）相鄰工作緊前工作：緊排在本工作之前的工作。緊后工作：緊排在本工作之后的工作。網(wǎng)絡(luò)計(jì)劃圖（3）（3）虛工作僅用來(lái)表示相鄰工作之間的邏輯關(guān)系，不占用時(shí)間，不消耗資源的虛擬工作。（4）相鄰兩個(gè)事件之間只能有一條箭線（工作），否則添加虛事件、虛工作網(wǎng)絡(luò)計(jì)劃圖（4）（5）網(wǎng)路計(jì)劃圖中不能有回路出現(xiàn)（6）網(wǎng)絡(luò)計(jì)劃圖中，僅有一個(gè)起點(diǎn)（代表項(xiàng)目開始），僅有一個(gè)終點(diǎn)（代表項(xiàng)目結(jié)束）（7）網(wǎng)絡(luò)計(jì)劃圖中盡量避免出現(xiàn)交叉線實(shí)例1實(shí)例2新產(chǎn)品項(xiàng)目，需要完成的工作和先后關(guān)系，各項(xiàng)工作需要的時(shí)間匯總在下表中，編制網(wǎng)絡(luò)計(jì)劃圖。實(shí)例3關(guān)鍵路線法（CriticalPathMethod）時(shí)間路線連接項(xiàng)目起點(diǎn)與項(xiàng)目終點(diǎn)的線路，并將該線路上的各項(xiàng)工作（弧）所耗費(fèi)的時(shí)間相加關(guān)鍵時(shí)間路線各條時(shí)間線路中，耗時(shí)最長(zhǎng)的時(shí)間路線意義關(guān)鍵時(shí)間路線是決定項(xiàng)目工期的主要矛盾，應(yīng)集中資源（人力、物力、財(cái)力），盡量縮短關(guān)鍵時(shí)間路線的長(zhǎng)度，可減少項(xiàng)目工期。網(wǎng)絡(luò)計(jì)劃圖（6）實(shí)例求上例中的關(guān)鍵時(shí)間路線網(wǎng)絡(luò)計(jì)劃圖的時(shí)間參數(shù)計(jì)算（1）網(wǎng)絡(luò)規(guī)劃圖中事件的時(shí)間參數(shù)事件的最早時(shí)間tE（j）網(wǎng)絡(luò)計(jì)劃圖的時(shí)間參數(shù)計(jì)算（2）事件的最遲時(shí)間tL（i）網(wǎng)絡(luò)計(jì)劃圖的時(shí)間參數(shù)計(jì)算（3）工作的時(shí)間參數(shù)工作最早開始時(shí)間（EarlyStart，ES）與工作最早完成時(shí)間（EarlyFinish，EF）網(wǎng)絡(luò)計(jì)劃圖的時(shí)間參數(shù)計(jì)算（4）工作的最遲必須開始時(shí)間（LastStart，LS）與工作的最遲必須完成時(shí)間（LastFinish，LF）事件時(shí)間參數(shù)與工作時(shí)間參數(shù)的關(guān)系任一事件i（除去始點(diǎn)事件和終點(diǎn)事件），即表示某些工作的開始又表示某些工作的結(jié)束。對(duì)于工作（i，j）有網(wǎng)絡(luò)計(jì)劃圖的時(shí)間參數(shù)計(jì)算（5）網(wǎng)絡(luò)計(jì)劃圖的時(shí)間參數(shù)計(jì)算（6）時(shí)差（工作的機(jī)動(dòng)時(shí)間）工作的總時(shí)差工作的單時(shí)差網(wǎng)絡(luò)計(jì)劃圖的時(shí)間參數(shù)計(jì)算（7）討論（1）工作總時(shí)差往往為