Cost/time trade-off analysis for the critical path method: A derivation of the network flow approach

A well-known problem in critical path analysis involves normal and crash durations being provided for each activity, with. corresponding costs, and requires a minimum cost schedule of durations to be determined for all possible durations of the project. It has long been known that an optimal solution to the problem can be obtained iteratively by constructing a minimum cost network flow problem and adjusting the durations of activities corresponding to a minimum capacity cut-set. A recent paper described this method, but gave no indication of how the method could be derived. It is shown here that a linear programming formulation and its dual enables this to be done very simply.