A worked example of a linear programming problem

Question

Clive has decided that as a fund-raising activity he will make and sell candles. He has decided to make two types of candle, a plain one, and a scented one. Each candle requires 200g of wax and Clive has bought enough ingredients to make a total of 1.6kg of wax. His idea is to make the scented candles tall and thin, and the plain candles shorter and fatter. This means that the length of wick required for a scented candle is 200mm but only 100mm is needed for a plain candle. Clive only has 1m of wick to use. Clive has worked out from a survey that he won’t be able to sell more scented candles than double the number of plain candles plus three.

If he is going to sell the candles at £3 for a scented candle and £2 for a plain, how many of each should he make so that he raises the most money possible?

Solution

Definitions

The first thing that we must do is define our variables:

Let:

x be the number of plain candles made,
y be the number of scented candles made, and
I be the income from selling the candles.

Variable definitions

Constraints

Having defined the variables we can construct our constraint inequalities using the information provided in the question. These describe the conditions that will restrict the number of candles that we can make.

The first constraint relates to the mass of wax available. 200g is required for each candle, and the total available is 1.6kg. Converting to consistent units and writing as an inequality, then simplifying we get:

\begin{aligned}200x + 200y &\leq 1600 \\ x + y &\leq 8\end{aligned}First constraint inequality

The second constraint is given by the amount of wick available and required. 100mm is needed for each plain candle and 200mm is needed for each scented candle. 1m is available. As with the first constraint, we make sure the units are consistent, then write as an inequality and simplify.

\begin{aligned}100x + 200y &\leq 1000 \\ x + 2y &\leq 10\end{aligned}Second constraint inequality

The final constraint is that Clive won’t be able to sell more scented candles than double the number of plain candles plus three. Although slightly complicated this constraint can be written as follows:

y \leq 2x + 3Third constraint inequality

Trivial constraints

Most linear programming problems will have some constraints that are not explicitly described. Sometimes you will need to infer a constraint from the context; most frequently these will be trivial. Although referred to as trivial, these constraints are important to include. In this case the context means that we are only interested in positive integers:

x\geq 0 \\ y \geq 0 \\ x\in \mathbb{Z} ^{+}Trivial constraints

Objective Function

Having constructed all of our constraint inequalities the only thing left for us to do before solving the problem is to generate an objective function. This is created from the information that tells us what we are to optimise (usually make biggest or smallest). In this case, we need to maximise income with each scented candle selling at £3 and each plain candle selling at £2. The objective function will be:

I = 2x + 3yObjective function

Solving the problem graphically

This problem can be solved graphically by constructing the graph below. Using the constraints that we have already constructed:

x + y \leq 8 \\ x + 2y \leq 10 \\ y \leq 2x + 3 \\ y \geq 0All of the constraints

[geogebra-activity material='fzx8dzcn' shiftdragzoom='false' width=700 height=500]

Using the coordinates found at or near the vertices in the objective function, we can work out which combination of scented and plain candles will give the greatest income. Because the only solutions that make sense in the context are integer values of both x and y, it is worth checking coordinate points near the vertices, inside the feasible region.

x	y	I = 2x+ 3y
0	3	2 × 0 + 3 × 3 = £9
0.8	4.6	2 × 0.8 + 3 × 4.6 = £15.40
1	4	2 × 1 + 3 × 4 = £14
6	2	2 × 6 + 3 × 2 = £18
8	0	2 × 8 + 3 × 0 = £16

As you can see, the highest income can be achieved when 6 plain candles and 2 scented candles are sold. This will give an income of £18.