運籌學(xué)基礎(chǔ) 課件 宋志華 第5、6章 動態(tài)規(guī)劃、網(wǎng)絡(luò)計劃

第5章動態(tài)規(guī)劃5.1多階段決策問題5.2網(wǎng)絡(luò)模型5.3Bellman遞歸方程5.4典型案例

5.1多階段決策問題

當(dāng)問題的對象處于某種狀態(tài)x時,會有一個決策集合μ{x}(在最優(yōu)控制中,決策也稱為控制),當(dāng)選定某種決策μi∈μ{x}并且付諸行動之后,問題的對象會從狀態(tài)x轉(zhuǎn)移為狀態(tài)y,一般可記為行動的成本記為

例5-1(多階段最短路問題)對如圖5-1所示的圖求解從起點S到終點E的最短路。

如果將圖5-1中的點看作決策問題的狀態(tài),則這個問題具有明顯的階段性,且狀態(tài)僅在相鄰的狀態(tài)之間向后轉(zhuǎn)移,因此這是一個多階段決策問題。狀態(tài)集合為

圖5-1多階段最短路問題

例5-2(背包問題)給定n種物品,每種物品都有自己的質(zhì)量wi和價值ri,背包的最大承重為W,請選擇裝入背包物品的種類和數(shù)量,使裝入背包的物品總價值最高。

假設(shè)背包最大承重W=10,可裝物品的單件質(zhì)量和單件價值如表5-1所示,可裝物品的數(shù)量足夠。

第4階段:考慮裝入C類物品,將第3階段狀態(tài)作為起始狀態(tài),其對應(yīng)的決策、到達(dá)狀態(tài)及行動收益如表5-3所示。

第5階段:只有一個結(jié)束狀態(tài),記為x26。從第4階段的狀態(tài)到x26的狀態(tài)轉(zhuǎn)移收益均為0。

5.2網(wǎng)絡(luò)模型在多階段決策問題中,如果令狀態(tài)集合X=X1∪X2∪…∪Xn代表網(wǎng)絡(luò)上的點集,狀態(tài)x到y(tǒng)的轉(zhuǎn)移y=f(x,μi)作為網(wǎng)絡(luò)上的邊,而狀態(tài)轉(zhuǎn)移的行動費用作為邊上的權(quán)重,則每一個多階段決策問題都可以轉(zhuǎn)換為一個網(wǎng)絡(luò)模型,即其中,

多階段決策問題網(wǎng)絡(luò)模型建立的過程如下:

步驟1:分析決策問題的狀態(tài)有哪些,將時間或者步驟分成n個階段,分析每個階段的狀態(tài),由此可以確定網(wǎng)絡(luò)上點的子集Vi。

步驟2:分析狀態(tài)之間是否有可能存在可行的遷移,如果存在,則分析狀態(tài)遷移的成本或者費用,并將其作為兩點之間的狀態(tài)轉(zhuǎn)移費用,由此可以確定序號相鄰子集之間的邊及邊的權(quán)重。

步驟3:根據(jù)問題分析起始狀態(tài)和最終狀態(tài),確定起點和終點。

5.3Bellman遞歸方程

5.3.1最優(yōu)性原則最優(yōu)性原則對以后階段所做出的未來決策將會產(chǎn)生一個最優(yōu)策略,它與前面各階段所采用的策略無關(guān)。在多階段決策問題的模型中,假設(shè)對階段k以后所做出的最優(yōu)策略為π*=(μk,…,μn),即則根據(jù)最優(yōu)性原則,π*與前面各階段X1,…,Xk-1所采用的策略無關(guān)。

最優(yōu)子結(jié)構(gòu)定理對滿足最優(yōu)性原則的多階段決策問題,最優(yōu)決策序列的子序列也是最優(yōu)的。

證明:假設(shè)路徑(A,A1,A2,…,Am,C,B1,B2,…,Bn,B)為從A到B的最優(yōu)決策序列,那么其子序列一定也是最優(yōu)的。例如,A,A1,A2,…,Am,C一定是從A到C的最優(yōu)決策序列,C,B1,B2,…,Bn,B也一定是從C到B的最優(yōu)決策序列。利用反證法很容易證明(證明略)。

需要注意的是,如果多階段決策問題不滿足最優(yōu)性原則,則不一定滿足最優(yōu)子結(jié)構(gòu)定理,也就是說,其最優(yōu)決策序列的子序列不一定是最優(yōu)的。

例5-3某導(dǎo)彈部隊的導(dǎo)彈火力單元隱蔽待機于待機地p1和p2,接收到3波次火力打擊任務(wù)?；鹆卧枰ㄟ^網(wǎng)絡(luò)(見圖5-2)機動到某導(dǎo)彈倉庫dj(j=1,2,…,5)裝載導(dǎo)彈,然后通過網(wǎng)絡(luò)機動到某一個發(fā)射點ri

(i=1,2,…,30)發(fā)射導(dǎo)彈,完成1波次的發(fā)射任務(wù)。整個任務(wù)需要完成3波次的打擊。假設(shè)為了提高生存能力,在整個火力打擊任務(wù)中,所有的火力單元均不會第二次使用同一個發(fā)射點,直到所有的火力單元都完成3波次火力打擊任務(wù)為止,則可以建立如圖5-3所示的多階段決策問題的網(wǎng)絡(luò)模型。

圖5-2多波次導(dǎo)彈火力打擊行動網(wǎng)絡(luò)

圖5-33波次導(dǎo)彈火力打擊行動問題的多階段網(wǎng)絡(luò)模型

圖5-3中,虛線所示的有向邊的權(quán)重為狀態(tài)轉(zhuǎn)移所對應(yīng)的物理上兩個地點的最短路的距離?；鹆卧娜我饪尚行袆勇窂揭欢▽?yīng)圖5-3所示模型中的一條從s到e的路,但是,一條從s到e的路未必是火力單元可行的行動路徑,因為要滿足發(fā)射點不重復(fù)的約束。例如,存在這種情況:從s到e的最短路如圖5-4中加粗實線箭頭所示,但是,根據(jù)發(fā)射點不重復(fù)的約束,這不是火力單元的一條可行路徑。

圖5-4模型的可行路徑未必是火力單元的可行路徑

因為要滿足發(fā)射點不重復(fù)的約束,這個模型不滿足最優(yōu)性原則,也就是對以后階段所做出的未來決策將會產(chǎn)生一個最優(yōu)策略,它與前面各階段所采用的策略不是無關(guān)的。這個模型也不滿足最優(yōu)子結(jié)構(gòu)定理。對于某個火力單元的最優(yōu)路徑,其子路徑不一定是最優(yōu)的。例如,存在這種情況:某火力單元的最優(yōu)路徑如圖5-5中加粗實線箭頭所示,則從第5階段的d1到e的子路徑不一定是最優(yōu)的。

圖5-5-3波次導(dǎo)彈火力打擊行動模型不滿足最優(yōu)子結(jié)構(gòu)定理

5.3.2兩個推論

5.3.3兩個方程

5.3.4多階段最短路問題的求解

例5-4利用Bellman逆序方程求解多階段最短路問題(見圖5-1)的具體步驟如下:

因此,從S到E的最短路長度為21。最短路的序列可以從求解的過程數(shù)據(jù)倒推得到。例5-1中,最短路的序列包括以下幾個:

利用Bellman順序方程求解多階段最短路問題(見圖5-1)的具體步驟如下:

5.4典型案例

5.4.1背包問題1.問題描述背包問題可以描述為:給定n種物品,每種物品都有自己的質(zhì)量wi和價值ri。背包的最大承重為W,請選擇裝入背包物品的種類和數(shù)量,使裝入背包的物品總價值最高。

如果令裝入第i(i=1,2,…,n)種物品的數(shù)量為xi,則可以建立如下背包問題的整數(shù)規(guī)劃模型:

2.建立動態(tài)規(guī)劃模型

建立動態(tài)規(guī)劃模型的具體步驟如下:

步驟1:輸入背包問題的參數(shù),確定階段的數(shù)量。將問題分成n+2個階段,增加一個虛擬的起始狀態(tài)和一個虛擬的結(jié)束狀態(tài),中間每個階段考慮一種類型的物品。因為要最大化背包中物品的價值,所以將單位物品的價值加上一個負(fù)號。

步驟2:建立每個階段狀態(tài)的集合,第1階段的狀態(tài)設(shè)定為一個虛擬的起點,最后一個階段也就是第NStage階段的狀態(tài)設(shè)定為一個虛擬的終點。狀態(tài)為當(dāng)前背包中物品的質(zhì)量。狀態(tài)之間是否可以轉(zhuǎn)移或者說點之間是否有邊相連,取決于兩個狀態(tài)之間的轉(zhuǎn)移是否對應(yīng)一種可行的裝包方案,也就是包里物品總質(zhì)量的增加是否是當(dāng)前物品的整數(shù)倍。相鄰兩個階段點xi(k)和xi-1(h)的狀態(tài)轉(zhuǎn)移采用如下規(guī)則確定:

若mod((xi(k)-xi-1

(h)),wi)=0,且xi(k)≥xi-1

(h),則兩者之間有邊相連,邊的權(quán)重為

建立的背包問題模型如圖5-6所示。圖5-6背包問題的動態(tài)規(guī)劃模型

3.求解

利用動態(tài)規(guī)劃的順序方程進行求解。

程序運行結(jié)果如圖5-7所示,其中最優(yōu)的決策序列使用加粗的路徑標(biāo)識。

圖5-7背包問題的動態(tài)規(guī)劃順序方程求解

5.4.2設(shè)備更新問題

1.問題描述

設(shè)備更新問題可以使用動態(tài)規(guī)劃的模型求解。設(shè)備更新問題是指機器或者設(shè)備(如汽車)會隨著使用年數(shù)的增加而老化,從而導(dǎo)致運行成本c的增加,折舊現(xiàn)值s的減少,收入r的減少,但是購買新機器又要花費一大筆費用,因此需要我們決定什么時候替換現(xiàn)有的機器,什么時候再替換,等等,以便在未來的N年內(nèi)將總成本降到最低。

例5-6某部門要對一臺已經(jīng)使用了2年的設(shè)備確定今后5年的最優(yōu)更新策略。已知設(shè)備的最大使用年限為6年,購買一臺新機器的費用是1000萬元。該問題的基本數(shù)據(jù)見表5-4。

2.建立動態(tài)規(guī)劃模型

假設(shè)我們必須在N個時間段內(nèi)(如年份)都擁有這樣一臺機器,令y表示機器當(dāng)前的年齡,c(i)表示一臺年初年齡為i的機器運行一年的運行成本,s(i)表示一臺年初年齡為i的機器折舊之后的現(xiàn)值,r(i)表示一臺年初年齡為i的機器運行一年能帶來的收入,Newr表示一臺新機器(0歲)的價格,則建立模型如下:

(1)確定階段。

(2)確定每個階段的狀態(tài)。

(3)確定相鄰階段狀態(tài)之間的轉(zhuǎn)移是否存在以及收益是多少。

3.求解

求解的具體步驟如下:

步驟1:輸入問題的基本參數(shù)。

步驟2:建立每個階段狀態(tài)的集合,第1階段的狀態(tài)設(shè)定為一個虛擬的起點,最后一階段也就是第NStage階段的狀態(tài)設(shè)定為一個虛擬的終點。中間的階段狀態(tài)設(shè)定為各種可能的設(shè)備年齡。

步驟3:建立鄰接矩陣,也就是檢驗每個前一階段的點與后一階段的點之間可能存在的狀態(tài)轉(zhuǎn)移,并計算狀態(tài)轉(zhuǎn)移的權(quán)重,將其存入狀態(tài)轉(zhuǎn)移矩陣A。

得到的動態(tài)規(guī)劃模型如圖5-8所示。圖5-8設(shè)備更新問題的動態(tài)規(guī)劃模型

步驟4:利用動態(tài)規(guī)劃的遞歸方程進行求解。

程序運行結(jié)果如圖5-9所示,其中最優(yōu)的決策序列使用加粗的路徑標(biāo)識。

圖5-9設(shè)備更新問題的動態(tài)規(guī)劃最優(yōu)解

5.4.3過河問題

1.問題描述

小明一家四口人要過河。單獨過河爸爸要1分鐘,媽媽要2分鐘,小明要5分鐘,弟弟要10分鐘。最多兩個人同時過河,并且只有一個手電筒,每次都需要手電筒。兩人過河按慢的時間算。請設(shè)計過河方案,使一家人過河總時間最少。

2.問題分析

為了描述方便,將爸爸、媽媽、小明、弟弟分別記為A、B、C、D。假設(shè)過河時的順序為從左到右,回程時的順序為從右到左,過河的時候兩個人,回程的時候一個人。

將系統(tǒng)的狀態(tài)記為沒有過河的人的組合,因此,起始狀態(tài)記為ABCD,代表四個人都沒有過河;最終的狀態(tài)為?,代表一家人都已過河。

3.建立模型

步驟1:第1階段的狀態(tài)集合為X1={ABCD},決策集合為{AB,AC,AD,BC,BD,CD},代表選擇兩個尚未過河的人一起過河,從起始狀態(tài)到第2階段的決策、到達(dá)狀態(tài)、行動耗時如表5-5所示。

步驟2:由表5-5可得第2階段的狀態(tài)集合為

下一步?jīng)Q策的內(nèi)容為選擇一個已經(jīng)過河的人帶手電筒回來,其決策、到達(dá)狀態(tài)、行動耗時如表5-6所示。

步驟3:由表5-6可得第3階段的狀態(tài)集合為

下一步?jīng)Q策的內(nèi)容為選擇兩個尚未過河的人一起過河,其決策、到達(dá)狀態(tài)、行動耗時如表5-7所示。

步驟4:由表5-7可得第4階段的狀態(tài)集合為

下一步?jīng)Q策的內(nèi)容為選擇一個已經(jīng)過河的人帶手電筒回來,其決策、到達(dá)狀態(tài)、行動耗時如表5-8所示。

步驟5:由表5-8可得第5階段的狀態(tài)集合為

下一步?jīng)Q策的內(nèi)容為選擇兩個尚未過河的人一起過河,其決策、到達(dá)狀態(tài)、行動耗時如表5-9所示。

4.求解

上述動態(tài)規(guī)劃模型中的階段、狀態(tài)、狀態(tài)轉(zhuǎn)移、行動耗時等均可使用動態(tài)規(guī)劃的圖模型來表示,如圖5-10所示。

圖5-10過河問題的動態(tài)規(guī)劃模型

程序運行結(jié)果如圖5-11所示圖5-11過河問題的動態(tài)規(guī)劃解

5.討論

值得注意的是,本題如果使用貪婪規(guī)則,也就是每次都派過河最快的A出動,則總的過河時間是19分鐘,不是最優(yōu)的,這與經(jīng)常在實際中出現(xiàn)的能者多勞的思想并不一致。經(jīng)過優(yōu)化后,工作效率提升超過5%。

5.4.4炮兵陣地問題

1.問題描述

司令部的將軍們打算在M×N的網(wǎng)格地圖上部署他們的炮兵部隊。一個M×N的網(wǎng)絡(luò)地圖由M行N列組成,其中的每一格可能是山地(用“-1”表示),也可能是平原(用“0”

表示),如圖5-12所示。在每一格平原地形上最多可以部署一支炮兵部隊(山地上不能部署炮兵部隊);如果在圖中的灰色格上部署一支炮兵部隊,則圖中的黑色網(wǎng)格表示它能夠攻擊到的區(qū)域:沿橫向左右各兩格,沿縱向上下各兩格。圖上的白色網(wǎng)格均表示攻擊不到的區(qū)域。由圖5-12可見炮兵的攻擊范圍不受地形的影響。

圖5-12炮兵部署及其攻擊范圍(部署于灰色格處,攻擊范圍為黑色格)

2.問題分析

如果將一種部署方案作為一個狀態(tài),那么起始狀態(tài)如圖5-13所示。圖5-13起始狀態(tài)

第2階段的狀態(tài)為在平原上部署一支炮兵部隊,其態(tài)勢圖如圖5-14所示。圖5-14在平原上部署一支炮兵部隊后的態(tài)勢圖

為了計算方便,我們將黑色區(qū)域標(biāo)記為2,代表已經(jīng)處于炮兵的攻擊范圍,不再考慮部署,將已經(jīng)部署炮兵的格子標(biāo)記為1,代表已經(jīng)部署炮兵部隊,也不再考慮部署,因此,這個狀態(tài)可以表示為如圖5-15所示的形式。

圖5-15-第2階段的狀態(tài)

3.建立模型

步驟1:第1階段使用矩陣Map存儲狀態(tài)，從起始狀態(tài)開始，針對所有的平原方格，判斷期可部署性，如果可以部署，則計算部署后的狀態(tài)矩陣，并將其作為第2階段的一個狀態(tài)。

步驟2:針對第Kmax(>2)階段,從Kmax-1階段的狀態(tài)開始,判斷是否可以進一步部署一支炮兵部隊,如果可以部署,則計算部署后的狀態(tài),將其歸并到第Kmax階段的狀態(tài),并記錄狀態(tài)與狀態(tài)之間的轉(zhuǎn)移關(guān)系到鄰接矩陣A。如果第K-1階段的狀態(tài)都無法進一步部署炮兵部隊,則算法結(jié)束。

對于本例來講,建立的動態(tài)規(guī)劃模型如圖5-16所示,可知最多可以部署三支炮兵部隊,具體方案如圖5-17所示。圖5-16炮兵陣地問題的動態(tài)規(guī)劃模型

圖5-17炮兵陣地部署問題的三個方案

5.4.5-巡邏隊分配問題

1.問題描述

某一警衛(wèi)部門共有12支巡邏隊,負(fù)責(zé)4個要害部位A、B、C、D的警衛(wèi)巡邏。對每個部位可分別派出2~4支巡邏隊,并且由于派出巡邏隊數(shù)量的不同,各部位預(yù)期在一段時期內(nèi)可能造成的損失有差別,具體數(shù)字如表5-10所示。問警衛(wèi)部門應(yīng)往各部位分別派多少支巡邏隊,可使總的預(yù)期損失最小?

2.建立模型

為了陳述方便,將巡邏隊數(shù)量2、3、4對應(yīng)的方案分別稱為巡邏方案1、2、3,四個部位A、B、C、D分別編號為1、2、3、4。

使用第i個巡邏方案巡邏部位j的損失變量記為cij,決策變量記為xij,則可以建立如下0－1整數(shù)規(guī)劃模型:

步驟1:第1階段的狀態(tài)集合為X1={0},代表尚未開始指派;決策集合為{2,3,4},代表可以為A區(qū)域指派2、3或者4個巡邏隊。從起始狀態(tài)到第2階段的決策、到達(dá)狀態(tài)、轉(zhuǎn)移費用如表5-11所示。

步驟2:第2階段的狀態(tài)集合為X2={2,3,4},決策集合為{2,3,4},代表可以為B區(qū)域指派2、3或者4個巡邏隊。從第2階段到第3階段的決策、到達(dá)狀態(tài)、轉(zhuǎn)移費用如表5-12所示。

步驟3:第3階段的狀態(tài)集合為X3={4,5,6,7,8},決策集合為{2,3,4},代表可以為C區(qū)域指派2、3或者4個巡邏隊。從第3階段到第4階段的決策、到達(dá)狀態(tài)、轉(zhuǎn)移費用如表5-13所示。

步驟4:第4階段的狀態(tài)集合為X4={6,7,8,9,10,11,12},決策集合為{2,3,4},代表可以為D區(qū)域指派2、3或者4個巡邏隊。從第4階段到第5階段的決策、到達(dá)狀態(tài)、轉(zhuǎn)移費用如表5-14所示,其中灰色區(qū)域的到達(dá)狀態(tài)大于12,不可行。

步驟5:第5階段的狀態(tài)集合為X5={8,9,10,11,12},決策集合為{0},指派結(jié)束,狀態(tài)轉(zhuǎn)移到虛擬的結(jié)束狀態(tài),到結(jié)束狀態(tài)轉(zhuǎn)移費用為0。

3.求解

上述動態(tài)規(guī)劃模型中的階段、狀態(tài)、狀態(tài)轉(zhuǎn)移、行動耗時等均可使用動態(tài)規(guī)劃的圖模型來表示,如圖5-18所示。

圖5-18巡邏隊分配問題的動態(tài)規(guī)劃模型

程序運行后,得到的最優(yōu)方案為x31=1,x12=1,x13=1,x34=1,也即四個區(qū)域指派的巡邏隊數(shù)量分別為4、2、2、4,可使損失最小,最小損失為97,如圖5-19所示。

圖5-19巡邏隊分配問題的動態(tài)規(guī)劃最優(yōu)解第6章網(wǎng)絡(luò)計劃6.1網(wǎng)絡(luò)計劃的發(fā)展歷程6.2網(wǎng)絡(luò)建模6.3關(guān)鍵路線法CPM6.4計劃評審技術(shù)PERT6.5時間－費用優(yōu)化

最早提出的統(tǒng)籌方法是甘特圖法,該方法是科學(xué)管理的奠基人泰勒的學(xué)生,美國?？颂m兵工廠顧問甘特于20世紀(jì)40年代開發(fā)的一種計劃與管理技術(shù)。甘特圖以時間為橫坐標(biāo),

以工序為縱坐標(biāo),以線條長短表示一項工作或作業(yè)的開始和完成時刻以及工作的進展情況。由于甘特圖以條形圖進行系統(tǒng)計劃和管理,故又稱為橫道圖、條形圖等(見圖6-1)。

圖6-1甘特圖

甘特圖的優(yōu)點是簡單明了、容易繪制、使用方便。甘特圖的缺陷是:

(1)不能反映各項工作之間錯綜復(fù)雜的聯(lián)系和制約的分工協(xié)作關(guān)系;

(2)不能區(qū)別系統(tǒng)中哪些工作是主要的、關(guān)鍵的生產(chǎn)聯(lián)系和工序,反映不出全局的關(guān)鍵所在,不利于最合理地管理整個系統(tǒng)。

6.1網(wǎng)絡(luò)計劃的發(fā)展歷程

PERT方法的優(yōu)化流程為:依據(jù)工作流程繪制網(wǎng)絡(luò)圖,計算網(wǎng)絡(luò)圖參數(shù),然后進行網(wǎng)絡(luò)圖的優(yōu)化。網(wǎng)絡(luò)圖的優(yōu)化以尋找關(guān)鍵路線為要點,在關(guān)鍵路線上尋找最有利的工序來縮短關(guān)鍵活動的時間,在可能的條件下將工序進一步細(xì)分,采用平行作業(yè)或交叉作業(yè)的方法使工期縮短。

縮短關(guān)鍵路線的方法有三種:

一是從非關(guān)鍵路線上抽調(diào)資源(人力、物力、財力等)集中于關(guān)鍵路線,以縮短關(guān)鍵路線的時間;

二是通過增加資源的方法來縮短關(guān)鍵路線上完成任務(wù)的期限;

三是采用新技術(shù)、新工藝等措施,縮短某些工序的時間,從而達(dá)到縮短關(guān)鍵路線時間的目的。

PM和PERT在原理上十分相似,都是采用網(wǎng)絡(luò)模型,只是在工序時間的確定上有所差別。由于PERT是軍方首創(chuàng),對時間進度最為關(guān)心,而CPM是民間首創(chuàng),對成本非常重視。一開始兩種方法的側(cè)重點略有差異,但在后來的使用與發(fā)展中逐漸靠攏并融為一體。

6.2網(wǎng)絡(luò)建模

項目由一系列活動組成,活動的完成需要時間,不同的活動之間有相互的依存關(guān)系。在利用網(wǎng)絡(luò)描述項目的時候,可以使用點來代表活動,使用有向邊代表活動之間的先后依存關(guān)系,如圖6-2所示。

圖6-2網(wǎng)絡(luò)中活動的先后關(guān)系

網(wǎng)絡(luò)建模的步驟如下:

(1)分解出相對獨立的活動。分解出相對獨立的活動就是將一項任務(wù)分解成若干項活動,分析并確定各項活動在工藝和組織方面的相互聯(lián)系及相互制約關(guān)系。

(2)分析活動的順序關(guān)系、依賴關(guān)系。確定各項活動的先后順序,分析各項活動的依賴關(guān)系,確定各項活動的所有緊前、緊后活動和與它平行的活動。

(3)列出活動的名稱、所需資源。確定各項活動的名稱、工期、所需資源(人力、物力、時間)等參數(shù)。

(4)每個活動使用一個網(wǎng)絡(luò)中的一個點來表示,緊前活動和當(dāng)前活動之間使用一條有向邊連接。

(5)為了便于分析,確保沒有緊前活動的活動只有一個,沒有直接后續(xù)活動的活動也只有一個。在所建立的網(wǎng)絡(luò)中,如果有多個沒有緊前活動的活動,則增加一個虛擬的起始活動,并將其連接到所有的沒有緊前活動的活動;如果有多個沒有直接后續(xù)活動的活動,則增加一個虛擬的結(jié)束活動,將所有的沒有直接后續(xù)活動的活動連接到虛擬的結(jié)束活動。

例6-1經(jīng)過分解和分析,某項目可以由11個活動組成,這些活動之間的關(guān)系和所需時間如表6-1所示。

利用項目活動分解表,可以繪制項目網(wǎng)絡(luò)計劃的網(wǎng)絡(luò)示意圖如圖6-3所示。圖6-3項目網(wǎng)絡(luò)計劃的網(wǎng)絡(luò)示意圖

利用網(wǎng)絡(luò)計劃技術(shù)能夠回答的問題包括:

(1)如果每個活動都按時完成,項目需要多久完工?

(2)如果項目要盡快完工,每個活動的工作時間窗口是什么?

(3)為了使項目盡快完成,哪些活動是瓶頸,哪些活動可以拖延,能拖延多久?

(4)如果有不確定性存在,項目按時完成的概率怎么計算?

(5)如果有一些額外的預(yù)算,花到什么地方可以使項目盡可能按時完成?

(6)如果要縮短項目工期,怎樣使增加的費用最小?

6.3關(guān)鍵路線法CPM

6.3.1關(guān)鍵路線的計算關(guān)鍵路線法是最先提出的網(wǎng)絡(luò)計劃技術(shù)。所謂關(guān)鍵路線,就是在項目的網(wǎng)絡(luò)中,從起始活動到結(jié)束活動所花費時間最長的路線,短于關(guān)鍵路線的路線稱為非關(guān)鍵路線。路線的長度使用路線上所有活動花費時間總和計算。

為了利用最短路算法,可以將網(wǎng)絡(luò)進行以下變換:將任意有向邊的長度設(shè)為其起點活動對應(yīng)的時間。

例如,對于圖6-3,就可以變換為如圖6-4所示的普通網(wǎng)絡(luò),在這個網(wǎng)絡(luò)中,可以利用最短路算法求解從A到K的最長路。

圖6-4轉(zhuǎn)換為有向邊帶權(quán)值的普通網(wǎng)絡(luò)

6.3.2幾個時間參數(shù)的計算

對于網(wǎng)絡(luò)中的任意一個活動,還可以計算以下幾個參數(shù):

(1)最早開始時間(ES)和最早完成時間(EF)。

任何活動的最早開始時間都決定于其所有緊前活動的最早完成時間,任何活動的最早完成時間都等于其最早開始時間加上本身所需要的時間,因此有

例如,在圖6-3中,首先將沒有緊前活動的活動A的最早開始時間設(shè)為0,則其最早完成時間EF=3,然后,對于B和C來講,最早開始時間都等于A的最早完成時間,然后依次進行計算,計算的順序參見圖6-5中Step的序號。

圖6-5最早開始時間和最早完成時間的計算

(2)最晚完成時間(LF)和最晚開始時間(LS)。

最晚完成時間和最晚開始時間,就是在保證整個項目最后一個活動的最早完成時間等于最晚完成時間的情況下,從后往前計算各個活動的最晚完成時間和最晚開始時間。在所

有活動的最早開始時間和最早完成時間已經(jīng)確定的情況下,可以計算所有活動的最晚完成時間和最晚開始時間,計算公式為

例如,在圖6-5中,首先將沒有直接后續(xù)活動的活動K的最晚完成時間(LF)設(shè)為活動K的最早完成時間(EF),這樣就可以保證整個項目的工期不被拖后?；顒覭的最晚開始時間(LS)等于最晚完成時間減去活動K本身所需要的時間。然后可以計算以K為直接后續(xù)活動的J的最晚完成時間(LF),等于活動K的最晚開始時間,然后依次進行計算,計算步驟如圖6-6中Step的序號所示。

圖6-6-項目活動的最晚完成時間和最晚開始時間

(3)可松弛時間。

可松弛時間就是某個活動在不影響整個項目工期的情況下,可以進行活動的時間窗口,其計算公式如下:

例如,對于圖6-6,可以計算每個活動的可松弛時間如圖6-7所示,其中,可松弛時間為零的關(guān)鍵活動使用深色表示。

圖6-7活動的可松弛時間及關(guān)鍵活動

6.4計劃評審技術(shù)PERT

樂觀時間to表示活動完成的樂觀估計時間,即在順利情況下完成某個活動所需的時間。最可能時間tm

表示活動完成的最可能估計時間,即在正常情況下完成某個活動所需的時間。悲觀時間tp表示活動完成的悲觀估計時間,即在不利情況下完成某個活動所需的時間。

例6-2經(jīng)過分解和分析,某項目可以由11個活動組成,這些活動之間的關(guān)系和所需時間如表6-2所示。

活動所需時間的期望為

對于所需時間的期望μ,這里實際上是采用了加權(quán)求和的方法,即假設(shè)活動最可能完成時間的權(quán)值為4/6,樂觀時間和悲觀時間的權(quán)值為1/6,而4/6≈0.6666,接近于黃金分割率。

在PERT中,假設(shè)所需時間的概率分布為一種貝塔分布,而對于貝塔分布來講,大部分值落在區(qū)間[μ-3σ,μ+3σ]內(nèi)。因此,假設(shè)tp-to=6σ,可以估計活動所需時間的方差為

需要注意的是,這里的活動所需時間的期望和方差,均是估計值。

例如,可以在表6-2的基礎(chǔ)上,計算任一活動所需時間的期望及其方差,如表6-3所示。

如果以活動所需時間的期望μ作為活動所需時間,將隨機問題轉(zhuǎn)化為確