求解GPRs条件下的项目最小费用问题

Solving the Minimal Cost Problem of Project under GPRs Condition

在项目管理中,最低成本是主要目标之一,也是求解诸如时间-费用权衡等相关问题时必备的起始点,通常只需令各工序选用费用最低的工期即可.但是当工序之间存在一般优先关系(简称GPRs)时,各工序选用费用最低的工期往往无法满足时间约束,使得项目不可行,因此需要考虑其它费用较高的工期.针对如何在满足GPRs条件下使项目成本最低,首先,通过分析GPRs网络的特点,建立了GPRs网络的最小费用模型;其次,对模型进行对偶变换,等效转化为最小费用流模型,其特点是,除了与起点或终点连接的弧,其余均没有容量限制.当前已有的算法能够有效求解该模型,并跟据其最优解可求得原问题的最优解.

The minimal cost is one main objective in project management,which also is necessary initial solution when solving related problem such as time-cost tradeoff,and the method is to make all activities choose the minimal cost durations of themselve normally.But if generalized precedence relations（GPRs for short） exist between activities,still making each activity choose the minimal cost duration often can＇t satisfy time constraints and leads project to be unfeasible,therefore need consider other expensive duration.Aiming at how to realize minimal project cost under GPRs condition,the minimal cost model of GPRs network was founded by analyzing properties of GPRs network;and then,by dual transforming,the model was transformed to minimal cost flow model with unlimited capacity,except arcs connect with start node or terminal node.The model could be solved effectively by using existing algorithm,and optimal solution of original problem could be solved according to optimal solution of the model.