補(bǔ)充：關(guān)鍵路徑

1、1關(guān)鍵路徑以AOE（activity on edge）網(wǎng)表示。 研究重點(diǎn)：（1）完成整個(gè)工程需要多少時(shí)間？（2）哪些活動(dòng)是關(guān)鍵活動(dòng)，會(huì)影響到工程進(jìn)度？如圖：這是一個(gè)有向無(wú)環(huán)圖。 頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)值表示活動(dòng)的持續(xù)時(shí)間。所以，AOE網(wǎng)常用來(lái)估算一個(gè)工程的完成時(shí)間。 右圖：9個(gè)事件v1,v2v9，11項(xiàng)活動(dòng)a1a11。 規(guī)定：整個(gè)工程只有一個(gè)開始點(diǎn)，一個(gè)結(jié)束點(diǎn)。并且入度為0的頂點(diǎn)稱為源點(diǎn)，出度為0稱為匯點(diǎn)。某一事件發(fā)生，說(shuō)明之前的活動(dòng)都已完成，之后的活動(dòng)可以開始。 說(shuō)明：某些活動(dòng)可以同時(shí)開工。如a1、a2、a3，a7與a8就可以同時(shí)開始。2關(guān)鍵路徑完成工程的最短時(shí)間是從開始點(diǎn)到完成點(diǎn)的最

2、長(zhǎng)路徑長(zhǎng)度。指此路徑上的各活動(dòng)所花費(fèi)時(shí)間之和，不是弧的數(shù)目之和。那么此路徑就稱之為關(guān)鍵路徑。 右圖：v1為開始點(diǎn)，從v1到vj的最長(zhǎng)路徑長(zhǎng)度稱為vj 的最早發(fā)生時(shí)間ve(j)。此時(shí)，說(shuō)明并且以vj為弧頭的工作俱已完成，以vj為弧尾的活動(dòng)（如ai）可以開始，也稱為ai的最早開始時(shí)間，記為e(i)，相對(duì)應(yīng)的，不影響工程進(jìn)度的情況下還有一個(gè)最遲開工時(shí)間，記為l(i)。兩者之差l(i)- e(i)表示活動(dòng)ai的時(shí)間余量。如果某活動(dòng)的l(i)= e(i)則稱為關(guān)鍵活動(dòng)。3關(guān)鍵路徑如果有活動(dòng)ai由弧表示，其持續(xù)時(shí)間為dut（），則有：求ve(j)和vl(j)步驟為：1、因?yàn)関e(1)=0，從開始點(diǎn)向后遞推

3、：2、因?yàn)関l(n)=ve(n)，從完成點(diǎn)向前遞推：4關(guān)鍵路徑所以，求取關(guān)鍵路徑的算法可總結(jié)如下：1、輸入e條弧，建立AOE網(wǎng)；2、從源點(diǎn)（開始點(diǎn)）v1開始，以ve(1)=0為基礎(chǔ)，按照公式求其余各頂點(diǎn)的最早發(fā)生時(shí)間ve(j)；注意：若得到的拓?fù)溆行蛐蛄许旤c(diǎn)個(gè)數(shù)小于網(wǎng)頂點(diǎn)個(gè)數(shù)n，則說(shuō)明有環(huán)的存在，關(guān)鍵路徑求取失敗！3、從匯點(diǎn)（完成點(diǎn)）vn開始，以vl(n)=ve(n)為基礎(chǔ)，按照公式求其余各頂點(diǎn)的最遲發(fā)生時(shí)間vl(j)；4、根據(jù)各頂點(diǎn)的ve和vl值，求每條?。ɑ顒?dòng)）的最早開始時(shí)間e(i)和最遲開始時(shí)間l(i)，并尋找e(i) = l(i) 的弧，此為關(guān)鍵活動(dòng)；5、把所有的關(guān)鍵活動(dòng)及相應(yīng)頂點(diǎn)畫出，即為關(guān)鍵路徑。5關(guān)鍵路徑以右圖為例： 0181814141616066457768710000000000022336664285377777161614141036關(guān)鍵路徑所以關(guān)鍵路徑如右圖所示 問(wèn)題（2）的回答：在不改變網(wǎng)的關(guān)鍵路徑的前提下 ，提