王亞梅

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

關鍵詞：最優(yōu)項目選擇；網(wǎng)絡流；最大流；最小割；Ford-Fulkerson標號算法

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

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

一、問題的提出

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

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

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

二、問題的分析

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

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

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

如果用點來表示題中各個項目，用有向線段來表示各項目間的依賴關系，即由項目i的前驅(qū)項目指向項目i，就能得到一個有 個結點的有向圖。

三、構造問題的圖論結構圖

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

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

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

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

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

若它實施后的凈收益di為負（即表示項目i虧損），則從頂點i向匯點vt引一條容量為di的邊。

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

■

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

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

采用Ford-Fulkerson標號算法步驟為：

第一步，標號過程

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

（2）任選一個已標號未檢查的點vi，若點vj與vi相鄰且未標號未檢查，則當

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

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

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

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

第二步，增廣過程

（1）按vt及其他點的標號的第二部分，利用反向追蹤的辦法找出增廣鏈μ．例如，若vt的標號為（+，vq，δ（t））或（-，vq，δ（t）），稱?。╲q，vt）（或相應的是（vt，vq））是μ上的弧．檢查vq的標號，以此類推，直到vs為止。這時，找出的弧就是增廣鏈μ。

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

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

（3）去掉所有標號，對弧的可行流f=｛f′ij｝重新回到第一步。

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

構造最小割，若將所有標號的點的集合記為V1，所有未標號的點的集合記為V1，就得到最小容量割（V1，V1）。

網(wǎng)絡流理論是一類既屬于圖論又屬于運籌學的理論知識，廣泛應用于工程設計和管理領域，并且對一些大型系統(tǒng)問題的解決有顯著效果。

參考文獻：

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

（作者單位 山西省襄汾縣趙曲高級中學校）

編輯 李建軍