企业项目的合理决策

王亚梅

摘 要：随着经济的迅速发展，企业项目的合理决策对企业生存和发展越来越重要，企业项目的合理决策问题实质上是企业项目的最优化问题，但是，现实生活中企业的项目不可能完全独立，有很多项目的实施必须以另一些项目的实施为前提，针对这类项目间有依赖关系的企业项目合理决策问题提出研究，主要运用既属于图论又属于运筹学的网络流理论，将企业项目的合理决策问题抽象为数学问题，应用图论理论分析建立问题的标号图，再运用有向网络及源点汇点定义将标号图转化为有向网络图，即得到该问题的网络模型。采用Ford-Fulkerson标号算法求解该模型，得到模型的最大流并找到最小割。

关键词：最优项目选择；网络流；最大流；最小割；Ford-Fulkerson标号算法

本课题将对企业中后期项目发展依赖前期项目的复杂项目发展规划问题提出研究，主要运用数学领域中的网络流理论，通

过实际与理论相结合的方法，将企业发展项目的合理决策问题抽象为数学问题，运用数学的观点解决这一实际问题。

一、问题的提出

我省某家电子有限公司是一家集设计、开发、生产、销售一条龙服务的电子产品公司，在近年的发展中，不断增加市场占有额，处于同行领先地位，但受世界金融危机的影响，在刚刚过去的一年里，该公司的销量明显少于历年，且管理费用及项目开发费用较以往大幅增加，直接导致公司总收入下降，净利润首次出现负值。公司决定今年继续开发新项目，受资金限制，决策者只能选择项目开发部提供的部分项目作为今年要开发的新项目，且要确保今年获得的净利润最大。

该公司项目开发部门提供的许多项目,规划表中都给出了每

个项目所需的投入资金或预计的盈利金额，另外，这些项目并不是完全独立的，其中某些项目的实施必须依赖于其他项目的开发成果，称该项目所依赖的项目为它的前期项目（由于涉及公司隐私，具体项目名称不便给出）。所以要开发这个项目，就必须先开发它的前驱项目。

二、问题的分析

假设该公司的规划表中新项目共有n个，其中第i个项目的投入资金为ai元，项目实施成功后可获得收益为bi元；另外，第i个项目有ri个前驱项目，分别用k1，k2，…，kri表示；公司获得的最大利润用Z表示。

令di=bi-ai，表示该公司在成功实施项目i后的净收益；令M=｛i|di≥0｝，表示该公司规划表中n个项目中能够获得利润的项目

的集合；令N=｛i|di<0｝，表示该公司规划表中n个项目中会亏损的项目集合。

如果用点来表示题中各个项目，用有向线段来表示各项目间的依赖关系，即由项目i的前驱项目指向项目i，就能得到一个有 个结点的有向图。

三、构造问题的图论结构图

从上述分析可知，首先要构造一个包含n个顶点的有向图G=（V，A），用图中每个顶点代表一个项目。其次用有向边来表示项目间的依赖关系，从i指向kj（j=1，2，…，ri）的有向边表示项目i依赖于项目kj（j=1，2，…，ri）即项目i的实施必须在项目kj（j=1，2，…，ri）完成的前提下，然后，每个项目的最终净收益应该标注在表示项目的顶点处，即每个项目点都有一个对应的值di.最后就将此问题转化为求顶点集V中的一个子集V1，子集V1满足：对图中任意有向边（i，j）∈A，若i∈V1，则j∈V1，并且使得V1中所有点的值之和最大。

设新增的源点为vs，汇点为vi.则此时的有向网络中就有n+2个顶点，下一步工作是建立源点、汇点与各个项目点的关系。根据源点和汇点的实质，可建立源点到各个盈利项目顶点的弧，并在弧上赋权值（该盈利项目的净收益），再建立亏损项目到汇点的弧，也在其弧上赋权值（该亏损项目的亏损额），并且在各个代表项目关系的弧上赋权值+∞，这样就将标号图转化成了有向网络，也就建立了该题的网络模型。

四、网络流模型建立

此题网络流模型建立方法：首先建立n个顶点代表n个项目，

并增加源点vs和汇点vt.其次，建立各个项目点间的关系，并给这些弧赋权值.若项目i依賴项目kj（j=1，2，…，ri）,则从顶点i向顶点kj引一条容量为无穷大的弧。然后，建立源点和汇点与其他项目点的关系弧，并赋权值。对于每一个项目i，若它实施后的净收益为正（即表示项目i盈利），则从源点vs向顶点引一条容量为di的边；

若它实施后的净收益di为负（即表示项目i亏损），则从顶点i向汇点vt引一条容量为di的边。

这样就能够得到网络图G=（V，A，W），其中有n+2个点，分为两类：源点vs和汇点vt，第i个项目点i（i=1，2，3…，n）。另外有三种弧：（1）若i∈M，则存在弧（vs，i），容量为di；（2）若i∈N，则存在弧（i，vs），容量为di；（3）若项目kj是项目i的前驱项目，则存在弧（i，kj），容量为+∞.此图即为该题的网络流模型。

■

五、网络流模型的求解

网络流模型求解的实质是构造网络模型的最小割（V1，V1），确定最优项目选择方案V1，即集合中的顶点表示最优方案选择的项目，并求该有向网络最大流值为f，从而可得，该公司采用此方案获得的最大净收益为Z=■di-f

采用Ford-Fulkerson标号算法步骤为：

第一步，标号过程

（1）源点vs标号（+，vs，+∞），vs处于被标号未检查状态，其余各点处于标号未检查状态。

（2）任选一个已标号未检查的点vi，若点vj与vi相邻且未标号未检查，则当

a.（vi，vj）∈A，cij>fij，将vj标上（+，vi，δ（j）），其中δ（j）=min｛δ（i），cij-fij｝，vj处于已标号未检查状态；

b.（vj，vi）∈A，fij>0，将vj标上（-，vi，δ（j）），其中δ（j）=min｛δ（i），fij｝，vj处于已标号未检查状态；

c.与点vi相邻的点都被标号后，将vi的第一部分“+”或“-”圈起来，vj处于已标号已检查状态。

（3）重复（2），直到汇点vt被标号，然后转入第二步增广过程；或者直到不再有点可被标号，转入第三步。

第二步，增广过程

（1）按vt及其他点的标号的第二部分，利用反向追踪的办法找出增广链μ．例如，若vt的标号为（+，vq，δ（t））或（-，vq，δ（t）），称弧（vq，vt）（或相应的是（vt，vq））是μ上的弧．检查vq的标号，以此类推，直到vs为止。这时，找出的弧就是增广链μ。

（2）令调整量θ=δ（t）

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

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

第三步，算法结束，现行流就是最大流

构造最小割，若将所有标号的点的集合记为V1，所有未标号的点的集合记为V1，就得到最小容量割（V1，V1）。

网络流理论是一类既属于图论又属于运筹学的理论知识，广泛应用于工程设计和管理领域，并且对一些大型系统问题的解决有显著效果。

参考文献：

薛楠.企业投资项目可行性分析［J］.现代商贸工业，2010（5）:185-186.

（作者单位 山西省襄汾县赵曲高级中学校）

编辑 李建军