Page 1 of 12

Week 15 – Linear programming

Objectives
Having successfully completed this unit you should be able to:
 formulate linear programming problems;

 graph the constraint inequalities and identify the feasible region;

 find an optimal solution to the problem.

Introduction
Earlier in this course we looked at methods for solving a pair of simultaneous
equations – but we didn’t say how, in practice, this could be useful.
The week we are going to look at a popular optimisation method which is often used
to improve efficiency or profit, or minimise cost in business.

1. Linear programming
Linear programming is a method for manipulating sets of linear equations which
represent some relationships which involve some constraints.
For example, it can be used to find optimal mixes of ingredients in food to optimise
the relationship between nutritious value, calories and product cost.
1.1 Suppose a company is providing two products; eg kitchen bins and washing up
Profit lines bowls.
The profit on a kitchen bin is £3 and the profit on a washing up bowl is £2.
Let 𝑥 = number of bins produced,
and 𝑦 = number of bowls produced,
then the Profit function is
𝑃 = 3𝑥 + 2𝑦.
(And now you can see where we get 𝑃 from.)
It’s usually helpful to use some form of graph or plot to help us understand a
particular situation we want to deal with methematically. But how can we do this?

Department of Design Engineering and Mathematics Faculty of Science and Technology

 Page 2 of 12

Week 15 – Linear programming

In this case, since we have three variables (P, x and y), we need a 3-dimensional plot,
which looks like this:

15

10
P

5 2
y
1
0
1 2 3 4 0
x

This is not ideal if we have to view it on paper. We would really want to be able to
rotate it so we can see what’s happening at different points, and you definitely don’t
want to be drawing 3-D plots by hand!
Alternatively, we can try to represent the situation in two dimensions.
This does cuase problems, because we need to represent the 𝑃 axis as a line
somewhere in the 𝑥, 𝑦 plane.

Example 1
If 𝑃 = £20 our linear equation is 20 = 3𝑥 + 2𝑦 which passes through the
points (0,10) and (6.67,0).
If 𝑃 = £60 our linear equation is 60 = 3𝑥 + 2𝑦 which passes through the
points (20,0) and (0,30).

35
30
25
𝟔𝟎 = 𝟑𝒙 + 𝟐𝒚
20
15
10
𝟐𝟎 = 𝟑𝒙 + 𝟐𝒚
5
0
-10 -5 0 5 10 15 20 25 30

Department of Design Engineering and Mathematics Faculty of Science and Technology

 Page 3 of 12

Week 15 – Linear programming

The profit lines are all parallel and as the profit increases the line moves further up
the graph.
Gradient of a
Let 𝑐 and 𝑑 be constants, then our profit function is
profit line
𝑃 = 𝑐𝑥 + 𝑑𝑦.
Taking 𝑐𝑥 from both side we have 𝑑𝑦 = − 𝑐𝑥 + 𝑃.
𝑐 𝑃
Then 𝑦 = −𝑑𝑥 + 𝑑
𝑐
The gradient of the profit line is− 𝑑, so for our example,
3
𝑃 = 3𝑥 + 2𝑦 so our gradient = − 2.

Remember that this is exactly what we did earlier to switch between the two forms
for expressing a straight line.
Of course, at this point we don’t know which of the infinitely many parallel profit
lines will coincide with the mximum profit point – that’s what we want to find out.

1.2 Linear programming is concerned with maximising (or minimising) some linear
Linear objective function (e.g. profit function), subject to some constraints on 𝑥 and 𝑦.
programming This means finding values for x and y which maximise the objective function and
which satisfy the constraints.

Example 2 – maximising profit

A manufacturer makes two products, X and Y.

Each X requires 5 hours in the assembly department, 3 hours in the spraying
department and 1 hour in the finishing department.
For Y, the time required in each of these departments is 12 hours, 4 hours and 5
hours respectively.
The total weekly hours available in each department are 2400, 1200 and 800.
If the profits are £30 on each X and £100 on each Y, what is the maximum profit
output?

X Y Total time available

(time in hrs) (time in hrs) (hrs)
Assembly 5 12 2400
Spraying 3 4 1200
Finishing 1 5 800
Profit 30 100

We now need to know how to express this as a linear programme.

Department of Design Engineering and Mathematics Faculty of Science and Technology

 Page 4 of 12

Week 15 – Linear programming

Linear programme We want to maximise profit 𝑃, where

𝑃 = 30𝑥 + 100𝑦
We do this subject to the constraints given:
Assembly 5𝑥 + 12𝑦 ≤ 2400
Spraying 3𝑥 + 4𝑦 ≤ 1200
Finishing 𝑥 + 5𝑦 ≤ 800
We have the additional constraints that 𝑥 and 𝑦 are positive. It is important to state
this, because with some problems, it is possible to have negative values (e.g.
reclaiming material from already manufactured goods). But we cannot do this with
time since my Tardis got towed for illegal parking.
Each constraint tells us how resources are used within the maximum resources we
have available.
In the Assembly department the time used for a given level of output (𝑥 , 𝑦) is
𝟓𝒙 + 𝟏𝟐𝒚. So we know that for any solution to our problem the amount used is less
than or equal to the amount available, 𝟐𝟒𝟎𝟎.
Now we need to know how to find the optimal profit point and find the values for 𝑥
and 𝑦 that maximise 𝑃.
Step 1
Find the region that satisfies our constraints by drawing a graph.
So we must plot each constraint equation onto our graph.
Assembly: 5𝑥 + 𝑙2𝑦 = 2400 (0, 200) and (480, 0).
Spraying: 3𝑥 + 4𝑦 = 1200 (0, 300) and (400, 0).
Finishing: 𝑥 + 5𝑦 = 800 (0, 160) and (800, 0).

Step 2
We now shade the area on our graph which satisfies our constraint inequalities
simultaneously. This produces our feasible region, the set of possible answers to our
linear programme.
The Optimum point is the point (𝑥, 𝑦) that is in the feasible region and which
maximises the objective function.

Department of Design Engineering and Mathematics Faculty of Science and Technology

 Page 5 of 12

Week 15 – Linear programming

To find the optimum point you can either compare slopes of the edges of the feasible
Step 3
region with the slope of the objective function, or find the co-ordinates of the points
A, B, C, and D, then calculate the profit at each of these points to see which is the
maximum value.

Department of Design Engineering and Mathematics Faculty of Science and Technology

 Page 6 of 12

Week 15 – Linear programming

Method 1: This involves nothing more than what we did earlier, solving simultaneous equations
calculating profit to find the point at which two lines meet.
We know the potential optimal points from the graph: A= (0, 160) and D = (400, 0).
(It may seem unlikely that either of these will be our optimal point, but one of them
might be, if, say, the most profitable course of action is to produce only X or Y.)
We then have to solve two sets of simultaneous equations to find the co-ordinates of
B and C, or estimate their co-ordinates by reading them from the graph.
Once we have the co-ordinates we substitute them into the profit function and find
the point that produces the maximum profit.

Point Co-ordinates (𝑥, 𝑦) Profit = 𝑃 = 30𝑥 + 100𝑦

A (0, 160) 30(0) + 100(160) = £16,000
B (184.6, 123.1) 30(184.6) + 100(123.1) = £17,846.15
C (300, 75) 30(300) + 100(75) = £16,500
D (400, 0) 30(400) + 100(0) = £12,000

We clearly see that point B is the optimal point, since it produces the maximum
profit.

Method 2: The slope of the objective function and the constraints are calculated and compared
calculating slopes to determine the optimum point. This works because the gradient of the objective
function will be between the gradients of the two lines that meet at the optimal point.
The slope or gradient of an equation of the form
𝑃 = 𝑐𝑥 + 𝑑𝑦
is given by
−𝑐/𝑑
So if we calculate the slopes of the constraints, finishing, assembly, and spraying,
and compare them to the slope of the profit function we will be able to identify the
optimum point.
Profit function 𝑃 = 30𝑥 + 100𝑦 Slope = − 30/100 = −0.3
Finishing 𝑥 + 5𝑦 = 800 Slope = −1/5 = −0.2
Assembly 5𝑥 + 12𝑦 = 2400 Slope = −5/12 = −0.42
Spraying 3𝑥 + 4𝑦 = 1200 Slope = −3/4 = −0.75

Department of Design Engineering and Mathematics Faculty of Science and Technology

 Page 7 of 12

Week 15 – Linear programming

Now – 0.3 is between – 0.2 and – 0.42, and so the optimum point is the intersection
of the Finishing and Assembly lines, the point marked B on our graph.
Next we must find the co-ordinates of B.
So we can either estimate the co-ordinates from the graph or use simultaneous
equations for an exact solution (something we already did in method 1 above).
So the Optimum Point = (184.6, 123.1) which produces a maximum profit of
30(184.6) + 100(123.1) = £17,846.15.

Optimal Solution
Using either method we find that point B is the optimal solution to our linear
programme and that we should produce 184 of product X and 123 of product Y to
maximise profit.

Department of Design Engineering and Mathematics Faculty of Science and Technology

 Page 8 of 12

Week 15 – Linear programming

Example 3 – minimising cost

A health food manufacturer wishes to blend two kinds of food so that the package
can claim that a 100g portion will contain enough of two particular vitamins to meet
the daily requirement for good health.
The requirements are:
Vitamin A at least 250 units and Vitamin B at least 225 units.
The vitamin content of each g of the two foods are shown below.
Food 1 Food 2
Vit A 5 12
Vit B 3 4
Problem: if food 1 costs 0.5p per gram, and food 2 costs 0.4p per gram, how much
of each food should be used in each 100g portion to give enough of vitamins A and
B at minimum cost?

Structuring the Let the manufacturer blend x grams of Food 1 with y grams of Food 2. This will help
linear programme us construct our cost function and constraint inequalities.
 We want to minimise the cost of the food portion. Since Food 1 costs 0.5p per
gram, and Food 2 costs 0.4g per gram and as our portion is made up of 𝑥 grams
of Food 1 and 𝑦 grams of Food 2 then the cost of a portion is
Cost = 𝐶 = 0.5𝑐 + 0.4𝑦
 We know that each portion’s weight must be at least 100g. So the weight of
Food 1(𝑥) plus Food 2 (𝑦) must be at least 100g. This produces
𝑥 + 𝑦 ≥ 100
 Also we know that the Vitamin A content of the portion must be at least 250
units. So the Vitamin A content of Food 1 plus the Vitamin A content Food 2
must be at least 250 units. This produces
5𝑥 + 12𝑦 ≥ 250
 Similarly the Vitamin B content of the portion must be at least 225 units. So the
Vitamin B content of Food 1 plus the Vitamin B content Food 2 must be at least
225 units. This produces
3𝑥 + 4𝑦 ≥ 225
 Common sense tells us that the quantities we use of each food will be positive.
This gives 𝑥 ≥ 0, 𝑦 ≥ 0.

Department of Design Engineering and Mathematics Faculty of Science and Technology

 Page 9 of 12

Week 15 – Linear programming

Linear programme We want to minimise Cost 0.5𝑥 + 0.4𝑦subject to the following constraints,
𝑥 + 𝑦  100 (1) 100g portion
2𝑥 + 5𝑦  250 (2) Vitamin A requirement
3𝑥 + 2𝑦  225 (3) Vitamin B requirement
𝑥 ≥ 0, 𝑦 ≥ 0
To find the region that satisfies our constraints we draw the graph of our constraints.
So we must plot each constraint equation onto our graph.
Constraint (1) 𝑥 + 𝑦 ≥ 100 This line passes through (0, 100) and (100, 0).
Constraint (2) 2𝑥 + 5 𝑦 ≥ 250 (0, 50) and (125, 0).
Constraint (3) 3𝑥 + 2 𝑦 ≥ 225 (0, 112.5) and (75, 0).
Method 1:
calculating cost

Feasible
region

First find the co-ordinates of A, B, C, D. Once we have the co-ordinates we

substitute them into the cost function and find the point that produces the minimum
8
cost.
Point Co-ordinates (𝑥, 𝑦) Cost (C) = 𝟎. 𝟓𝒙 + 𝟎. 𝟒𝒚
A (0, 112.5) 0.5(0) + 0.4(112.5) = 45𝑝
B (25, 75) 0.5(25) + 0.4(75) = 42.5𝑝

C (83⅓, 16⅔) 0.5(83⅓) + 0.4(16⅔) = 49.93𝑝

D (125, 0) 0.5(125) + 0.4(0) = 62.5𝑝

We clearly see that point B is the optimal point, since it produces the minimum cost.

Department of Design Engineering and Mathematics Faculty of Science and Technology

 Page 10 of 12

Week 15 – Linear programming

Method 2: The slope of the objective function and the constraints are calculated and compared
calculating slopes to determine the optimum point. The slope or gradient of an equation of the form
𝑃 = 𝑐𝑥 + 𝑑𝑦 , is given by −𝑐⁄𝑑 .

So if we calculate the slopes of the constraints, food, vitamin A and vitamin B, and
compare them to the slope of the profit function we will be able to identify the
optimum point.
0.5
Cost (C) 0.5𝑥 + 0.4𝑦 Slope = − 0.4 = −1.25
1
Constraint (1) 𝑥 + 𝑦 ≥ 100 Slope = − 1 = 1
2
Constraint (2) 2𝑥 + 5 𝑦 ≥ 250 Slope = − 5 = −0.4
3
Constraint (3) 3𝑥 + 2 𝑦 ≥ 225 Slope = − 2 = −1.5

Now – 1.25 is between −1 and −1.5, and so the optimum point is the intersection of
(1) and (3), so point B.
Now we can either estimate the co-ordinates from the graph or use simultaneous
equations for an exact solution.
So the Optimum Point = (25, 75) which produces a minimum cost of £(0.5(25) +
0.4(75)) = 42.5𝑝.
Therefore the manufacturer should blend 25 grams of Food 1 with 75 grams of Food
2 to achieve a minimum cost of 42.5p per 100g.

Optimal Solution
Using either method we find that
point B is the optimal solution to our
linear programme and that we Feasible
should include 25g of Food 1 and region
75g of Food 2 to minimise cost
subject to our constraints. So the
manufacturer should blend 25g of
Food 1 with 75g of Food 2 to
achieve a minimum cost of 42.5p
per 100g.

Department of Design Engineering and Mathematics Faculty of Science and Technology

 Page 11 of 12

Week 15 – Linear programming

For next week…

This was the final lecture of the module.
This week, the seminar, lab and assessment sessions will run as usual.

For the final two weeks, the lab and assessment sessions will run to enobale you to
catch up with any work not yet completed, and also allow you to be observed on any
outstanding SOBs.

Department of Design Engineering and Mathematics Faculty of Science and Technology

 Page 12 of 12

Week 15 Exercises
These exercises will be reviewed in this week’s seminar session.

Exercise 1 The table below gives information about a bed manufacturer, Sleepy Nights Ltd,
who make and distribute single and double beds. Each manufactured item goes
through 3 departments, assembly, testing and distribution.

Time for activity in mins

Singles (x) Doubles (y) Total time available

Assembly 9 12 7200

Testing 10 10 6500

Distribution 12 6 6000

Profit 150 100

a) Formulate the above information as a linear programming problem, and write

down your objective function.
b) Draw a graph of the constraint inequalities.
c) Find the optimum profit point, indicate this on your graph and evaluate the
maximum profit.

Department of Design Engineering and Mathematics Faculty of Science and Technology