圖論在建筑工程項目中的應(yīng)用

方冬云

(莆田學(xué)院 數(shù)學(xué)與金融學(xué)院, 福建 莆田 351100)

1引言

工程項目是以工程建設(shè)為載體的項目，是作為被管理對象的一次性工程建設(shè)任務(wù)。它以建筑物或構(gòu)筑物為目標(biāo)產(chǎn)出物，需要支付一定的費用，按照一定的程序，在一定的時間內(nèi)完成，并符合質(zhì)量要求[1]。建筑工程項目是具有一個設(shè)計任務(wù)書和總體設(shè)計，經(jīng)濟(jì)上實行獨立核算，管理上具有獨立組織形式的工程項目，包括工程建設(shè)項目、單項工程、分部工程、分項工程[2]。

文章以莆田學(xué)院新校區(qū)的建筑來展開闡述圖論的相關(guān)理論的應(yīng)用。

2 項目建筑的關(guān)鍵路徑問題

建筑工程項目必須有工程前期，如先做好市場調(diào)查，隨后編制可行性研究報告，規(guī)劃藍(lán)圖等等，而估計一個工程完成的時間也是必需的。如莆田學(xué)院新校區(qū)需要建筑教學(xué)樓、學(xué)生宿舍、實驗室、食堂等項目，就其中含有13個工序的項目為例。各工序之間的關(guān)系和完成時間如表1：

表1 工序之間的關(guān)系及完成時間

而估計這個項目完成所需的時間要涉及到圖論中的關(guān)鍵路徑問題。關(guān)鍵路徑指的是項目圖中從起點到終點的最長路徑。這個圖稱為項目網(wǎng)絡(luò)圖，在圖論中可以用帶有權(quán)的有向圖表示：有向圖中的各個頂點表示各個工序的開始和結(jié)束，有向圖中的邊用項目中的各個工序來表示。邊之間的鄰接關(guān)系用工序之間的前后順序來表示，有向圖中邊上的權(quán)用工序的完成時間來表示。這樣把項目中的各個工序之間的關(guān)系及完成時間用以下有向圖來表示(如圖1)

圖1 工序的有向圖

對于關(guān)鍵路徑的算法在相關(guān)書上都已提過。這里不再重復(fù)，關(guān)鍵要把整個項目的完成時間計算出來。在計算過程中需要涉及相關(guān)的量還是要明確指出：工序有向圖中的各頂點稱為事項，頂點之間邊表示工序(或活動)。

(1)事項的最早開始時間用ES(i)表示；

(2)事項的最晚完成時間用LF(i)表示；

(3)工序的最早開始時間用ES表示；

(4)工序的最早完成時間用EF表示；

(5)工序的最晚開始時間用LS表示；

(6)工序的最晚完成時間用LF表示；

(7)工序的緩沖時間用SL表示。

這樣各個時間之間的關(guān)系如下：

ES=ES(i)，EF=ES(i)+wij(邊上的權(quán))。

LF=LF(i)，LS=LF(i)+wij(邊上的權(quán))。

SL=LS(i，j)-ES=LF〈i，j〉-EF〈i，j〉。

顯然ES(1)=0，ES(i)=max{ES(j)+wij，i、j∈Z+}。

圖1中各事項的相關(guān)時間計算如下：

ES(1)=0，ES(2)=0+3=3，ES(3)=max{ES(2)+0，ES(1)+2}=3。

ES(4)=max{ES(3)+2，ES(1)+4}=max{3+2，0+4}=5。

ES(5)=max{ES(2)+4，ES(3)+4}=max{3+4，3+4}=7。

ES(6)=max{ES(5)+0，ES(3)+4}=max{7+0，3+4}=7。

ES(7)=max{ES(5)+3，ES(4)+5}=max{7+3，5+5}=10。

ES(8)=max{ES(6)+3，ES(7+1)}=max{7+3，10+1}=11。

ES(9)=max{ES(5)+6，ES(8)+1}=max{7+5，11+1}=13。

顯然，LF(n)=ES(n)，LF(i)=min{LF(j)-wij，i、j∈Z+}，那么

LF(9)=ES(9)=1。

LF(8)=min{LF(9)-1}=13-1=12。

LF(7)=min{LF(8)-1}=12-1=11。

LF(6)=min{LF(8)-3}=12-3=9。

LF(5)=min{LF(9)-6，LF(7)-3，LS(6)-0}=min{12-6，11-3，9-0}=7。

LF(4)=min{LF(7)-5}=11-5=6。

LF(3)=min{LF(6)-4，LF(5)-4，LS(4)-2}=min{9-4，7-4，6-2}=3。

LF(2)=min{LF(5)-4，LS(3)-0}=min{7-4，3-0}=3。

LF(1)=min{LF(4)-4，LF(3)-2，LS(2)-3}=min{6-4，3-2，3-3}=0。

這樣各工序的相關(guān)時間如表2所示：

根據(jù)各工序緩沖時間為零來選擇關(guān)鍵路徑，這樣得到的關(guān)鍵路徑為A→D→E→K，整個項目完成所需的最長時間為3+4+4+6=17天[3]。

表2 各工序之間的相關(guān)時間

上述各工序之間的關(guān)系及完成時間的天數(shù)是一個代表，它可以發(fā)生變化，但是它計算整個項目完成所需的最長時間的原理是一樣的。在估計一個項目完成所需要的時間后，一個項目的完成還需要人力資源。

3 建筑工程項目人力資源的著色問題及匹配問題

前面提到的13個工序有些需要相同的人力資源。假如，這13項工作每項工作平均需要4天時間完成，有些工序由于需要相同的人員或設(shè)備，這些工序不能同時進(jìn)行，問至少需要多少天才能完成所有的工序。這樣人力資源的分配就轉(zhuǎn)化為下面的無向圖來表示(如圖2)：其中各頂點表示工序，頂點之間的邊表示兩個工序不能同時進(jìn)行。

圖2 人力資源分配的無向圖

圖3 無向圖的點著色

這樣項目的時間安排就對應(yīng)著無向圖的點著色問題(如圖3)，圖中括號的數(shù)字表示頂點的著色，相同的數(shù)字表示著相同的顏色。著同一種顏色的工序可以同時工作，這樣項目完成所需要的最少時間為天[4]。

上面涉及到的問題是相同人員或設(shè)備在工作中不能同時進(jìn)行，接下來涉及的問題是這些人員的分配，因為有些人員不止擅長一個工種，有時有人身上懷有兩三種技能，而這13個工序中每個工序至少需要6個工種。假如一個工序需要10個人員，每個工種需要1-2名人員，那么這10個人員與6個工種之間產(chǎn)生了一個分配問題，如何分配才能夠讓這10個人員都能發(fā)揮自己的技能。先把這10個人與6個工種之間的關(guān)系用二部圖來表示(如圖4)，其中：頂點v1、v2、v3、v4、v5、v6表示6個工種，頂點u1、u2、u3、u4、u5、u6、u7、u8、u9、u10表示10個人員，頂點之間的邊表示人員擅長的工種。

圖4 人員分配的二部圖

那么分配方案就涉及到二部圖的匹配理論，而圖4的匹配有好幾種情況，假設(shè)圖4的匹配如圖5表示：

圖5 人員分配的匹配圖

匹配的結(jié)果：v1工種需要u1、u2兩個人員，v2工種需要u3、u4兩個人員，v3工種需u5要人員，v4工種需要u6、u7兩個人員，v5工種需要u8人員，v6工種需要u9、u10兩個人員[5]。這樣匹配當(dāng)然還要考慮各個人員對工種的熟悉程度，這樣即可以節(jié)省時間，也可以節(jié)省費用，這些問題在項目的規(guī)劃圖中已落實。

4 建筑工程項目的最小費用最大流問題

人力資源問題解決后就是項目建筑所需的物資問題。物資問題有物資的采購、運輸、分配等問題，這里要闡述的是物資的運輸。比如這個項目所需的物資從外地的某個地方集中購買，從這個地方把物資通過小型火車、汽車、輪船等三種途徑運輸?shù)狡翁?這三種運輸工具所承載的重量都為幾十噸)，再從這個地方運輸?shù)狡翁飳W(xué)院的各個投放點。假設(shè)，物資集中購買的地方用表示，物資通過火車運輸?shù)竭_(dá)的地方用表示，通過汽車運輸?shù)竭_(dá)的地方用表示，通過輪船運輸?shù)竭_(dá)的地方用v3表示。y1、y2、y3、y4分別表示物資從v1、v2、v3點運輸?shù)狡翁飳W(xué)院的各個投放點。其中y1可以從v1、v2兩個地方運輸物資，y2可以從這個地方運輸物資，y3可以從v1、v3兩個地方運輸物資，y4可以從v2、v3兩個地方運輸物資，這樣物資運輸過程轉(zhuǎn)化為有向圖6：

圖6 物資運輸?shù)挠邢驁D

物資運輸要考慮到物資運輸?shù)某休d重量及運費問題，這個問題可以用圖論中的最小費用最大流理論來解決，用圖7來表示物資運輸?shù)某休d重量及最小運費，邊上的有序?qū)Γ耙粋€數(shù)值表示按公里數(shù)計算的運費，后一個數(shù)值表示所承載的重量，其中各個數(shù)值是一個代表，可以變化的。

圖7 物資運輸?shù)膸?quán)圖

根據(jù)上面圖中的數(shù)值，可以計算出這批物資從出發(fā)地到各個投放點的最小費用最大流，最小費用最大流的算法在其它書上都有提到，這里就不再闡述。根據(jù)最小費用最大流算法演示圖7的求解過程：

根據(jù)上述的計算可以得到從出發(fā)點S到投放點y1的最小費用及承載的重量：

150×68+80×68=15640元，承載的重量為68噸。

從出發(fā)點S到投放點y2的最小費用及承載的重量：

240×20+60×20=6000元，承載的重量為20噸。

從出發(fā)點S到投放點的最小費用及承載的重量：

1000×65+70×40=9300元，承載的重量為40噸。

從出發(fā)點S到投放點的最小費用及承載的重量：

100×25+30×25=3250元，承載的重量為25噸[6]。

5 結(jié)束語

最小費用最大流理論不但在運輸問題上有所應(yīng)用，同時對于這個建筑工程項目后期的項目中也可應(yīng)用，如電線、水管的布置等，而且整個建筑工程項目也不單單只涉及到文章所提到的這三個圖論理論，還會涉及到圖論中其他理論，如覆蓋問題、最短路徑等問題，建筑工程項目還需要與其他相關(guān)知識結(jié)合研究，才能使項目管理得更加完善。