# Recitation 9

Example: Consider the CPM project network below, where time is measured in days:

Set up the linear program to determine the critical path.

Solution: Suppose the times are $t_0, \dots, t_6$ for node 0 to 6. The linear programming is as follows.

 Minimize: $t_6$ Subject to: $t_1 - t_0 \ge 6$ $t_2 - t_0 \ge 5$ $t_3 - t_1 \ge 6$ $t_3 - t_2 \ge 4$ $t_4 - t_1 \ge 8$ $t_5 - t_2 \ge 7$ $t_5 - t_3 \ge 5$ $t_6 - t_2 \ge 2$ $t_6 - t_3 \ge 6$ $t_6 - t_5 \ge 2$ $t_0, t_1, \dots, t_6 \ge 0$