王亞梅

摘 要：隨著經(jīng)濟(jì)的迅速發(fā)展，企業(yè)項(xiàng)目的合理決策對(duì)企業(yè)生存和發(fā)展越來越重要，企業(yè)項(xiàng)目的合理決策問題實(shí)質(zhì)上是企業(yè)項(xiàng)目的最優(yōu)化問題，但是，現(xiàn)實(shí)生活中企業(yè)的項(xiàng)目不可能完全獨(dú)立，有很多項(xiàng)目的實(shí)施必須以另一些項(xiàng)目的實(shí)施為前提，針對(duì)這類項(xiàng)目間有依賴關(guān)系的企業(yè)項(xiàng)目合理決策問題提出研究，主要運(yùn)用既屬于圖論又屬于運(yùn)籌學(xué)的網(wǎng)絡(luò)流理論，將企業(yè)項(xiàng)目的合理決策問題抽象為數(shù)學(xué)問題，應(yīng)用圖論理論分析建立問題的標(biāo)號(hào)圖，再運(yùn)用有向網(wǎng)絡(luò)及源點(diǎn)匯點(diǎn)定義將標(biāo)號(hào)圖轉(zhuǎn)化為有向網(wǎng)絡(luò)圖，即得到該問題的網(wǎng)絡(luò)模型。采用Ford-Fulkerson標(biāo)號(hào)算法求解該模型，得到模型的最大流并找到最小割。

關(guān)鍵詞：最優(yōu)項(xiàng)目選擇；網(wǎng)絡(luò)流；最大流；最小割；Ford-Fulkerson標(biāo)號(hào)算法

本課題將對(duì)企業(yè)中后期項(xiàng)目發(fā)展依賴前期項(xiàng)目的復(fù)雜項(xiàng)目發(fā)展規(guī)劃問題提出研究，主要運(yùn)用數(shù)學(xué)領(lǐng)域中的網(wǎng)絡(luò)流理論，通

過實(shí)際與理論相結(jié)合的方法，將企業(yè)發(fā)展項(xiàng)目的合理決策問題抽象為數(shù)學(xué)問題，運(yùn)用數(shù)學(xué)的觀點(diǎn)解決這一實(shí)際問題。

一、問題的提出

我省某家電子有限公司是一家集設(shè)計(jì)、開發(fā)、生產(chǎn)、銷售一條龍服務(wù)的電子產(chǎn)品公司，在近年的發(fā)展中，不斷增加市場(chǎng)占有額，處于同行領(lǐng)先地位，但受世界金融危機(jī)的影響，在剛剛過去的一年里，該公司的銷量明顯少于歷年，且管理費(fèi)用及項(xiàng)目開發(fā)費(fèi)用較以往大幅增加，直接導(dǎo)致公司總收入下降，凈利潤(rùn)首次出現(xiàn)負(fù)值。公司決定今年繼續(xù)開發(fā)新項(xiàng)目，受資金限制，決策者只能選擇項(xiàng)目開發(fā)部提供的部分項(xiàng)目作為今年要開發(fā)的新項(xiàng)目，且要確保今年獲得的凈利潤(rùn)最大。

該公司項(xiàng)目開發(fā)部門提供的許多項(xiàng)目,規(guī)劃表中都給出了每

個(gè)項(xiàng)目所需的投入資金或預(yù)計(jì)的盈利金額，另外，這些項(xiàng)目并不是完全獨(dú)立的，其中某些項(xiàng)目的實(shí)施必須依賴于其他項(xiàng)目的開發(fā)成果，稱該項(xiàng)目所依賴的項(xiàng)目為它的前期項(xiàng)目（由于涉及公司隱私，具體項(xiàng)目名稱不便給出）。所以要開發(fā)這個(gè)項(xiàng)目，就必須先開發(fā)它的前驅(qū)項(xiàng)目。

二、問題的分析

假設(shè)該公司的規(guī)劃表中新項(xiàng)目共有n個(gè)，其中第i個(gè)項(xiàng)目的投入資金為ai元，項(xiàng)目實(shí)施成功后可獲得收益為bi元；另外，第i個(gè)項(xiàng)目有ri個(gè)前驅(qū)項(xiàng)目，分別用k1，k2，…，kri表示；公司獲得的最大利潤(rùn)用Z表示。

令di=bi-ai，表示該公司在成功實(shí)施項(xiàng)目i后的凈收益；令M=｛i|di≥0｝，表示該公司規(guī)劃表中n個(gè)項(xiàng)目中能夠獲得利潤(rùn)的項(xiàng)目

的集合；令N=｛i|di<0｝，表示該公司規(guī)劃表中n個(gè)項(xiàng)目中會(huì)虧損的項(xiàng)目集合。

如果用點(diǎn)來表示題中各個(gè)項(xiàng)目，用有向線段來表示各項(xiàng)目間的依賴關(guān)系，即由項(xiàng)目i的前驅(qū)項(xiàng)目指向項(xiàng)目i，就能得到一個(gè)有 個(gè)結(jié)點(diǎn)的有向圖。

三、構(gòu)造問題的圖論結(jié)構(gòu)圖

從上述分析可知，首先要構(gòu)造一個(gè)包含n個(gè)頂點(diǎn)的有向圖G=（V，A），用圖中每個(gè)頂點(diǎn)代表一個(gè)項(xiàng)目。其次用有向邊來表示項(xiàng)目間的依賴關(guān)系，從i指向kj（j=1，2，…，ri）的有向邊表示項(xiàng)目i依賴于項(xiàng)目kj（j=1，2，…，ri）即項(xiàng)目i的實(shí)施必須在項(xiàng)目kj（j=1，2，…，ri）完成的前提下，然后，每個(gè)項(xiàng)目的最終凈收益應(yīng)該標(biāo)注在表示項(xiàng)目的頂點(diǎn)處，即每個(gè)項(xiàng)目點(diǎn)都有一個(gè)對(duì)應(yīng)的值di.最后就將此問題轉(zhuǎn)化為求頂點(diǎn)集V中的一個(gè)子集V1，子集V1滿足：對(duì)圖中任意有向邊（i，j）∈A，若i∈V1，則j∈V1，并且使得V1中所有點(diǎn)的值之和最大。

設(shè)新增的源點(diǎn)為vs，匯點(diǎn)為vi.則此時(shí)的有向網(wǎng)絡(luò)中就有n+2個(gè)頂點(diǎn)，下一步工作是建立源點(diǎn)、匯點(diǎn)與各個(gè)項(xiàng)目點(diǎn)的關(guān)系。根據(jù)源點(diǎn)和匯點(diǎn)的實(shí)質(zhì)，可建立源點(diǎn)到各個(gè)盈利項(xiàng)目頂點(diǎn)的弧，并在弧上賦權(quán)值（該盈利項(xiàng)目的凈收益），再建立虧損項(xiàng)目到匯點(diǎn)的弧，也在其弧上賦權(quán)值（該虧損項(xiàng)目的虧損額），并且在各個(gè)代表項(xiàng)目關(guān)系的弧上賦權(quán)值+∞，這樣就將標(biāo)號(hào)圖轉(zhuǎn)化成了有向網(wǎng)絡(luò)，也就建立了該題的網(wǎng)絡(luò)模型。

四、網(wǎng)絡(luò)流模型建立

此題網(wǎng)絡(luò)流模型建立方法：首先建立n個(gè)頂點(diǎn)代表n個(gè)項(xiàng)目，

并增加源點(diǎn)vs和匯點(diǎn)vt.其次，建立各個(gè)項(xiàng)目點(diǎn)間的關(guān)系，并給這些弧賦權(quán)值.若項(xiàng)目i依賴項(xiàng)目kj（j=1，2，…，ri）,則從頂點(diǎn)i向頂點(diǎn)kj引一條容量為無窮大的弧。然后，建立源點(diǎn)和匯點(diǎn)與其他項(xiàng)目點(diǎn)的關(guān)系弧，并賦權(quán)值。對(duì)于每一個(gè)項(xiàng)目i，若它實(shí)施后的凈收益為正（即表示項(xiàng)目i盈利），則從源點(diǎn)vs向頂點(diǎn)引一條容量為di的邊；

若它實(shí)施后的凈收益di為負(fù)（即表示項(xiàng)目i虧損），則從頂點(diǎn)i向匯點(diǎn)vt引一條容量為di的邊。

這樣就能夠得到網(wǎng)絡(luò)圖G=（V，A，W），其中有n+2個(gè)點(diǎn)，分為兩類：源點(diǎn)vs和匯點(diǎn)vt，第i個(gè)項(xiàng)目點(diǎn)i（i=1，2，3…，n）。另外有三種?。海?）若i∈M，則存在?。╲s，i），容量為di；（2）若i∈N，則存在?。╥，vs），容量為di；（3）若項(xiàng)目kj是項(xiàng)目i的前驅(qū)項(xiàng)目，則存在?。╥，kj），容量為+∞.此圖即為該題的網(wǎng)絡(luò)流模型。

■

五、網(wǎng)絡(luò)流模型的求解

網(wǎng)絡(luò)流模型求解的實(shí)質(zhì)是構(gòu)造網(wǎng)絡(luò)模型的最小割（V1，V1），確定最優(yōu)項(xiàng)目選擇方案V1，即集合中的頂點(diǎn)表示最優(yōu)方案選擇的項(xiàng)目，并求該有向網(wǎng)絡(luò)最大流值為f，從而可得，該公司采用此方案獲得的最大凈收益為Z=■di-f

采用Ford-Fulkerson標(biāo)號(hào)算法步驟為：

第一步，標(biāo)號(hào)過程

（1）源點(diǎn)vs標(biāo)號(hào)（+，vs，+∞），vs處于被標(biāo)號(hào)未檢查狀態(tài)，其余各點(diǎn)處于標(biāo)號(hào)未檢查狀態(tài)。

（2）任選一個(gè)已標(biāo)號(hào)未檢查的點(diǎn)vi，若點(diǎn)vj與vi相鄰且未標(biāo)號(hào)未檢查，則當(dāng)

a.（vi，vj）∈A，cij>fij，將vj標(biāo)上（+，vi，δ（j）），其中δ（j）=min｛δ（i），cij-fij｝，vj處于已標(biāo)號(hào)未檢查狀態(tài)；

b.（vj，vi）∈A，fij>0，將vj標(biāo)上（-，vi，δ（j）），其中δ（j）=min｛δ（i），fij｝，vj處于已標(biāo)號(hào)未檢查狀態(tài)；

c.與點(diǎn)vi相鄰的點(diǎn)都被標(biāo)號(hào)后，將vi的第一部分“+”或“-”圈起來，vj處于已標(biāo)號(hào)已檢查狀態(tài)。

（3）重復(fù)（2），直到匯點(diǎn)vt被標(biāo)號(hào)，然后轉(zhuǎn)入第二步增廣過程；或者直到不再有點(diǎn)可被標(biāo)號(hào)，轉(zhuǎn)入第三步。

第二步，增廣過程

（1）按vt及其他點(diǎn)的標(biāo)號(hào)的第二部分，利用反向追蹤的辦法找出增廣鏈μ．例如，若vt的標(biāo)號(hào)為（+，vq，δ（t））或（-，vq，δ（t）），稱?。╲q，vt）（或相應(yīng)的是（vt，vq））是μ上的?。畽z查vq的標(biāo)號(hào)，以此類推，直到vs為止。這時(shí)，找出的弧就是增廣鏈μ。

（2）令調(diào)整量θ=δ（t）

令f′ij=fij+θ，（vi，vj）∈μ+fij-θ，（vi，vj）∈μ-fij（vi，vj）■μ+

（3）去掉所有標(biāo)號(hào)，對(duì)弧的可行流f=｛f′ij｝重新回到第一步。

第三步，算法結(jié)束，現(xiàn)行流就是最大流

構(gòu)造最小割，若將所有標(biāo)號(hào)的點(diǎn)的集合記為V1，所有未標(biāo)號(hào)的點(diǎn)的集合記為V1，就得到最小容量割（V1，V1）。

網(wǎng)絡(luò)流理論是一類既屬于圖論又屬于運(yùn)籌學(xué)的理論知識(shí)，廣泛應(yīng)用于工程設(shè)計(jì)和管理領(lǐng)域，并且對(duì)一些大型系統(tǒng)問題的解決有顯著效果。

參考文獻(xiàn)：

薛楠.企業(yè)投資項(xiàng)目可行性分析［J］.現(xiàn)代商貿(mào)工業(yè)，2010（5）:185-186.

（作者單位 山西省襄汾縣趙曲高級(jí)中學(xué)校）

編輯 李建軍