Contents · 0% complete

Learning objectives
Core idea
Key formulae
Worked examples
Explore the graph
Common mistakes
Exam tip
Guided practice
Practice questions
Challenge
Summary
Quick quiz
Same topic, different board
Past paper questions

Learn7367Paper 3 · Discrete optionLinear programmingFormulating and solving linear programmes

Linear programming · Subtopic 1 of 1

Linear Programming

Choose decision variables, write linear constraints and a linear objective. The feasible region is a polygon, and the optimum lies at a vertex: slide the objective line across, or test every vertex. The simplex method does the vertex-hopping algebraically, using slack variables and pivots.

Edexcel YMA01 WDM11Edexcel 9FM0 OptionAQA 7367 Paper 3≈ 50 minRevision 1 · updated 2026-10-27

Practise this topicTimed test Ask Salam TutorSwitch board

Section 1 of 14

Learning objectives

Formulate a linear programme from words.
Solve graphically with the objective line or vertex method.
Find integer solutions.
Set up and apply the simplex tableau.

Pause and think

A baker has 4 kg of flour and 6 kg of sugar. Why must the best plan use up at least one of them completely?

Section 2 of 14

Core idea

Start hereThe best mix

A workshop makes chairs and tables, with limited timber and labour. What mix earns the most? Each limit is a straight-line boundary; together they fence in the possible plans, and the best plan sits in a corner.

The big idea

Formulate: decision variables, linear constraints, linear objective. The feasible region is a convex polygon and the optimum occurs at a vertex, found by sliding the objective line or testing vertices; simplex automates vertex-hopping.

1. Graphical method

Worked exampleVertex testing

Maximise $P=2x+3y$ subject to $x+y\le4$ , $x+3y\le6$ , $x,y\ge0$ .

Goal: $P_{\max}$ .
Strategy: Find vertices, evaluate $P$ .

$(0,0),(4,0),(0,2)$
Axis intercepts of the binding constraints.
$x+y=4,\ x+3y=6\Rightarrow(3,1)$
Subtract: $2y=2$ .
$P=0,\ 8,\ 6,\ 9$
Evaluate at each vertex.

Answer

P_{\max}=9

(3,1)

✓ Check

(3,1)

satisfies both constraints with equality ✓.

Why the optimum is at a vertex

$2x+3y=k$
Lines of constant $P$ are parallel.
$k\uparrow\Rightarrow\text{line moves outward}$
Larger $P$ further from the origin.
$\text{last contact with a convex polygon is a vertex (or an edge)}$
A straight line leaves a convex region at a corner.

2. Simplex

x+y+s_1=4,\quad x+3y+s_2=6,\quad P-2x-3y=0

$s_1,s_2$: slack variables (unused resource).

Worked exampleChoosing the first pivot

Set up the tableau and choose the pivot.

Goal: Pivot element.
Strategy: Most negative in the objective row; smallest positive ratio.

$\text{objective row: }-2,-3$
$y$ column is most negative.
$\text{ratios: }4/1=4,\ 6/3=2$
Value ÷ $y$ coefficient.
$\text{pivot: }3\text{ in row }s_2$
Smallest ratio.

AnswerPivot on the

3

;

y

enters,

s_2

leaves.

✓ CheckAfter pivoting,

y=2

P=6

: the vertex

(0,2)

✓.

LP workflow

Drawing diagram…

From words to an answer.

Common misconceptionInteger answers If variables must be whole numbers, test integer points near the optimum that lie inside the region.

Key takeawayOptimal tableau Stop when no negative values remain in the objective row.

Pause and think

If the objective were $P=x+y$ , which points are optimal?

Summary

Formulate carefully.
Optimum at a vertex.
Simplex: pivot until objective row $\ge0$ .

Feasible region: Points satisfying every constraint.
Objective function: Quantity to maximise or minimise.
Slack variable: Amount of a resource left unused.

HistoryDantzig. George Dantzig invented the simplex method in 1947 for US Air Force planning. As a student he once solved two famous unsolved problems, thinking they were homework.

Fun factAirlines. Airlines solve linear programmes with millions of variables to assign crews to flights every month.

Section 3 of 14

Key formulae

General form

\text{maximise }P=c_1x+c_2y\ \text{subject to }a_ix+b_iy\le k_i,\ x,y\ge0

Objective line

c_1x+c_2y=\text{const}:\ \text{gradient }-\tfrac{c_1}{c_2}

Slack variables

a x+b y\le k\ \to\ a x+b y+s=k,\ s\ge0

TrickVertex method. Find every vertex of the feasible region (solve pairs of boundary equations) and evaluate

P

at each. The best value wins.

Section 4 of 14

Worked examples

Example 1 · Graphical0 / 3 steps

Maximise

P=2x+3y

subject to

x+y\le4

x+3y\le6

x,y\ge0

Example 2 · Formulating0 / 2 steps

Chairs use 2 h, tables 3 h of labour; 60 h available. Profit £20, £35. Write the labour constraint and objective.

Section 5 of 14

Explore the graph

Feasible region and objective line

Loading the interactive graph…

Try this

The darkest overlap is the feasible region. The line is $2x+3y=k$ .
Increase $k$ : the last feasible point the line touches is $(3,1)$ , with $k=9$ .

Slide the objective line outward.

In the real worldDiet problem. One of the first LPs (Stigler, 1945) found the cheapest diet meeting nutritional needs; it included lots of cabbage and beans.

Section 6 of 14

Common mistakes

IncorrectForgetting

x,y\ge0

CorrectInclude non-negativity

You can't make negative chairs.

IncorrectRounding the optimum to integers

CorrectCheck nearby integer points in the region

Rounding may leave the region or miss the best.

IncorrectShading the wrong side

CorrectTest a point like

(0,0)

Be consistent: shade unwanted or wanted as instructed.

Infinite options in the region

Optimum: I'm in the corner, obviously.

Section 7 of 14

Exam tip

Exam tipDefine variables in words. "Let

x

be the number of chairs made per week": method marks require clear definitions.

Section 8 of 14

Guided practice

SA-DM-LP-G012 marksL2 StandardNon-calculatorGraphical

Find the

x

-coordinate where

x+y=4

meets

x+3y=6

Salam Academy Original Practice · Proposed mark scheme

Section 9 of 14

Practice questions

SA-DM-LP-0012 marksL2 StandardNon-calculatorGraphical

Maximise

P=2x+3y

subject to

x+y\le4

x+3y\le6

x,y\ge0

. Find the maximum value of

P

Salam Academy Original Practice · Proposed mark scheme

SA-DM-LP-0021 markL1 FoundationNon-calculatorSimplex

How many slack variables are needed to put the constraints

x+y\le4

x+3y\le6

into simplex form?

Salam Academy Original Practice · Proposed mark scheme

SA-DM-LP-0032 marksL2 StandardNon-calculatorFormulating

Chairs need 2 h and tables 3 h of labour; 60 h are available. What is the largest number of tables that could be made?

Salam Academy Original Practice · Proposed mark scheme

More questions on every skill in this subtopic are in the question bank under Practise.

Section 10 of 14

Challenge

SA-DM-LP-0042 marksL3 ExamNon-calculatorGraphical

For the region

x+y\le4

x+3y\le6

x,y\ge0

, the objective is changed to

P=x+ky

. Find the largest

k

for which

(4,0)

is still optimal.

Salam Academy Original Practice · Proposed mark scheme

Section 11 of 14

Summary

Variables, constraints, objective.
Optimum at a vertex.
Objective line or vertex method.
Simplex: slack variables and pivots.

Section 12 of 14

Quick quiz

Q1 · SA-DM-LP-Q011 markL1 FoundationNon-calculatorGraphical

In a linear programme with a bounded feasible region, the optimum always occurs

Salam Academy Original Practice · Proposed mark scheme

Section 13 of 14

Same topic, different board

Specification: 7367 A-level Further Mathematics
Where: Discrete · Linear programming
Expected: Formulation; graphical solution; simplex method for maximising with ≤ constraints.
Calculator: Permitted on all papers.
Typical style: AQA mixes short multiple-choice questions with longer structured ones.
Open in: 7367 · Paper 3

Section 14 of 14

Past paper questions

No past paper questions are tagged to this subtopic yet. We add papers every week.

Browse past papers

Salam Academy original content · Content status: reviewed and published. Syllabus mapping: AQA 7367, First teaching 2017 (official specification).