最小成本加快法中的优化组合方案定理及其计算机程序

THE THEOREM OF FINDING THE TIME-COMPRESSED ACTIVITIES AT LEAST COST IN A NETWORK AND ITS ALGORITHM

本文提出了最小成本加快法中寻找多关键路线情况下的组合压缩方案的方法,并用图论中有关割集的理论进行了论证,得到了优化组合方案定理。该定理指出:在由网络计划图中的关键路线构成的子图中,如果每项作业都允许压缩或放宽作业时间,则其最小费用率完全割集中的每个正向割弧(作业)压缩单位时间,每个反向割弧(作业)放宽单位时间,则总工期以最低成本压缩单位时间。文中详细介绍了这种算法。

In this paper the perfect cut-set of a directed graph is defined as a set which is composed of a forward cut-set and a backward cut-set. The capacity of a perfect cut-set is equal to the capacity difference between the forward cut-set and the backward cut-set. With these definitions the paper presents the theorem with which it is easy to find the time-compressed activities at least cost in a network. The theoremproved by the Graph theory indicates: In the graph composed of the key activities in a network, each forward activity in the cut-set with minimum cost rate is compressed by a unit time and each backward activity in the same cut-set is relaxed by a unit time, the result is the time compression at least cost by a unit time for the whole project, if the compression or the relaxation of the activities in the cut-set is allowed. In the paper the algorithm based on this theorem is discussed in detail.