Constrained Optimisation Revision Notes for AQA A-Level Further Maths

Constrained Optimisation

Introduction to linear programming

Linear programming consists of mathematical methods used to make optimal decisions in various industrial and economic contexts. The goal is to determine the best combination of quantities (variables) to achieve the most favourable outcome. This typically involves maximising profit or minimising cost whilst working within certain limitations.

infoNote

Linear programming is particularly powerful because it provides a systematic approach to decision-making problems where you need to allocate limited resources efficiently. Common applications include production planning, resource allocation, transportation logistics, and financial portfolio management.

Linear programming formulation

To convert a real-world problem into mathematical language, you must create a linear programming (LP) formulation. This involves three key components—remember them with the mnemonic "DeCO": Decision variables, Constraints, and Objective function.

Decision variables (control variables)

Definition: The quantities that you can vary in the problem.

These are typically denoted by letters such as $x$ , $y$ , or $z$ . For instance, if a manufacturer produces two types of product, you might let $x$ represent the quantity of the first product and $y$ represent the quantity of the second product.

Constraints

Definition: The limitations or restrictions on the values that the decision variables can take.

Constraints are expressed as inequalities. They reflect practical limits such as:

Available resources (raw materials, labour hours, machine time)
Market restrictions (maximum sales capacity)
Production requirements (minimum quantities needed)
Physical limitations (non-negative quantities)

chatImportant

There are typically non-negativity constraints which state that $x \geq 0$ , $y \geq 0$ , etc., because negative quantities usually make no practical sense. These appear in virtually every LP problem unless explicitly stated otherwise.

Objective function

Definition: The quantity to be optimised, which is either maximised or minimised.

The objective function is commonly denoted by $P$ (for profit in maximisation problems) or $C$ (for cost in minimisation problems). It is expressed as a linear combination of the decision variables, such as:

$P = ax + by$

where $a$ and $b$ are coefficients representing contribution per unit.

The graphical method

When an LP problem has only two decision variables, you can solve it using the graphical method. This visual approach involves several key steps.

Drawing constraint lines

First, represent each constraint as a line on a coordinate plane:

Convert each inequality to an equation by replacing the inequality symbol with an equals sign
Find two points on the line (often by setting $x = 0$ then $y = 0$ )
Draw the line through these points
Determine which side of the line satisfies the inequality

chatImportant

Important convention for boundary lines:

For strict inequalities ( $<$ or $>$ ), draw the boundary line dotted
For non-strict inequalities ( $\leq$ or $\geq$ ), draw the boundary line solid (continuous)

Remember: "Less-or-equal solid, less than dotted"

Shade out the regions that do not satisfy each constraint. This process is called shading out. Use the mnemonic "SHADE OUT": Shade the regions that do NOT satisfy constraints.

Identifying the feasible region

Definition: The feasible region is the set of all points $(x, y)$ that satisfy all the constraints simultaneously.

On your graph, this is the unshaded region where all constraints overlap. It forms a polygon (possibly unbounded) whose corners are called vertices. All allowable combinations of the decision variables lie within this region, including its boundary lines.

Using the objective line

Definition: The objective line is a line connecting all points $(x, y)$ for which the objective function has a specified value.

To use the objective line:

Choose any convenient value for the objective function (e.g., $P = 1000$ )
Draw the corresponding line on your graph
All points on this line give the same value of the objective function

infoNote

Direction of movement—"Max moves right, Min moves left":

For a maximisation problem, profit increases as the objective line moves away from the origin (maintaining the same gradient)
For a minimisation problem, cost decreases as the objective line moves toward the origin

Finding the optimal solution

chatImportant

Key principle—"Vertex Victory": The optimal solution occurs at a vertex (corner point) of the feasible region.

To find the optimal value:

Identify the vertices of the feasible region
Calculate the objective function value at each vertex
Select the vertex giving the best value (maximum for maximisation, minimum for minimisation)

Alternatively, imagine sliding the objective line parallel to itself across the graph:

For maximisation: Move it away from the origin until it's about to leave the feasible region
For minimisation: Move it toward the origin until it first touches the feasible region

The last point of contact (for maximisation) or first point of contact (for minimisation) identifies the optimal vertex.

infoNote

Special case: If the objective line is parallel to a boundary of the feasible region, then all points along that boundary segment give the optimal value. In this case, you have multiple optimal solutions.

Worked examples

lightbulbExample

Worked Example 1: Maximising Profit (Muesli Production)

Problem: A manufacturer produces two types of muesli: Standard and De Luxe.

Product	Oat mix (kg)	Fruit mix (kg)	Max sales (kg)	Profit (£ per kg)
Standard	0.8	0.2	3500	0.60
De Luxe	0.6	0.4	2000	0.80
Availability	3000	1000

Determine how much of each type to produce to maximise profit.

Step 1: Define decision variables

Let $x$ = kg of Standard muesli produced
Let $y$ = kg of De Luxe muesli produced

Step 2: Formulate constraints

Upper limits on sales:

$x \leq 3500$
$y \leq 2000$

Oat mix constraint:

Standard uses 0.8 kg per kg, De Luxe uses 0.6 kg per kg
Total available: 3000 kg
$0.8x + 0.6y \leq 3000$

Simplifying by dividing by 0.2: $4x + 3y \leq 15000$

Fruit mix constraint:

Standard uses 0.2 kg per kg, De Luxe uses 0.4 kg per kg
Total available: 1000 kg
$0.2x + 0.4y \leq 1000$

Simplifying by dividing by 0.2: $x + 2y \leq 5000$

Non-negativity: $x \geq 0, y \geq 0$

Step 3: Formulate objective function

Profit: $P = 0.6x + 0.8y$

Complete formulation:

Maximise $P = 0.6x + 0.8y$

Subject to:

$4x + 3y \leq 15000$
$x + 2y \leq 5000$
$x \leq 3500$
$y \leq 2000$
$x \geq 0, y \geq 0$

Step 4: Solve graphically

First, draw the constraints $x \leq 3500$ and $y \leq 2000$ as vertical and horizontal lines. Next, add the constraint $4x + 3y \leq 15000$ . Finally, add $x + 2y \leq 5000$ to identify the complete feasible region.

The feasible region is shown as the unshaded area where all constraints are satisfied.

Step 5: Find the optimal solution

Draw a sample objective line, say $P = 1400$ :

This gives points like $(1000, 1000)$ , $(0, 1750)$ , or $(2000, 250)$

As $P$ increases, the objective line moves to the right. The maximum profit occurs at the last vertex the line touches before leaving the feasible region.

This occurs where the lines $x + 2y = 5000$ and $4x + 3y = 15000$ intersect.

Solving simultaneously:
From the first equation: $x = 5000 - 2y$

Substituting into the second: $4(5000 - 2y) + 3y = 15000$

20000 - 8y + 3y = 15000

-5y = -5000

y = 1000

Therefore $x = 5000 - 2(1000) = 3000$

At the point $(3000, 1000)$ : $P = 0.6 \times 3000 + 0.8 \times 1000 = 1800 + 800 = 2600$

Answer: The optimal production plan is 3000 kg of Standard muesli and 1000 kg of De Luxe muesli, giving a profit of £2600.

lightbulbExample

Worked Example 2: Minimising Cost (Paper Processing)

Problem: A paper recycler has two processing plants.

Plant	Waste paper (tonnes/hour)	Cardboard (tonnes/hour)	Cost (£/hour)
Plant A	4	1	400
Plant B	5	2	600
Requirement	100	35

There is a union agreement requiring each plant to operate for at least one third of the total run time. A consignment of 100 tonnes of waste paper and 35 tonnes of cardboard must be processed. Minimise the cost.

Step 1: Define decision variables

Let $x$ = hours for Plant A
Let $y$ = hours for Plant B

Step 2: Formulate constraints

Union agreement (each plant gets at least 1/3 of run time):

$x \geq \frac{1}{3}(x + y)$ , which simplifies to $y \leq 2x$
$y \geq \frac{1}{3}(x + y)$ , which simplifies to $x \leq 2y$

Waste paper requirement:

$4x + 5y \geq 100$

Cardboard requirement:

$x + 2y \geq 35$

Non-negativity: $x \geq 0, y \geq 0$

Step 3: Formulate objective function

Cost: $C = 400x + 600y$

Complete formulation:

Minimise $C = 400x + 600y$

Subject to:

$y \leq 2x$
$x \leq 2y$
$4x + 5y \geq 100$
$x + 2y \geq 35$
$x \geq 0, y \geq 0$

Step 4: Solve graphically

The feasible region is bounded by the constraint lines, forming a polygon where all constraints are satisfied.

Step 5: Find the optimal vertex

For a minimisation problem, move the objective line toward the origin (to the left, parallel to itself) until it reaches the last point still in the feasible region.

Testing the vertices:

At $y = 2x$ and $4x + 5y = 100$ :

Substituting: $4x + 5(2x) = 100$

$14x = 100$ , so $x = 7\frac{1}{7}$ , $y = 14\frac{2}{7}$

$C = 400 \times 7\frac{1}{7} + 600 \times 14\frac{2}{7} = 11428\frac{4}{7}$ (approximately £11428.57)

At $4x + 5y = 100$ and $x + 2y = 35$ :

From the second equation: $x = 35 - 2y$

Substituting: $4(35 - 2y) + 5y = 100$

140 - 8y + 5y = 100

-3y = -40

y = 13\frac{1}{3}

$x = 35 - 2(13\frac{1}{3}) = 8\frac{1}{3}$

$C = 400 \times 8\frac{1}{3} + 600 \times 13\frac{1}{3} = 11333\frac{1}{3}$ (approximately £11333.33)

At $x + 2y = 35$ and $x = 2y$ :

Substituting: $2y + 2y = 35$

$y = 8\frac{3}{4}$ , $x = 17\frac{1}{2}$

$C = 400 \times 17\frac{1}{2} + 600 \times 8\frac{3}{4} = 12250$ (£12250)

Answer: The minimum cost is £11333.33, achieved by running Plant A for $8\frac{1}{3}$ hours and Plant B for $13\frac{1}{3}$ hours.

lightbulbExample

Worked Example 3: Integer Solutions (Chair Manufacturing)

Problem: A manufacturer makes three types of dining chair (A, B, and C). All chairs pass through cutting, assembly, and finishing workshops. Workshop hours available per week: cutting 50 hours, assembly 35 hours, finishing 40 hours.

Chair type	Cutting (hours)	Assembly (hours)	Finishing (hours)	Profit (£)
A	0.5	0.6	0.75	20
B	2	1	0.75	60
C	0.5	0.4	0.5	20

Given that half the chairs sold are type C, find the best production plan.

Step 1: Define decision variables

Let $x$ = number of type A chairs
Let $y$ = number of type B chairs
Let $z$ = number of type C chairs

Step 2: Use the additional constraint

Given that half the chairs sold are type C: $z = \frac{1}{2}(x + y + z)$

This gives $z = x + y$

Substituting $z = x + y$ reduces the problem to two variables.

Step 3: Formulate constraints

Cutting time: $0.5x + 2y + 0.5z \leq 50$

With $z = x + y$ : $0.5x + 2y + 0.5(x + y) \leq 50$

Simplifying: $x + 2.5y \leq 50$ , or $2x + 5y \leq 100$

Assembly time: $0.6x + y + 0.4z \leq 35$

With $z = x + y$ : $0.6x + y + 0.4(x + y) \leq 35$

Simplifying: $x + 1.4y \leq 35$ , or $5x + 7y \leq 175$

Finishing time: $0.75x + 0.75y + 0.5z \leq 40$

With $z = x + y$ : $0.75x + 0.75y + 0.5(x + y) \leq 40$

Simplifying: $1.25x + 1.25y \leq 40$ , or $x + y \leq 32$

Non-negativity and integer constraints: $x \geq 0, y \geq 0$ , and $x, y$ are integers

Step 4: Formulate objective function

Profit: $P = 20x + 60y + 20z = 20x + 60y + 20(x + y) = 40x + 80y$

Complete formulation:

Maximise $P = 40x + 80y$

Subject to:

$2x + 5y \leq 100$
$5x + 7y \leq 175$
$x + y \leq 32$
$x \geq 0, y \geq 0$
$x, y$ are integers

Step 5: Solve graphically

The optimal solution typically occurs at the intersection of $2x + 5y = 100$ and $5x + 7y = 175$ .

Solving simultaneously gives $(15.9, 13.6)$ , but we need integers.

Testing integer points near this vertex:

At $(15, 14)$ : $P = 40(15) + 80(14) = 600 + 1120 = 1720$

At $(16, 13)$ : $P = 40(16) + 80(13) = 640 + 1040 = 1680$

Answer: The maximum profit of £1720 occurs at $x = 15$ , $y = 14$ , so $z = x + y = 29$ .
The best production plan is 15 type A chairs, 14 type B chairs, and 29 type C chairs.

infoNote

Integer solutions:

When solutions must be whole numbers, the optimal vertex from the continuous solution may give non-integer values. In this case, test integer points in the neighbourhood of the optimal vertex to find which gives the best objective function value.

lightbulbExample

Worked Example 4: Blending Problem (Vegetable Oil)

Problem: A company buys vegetable oil from two sources (A and B), which are already blends of olive oil, sunflower oil, and other oils.

Source	Olive oil	Sunflower oil	Other	Cost (p per litre)	Minimum order (litres)
A	50%	10%	40%	25	35000
B	20%	60%	20%	20	50000

The company wants a blend with at least 30% olive oil and at least 30% sunflower oil. They need to produce at least 90000 litres per week at minimum cost.

Step 1: Define decision variables

Let $x$ = litres of oil A
Let $y$ = litres of oil B

Step 2: Formulate constraints

Olive oil requirement (at least 30%): $\frac{0.5x + 0.2y}{x + y} \geq 0.3$

Multiplying by $x + y$ : $0.5x + 0.2y \geq 0.3(x + y)$

Simplifying: $0.2x - 0.1y \geq 0$ , or $y \leq 2x$

Sunflower oil requirement (at least 30%): $\frac{0.1x + 0.6y}{x + y} \geq 0.3$

Simplifying: $-0.2x + 0.3y \geq 0$ , or $3y \geq 2x$

Minimum orders:

$x \geq 35000$
$y \geq 50000$

Total production:

$x + y \geq 90000$

Step 3: Formulate objective function

Cost: $C = 0.25x + 0.2y$ (in pounds)

Complete formulation:

Minimise $C = 0.25x + 0.2y$

Subject to:

$y \leq 2x$
$3y \geq 2x$
$x \geq 35000$
$y \geq 50000$
$x + y \geq 90000$

Step 4: Solve graphically

For minimum cost, move the objective line toward the origin until it reaches the first point of the feasible region. This occurs at the intersection of $x + y = 90000$ and $x = 35000$ .

Solving: $y = 90000 - 35000 = 55000$

At $(35000, 55000)$ : $C = 0.25(35000) + 0.2(55000) = 8750 + 11000 = 19750$

Answer: The optimal plan is to use 35000 litres of oil A and 55000 litres of oil B to make 90000 litres of blend at a cost of £19750.

Problem-solving strategy

To solve a linear programming problem systematically, follow these five steps:

Identify the decision variables and label them (e.g., $x$ , $y$ , $z$ ...)
Express the constraints as inequalities representing resource limitations, requirements, and practical bounds
Identify the objective function (to be maximised or minimised)
If the problem has two variables, solve graphically:
- Draw lines for each constraint and shade out regions not satisfying them
- Identify the feasible region (unshaded area satisfying all constraints)
- Draw a sample position of the objective line
- Slide the objective line parallel to itself to find where it leaves (maximisation) or enters (minimisation) the feasible region
- The optimal solution occurs at a vertex
Answer the question in context with appropriate units

infoNote

For integer solutions: If the optimal vertex gives non-integer values but integer solutions are required, test integer points near that vertex to find which gives the best objective function value.

For three or more variables: Look for relationships that allow you to reduce the number of variables, or use more advanced techniques beyond the graphical method.

bookmarkSummary

Key Points to Remember:

Linear programming formulation requires three components: decision variables, constraints, and objective function (remember: "DeCO")
The feasible region contains all points satisfying all constraints simultaneously—it's the unshaded region on your graph
The optimal solution for an LP problem always occurs at a vertex (corner point) of the feasible region ("Vertex Victory")
For maximisation, slide the objective line away from the origin; for minimisation, slide it toward the origin ("Max moves right, Min moves left")
Non-negativity constraints ( $x \geq 0, y \geq 0$ ) are standard unless the problem states otherwise
When integer solutions are required, test integer points near the optimal vertex to find the best whole-number solution
Use solid lines for $\leq$ or $\geq$ constraints; use dotted lines for $<$ or $>$ constraints
Shade out the regions that do NOT satisfy constraints—the remaining unshaded area is your feasible region

Constrained Optimisation (AQA A-Level Further Maths): Revision Notes