What is linear programming in the context of Decision Mathematics 1?

Linear programming is a mathematical method used in Decision Mathematics 1 to find the best possible outcome in a given mathematical model. This involves maximizing or minimizing a linear objective function, subject to a set of linear inequalities or constraints. It is a crucial topic in the Edexcel International A Levels Mathematics curriculum, particularly for optimizing resources in various fields such as economics, business, and engineering.

How do you formulate a linear programming problem?

To formulate a linear programming problem, you need to identify the objective function, which is the function you want to maximize or minimize. Next, determine the constraints, which are the limitations or requirements expressed as linear inequalities. Finally, define the decision variables, which represent the quantities you want to solve for. This formulation is essential for solving linear programming problems in Decision Mathematics 1.

What methods are used to solve linear programming problems in Edexcel International A Levels?

In the Edexcel International A Levels, particularly in Decision Mathematics 1, linear programming problems are typically solved using graphical methods for two-variable problems. This involves plotting the constraints on a graph, identifying the feasible region, and then finding the optimal solution by evaluating the objective function at the vertices of the feasible region. For more complex problems, the Simplex method may be introduced, which is an algorithmic approach to finding the optimal solution.

What are the common applications of linear programming in real-world scenarios?

Linear programming is widely used in various real-world applications, including optimizing production schedules, minimizing costs in transportation and logistics, maximizing profits in business operations, and resource allocation in project management. These applications are relevant to the Decision Mathematics 1 curriculum, as they demonstrate how mathematical concepts can be applied to solve practical problems efficiently.

What are the limitations of linear programming?

While linear programming is a powerful tool, it has limitations. It assumes linearity in both the objective function and constraints, which may not always represent real-world situations accurately. Additionally, it requires that all relationships be deterministic and that decision variables be continuous, which may not be feasible in all scenarios. Understanding these limitations is important for students studying Decision Mathematics 1 in the Edexcel International A Levels curriculum.

Why is "Forgetting non-negativity constraints $x \ge 0, y \ge 0$" a common mistake in Linear programming ?

Why it happens: They seem obvious. How to avoid it: ALWAYS write them explicitly. Edexcel mark schemes award a B1 specifically for non-negativity. Even if the question implies x, y 0, include them in your formulation. Source: WDM01/01 Examiner Reports — flagged every session

Why is "Shading the FEASIBLE side instead of the infeasible side" a common mistake in Linear programming ?

Why it happens: Confusing convention. How to avoid it: Edexcel convention: SHADE the INFEASIBLE side; leave the feasible region clear. State this convention on your graph: 'unshaded region = feasible'.

Why is "Sliding the objective line in the wrong direction (inward for max or outward for min)" a common mistake in Linear programming ?

Why it happens: Confusing the role of the gradient. How to avoid it: MAXIMISE = slide AWAY from origin (assuming all positive coefficients). MINIMISE = slide TOWARD origin. Always sketch the gradient direction (perpendicular to the objective line).

Why is "For an INTEGER LP, taking the integer point CLOSEST to the LP optimum as the answer" a common mistake in Linear programming ?

Why it happens: Naive rounding. How to avoid it: The closest integer point may be INFEASIBLE or sub-optimal. Test SEVERAL integer points near the LP optimum AND near each binding constraint.

Why is "Writing $\ge$ when the constraint is $\le$ (or vice versa)" a common mistake in Linear programming ?

Why it happens: Misreading 'at most' vs 'at least'. How to avoid it: 'Available', 'budget', 'capacity' → . 'Minimum requirement', 'demand', 'at least' → . Write each constraint in words first, then translate.

Why is "Writing the LP without DEFINING $x$ and $y$" a common mistake in Linear programming ?

Why it happens: Rushing into algebra. How to avoid it: ALWAYS begin: 'Let x = ... and y = ...'. Edexcel awards a B1 specifically for variable definitions. Without them, marks for the rest of the formulation can be withheld.

Decision Mathematics 1Edexcel International A Levels Mathematics (XMA01-YMA01)

Linear programming

Work through the notes, try the practice questions, then take the quiz. The report tells you exactly what to revise next.

PreviousNext

Learn this Topic

Start with the slides for the quick version, then go deeper with the full study notes.

Detailed Notes

Full prose, callouts and a recap — built for A* mastery, not just a quick scan.

Take these study notes with you

Download a branded PDF — full prose, callouts, recap and memorise list for Linear programming , ready to print or save offline.

Linear Programming Study Notes — Edexcel IAL Mathematics D1 (WDM01/01, 2018 spec — 2026 onwards)

Two-variable LP. FORMULATE: define $x, y$ ; write linear objective $P = ax + by$ to optimise; write linear inequality constraints (resources $\le$ , requirements $\ge$ , non-negativity $\ge 0$ ). GRAPH boundary lines; SHADE the infeasible side; identify vertices of the feasible region. SOLVE: (a) objective-line method — slide $P = c$ parallel outward (max) or inward (min); (b) vertex method — evaluate $P$ at each vertex. Integer LP: the LP optimum is an UPPER bound (for max); test integer points near it.

What you’ll learn

Mapped to the Pearson Edexcel International A Levels XMA01-YMA01 syllabus (2026 onwards).

D1 5.1 — Formulate a real-world problem as a 2-variable linear programming problem.
D1 5.2 — Graphically represent the feasible region.
D1 5.3 — Use the objective-line (ruler) method to find the optimum vertex.
D1 5.4 — Use vertex testing to confirm the optimum.
D1 5.5 — Handle integer-valued solutions by testing integer points near the LP optimum.

Formulating an LP problem

Variables → objective → constraints → non-negativity.

Steps to formulate.

Identify decision variables. Name them and define them in words (e.g. $x$ = number of bicycles manufactured per week).
Write the objective function. Always linear in the decision variables: $P = ax + by$ . State 'maximise' or 'minimise'.
Write constraints. For each resource or requirement: turn the English into an inequality.
- 'X hours available' → $\text{usage} \le X$ .
- 'At least $N$ units required' → $\text{production} \ge N$ .
- 'At most $N$ units allowed' → $\text{production} \le N$ .
- 'Equal supply and demand' → $\text{supply} = \text{demand}$ (equality).
Non-negativity. Almost always $x \ge 0$ and $y \ge 0$ . ALWAYS include explicitly.
Integer requirement (if applicable). Add 'and $x, y \in \mathbb{Z}$ '.

Worked example.

A factory makes $x$ chairs and $y$ tables. Each chair uses $2$ kg wood and $3$ hours labour. Each table uses $5$ kg wood and $4$ hours labour. The factory has $40$ kg wood and $36$ hours labour weekly. Profit: $\$ 10 $per chair,$ $15$ per table. Formulate.

Decision variables: $x =$ chairs/week, $y =$ tables/week.
Objective: maximise $P = 10x + 15y$ .
Wood: $2x + 5y \le 40$ .
Labour: $3x + 4y \le 36$ .
Non-negativity: $x \ge 0, y \ge 0$ .
Integer: $x, y \in \mathbb{Z}$ .

Translation rules.

English	Mathematical
'at most $k$ '	$\le k$
'at least $k$ '	$\ge k$
'no more than $k$ '	$\le k$
'a minimum of $k$ '	$\ge k$
'twice as many $x$ as $y$ '	$x = 2y$ or $x - 2y = 0$
'at least twice as many $x$ as $y$ '	$x \ge 2y$
'ratio of $x$ to $y$ is at most $3$ to $1$ '	$x \le 3y$

LP feasible region: slide the objective line outward (max) until the last point of contact — always a vertex.

Always define variables in words first.
Objective is LINEAR; max or min.
Constraints: $\le$ for resources, $\ge$ for requirements.
Non-negativity is mandatory.

Graphing the feasible region

Draw boundary lines; shade infeasible side; identify vertices.

Procedure.

For each inequality constraint, draw the BOUNDARY LINE (replace inequality with equality).
Find two points on the line — typically intercepts. Connect them.
Determine which side of the line is infeasible: substitute the origin $(0, 0)$ (or another test point if the origin is on the line).
SHADE the INFEASIBLE side (Edexcel convention).
The unshaded region satisfying ALL constraints is the FEASIBLE REGION.
Identify the VERTICES (corners) by finding intersections of pairs of boundary lines.
Check each candidate vertex against ALL constraints — discard those outside the feasible region.

Worked example.

Max $P = 20x + 30y$ subject to $2x + 4y \le 40$ , $3x + y \le 24$ , $x \ge 3$ , $y \ge 0$ .

Lines:

$2x + 4y = 40$ , i.e. $x + 2y = 20$ : intercepts $(20, 0)$ and $(0, 10)$ .
$3x + y = 24$ : intercepts $(8, 0)$ and $(0, 24)$ .
$x = 3$ : vertical.
$y = 0$ : $x$ -axis.

Test origin: $0 + 0 = 0 \le 40$ ✓; $0 + 0 = 0 \le 24$ ✓; $0 < 3$ ✗ (origin infeasible). Shade accordingly.

Vertices by intersection:

$(3, 0)$ : from $x = 3$ and $y = 0$ .
$(8, 0)$ : from $3x + y = 24$ and $y = 0$ .
$(5.6, 7.2)$ : from $3x + y = 24$ and $2x + 4y = 40$ .
$(3, 8.5)$ : from $x = 3$ and $2x + 4y = 40$ .

Check all four: each satisfies the remaining constraints. Feasible region is a quadrilateral.

Graphing essentials (Edexcel marking).

Label both axes with the variable name AND scale.
Use a ruler — no freehand lines.
Clearly label the feasible region (often with an 'R').
Mark vertices with coordinates.
Use a graphics calculator only to check, never to bypass the construction.

Draw each boundary line via intercepts.
Test origin (or another point) to determine feasible side.
Shade infeasible side; leave feasible clear.
Vertices = intersections of pairs of boundary lines.
Discard vertices that violate other constraints.

Objective-line (ruler) method

Slide a line of constant $P$ parallel to itself until it just leaves the feasible region.

Why it works. The set of points where $P = c$ is a STRAIGHT LINE with slope $-a/b$ (for $P = ax + by$ ). As $c$ increases, the line moves PARALLEL away from the origin (when $a, b > 0$ ). The optimum is where the line LAST touches the feasible region.

Procedure (maximisation).

Choose a convenient constant $c$ and draw $P = c$ .
Note the slope $-a/b$ .
Slide the line AWAY from the origin (assuming positive coefficients).
The LAST vertex the line touches is the optimum.
Substitute that vertex into $P$ to read off the optimum value.

Procedure (minimisation). Same, but slide TOWARD the origin until the line just leaves the feasible region.

Worked example.

Max $P = 20x + 30y$ over the feasible region (vertices $(3, 0), (8, 0), (5.6, 7.2), (3, 8.5)$ ). Slope of objective line: $-20/30 = -2/3$ .

Draw $P = 60$ : $20x + 30y = 60$ , intercepts $(3, 0), (0, 2)$ . Slide outward. The slope $-2/3$ is between $-1/2$ (slope of $2x + 4y = 40$ ) and $-3$ (slope of $3x + y = 24$ ). The objective line exits the feasible region at the corner where these two lines meet: $(5.6, 7.2)$ . So $P_{\max} = 20(5.6) + 30(7.2) = 328$ .

When the objective line is PARALLEL to a binding constraint. The optimum lies along an entire EDGE of the feasible region, not just a vertex. Any point on that edge is optimal (multiple optimal solutions).

Practical tips.

Use a transparent ruler or set square to keep the slide parallel.
Draw the line at TWO values of $P$ (e.g. $P = 60$ and $P = 120$ ) to make the direction clear.
State the chosen $c$ in your written answer.

Slope of $P = ax + by$ is $-a/b$ .
Slide AWAY from origin for max (positive coefficients).
Slide TOWARD origin for min.
Optimum is the LAST vertex touched.
State the chosen objective-line value.

Vertex testing

Evaluate the objective at every vertex; pick the best.

Theorem (Fundamental theorem of LP). If the feasible region is BOUNDED and non-empty, the optimum of a linear objective is attained at a VERTEX.

Procedure.

Identify all vertices of the feasible region.
Evaluate $P$ at each vertex.
The maximum value (for a max problem) or minimum value (for a min problem) is the optimum.

Worked example.

Vertex	$P = 20x + 30y$
$(3, 0)$	$60$
$(8, 0)$	$160$
$(5.6, 7.2)$	$328$
$(3, 8.5)$	$315$

Maximum: $328$ at $(5.6, 7.2)$ . (Matches the objective-line method.)

Advantages. Foolproof; no slope-tracking; works for ANY feasible region.

Disadvantages. Slower when there are many vertices. Risks of arithmetic error.

Edexcel guidance. Either method is accepted. The objective-line method is often faster; vertex testing is more reliable for arithmetic-heavy problems.

Special case: degenerate vertices. If three or more boundary lines meet at the same point, the vertex is 'degenerate'. Edexcel D1 rarely tests this directly.

Only need to check VERTICES (Fundamental theorem of LP).
Evaluate objective at each.
Best value is the optimum.
Slower but foolproof.

Integer linear programming

LP optimum is a bound; test integer points nearby.

Many real LP problems have integer-valued variables — number of products, employees, vehicles, etc. The LP relaxation (dropping integrality) gives a value at a (typically non-integer) vertex; the integer optimum is usually nearby BUT NOT ALWAYS the closest integer point.

Method.

Solve the LP relaxation; find the LP optimum vertex.
List INTEGER POINTS near that vertex (e.g. floor/ceil of each coordinate, neighbours).
Check each integer point for feasibility against ALL constraints.
Evaluate the objective at each feasible integer point.
The best integer point is the integer LP optimum.

Bounding. The LP optimum is an UPPER BOUND for an integer maximisation (the integer best can be no higher). For minimisation it's a LOWER BOUND.

Worked example.

LP optimum: $(5.6, 7.2)$ , $P = 328$ . Now demand $x, y \in \mathbb{Z}$ subject to $2x + 4y \le 40$ , $3x + y \le 24$ , $x \ge 3$ , $y \ge 0$ .

Integer candidates near $(5.6, 7.2)$ :

$(x, y)$	Feasible?	$P = 20x + 30y$
$(5, 7)$	$2(5)+4(7)=38 \le 40$ ; $3(5)+7=22 \le 24$ ; $x \ge 3$ — YES	$310$
$(5, 8)$	$2(5)+4(8)=42 > 40$ — NO	—
$(6, 6)$	$36 \le 40$ , $24 \le 24$ — YES	$300$
$(6, 7)$	$40 \le 40$ , $25 > 24$ — NO	—
$(4, 8)$	$40 \le 40$ , $20 \le 24$ — YES	$320$
$(3, 8)$	$38 \le 40$ , $17 \le 24$ — YES	$300$
$(4, 7)$	$36 \le 40$ , $19 \le 24$ — YES	$290$

Best integer point: $(4, 8)$ with $P = 320$ . The LP optimum $328$ is an upper bound; the integer optimum is at most $328$ . Found integer optimum $320$ .

Surprising lesson. $(4, 8)$ is not the integer point nearest to $(5.6, 7.2)$ — that would be $(6, 7)$ , which is infeasible! Always check feasibility AND objective for several candidates.

When does the LP optimum equal the integer optimum? When the LP optimum already has integer coordinates. Otherwise, integer LP value is STRICTLY worse than the LP value.

LP optimum is an upper bound (max) or lower bound (min).
Test integer points near the LP optimum.
Check feasibility AGAINST ALL constraints.
The integer-best may not be the closest integer point.

How it’s examined

Linear Programming is a $12$ - $15$ -mark question on every WDM01/01 paper. Standard format: (a) formulate the LP from a worded problem ( $4$ - $5$ marks) — variables, objective, constraints, non-negativity; (b) graph the feasible region with all constraints and label vertices ( $4$ - $5$ marks); (c) find the optimum by objective-line OR vertex method ( $3$ - $4$ marks); (d) if applicable, identify the integer-valued optimum ( $2$ - $3$ marks). Marks lost: missing variable definitions (B1), missing non-negativity (B1), wrong shading convention, sliding in the wrong direction, naive integer rounding. Always state the OBJECTIVE-LINE VALUE chosen and the final answer in CONTEXT (e.g. 'produce 5.6 of $X$ and 7.2 of $Y$ for max profit $\$ 328$').

Sources: Pearson Edexcel International Advanced Level Mathematics specification (2018 — current for 2026 onwards); Edexcel IAL Mathematical Formulae and Statistical Tables (2018); WDM01/01 Examiner Reports — January 2023, June 2023, January 2024, June 2024. Last reviewed 2026-05-12.

Master this Topic

Worked examples, formulae, definitions and the mistakes examiners flag — everything you need to push from a pass to an A*.

Take this whole topic with you

Download a branded revision sheet — worked examples, formulae, definitions and common mistakes for Linear programming , ready to print or save as PDF.

Step-by-step worked examples — Linear programming

Step-by-step solutions to past-paper-style questions on linear programming , written exactly the way a tutor would explain them at the board.

1Formulate a linear programming problem (5 marks, D1)
Core• Adapted from WDM01/01 January 2024 Q8(a)• formulation, objective, constraints
Question
A factory makes two products, $X$ and $Y$ , on a single machine. Each $X$ takes $2$ hours of machine time and $3$ units of material; each $Y$ takes $4$ hours and $1$ unit of material. The machine is available for $\le 40$ hours per week; material supply is $\le 24$ units per week. The contract requires AT LEAST $3$ units of $X$ to be made. Profit is $\$ 20 $per$ X $and$ $30 $per$ Y $. Formulate the LP problem in terms of$ x $= number of$ X $,$ y $= number of$ Y$.
Step-by-step solution
1. Step 1
  Define variables. $x$ = number of product $X$ made per week. $y$ = number of product $Y$ made per week. Both are NON-NEGATIVE and (for context) INTEGER.
2. Step 2
  Objective function. Profit per week $P = 20x + 30y$ . We want to MAXIMISE $P$ .
3. Step 3
  Machine-time constraint. $2x$ (for $X$ ) $+ 4y$ (for $Y$ ) $\le 40$ .
4. Step 4
  Material constraint. $3x + y \le 24$ .
5. Step 5
  Contract constraint. $x \ge 3$ .
6. Step 6
  Non-negativity. $y \ge 0$ (implicit for production). Also $x \ge 3 > 0$ so $x \ge 0$ is automatic.
Answer
Maximise $P = 20x + 30y$ subject to $2x + 4y \le 40$ , $3x + y \le 24$ , $x \ge 3$ , $y \ge 0$ (and integer for a realistic problem).
Examiner tip
B1 define variables clearly. B1 objective function with correct coefficients. M1 set up all inequality signs. A1 each constraint correctly transcribed. A1 non-negativity. Edexcel mark schemes deduct for missing $\ge 0$ constraints or wrong inequality directions. ALWAYS define $x$ and $y$ in words before writing equations.
2Graph the feasible region (5 marks, D1)
Extended• Adapted from WDM01/01 January 2024 Q8(b)• feasible region, graph
Question
Graph the feasible region for the LP problem: maximise $P = 20x + 30y$ subject to $2x + 4y \le 40$ , $3x + y \le 24$ , $x \ge 3$ , $y \ge 0$ . State the vertices of the feasible region.
Step-by-step solution
1. Step 1
  Draw each boundary line.
  
  $2x + 4y = 40 \Rightarrow x + 2y = 20$ ⇒ intercepts $(20, 0)$ and $(0, 10)$ .
  
  $3x + y = 24$ ⇒ intercepts $(8, 0)$ and $(0, 24)$ .
  
  $x = 3$ ⇒ vertical line.
  
  $y = 0$ ⇒ horizontal $x$ -axis.
2. Step 2
  Identify the feasible side. Test the origin where possible.
  
  $2(0) + 4(0) = 0 \le 40$ ✓ — origin is on the feasible side; shade the OTHER side (above the line) as infeasible.
  
  $3(0) + 0 = 0 \le 24$ ✓ — origin feasible; shade infeasible (right).
  
  $x = 3$ : origin has $x = 0 < 3$ — origin infeasible; shade LEFT of $x = 3$ as infeasible.
  
  $y \ge 0$ : shade below the $x$ -axis as infeasible.
3. Step 3
  Compute vertex intersections.
  
  $(x = 3) \cap (y = 0)$ : $(3, 0)$ . Check: $2(3)+0=6 \le 40$ ✓, $3(3)+0=9 \le 24$ ✓. FEASIBLE.
  
  $(3x+y=24) \cap (y=0)$ : $(8, 0)$ . Check: $2(8)+0=16 \le 40$ ✓. FEASIBLE.
  
  $(3x+y=24) \cap (2x+4y=40)$ : solve. From $y = 24 - 3x$ into $2x + 4(24-3x) = 40$ : $2x + 96 - 12x = 40 \Rightarrow -10x = -56 \Rightarrow x = 5.6$ . Then $y = 24 - 3(5.6) = 24 - 16.8 = 7.2$ . Vertex $(5.6, 7.2)$ .
  
  $(2x+4y=40) \cap (x=3)$ : $2(3)+4y=40 \Rightarrow 4y = 34 \Rightarrow y = 8.5$ . Vertex $(3, 8.5)$ .
4. Step 4
  Final vertices (going around the boundary). $(3, 0), (8, 0), (5.6, 7.2), (3, 8.5)$ .
Answer
Feasible region is a quadrilateral with vertices $(3, 0), (8, 0), (5.6, 7.2), (3, 8.5)$ .
Examiner tip
B1 each boundary line correctly drawn with intercepts. B1 correct shading (infeasible side). M1 solving any two boundary lines simultaneously. A1 each vertex. Edexcel mark schemes are strict about labelling axes ( $x$ and $y$ with units and ranges) and indicating the feasible region clearly. Always SHADE the infeasible side (Edexcel convention) — feasible region remains unshaded.
3Objective line / ruler method (5 marks, D1)
Extended• Adapted from WDM01/01 January 2024 Q8(c)• objective line, ruler method
Question
Using the feasible region from the previous example (vertices $(3, 0), (8, 0), (5.6, 7.2), (3, 8.5)$ ), find the maximum of $P = 20x + 30y$ by drawing an objective line and sliding it outward.
Step-by-step solution
1. Step 1
  Draw an objective line at a convenient value. Pick $P = 60$ : $20x + 30y = 60$ ⇒ intercepts $(3, 0)$ and $(0, 2)$ . (Or $P = 120$ for a more visible line.)
  
  The slope of any objective line is $-20/30 = -2/3$ .
2. Step 2
  Slide the line OUTWARD (away from the origin, since we are maximising) parallel to itself. The LAST point at which the line still touches the feasible region is the optimum.
3. Step 3
  Visualise the candidates. The slope $-2/3$ is between the slope of $2x+4y=40$ ( $-1/2$ ) and the slope of $3x+y=24$ ( $-3$ ). So the optimum is at the vertex where these two lines meet: $(5.6, 7.2)$ .
4. Step 4
  Compute the optimum value. $P = 20(5.6) + 30(7.2) = 112 + 216 = 328$ .
Answer
Optimum at $(x, y) = (5.6, 7.2)$ with $P = 328$ .
Examiner tip
B1 draw objective line at a stated value. M1 indicate the direction of slide (outward for max). A1 identify the vertex. A1 substitute into $P$ . A1 final value $328$ . Edexcel requires you to STATE the objective-line value used (e.g. 'I drew $P = 120$ '). Without that, the M mark may be withheld.

4Vertex testing (4 marks, D1)

Core• Adapted from WDM01/01 June 2024 Q9• vertex testing, evaluation

Question

Using the same feasible region with vertices $(3, 0), (8, 0), (5.6, 7.2), (3, 8.5)$ , find the maximum of $P = 20x + 30y$ by evaluating at every vertex.

Step-by-step solution

Step 1

Evaluate $P$ at each vertex.

Vertex	$P = 20x + 30y$
$(3, 0)$	$20(3) + 30(0) = 60$
$(8, 0)$	$20(8) + 30(0) = 160$
$(5.6, 7.2)$	$20(5.6) + 30(7.2) = 112 + 216 = 328$
$(3, 8.5)$	$20(3) + 30(8.5) = 60 + 255 = 315$

Step 2
Compare. Maximum is $P = 328$ at $(5.6, 7.2)$ .

Answer

Maximum $P = 328$ at $(x, y) = (5.6, 7.2)$ . (Matches the objective-line method.)

Examiner tip

B1 list all vertices. M1 evaluate the objective. A1 each correct evaluation. A1 identify the maximum. Vertex testing is foolproof but slower than the objective-line method; both give the same answer. Edexcel D1 papers accept either method.

5Integer-valued solution (5 marks, D1)
Challenge• Adapted from WDM01/01 January 2024 Q8(d)• integer LP, integer constraint
Question
If $x$ and $y$ must be INTEGERS (whole numbers of products), find the maximum of $P = 20x + 30y$ given the feasible region with vertices $(3, 0), (8, 0), (5.6, 7.2), (3, 8.5)$ .
Step-by-step solution
1. Step 1
  LP optimum (non-integer). From the previous example, LP max is at $(5.6, 7.2)$ with $P = 328$ . Neither coordinate is integer — need to look at integer points NEAR this.
2. Step 2
  Integer points near $(5.6, 7.2)$ . Candidates: $(5, 7), (5, 8), (6, 6), (6, 7)$ . Check feasibility for each:
  
  $(5, 7)$ : $2(5)+4(7) = 10+28 = 38 \le 40$ ✓, $3(5)+7 = 22 \le 24$ ✓, $x=5 \ge 3$ ✓, $y=7 \ge 0$ ✓. Feasible.
  
  $(5, 8)$ : $2(5)+4(8) = 10+32 = 42 > 40$ ✗. INFEASIBLE.
  
  $(6, 6)$ : $2(6)+4(6) = 12+24 = 36 \le 40$ ✓, $3(6)+6 = 24 \le 24$ ✓. Feasible.
  
  $(6, 7)$ : $2(6)+4(7) = 12+28 = 40 \le 40$ ✓, $3(6)+7 = 25 > 24$ ✗. INFEASIBLE.
3. Step 3
  Evaluate feasible integer candidates.
  
  $(5, 7)$ : $P = 20(5) + 30(7) = 100 + 210 = 310$ .
  
  $(6, 6)$ : $P = 20(6) + 30(6) = 120 + 180 = 300$ .
4. Step 4
  Also check additional candidates. $(5, 6)$ : $2(5)+4(6) = 34 \le 40$ ✓, $3(5)+6 = 21 \le 24$ ✓. $P = 100 + 180 = 280$ . Smaller.
  
  $(4, 7)$ : $2(4)+4(7) = 36 \le 40$ ✓, $3(4)+7 = 19 \le 24$ ✓. $P = 80 + 210 = 290$ . Smaller.
  
  $(4, 8)$ : $2(4)+4(8) = 40 \le 40$ ✓, $3(4)+8 = 20 \le 24$ ✓. $P = 80 + 240 = 320$ . LARGER!
  
  $(3, 8)$ (vertex-adjacent): $2(3)+4(8) = 38 \le 40$ ✓, $3(3)+8 = 17 \le 24$ ✓. $P = 60 + 240 = 300$ .
5. Step 5
  Final. Best integer solution: $(4, 8)$ with $P = 320$ . Worth less than the LP optimum of $328$ (the price of rounding).
Answer
Best integer point: $(x, y) = (4, 8)$ with $P = 320$ . (Lower than the LP optimum of $328$ because $(5.6, 7.2)$ is not integer.)
Examiner tip
B1 LP optimum recalled. M1 list integer candidates near the LP optimum. A1 feasibility checks. A1 evaluate $P$ at feasible integer points. A1 final answer. Integer LP can be SURPRISING — the best integer point is not always the one closest to the LP optimum. Edexcel often asks 'why is the integer answer lower?' — because the LP relaxation gives an UPPER BOUND.
6Minimisation LP problem (6 marks, D1)
Extended• Adapted from WDM01/01 June 2024 Q9• minimisation, objective line
Question
A dietician requires a meal to contain AT LEAST $30$ g protein and AT LEAST $24$ g fibre. Food $A$ provides $3$ g protein and $4$ g fibre per portion; food $B$ provides $5$ g protein and $2$ g fibre per portion. $A$ costs $\$ 0.40 $per portion,$ B $costs$ $0.30$ per portion. Minimise total cost. Formulate and solve.
Step-by-step solution
1. Step 1
  Formulate. Let $a$ = portions of food $A$ , $b$ = portions of food $B$ . Constraints: $3a + 5b \ge 30$ (protein), $4a + 2b \ge 24$ (fibre), $a \ge 0$ , $b \ge 0$ . Minimise $C = 0.4a + 0.3b$ .
2. Step 2
  Graph the feasible region. Lines $3a + 5b = 30$ (intercepts $(10, 0)$ and $(0, 6)$ ); $4a + 2b = 24$ (intercepts $(6, 0)$ and $(0, 12)$ ).
  
  Feasibility: this time the inequalities are $\ge$ , so the feasible side is AWAY from the origin (origin gives $0 < 30, 0 < 24$ — infeasible).
3. Step 3
  Vertices of the feasible region.
  
  $(10, 0)$ on $3a + 5b = 30$ AND $b = 0$ . Check fibre: $4(10) + 0 = 40 \ge 24$ ✓. Feasible.
  
  $(0, 12)$ on $4a + 2b = 24$ AND $a = 0$ . Check protein: $0 + 60 = 60 \ge 30$ ✓. Feasible.
  
  $(3a + 5b = 30) \cap (4a + 2b = 24)$ : solve. $b = (30 - 3a)/5$ . Substitute: $4a + 2(30-3a)/5 = 24 \Rightarrow 20a + 2(30-3a) = 120 \Rightarrow 20a + 60 - 6a = 120 \Rightarrow 14a = 60 \Rightarrow a = 30/7 \approx 4.286$ . Then $b = (30 - 3 \cdot 30/7)/5 = (30 - 90/7)/5 = (210/7 - 90/7)/5 = (120/7)/5 = 24/7 \approx 3.429$ .
4. Step 4
  Evaluate $C$ at each vertex.
  
  $(10, 0)$ : $C = 0.4(10) + 0.3(0) = 4.00$ .
  
  $(30/7, 24/7)$ : $C = 0.4(30/7) + 0.3(24/7) = 12/7 + 7.2/7 = 19.2/7 \approx 2.74$ .
  
  $(0, 12)$ : $C = 0.4(0) + 0.3(12) = 3.60$ .
5. Step 5
  Minimum cost. $C_{\min} = 19.2/7 \approx \$ 2.74 $at$ (a, b) = (30/7, 24/7) $or roughly$ (4.29, 3.43)$ portions.
Answer
Minimum cost $\approx \$ 2.74 $at$ a = 30/7 \approx 4.29 $portions of$ A $and$ b = 24/7 \approx 3.43 $portions of$ B$.
Examiner tip
B1 formulation correct. B1 feasible region drawn (correctly identifying the away-from-origin side). M1 find intersection. A1 each vertex evaluation. A1 minimum stated. For minimisation, SLIDE the objective line INWARD toward the origin until it just leaves the feasible region. The 'feasible region' for $\ge$ constraints is unbounded above — without an upper bound, only minimisation makes sense.

Key Formulae — Linear programming

The formulae you need to memorise for linear programming on the Pearson Edexcel IAL XMA01 / YMA01 paper, with every variable defined in plain English and a note on when to use it.

Two-variable LP standard form
$\text{Optimise } P = ax + by \;\text{subject to } a_{i}x + b_{i}y \le c_{i},\; x, y \ge 0$
$x, y$
decision variables
$a, b$
objective coefficients
$a_{i}, b_{i}, c_{i}$
constraint coefficients
When to use
Any 2-variable LP. Maximise or minimise a linear $P$ over a polygonal feasible region. NOT in the IAL formula booklet — definitional.
Example
Maximise $P = 20x + 30y$ subject to $2x + 4y \le 40$ , $3x + y \le 24$ , $x \ge 3$ , $y \ge 0$ .
Slope of the objective line
$P = ax + by \;\Rightarrow\; \text{slope} = -\dfrac{a}{b}$
$a, b$
objective coefficients
When to use
Drawing the objective line for the ruler method. NOT in the IAL formula booklet.
Example
$P = 20x + 30y$ : slope $= -20/30 = -2/3$ .
Fundamental theorem of LP
$\text{Optimal value of a feasible bounded LP is attained at a VERTEX of the feasible region}$
$\text{vertex}$
corner of the feasible region polygon
When to use
Justifies vertex testing: only need to check the corners, not interior points. NOT in the IAL formula booklet but assumed.
Example
Feasible region with $4$ vertices: just evaluate $P$ at each and take the best.

Key Definitions and Keywords — Linear programming

Definitions to memorise and the exact keywords mark schemes credit for linear programming answers — sharpened from recent examiner reports for the 2026 Pearson Edexcel IAL XMA01 / YMA01 sitting.

Decision variable
Examiner keyword
An unknown quantity that the decision-maker controls. Typically $x, y$ (or $a, b$ etc.) representing quantities to produce, hours to work, etc.
Objective function
Examiner keyword
A LINEAR function of the decision variables to be maximised (e.g. profit) or minimised (e.g. cost). Form $P = ax + by$ for two variables.
Constraint
Examiner keyword
A LINEAR inequality that the decision variables must satisfy. Common types: resource ( $\le$ ), requirement ( $\ge$ ), non-negativity ( $\ge 0$ ), bound (equality).
Feasible region
Examiner keyword
The set of all $(x, y)$ satisfying every constraint. A CONVEX polygon (possibly unbounded). Solutions exist only in this region.
Objective line (ruler method)
Examiner keyword
A line of constant objective value $P = c$ . Drawn for some convenient $c$ , then SLID parallel to itself in the increasing- $P$ direction (for max) or decreasing- $P$ direction (for min). The optimum is the last vertex of the feasible region the line touches.
Vertex method
Examiner keyword
Compute every vertex of the feasible region and evaluate the objective at each; the best is the LP optimum. Foolproof when the region is bounded; more tedious than the objective-line method.
Integer linear programming (ILP)
Examiner keyword
LP with the additional restriction that $x, y$ must be INTEGER. Solved by computing the LP optimum, then testing integer points near it. NP-hard in general; D1 handles only small cases.

Common Mistakes and Misconceptions — Linear programming

The traps other students keep falling into on linear programming questions — taken from recent Pearson Edexcel IAL XMA01 / YMA01 examiner reports and mark schemes — and how to avoid them.

✕Forgetting non-negativity constraints $x \ge 0, y \ge 0$
WDM01/01 Examiner Reports — flagged every session
Why it happens
They seem obvious.
How to avoid it
ALWAYS write them explicitly. Edexcel mark schemes award a B1 specifically for non-negativity. Even if the question implies $x, y \ge 0$ , include them in your formulation.
✕Shading the FEASIBLE side instead of the infeasible side
Why it happens
Confusing convention.
How to avoid it
Edexcel convention: SHADE the INFEASIBLE side; leave the feasible region clear. State this convention on your graph: 'unshaded region = feasible'.
✕Sliding the objective line in the wrong direction (inward for max or outward for min)
Why it happens
Confusing the role of the gradient.
How to avoid it
MAXIMISE = slide AWAY from origin (assuming all positive coefficients). MINIMISE = slide TOWARD origin. Always sketch the gradient direction (perpendicular to the objective line).
✕For an INTEGER LP, taking the integer point CLOSEST to the LP optimum as the answer
Why it happens
Naive rounding.
How to avoid it
The closest integer point may be INFEASIBLE or sub-optimal. Test SEVERAL integer points near the LP optimum AND near each binding constraint.
✕Writing $\ge$ when the constraint is $\le$ (or vice versa)
Why it happens
Misreading 'at most' vs 'at least'.
How to avoid it
'Available', 'budget', 'capacity' → $\le$ . 'Minimum requirement', 'demand', 'at least' → $\ge$ . Write each constraint in words first, then translate.
✕Writing the LP without DEFINING $x$ and $y$
Why it happens
Rushing into algebra.
How to avoid it
ALWAYS begin: 'Let $x$ = ... and $y$ = ...'. Edexcel awards a B1 specifically for variable definitions. Without them, marks for the rest of the formulation can be withheld.

Past paper style quiz

Get a report showing which sub-topics you've nailed and which ones still need work.

Linear programming — frequently asked questions

The things students keep getting wrong in this sub-topic, answered.

Linear programming

Detailed Notes

What you’ll learn

How it’s examined

1Formulate a linear programming problem (5 marks, D1)

2Graph the feasible region (5 marks, D1)

3Objective line / ruler method (5 marks, D1)

4Vertex testing (4 marks, D1)

5Integer-valued solution (5 marks, D1)

6Minimisation LP problem (6 marks, D1)

Two-variable LP standard form

Slope of the objective line

Fundamental theorem of LP

Decision variable

Objective function

Constraint

Feasible region

Objective line (ruler method)

Vertex method

Integer linear programming (ILP)

✕Forgetting non-negativity constraints x≥0,y≥0x \ge 0, y \ge 0x≥0,y≥0

✕Shading the FEASIBLE side instead of the infeasible side

✕Sliding the objective line in the wrong direction (inward for max or outward for min)

✕For an INTEGER LP, taking the integer point CLOSEST to the LP optimum as the answer

✕Writing ≥\ge≥ when the constraint is ≤\le≤ (or vice versa)

✕Writing the LP without DEFINING xxx and yyy

Past paper style quiz

Linear programming — frequently asked questions

✕Forgetting non-negativity constraints $x \ge 0, y \ge 0$

✕Writing $\ge$ when the constraint is $\le$ (or vice versa)

✕Writing the LP without DEFINING $x$ and $y$