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