Linear Programming (Edexcel IAL Maths D1)

Edexcel International A-Level Mathematics· 2018 Specification Issue 3· 25 min read

1. Formulating Linear Programming Problems★★☆☆☆⏱ 6 min

✓ Calculator OK

📘 Definition

Linear Programming (LP)

A mathematical method to find the optimal (maximum or minimum) value of a linear objective function, subject to a set of linear inequality or equality constraints.

To formulate any 2-variable LP problem, you need three core components: decision variables, an objective function, and constraints. Always define decision variables clearly at the start of your working, as Edexcel examiners award dedicated marks for explicit definitions.

Decision variables: Variables representing the quantities you can control, e.g. number of chairs produced, hours allocated to a project. Always define them explicitly with full context.
Objective function: A linear function representing the quantity you want to maximise (e.g. profit, revenue) or minimise (e.g. cost, time), written in terms of x and y, usually denoted as Z.
Constraints: Linear inequalities representing limits on resources (e.g. total labour hours available) or requirements, plus non-negativity constraints ( $x \geq 0$ , $y \geq 0$ ) unless specified otherwise.

📐 Worked Example

A carpenter makes small and large tables. Each small table takes 2 hours of labour and uses 3m of wood, generating £25 profit. Each large table takes 4 hours of labour and uses 5m of wood, generating £40 profit. The carpenter has a maximum of 40 labour hours and 60m of wood available per week. Formulate this as a linear programming problem to maximise weekly profit.

1
Step 1: Define decision variables
2
Let $x$ = number of small tables produced per week, $y$ = number of large tables produced per week
3
Step 2: Write the objective function (maximise profit):
4
$Z = 25x + 40y$
5
Step 3: Write constraints for resources, simplified for easier graphing:
6
Labour constraint: 2 hours per small table, 4 per large table, max 40 total hours:
7
$2x + 4y \leq 40 \implies x + 2y \leq 20$
8
Wood constraint: 3m per small table, 5 per large table, max 60 total m:
9
$3x + 5y \leq 60$
10
Step 4: Add non-negativity constraints:
11
$x \geq 0, y \geq 0$

Exam tip:

Always simplify constraints where possible (e.g. divide the labour constraint by 2 in the example above) to make graphing easier later. Examiners accept simplified constraints as long as they are equivalent to the original.

2. Graphical Solution: Objective Line (Ruler) Method★★★☆☆⏱ 7 min

✓ Calculator OK

📘 Definition

Feasible Region

The set of all (x, y) points that satisfy every constraint in a linear programming problem. For 2-variable problems, this is a convex polygon (including its boundary) on the x-y plane.

The objective line method uses a sliding ruler to find the point in the feasible region where the objective function is maximised or minimised. This method is particularly useful if you are asked to identify the optimal point without calculating its exact coordinates, or to explain how a change in the objective function would change the optimal solution.

1. Plot all constraint lines on the x-y plane, and shade the feasible region that satisfies all constraints (including non-negativity).
1. Plot the objective line for an arbitrary value of Z, chosen to make the line easy to plot (e.g. for $Z = 25 x + 40 y$ , use $Z = 200$ to get $5 x + 8 y = 40$ ).
1. For a maximisation problem, slide the objective line parallel to itself upwards/rightwards as far as possible while still touching the feasible region. For minimisation, slide it downwards/leftwards.
1. The last point of contact between the objective line and the feasible region is the optimal point.

📐 Worked Example

Using the LP formulation from the carpenter example, use the objective line method to identify the optimal point that maximises profit.

1
Step 1: Plot the constraints $x + 2 y \leq 20$ , $3 x + 5 y \leq 60$ , $x \geq 0$ , $y \geq 0$ . The feasible region is a triangle with vertices at (0,0), (20, 0), (0, 10).
2
Step 2: Plot the objective line $25 x + 40 y = 200$ , which passes through (8, 0) and (0, 5).
3
Step 3: Slide the objective line parallel upwards to maximise Z. The furthest point it touches while remaining in the feasible region is (20, 0).
4
Step 4: The optimal point is (20, 0), giving a maximum profit of $Z = 25 (20) + 40 (0) = £500$ .

Exam tip:

Always label your objective line clearly on your graph in exams, and indicate the direction you are sliding it with an arrow, as this is required to get full marks for the objective line method.

3. Graphical Solution: Vertex Testing Method★★★☆☆⏱ 7 min

✓ Calculator OK

The vertex testing method relies on the fundamental property of linear programming: the optimal value of the objective function always occurs at one of the vertices (corner points) of the feasible region. This method is more reliable for calculating exact optimal values, and is the preferred method if you need to compute the exact maximum or minimum value of Z.

1. Identify all vertices of the feasible region by solving pairs of linear equations for the constraint lines that intersect at each vertex.
1. Calculate the value of the objective function Z at every vertex.
1. Select the vertex with the highest Z value for maximisation problems, or lowest Z value for minimisation problems.

📐 Worked Example

Use the vertex testing method to confirm the optimal profit for the carpenter example from the previous sections.

1
Step 1: Identify all vertices of the feasible region:
2
Vertex 1: Intersection of $x = 0$ and $y = 0$ : (0, 0)
3
Vertex 2: Intersection of $y = 0$ and $x + 2 y = 20$ : (20, 0)
4
Vertex 3: Intersection of $x = 0$ and $x + 2 y = 20$ : (0, 10)
5
Step 2: Calculate Z at each vertex:
6
At (0,0): $Z = 25 (0) + 40 (0) = £0$
7
At (20,0): $Z = 25 (20) + 40 (0) = £500$
8
At (0,10): $Z = 25 (0) + 40 (10) = £400$
9
Step 3: The maximum Z value is £500 at (20, 0), matching the result from the objective line method.

Exam tip:

Always list all vertices of the feasible region, even if some look like they will obviously give a low Z value. Edexcel examiners award marks for correctly identifying all vertices, even if your final optimal value is correct.

4. Integer Linear Programming Solutions★★★★☆⏱ 6 min

✓ Calculator OK

Many LP problems have decision variables that represent indivisible items (e.g. number of tables, number of staff), so solutions must be integers. For Edexcel IAL D1, you only need to test feasible integer points near the optimal continuous solution to find the integer optimum; more advanced integer programming algorithms are not required.

📘 Definition

Integer Feasible Point

A point (x, y) with integer x and y values that satisfies all constraints of the LP problem.

1. First find the optimal continuous solution using either the objective line or vertex testing method.
1. Identify all integer points that lie inside or on the boundary of the feasible region, near the continuous optimal point.
1. Calculate Z for each of these integer points, and select the one with the optimal (maximum/minimum) Z value.

📐 Worked Example

For the carpenter example, suppose the carpenter is required to make at least 3 large tables per week. Find the integer solution that maximises profit.

1
Step 1: Add the new constraint $y \geq 3$ . The updated feasible region now has vertices at (0,3), (14, 3), (0, 10).
2
Step 2: Find the continuous optimal solution by testing vertices:
3
At (0,3): $Z = 25 (0) + 40 (3) = £120$
4
At (14,3): $Z = 25 (14) + 40 (3) = £470$
5
At (0,10): $Z = 25 (0) + 40 (10) = £400$
6
Step 3: The continuous optimal point (14, 3) is already integer, so the integer optimal profit is £470, from producing 14 small tables and 3 large tables.
7
If the continuous optimal was, for example, (3.2, 5.7), you would test integer points (3,5), (3,6), (4,5), (4,6) to check which are feasible and give the highest Z value.

Exam tip:

Never round the continuous optimal solution directly, as rounded values often lie outside the feasible region. Always explicitly check that each integer point you test satisfies all constraints.

5. Common Pitfalls

Wrong move:

Failing to explicitly define decision variables when formulating LP problems

Why:

Edexcel examiners award dedicated marks for clear variable definitions, so you lose easy marks if you skip this step

Correct move:

Always start formulation with "Let x = ..., Let y = ..." with full context, e.g. "Let x = number of small tables produced per week"

Wrong move:

Rounding continuous optimal values to get integer solutions without checking feasibility

Why:

Rounded values often violate one or more constraints, leading to an invalid solution

Correct move:

Test all integer points near the continuous optimal point, and confirm each point satisfies all constraints before calculating Z

Wrong move:

Forgetting to include non-negativity constraints ( $x \geq 0, y \geq 0$ ) in your formulation

Why:

Non-negativity constraints are required for almost all LP problems, and omitting them can change the feasible region entirely

Correct move:

Always add $x \geq 0$ and $y \geq 0$ unless the problem explicitly allows negative values for decision variables

Wrong move:

Shading the wrong side of constraint lines when plotting the feasible region

Why:

This leads to an incorrect feasible region, so all subsequent calculations of optimal points will be wrong

Correct move:

Test a point (usually (0,0) if it is not on the line) to see which side of the line satisfies the inequality, and shade that side

Wrong move:

Only testing one vertex of the feasible region when using the vertex testing method

Why:

The optimal point could be another vertex, and you lose marks for not showing all calculations

Correct move:

Calculate Z for every vertex of the feasible region, even if some appear to give low Z values

6. Quick Reference Cheatsheet

Task	Steps	Key Exam Tip
Formulate LP problem	Define decision variables 2. Write objective function 3. Write constraints + non-negativity	Simplify constraints to make graphing easier
Objective line method	Plot feasible region 2. Plot arbitrary objective line 3. Slide line parallel to find optimal point	Label objective line and direction of sliding with an arrow
Vertex testing method	Find all feasible region vertices 2. Calculate Z at each vertex 3. Select optimal Z	List all vertices to get full method marks
Integer solution	Find continuous optimal 2. Test nearby integer feasible points 3. Select optimal integer Z	Never round directly: always check feasibility of each integer point

7. Frequently Asked

Do I need to learn both graphical solution methods for Edexcel IAL D1?

Yes, both the objective line and vertex testing methods are explicitly examinable, and you may be asked to use a specific method in a question. The vertex method is more reliable for integer solution problems, while the objective line method is faster for qualitative questions about changing the objective function.

Can I use a calculator for linear programming questions?

Yes, standard calculators are permitted for all Edexcel IAL D1 papers, but CAS calculators with symbolic algebra functionality are forbidden. You can use calculators to compute objective function values at vertices quickly.

Do I always need integer solutions for LP problems?

No, only if the problem specifies that decision variables represent indivisible items (e.g. number of tables) or explicitly asks for integer solutions. Always check the problem context first.

Going deeper

What's Next

Now that you have mastered linear programming for Edexcel IAL D1, you can move on to practicing full past paper questions to apply your skills under timed conditions. Linear programming is often combined with other D1 topics such as algorithms and graph theory in longer 6-8 mark exam questions, so make sure you have a strong grasp of all D1 content to maximise your marks. Remember that both graphical solution methods are examinable, so practice both to be prepared for any question type. Integer solution questions are often worth 3-4 marks, so practice testing feasible points quickly to avoid losing marks here.

→Algorithms (Edexcel IAL D1)