linear Programming Formulation of CPM
A CPM problem can thought of as the opposite of the shortest-route problem (Section 6.3), in the sense that we are interested in finding the Longest route of a unit flow entering at the start node and terminating at the finish node. We can thus apply the shortest route LP formulation in Section 6.3.3 to CPM in the following manner. Define
xij = Amount of flow in activity (i, j), for all defined i and j
Dij = Duration of activity (i, j), for all defined i and j
Thus, the objective function of the linear program becomes
(Compare with the shortest route LP formulation in Section 6.3.3 where the objective function is minimized.) For each node, there is one constraint that represents the conservation of flow:
Total input flow = Total output flow
All the variables, Xij, are nonnegative.
The· LP formulation of the project of Example 6.5-2 (Figure 6.42 ) is given below. Note that nodes 1 and 6 are the start and finish nodes, respectively.
The solution defines the critical path as A --> D --> Dummy ---> H, and the duration of the project is 25 days. The LP solution is not complete, because it determines the critical path, but does not provide the data needed to construct the CPM chart. We have seen in Figure 6.48, however, that AMPL can be used to provide all the needed information without the LP optimization.
PROBLEM SET 6.5D
1. Use LP to determine the critical path for the project network in Figure 6.43.
2. Use LP to determine the critical path for the project networks in Figure 6.44.