Decision Maths: Critical Path Analysis and Linear Programming
Critical path analysis finds the minimum time needed to complete a project made up of activities with durations and precedence requirements (which activities must finish before others can start), by finding the earliest and latest start and finish time of every activity; the critical path is the sequence of activities with zero float (spare time) that fixes the overall project length. Linear programming formulates a real-world problem with two decision variables as an objective function to maximise or minimise, subject to linear inequality constraints, and solves it by evaluating the objective function at each vertex of the feasible region.
Before you start
Make sure you're comfortable with these topics first:
Method
- From a precedence table, list each activity, its duration, and its immediate predecessors (the activities that must finish before it can start).
- Forward pass: find the earliest start time (ES) and earliest finish time (EF = ES + duration) of each activity; an activity's ES equals the largest EF among all its immediate predecessors (0 if it has none).
- The project duration equals the largest EF among activities that are not a predecessor of anything else (the 'terminal' activities).
- Backward pass: working from the project duration, find the latest finish time (LF) and latest start time (LS = LF - duration) of each activity; an activity's LF equals the smallest LS among all the activities that depend directly on it (the project duration if it has no successor).
- Find the total float of each activity as LS - ES (equivalently LF - EF); the critical activities are those with float 0, and together they form the critical path, which fixes the minimum project duration.
- For linear programming, define the decision variables, translate every constraint (including any resource limits) into a linear inequality, and write the objective function to be maximised or minimised.
- Find the vertices of the feasible region by solving pairs of constraint boundary equations simultaneously, checking each candidate point against every other constraint to confirm it is genuinely feasible.
- Evaluate the objective function at every vertex of the feasible region; the optimal solution is the vertex giving the largest value (for a maximise problem) or the smallest value (for a minimise problem).
Worked example
A project has activities with durations (days) and immediate predecessors given in the table below. Find the earliest start and finish time of every activity, the project duration, and the critical path. Activity A, duration 4, predecessors: none. Activity B, duration 3, predecessors: none. Activity C, duration 5, predecessors: A. Activity D, duration 2, predecessors: A. Activity E, duration 6, predecessors: B. Activity F, duration 3, predecessors: C, D. Activity G, duration 4, predecessors: E, F.
- Forward pass: A and B have no predecessors, so ES(A)=0, EF(A)=4; ES(B)=0, EF(B)=3.
- C and D depend only on A, so ES(C)=ES(D)=EF(A)=4; EF(C)=4+5=9; EF(D)=4+2=6. E depends only on B, so ES(E)=EF(B)=3; EF(E)=3+6=9.
- F depends on both C and D, so ES(F)=max(EF(C),EF(D))=max(9,6)=9; EF(F)=9+3=12. G depends on both E and F, so ES(G)=max(EF(E),EF(F))=max(9,12)=12; EF(G)=12+4=16.
- G is the only activity with no successor, so the project duration = EF(G) = 16 days.
- Backward pass from LF(G)=16: LS(G)=12. F's only successor is G, so LF(F)=LS(G)=12, LS(F)=9. E's only successor is G, so LF(E)=12, LS(E)=6. D's only successor is F, so LF(D)=LS(F)=9, LS(D)=7. C's only successor is F, so LF(C)=9, LS(C)=4. B's only successor is E, so LF(B)=LS(E)=6, LS(B)=3. A's successors are C and D, so LF(A)=min(LS(C),LS(D))=min(4,7)=4, LS(A)=0.
- Float = LS - ES for each activity: A=0, B=3, C=0, D=3, E=3, F=0, G=0. The critical activities (float 0) are A, C, F, G.
- Final answer: project duration = 16 days; critical path A-C-F-G (4+5+3+4=16).
Practice questions
Try each question, then tap to reveal the answer.
Q1Define 'total float' for an activity in a precedence network.Show answer
Answer: Float = latest start time - earliest start time (equivalently latest finish - earliest finish) for that activity: the amount of time it could be delayed without delaying the overall project.
Q2An activity has earliest start time 5, latest start time 5, and duration 3. State whether it is a critical activity, giving a reason.Show answer
Answer: Yes; float = latest start - earliest start = 5-5 = 0, and an activity with zero float is critical, since any delay to it would delay the whole project.
Q3Activity X has duration 7 and no predecessor. Activity Y has duration 5 and predecessor X. Find the earliest start and earliest finish time of Y.Show answer
Answer: ES(Y) = 7, EF(Y) = 12 (ES(Y) = EF(X) = 0+7 = 7; EF(Y) = 7+5 = 12).
Q4A furniture maker makes chairs (x) and tables (y). Each chair needs 3 hours of carpentry and 1 hour of finishing; each table needs 2 hours of carpentry and 2 hours of finishing. There are 60 hours of carpentry and 32 hours of finishing available. Write down the two resource constraints as inequalities (excluding non-negativity).Show answer
Answer: 3x + 2y <= 60 (carpentry); x + 2y <= 32 (finishing).
Q5The feasible region for a linear programming problem has vertices (0,0), (0,10), (8,6), (12,0). The objective is to maximise P=5x+4y. Evaluate P at each vertex and state the optimal solution.Show answer
Answer: P values: 0, 40, 64, 60; the optimal solution is at (8,6), where P=64.
Q6Explain why, for a linear programming problem where x and y must be whole numbers, the optimal vertex found by evaluating the objective function at the vertices of the feasible region might not give the final answer.Show answer
Answer: The optimal vertex of the continuous feasible region may have non-integer coordinates, which is not a valid solution if x and y represent whole quantities; the nearby integer points inside the feasible region must then be tested in the objective function to find the best integer solution.
Q7A minimisation linear programming problem has objective function C=3x+7y and feasible region vertices (2,1), (6,0) and (0,4). Evaluate C at each vertex and state the minimum value.Show answer
Answer: C(2,1)=13, C(6,0)=18, C(0,4)=28; the minimum value is C=13, at the vertex (2,1).
Exam-style questions
Written in the style of a A Level Further Maths exam paper, with a full mark scheme.
A project has the following activities, durations (days) and immediate predecessors: Activity A, duration 5, predecessors: none. Activity B, duration 6, predecessors: none. Activity C, duration 3, predecessors: A. Activity D, duration 7, predecessors: A. Activity E, duration 4, predecessors: B. Activity F, duration 2, predecessors: C, E. Activity G, duration 5, predecessors: D. Activity H, duration 3, predecessors: F, G. (a) Find the earliest start and finish time of every activity, and state the minimum project duration. (b) Find the latest start and finish time of every activity. (c) Hence state the critical path and the float of activity C.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 9 available
A garden centre grows roses (x trays) and tulips (y trays) for sale each week. Each tray of roses needs 2 hours of potting and 1 hour of watering; each tray of tulips needs 1 hour of potting and 3 hours of watering. There are 40 hours of potting time and 60 hours of watering time available, and the centre can display at most 25 trays in total. Profit is 8 pounds per tray of roses and 5 pounds per tray of tulips. (a) Write down the objective function to be maximised and the three resource constraints (excluding x, y >= 0). (b) The vertices of the feasible region are (0,0), (20,0), (15,10), (7.5,17.5) and (0,20). Evaluate the objective function at each vertex and state the number of trays of each type that maximises profit, and the maximum profit.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 7 available
In a precedence network, activity K has earliest start time 12 and duration 5. Its only successor is activity L, which has latest start time 24. (a) Find the earliest finish time of K. (b) Find the latest finish time of K. (c) Find the float of K, and state whether K is critical.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 5 available
See real A Level Further Maths past-paper questions, with official mark schemes →
Free printable worksheet
Want more practice on paper? Download the decision maths: critical path analysis and linear programming worksheet pack - 10 pages of exam-style questions with a full mark scheme. One email opens every download in this browser for 14 days - no account, no card. Print it for personal and classroom use.
Next topics
Not quite what you needed?
Tell us what is missing on decision maths: critical path analysis and linear programming, or which topic to write up next. Every request is read, and we reply to every one.
Build a full practice pack.
This topic is one of hundreds in the library - pick the ones a student needs and generate a printable PDF in minutes.