運(yùn)籌學(xué)課件第6講雙代號(hào)網(wǎng)絡(luò)圖

引例：貝克特爾公司時(shí)間：1991年海灣戰(zhàn)爭后地點(diǎn)：科威特人物：項(xiàng)目管理小組事件：油田滅火大型項(xiàng)目管理階段劃分

1.規(guī)劃：（1）設(shè)定目標(biāo)（2）組織團(tuán)隊(duì)（3）將需求與定時(shí)項(xiàng)目活動(dòng)相連2.排程：將資源（人，財(cái)，物）與具體活動(dòng)相連所用工具：關(guān)鍵路線方法（CPM）；

網(wǎng)絡(luò)計(jì)劃平審方法（PERT）3.控制：（1）監(jiān)控資源，成本，質(zhì)量等（2）修訂，更改計(jì)劃（3）轉(zhuǎn)換資源以滿足時(shí)間，成本和質(zhì)量的要求項(xiàng)目排程的作用

1.顯示每項(xiàng)活動(dòng)之間以及與整個(gè)項(xiàng)目之間的關(guān)系。2.確定活動(dòng)之間的先后次序關(guān)系。3.對各項(xiàng)活動(dòng)進(jìn)行現(xiàn)實(shí)的排程和成本估計(jì)。4.確定項(xiàng)目中的關(guān)鍵障礙。

對生產(chǎn)、科研等項(xiàng)目（工程）的計(jì)劃和管理，用網(wǎng)絡(luò)圖表示；對網(wǎng)絡(luò)圖進(jìn)行分析；對項(xiàng)目的計(jì)劃和管理進(jìn)行統(tǒng)籌安排

現(xiàn)常用對項(xiàng)目（工程）的直觀圖示中，用橫線圖(條形圖（華羅庚）、甘特圖（Gantt）)。網(wǎng)絡(luò)圖的繪劃項(xiàng)目（工程）與網(wǎng)絡(luò)圖下面討論在對項(xiàng)目（工程）已經(jīng)分解成為工作，并已知工作邏輯關(guān)系后如何繪制網(wǎng)絡(luò)圖。雙代號(hào)網(wǎng)絡(luò)圖基本概念工序(作業(yè)、活動(dòng)、工作)：指任何消耗時(shí)間或資源的行動(dòng)。事項(xiàng)(節(jié)點(diǎn))：工序的開始或結(jié)束(發(fā)生于瞬間，既不消耗時(shí)間、也不消耗資源)。緊前工序：在另一工序開始前必須完成的工序。箭線：表示工序(作業(yè)、活動(dòng)、工作)。虛箭線表虛工序。ij工序名稱持續(xù)時(shí)間雙代號(hào)網(wǎng)絡(luò)圖的組成要素（1）實(shí)箭頭線：代表實(shí)際工序（2）虛箭頭線：代表虛工序（3）結(jié)點(diǎn)：代表工序的結(jié)束或開始，又稱事件或事項(xiàng)。關(guān)于結(jié)點(diǎn)的說明結(jié)點(diǎn)表示一個(gè)事項(xiàng)，又稱為事件，代表工序的開始或者結(jié)束。在雙代號(hào)網(wǎng)絡(luò)圖中，每道工序首尾都必須采用結(jié)點(diǎn)來表示，連接工序箭尾的結(jié)點(diǎn)稱為該工序的緊前事項(xiàng)，連接工序箭頭的結(jié)點(diǎn)稱為該工序的緊后事項(xiàng)。網(wǎng)絡(luò)圖的開始結(jié)點(diǎn)稱為總開工事項(xiàng)，而最后工序的結(jié)束結(jié)點(diǎn)稱為完工事項(xiàng)。在雙代號(hào)網(wǎng)絡(luò)圖中，結(jié)點(diǎn)采用圓圈表示，圈內(nèi)標(biāo)注上該結(jié)點(diǎn)的序號(hào)。結(jié)點(diǎn)編號(hào)一般采用箭桿刪除法進(jìn)行。繪制雙代號(hào)網(wǎng)絡(luò)圖規(guī)則1.不允許出現(xiàn)循環(huán)回路。2.每一箭頭線首尾必須有結(jié)點(diǎn)。3.任意兩個(gè)結(jié)點(diǎn)之間最多只能有一條箭頭線直接相連。4.總開工事項(xiàng)和完工事項(xiàng)都僅有一個(gè)。5.事項(xiàng)編號(hào)：一般采用箭桿刪除法。繪圖規(guī)則(雙代號(hào))1.起點(diǎn)和終點(diǎn)(一般都只一個(gè))2.方向和事項(xiàng)(節(jié)點(diǎn))3.虛工序4.兩個(gè)節(jié)點(diǎn)之間不能有兩道以上的工序5.網(wǎng)絡(luò)圖中不能有回路6.平行作業(yè)7.交叉作業(yè)(把工序分成多段進(jìn)行)8.作網(wǎng)絡(luò)圖9.節(jié)點(diǎn)的編號(hào)：結(jié)點(diǎn)編號(hào):編號(hào)從始點(diǎn)開始，從左到右，由小到大，始點(diǎn)編號(hào)最小，終點(diǎn)編號(hào)最大。41235ABCDE1235ABC4671235A1A2A3B1B2B3135ABC41235ABCDE平行工序的繪制：錯(cuò)誤圖710ACB

平行工序的繪制：正確圖710ACB89EF

交叉工序的繪制a1a2a3b3b1b2網(wǎng)絡(luò)圖繪制例1工序名稱ABCD緊前工序——AB1234ABCD網(wǎng)絡(luò)圖繪制例2正確嗎？工序名稱ABCD緊前工序——A,BBABCD

網(wǎng)絡(luò)圖繪制例2正確嗎？工序名稱ABCD緊前工序——A,BBABCD

E網(wǎng)絡(luò)圖繪制例2正確嗎？工序名稱ABCD緊前工序——A,BBABCDE

網(wǎng)絡(luò)圖繪制例2

工序名稱ABCD緊前工序——A，BB1234ABCDE

網(wǎng)絡(luò)圖繪制例3

正確嗎？

工序名稱ABCDEFGH緊前工序——ABC，DDEF1234567ACBFEGDHDFCE網(wǎng)絡(luò)圖時(shí)間參數(shù)事項(xiàng)最早時(shí)間tE(i),特別地，tE(n)為工程工期TE事項(xiàng)最遲時(shí)間tL(i)，特別地，tL(n)為工程工期TE工序(i,j)完成時(shí)間t(i,j)工序最早可能開工時(shí)間tES(i,j)

tES(i,j)=tE(i)注：從左往右計(jì)算工序最遲必須開工時(shí)間tLS(i,j)

tLS(i,j)=tL(j)-t(i,j)注：從右往左計(jì)算工序的總時(shí)差R(i,j)，即在不影響整個(gè)工期情況下工序最早可能開工時(shí)間可以推遲的時(shí)間數(shù)，它等于工序最遲必須開工時(shí)間與最早可能開工時(shí)間之差

R(i,j)=tLS(i,j)-tES(i,j)事項(xiàng)最早時(shí)間tE(j)事項(xiàng)最早時(shí)間tE(j)表示從起點(diǎn)事項(xiàng)到本事項(xiàng)的最短時(shí)間長度，通常從左往右逐個(gè)進(jìn)行計(jì)算。如果是箭尾事項(xiàng)，則事項(xiàng)最早時(shí)間為工序的最早可能開工時(shí)間。如果是箭頭事項(xiàng)，則事項(xiàng)最早時(shí)間為工序的最早可能結(jié)束時(shí)間。箭頭事項(xiàng)的最早時(shí)間等于箭尾事項(xiàng)最早時(shí)間加上作業(yè)時(shí)間t(i,j)，當(dāng)同時(shí)有兩個(gè)以上箭線指向箭頭事項(xiàng)時(shí)，應(yīng)該選擇各工序的箭尾事項(xiàng)最早時(shí)間與各工序作業(yè)時(shí)間之和的最大值，即：tE(1)=0

tE(j)=max{tE(i)+t(i,j)},j=1,2,…,n事項(xiàng)最遲時(shí)間tL(i)事項(xiàng)最遲時(shí)間tL(i)表示在不延誤工期的情況下從起點(diǎn)事項(xiàng)到本事項(xiàng)的最遲時(shí)間長度，通常從右往左（反順序?。┲饌€(gè)進(jìn)行計(jì)算。如果是箭頭事項(xiàng)，則事項(xiàng)最遲時(shí)間為各工序的最遲必須結(jié)束時(shí)間。如果是箭尾事項(xiàng)，則事項(xiàng)最遲時(shí)間為各工序的最遲必須開工時(shí)間。箭尾事項(xiàng)的最遲時(shí)間等于箭頭事項(xiàng)最遲時(shí)間減去工序的作業(yè)時(shí)間t(i,j)，當(dāng)箭尾同時(shí)有兩個(gè)以上箭線引出時(shí)，該箭尾事項(xiàng)的最遲時(shí)間必須同時(shí)滿足這些工序的最遲必須開工時(shí)間，因此必須選擇一個(gè)最早（最?。┑臅r(shí)間，即：

tL(n)=0,n為終點(diǎn)事項(xiàng)

tL(i)=max{tL(j)-t(i,j)},i=1,2,…,n-1工序的時(shí)間參數(shù)工序最早開始時(shí)間tES(i,j)：

tES(i,j)=tE(i)工序最早結(jié)束時(shí)間tEF(i,j)：

tEF(i,j)=tE(i)+t(i,j)工序最遲結(jié)束時(shí)間tLF(i,j)：

tLF(i,j)=tL(j)工序最遲開始時(shí)間tLS(i,j)：

tLS(i,j)=tLF(i)-t(i,j)工序的時(shí)差工序總時(shí)差TF（i,j）:指在不影響整個(gè)工期的前提下，工序最早開始（或結(jié)束）的時(shí)間可以推遲的時(shí)間。工序總時(shí)差=最遲開工時(shí)間-最早開工時(shí)間=最遲完工時(shí)間-最早完工時(shí)間工序的單時(shí)差FF（i,j）:指在不影響緊后工序的最早開工時(shí)間的條件下，工序最早開始（或結(jié)束）的時(shí)間可以推遲的時(shí)間。TF（i,j）=tLF(i,j)-tEF(i,j)

=tLF(i,j)-[tE(i)+t

(i,j)]=tL(j)-tE(i)-t

(i,j)=箭頭事項(xiàng)最遲時(shí)間-箭尾事項(xiàng)最早時(shí)間–工序作業(yè)時(shí)間求關(guān)鍵路線的圖上作業(yè)法步驟

1.正確繪制網(wǎng)絡(luò)圖2.從左至右逐點(diǎn)計(jì)算事項(xiàng)最早時(shí)間tE(i)3.從右至左逐點(diǎn)計(jì)算事項(xiàng)最遲時(shí)間tL(i)4.計(jì)算各工序最早開工時(shí)間和最遲開工時(shí)間5.計(jì)算總時(shí)差，確定關(guān)鍵工序和關(guān)鍵路線注：關(guān)鍵工序，指總時(shí)差為零的工序關(guān)鍵路線，指由關(guān)鍵工序連接而成的線路例：科研課題分解作業(yè)表工序代號(hào)工序緊前工序時(shí)間（天）A系統(tǒng)提出研究問題—4B研究選點(diǎn)問題A7C準(zhǔn)備調(diào)研方案A10D收集資料工作安排B8E挑選培訓(xùn)工作人員B，C12F準(zhǔn)備收集資料表格C7G實(shí)地調(diào)查D，E，F(xiàn)5H分析準(zhǔn)備調(diào)查報(bào)告G4I任務(wù)結(jié)束H0例繪制網(wǎng)絡(luò)圖IHGDEFBCA1234567894710812754000例計(jì)算事項(xiàng)最早時(shí)間IHGDEFBCA12345678947108127540000411141426313535例計(jì)算事項(xiàng)最遲時(shí)間IHGDEFBCA123456789471081275400000441114141414142626313135353535例計(jì)算工序最早和最遲開工時(shí)間(i,j)

IHGDEFBCA123456789471081275400000441114141414142626313135353535(0，0)(4，7)(4，4)(11，18)(14，14)(14,19)(26，26)(31，31)(35，35)工序的時(shí)差工序總時(shí)差TF（i,j）:指在不影響整個(gè)工期的前提下，工序最早開始（或結(jié)束）的時(shí)間可以推遲的時(shí)間。工序總時(shí)差=最遲開工時(shí)間-最早開工時(shí)間=最遲完工時(shí)間-最早完工時(shí)間工序的單時(shí)差FF（i,j）:指在不影響緊后工序的最早開工時(shí)間的條件下，工序最早開始（或結(jié)束）的時(shí)間可以推遲的時(shí)間。TF（i,j）=tLF(i,j)-tEF(i,j)=tLF(i,j)-[tE(i)+t

(i,j)]=tL(j)-tE(i)-t

(i,j)=箭頭事項(xiàng)最遲時(shí)間-箭尾事項(xiàng)最早時(shí)間–工序作業(yè)時(shí)間例計(jì)算總時(shí)差，確定關(guān)鍵工序和關(guān)鍵路線

IHGDEFBCA12