Decision: Linear Programming and Critical Path Depth
Linear Programming and Critical Path Depth extends Decision Maths beyond the graphical method for linear programming to the Simplex algorithm, a systematic tabular procedure that solves linear programming problems with more than two decision variables by moving from one corner of the feasible region to another, always improving the objective function, until no further improvement is possible. It also extends critical path analysis from finding the project duration and float to resource scheduling: given a limited number of resources (such as workers), the topic covers building a schedule (using earliest start times and the float of non-critical activities) and finding the minimum number of resources needed so the project is not delayed.
Before you start
Make sure you're comfortable with these topics first:
Method
- For a linear programming problem written as 'maximise P = ...' subject to '<=' constraints, introduce one slack variable for each constraint to convert every inequality into an equation, and write the objective as an equation P - (coefficients) = 0.
- Set up the initial Simplex tableau, with one row per constraint (labelled by its slack variable, which starts as the basic variable) plus a final row for the objective equation.
- Choose the pivot column: the column (other than the RHS) with the most negative entry in the objective row. If every entry in the objective row is zero or positive, the tableau is already optimal, so stop.
- Choose the pivot row using the ratio test: divide the RHS of each constraint row by its entry in the pivot column (ignoring rows with a zero or negative entry in that column), and pick the row with the smallest non-negative ratio.
- Divide the pivot row by the pivot element so the pivot entry becomes 1, then subtract a suitable multiple of this new row from every other row (including the objective row) so every other entry in the pivot column becomes 0. Relabel the pivot row with the variable that has just entered the basis.
- Repeat the column and row choice and the row operations until every entry in the objective row is zero or positive; read the solution from the RHS column, where the value of each basic variable is its RHS entry and every non-basic variable equals 0.
- For a resource-scheduling question, first find the earliest start time (ES) and earliest finish time (EF) of every activity by a forward pass, then the latest start time (LS) and latest finish time (LF) by a backward pass from the project duration; total float = LS - ES.
- To find the resources needed if every activity starts at its earliest time, list every activity active in each time interval between events and add its resource requirement; the peak total across all intervals is the minimum number of resources needed to avoid delaying the project, and only activities with positive float can be shifted later to try to reduce a peak that occurs away from the critical path.
Worked example
Maximise P = 3x + 2y subject to 2x + y <= 18, 2x + 3y <= 42, x >= 0, y >= 0. Solve using the Simplex algorithm, showing each tableau.
- Introduce slack variables s1, s2 and write the constraints as equations: 2x+y+s1=18, 2x+3y+s2=42, and the objective as P-3x-2y=0. Initial tableau (basic variables s1=18, s2=42): row s1: x=2, y=1, s1=1, s2=0, RHS=18. Row s2: x=2, y=3, s1=0, s2=1, RHS=42. Row P: x=-3, y=-2, s1=0, s2=0, RHS=0.
- The most negative entry in the P row is -3 (x column), so x is the entering variable. Ratio test: 18/2=9 for row s1, 42/2=21 for row s2; the smaller ratio is 9, so s1 leaves and the pivot element is 2.
- Divide row s1 by 2 to form the new x row: x=1, y=0.5, s1=0.5, s2=0, RHS=9. Update row s2 by subtracting 2 times the new x row: x=0, y=2, s1=-1, s2=1, RHS=24. Update row P by adding 3 times the new x row: x=0, y=-0.5, s1=1.5, s2=0, RHS=27.
- The only negative entry in the P row is now -0.5 (y column), so y is the entering variable. Ratio test: 9/0.5=18 for row x, 24/2=12 for row s2; the smaller ratio is 12, so s2 leaves and the pivot element is 2.
- Divide row s2 by 2 to form the new y row: x=0, y=1, s1=-0.5, s2=0.5, RHS=12. Update row x by subtracting 0.5 times the new y row: x=1, y=0, s1=0.75, s2=-0.25, RHS=3. Update row P by adding 0.5 times the new y row: x=0, y=0, s1=1.25, s2=0.25, RHS=33.
- Every entry in the P row is now zero or positive (1.25 and 0.25), so the tableau is optimal. Reading the RHS column against the basic variables gives x=3, y=12, and maximum P=33. This matches the graphical solution, since the vertices of the feasible region are (0,0), (9,0), (3,12) and (0,14), and P=3x+2y is largest, at 33, at (3,12).
Practice questions
Type your answer and press Check to be marked straight away, or reveal the answer and mark yourself.
Q1Write the constraint 3x + 4y <= 24 as an equation by introducing a slack variable s.Show answer
Answer: 3x + 4y + s = 24, with s >= 0.
Q2In a Simplex tableau the objective row (for maximising P) reads P - 5x - 2y = 0. Which variable enters the basis first, and why?Show answer
Answer: x, because -5 is the most negative entry in the objective row, so increasing x gives the greatest rate of improvement to P.
Q3In a ratio test, the x column has entries 4 and 2 in two constraint rows, with RHS values 20 and 8. Which row is the pivot row?Show answer
Answer: The second row, since 20/4=5 and 8/2=4, and 4 is the smaller non-negative ratio.
Q4A final Simplex tableau is optimal, with basic variables x=6 (row 1) and s2=10 (row 2), and y and s1 non-basic, giving P=42. State the values of x, y and the maximum value of P.Show answer
Answer: x=6, y=0 (non-basic variables equal 0), maximum P=42.
Q5State whether the point (7,5) is feasible for the constraints 3x+y<=21 and x+2y<=20.Show answer
Answer: Not feasible: substituting into the first constraint gives 3(7)+5=26, which is greater than 21, so the point violates that constraint.
Q6An activity has earliest start time 8 and latest start time 8. State, with a reason, whether it lies on the critical path.Show answer
Answer: Yes: its total float is latest start minus earliest start = 8-8=0, and an activity with zero float is critical.
Q7Explain what it means, in the context of the original problem, for a Simplex tableau's objective row to have every entry zero or positive.Show answer
Answer: Each entry shows how much P would fall, per unit increase in that non-basic variable, if it were brought into the solution; if every entry is zero or positive, no currently excluded variable can improve P, so the current solution is optimal.
Q8Activities A (0 to 3, using 2 workers) and B (0 to 5, using 3 workers) both start at time 0 with no other activity running before time 3. Find the total number of workers required between time 0 and time 3.Show answer
Answer: 5 workers (2 for A plus 3 for B, since both are running throughout that interval).
Exam-style questions
Written in the style of a A Level Further Maths exam paper, with a full mark scheme.
Maximise P = 5x + 4y subject to 6x + 4y <= 24, x + 2y <= 6, x >= 0, y >= 0. Use the Simplex algorithm to find the optimal values of x, y and P, showing each tableau.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 8 available
The table shows the activities needed for a small project, their duration in days, their immediate predecessor activities, and the number of workers each activity needs while it is running. Activity | Duration (days) | Predecessor(s) | Workers needed A | 4 | none | 2 B | 3 | none | 1 C | 2 | A | 3 D | 5 | A | 2 E | 3 | B, C | 2 F | 4 | D, E | 1 (a) Find the earliest and latest start time of every activity, and hence find the length of the critical path and the total float of activity B. (b) Given that every activity is scheduled to start at its earliest start time, find the maximum number of workers required at any one time, stating the days on which this maximum occurs. (c) Explain why delaying the start of activity B cannot reduce this maximum.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 9 available
A Simplex tableau for a maximisation problem with two original variables x and y and slack variables s1, s2 has reached its final, optimal form: row y: x=0, y=1, s1=1/2, s2=-1/4, RHS=5. Row x: x=1, y=0, s1=-1, s2=1, RHS=8. Row P: x=0, y=0, s1=3, s2=1, RHS=61. (a) Write down the maximum value of P, and the values of x and y at which it occurs. (b) State the value of the slack variable s2 at the optimal solution, and explain what this tells you about the constraint associated with s2. (c) Explain how you know this tableau is optimal.
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: linear programming and critical path depth worksheet pack - 12 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: linear programming and critical path depth, 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.