方冬云

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

1引言

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

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

2 項(xiàng)目建筑的關(guān)鍵路徑問(wèn)題

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

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

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

圖1 工序的有向圖

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

(1)事項(xiàng)的最早開(kāi)始時(shí)間用ES(i)表示；

(2)事項(xiàng)的最晚完成時(shí)間用LF(i)表示；

(3)工序的最早開(kāi)始時(shí)間用ES表示；

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

(5)工序的最晚開(kāi)始時(shí)間用LS表示；

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

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

這樣各個(gè)時(shí)間之間的關(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中各事項(xiàng)的相關(guān)時(shí)間計(jì)算如下：

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)時(shí)間如表2所示：

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

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

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

3 建筑工程項(xiàng)目人力資源的著色問(wèn)題及匹配問(wèn)題

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

圖2 人力資源分配的無(wú)向圖

圖3 無(wú)向圖的點(diǎn)著色

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

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

圖4 人員分配的二部圖

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

圖5 人員分配的匹配圖

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

4 建筑工程項(xiàng)目的最小費(fèi)用最大流問(wèn)題

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語(yǔ)

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