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.

**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

*x _{ij}* = Amount of flow in activity

*D*_{ij}* *=* *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.

**Example
6.5-5**

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.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Operations Research: An Introduction : Network Models : CPM AND PERT: linear Programming Formulation of CPM |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.