# Linear Programming (Edexcel IAL Maths D1)

> Edexcel International A-Level Mathematics · IAL D1 (WDM11)
> Source: https://www.owlsprep.com/study/edexcel-ial-math-d1-linear-programming/

This guide covers all linear programming content for Edexcel IAL D1, including problem formulation, graphical solution methods for 2-variable problems, and integer solution calculation, with exam-aligned worked examples.

**Prerequisites:** [Graphing linear inequalities on a 2D coordinate plane](https://www.owlsprep.com/study/edexcel-ial-math-d1-linear-inequalities/); [Solving systems of simultaneous linear equations](https://www.owlsprep.com/study/edexcel-ial-math-core-1-simultaneous-equations/)

## Learning objectives

- Formulate 2-variable linear programming problems by defining decision variables, writing an objective function and constraints
- Solve 2-variable linear programs using both the objective line (ruler) method and vertex testing method
- Find valid integer solutions to linear programming problems by testing feasible integer points near the continuous optimum
- Interpret linear programming solutions in the context of the original problem

## Formulating Linear Programming Problems

**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.

*Calculator:* allowed

## Graphical Solution: Objective Line (Ruler) Method

**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. 1. Plot all constraint lines on the x-y plane, and shade the feasible region that satisfies all constraints (including non-negativity).
2. 2. Plot the objective line for an arbitrary value of Z, chosen to make the line easy to plot (e.g. for $Z=25x+40y$, use $Z=200$ to get $5x+8y=40$).
3. 3. 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.
4. 4. 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+2y \leq 20$, $3x+5y \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 $25x + 40y = 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.

*Calculator:* allowed

## Graphical Solution: Vertex Testing Method

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. 1. Identify all vertices of the feasible region by solving pairs of linear equations for the constraint lines that intersect at each vertex.
2. 2. Calculate the value of the objective function Z at every vertex.
3. 3. 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+2y=20$: (20, 0)
4. Vertex 3: Intersection of $x=0$ and $x+2y=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.

> **info**
>
> If two adjacent vertices have the same optimal Z value, every point along the line connecting those two vertices is also optimal. You should state this in your answer if it occurs.

> **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.

*Calculator:* allowed

## Integer Linear Programming Solutions

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.

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

1. 1. First find the optimal continuous solution using either the objective line or vertex testing method.
2. 2. Identify all integer points that lie inside or on the boundary of the feasible region, near the continuous optimal point.
3. 3. 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.

*Calculator:* allowed

## Common pitfalls

- **Wrong:** Failing to explicitly define decision variables when formulating LP problems
  - Why it fails: Edexcel examiners award dedicated marks for clear variable definitions, so you lose easy marks if you skip this step
  - Correct: Always start formulation with "Let x = ..., Let y = ..." with full context, e.g. "Let x = number of small tables produced per week"
- **Wrong:** Rounding continuous optimal values to get integer solutions without checking feasibility
  - Why it fails: Rounded values often violate one or more constraints, leading to an invalid solution
  - Correct: Test all integer points near the continuous optimal point, and confirm each point satisfies all constraints before calculating Z
- **Wrong:** Forgetting to include non-negativity constraints ($x \geq 0, y \geq 0$) in your formulation
  - Why it fails: Non-negativity constraints are required for almost all LP problems, and omitting them can change the feasible region entirely
  - Correct: Always add $x \geq 0$ and $y \geq 0$ unless the problem explicitly allows negative values for decision variables
- **Wrong:** Shading the wrong side of constraint lines when plotting the feasible region
  - Why it fails: This leads to an incorrect feasible region, so all subsequent calculations of optimal points will be wrong
  - Correct: 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:** Only testing one vertex of the feasible region when using the vertex testing method
  - Why it fails: The optimal point could be another vertex, and you lose marks for not showing all calculations
  - Correct: Calculate Z for every vertex of the feasible region, even if some appear to give low Z values

## Cheatsheet

| Task | Steps | Key Exam Tip |
| --- | --- | --- |
| Formulate LP problem | 1. Define decision variables 2. Write objective function 3. Write constraints + non-negativity | Simplify constraints to make graphing easier |
| Objective line method | 1. 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 | 1. 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 | 1. Find continuous optimal 2. Test nearby integer feasible points 3. Select optimal integer Z | Never round directly: always check feasibility of each integer point |

## 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)](https://www.owlsprep.com/study/edexcel-ial-math-d1-algorithms/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/edexcel-ial-math-d1-linear-programming/