Functions and algebra: Use Mathematical models to investigate linear programming problems

# Unit 1: Linear programming

Dylan Busa

### Unit outcomes

By the end of this unit you will be able to:

• Sketch given constraints.
• Find the feasible region and objective function.
• Use a boundary search to find the vertices of the feasible region.
• Optimise the objective function.

## What you should know

Before you start this unit, make sure you can:

## Introduction

Qhubeka is a wonderful organisation that donates bicycles to children in rural areas to make things such as getting to and from school easier and quicker.

Qhubeka makes all the bicycles it donates, thereby also creating employment. Suppose it makes two types of bicycles – the Buffalo and the Cheetah. The Buffalo is rugged and designed for areas where the roads aren’t so good. The Cheetah is designed for areas where there are at least basic roads.

Now suppose that each day Qhubeka can produce at most seven Buffalos and six Cheetahs. It takes three technicians to build a Buffalo and two technicians to build a Cheetah. There is a total of $\scriptsize 18$ technicians at the organisation.

Each Buffalo costs $\scriptsize \text{R2}\ 400$ to make and each Cheetah costs $\scriptsize \text{R1}\ 200$ to make. If every bicycle that Qhubeka makes is needed by a child, how many of each type should Qhubeka make in order to minimise costs?

This is an example of an optimisation problem. There are several constraints that all need to be taken into account to find an optimal solution, in this case the lowest cost.

Another example of an optimisation problem would be a farmer working out how much of two different crops to plant, with different input costs and different market values, in order to maximise his profit. In all cases, we want to calculate the maximum or minimum in a specific situation.

## Solve optimisation problems graphically

The easiest and most efficient way to solve these kinds of optimisation problems is graphically using a technique called linear programming. Linear programming is a graphical modelling technique in which the optimal solution of a linear function is found by applying various other constraints. Linear programming is, therefore, a special case of the broader area of mathematical programming and is most often used to guide decision making in business, engineering, social sciences, and physical sciences.

A detailed worked example of the solution to the problem Qhubeka faces is the best way to demonstrate how linear programming works.

### Example 1.1

This is what we know:

• Qhubeka makes two types of bicycles – the Buffalo and the Cheetah.
• Each day Qhubeka can produce at most seven Buffalos and four Cheetahs.
• Each Buffalo needs three technicians to build it.
• Each Cheetah needs two technicians.
• There is a total of $\scriptsize 18$ technicians.
• Each Buffalo costs $\scriptsize \text{R2}\ 400$ to make and each Cheetah costs $\scriptsize \text{R1}\ 200$ to make.
1. If every bicycle that Qhubeka makes is needed by a child, how many of each type should Qhubeka make per day in order to minimise costs?
2. What is this minimum cost?

Solution

There are five basic steps to using linear programming to solve optimisation problems.

Step 1: Assign variables
In this problem, there are two types of bicycles and we want to find out how many of each kind should be produced. We need to assign a variable to each type of bicycle. You can assign any variables you like but, because we will be sketching linear functions, it is often simplest to just use $\scriptsize x$ and $\scriptsize y$.

Let the number of Buffalo bicycles be $\scriptsize x$.
Let the number of Cheetah bicycles be $\scriptsize y$.

In both cases, the values of $\scriptsize x$ and $\scriptsize y$ are limited to natural numbers. We cannot have a fraction of a bicycle. Therefore $\scriptsize \{x|x\in \mathbb{N}\}\text{ }$ and $\scriptsize \{y|y\in \mathbb{N}\}\text{ }$.

Step 2: Express the constraints
In all cases a set of constraints is given to you. The first constraint we are given is that each day at most seven Buffalo bicycles can be built. Therefore, $\scriptsize x\le 7$.

We are also told that at most four Cheetah bicycles can be built. Therefore, $\scriptsize y\le 4$.

Each Buffalo needs three technicians and each Cheetah needs two technicians. But there are only $\scriptsize 18$ technicians. Therefore, we can say that $\scriptsize 3x+2y\le 18$ where $\scriptsize 3x$ is the total number of technicians needed to build $\scriptsize x$ Buffalos and $\scriptsize 2y$ is the total number of technicians needed to build $\scriptsize y$ Cheetahs.

Step 3: Determine the objective function
The objective function is the linear function we are trying to find a maximum or minimum solution for. In our case, we need to minimise cost. We are told that each Buffalo costs $\scriptsize \text{R2}\ 400$ to make and each Cheetah costs $\scriptsize \text{R1}\ 200$ to make. Therefore, $\scriptsize 2\ 400x+1\ 200y=C$ where $\scriptsize C$ is the total cost of producing $\scriptsize x$ Buffalo bicycles and $\scriptsize y$ Cheetah bicycles.

Step 4: Graph the constraints
It is time to start graphing our constraints so that we can optimise the objective function. Here are our constraints:

• $\scriptsize x\le 7$
• $\scriptsize y\le 4$
• $\scriptsize 3x+2y\le 18$

Let’s start with $\scriptsize x\le 7$. If we plot the graph of $\scriptsize x=7$ we get a vertical line that cuts the x-axis at $\scriptsize 7$. But our graph needs to show $\scriptsize x\le 7$. Therefore, this is not a line but a region (see Figure 2). Remember that $\scriptsize x\in \mathbb{N}\text{ }$ so we are only including natural numbers between zero and seven.

Next, we graph the next constraint, $\scriptsize y\le 4$ (see Figure 3). Again, $\scriptsize y\in \mathbb{N}\text{ }$ so we are only including natural numbers between zero and four.

The overlapping region is what we are interested in because this represents all the values for $\scriptsize x$ and $\scriptsize y$ that would satisfy both constraints at the same time.

But we have another constraint: $\scriptsize 3x+2y\le 18$.

\scriptsize \begin{align*}3x+2y & \le 18\\\therefore 2y & \le -3x+18\\\therefore y & \le -\displaystyle \frac{3}{2}x+9\end{align*}

First, we sketch the line $\scriptsize y=-\displaystyle \frac{3}{2}x+9$ and then we shade the region below this line because our constraint is $\scriptsize y\le -\displaystyle \frac{3}{2}x+9$ (see Figure 4). If the constraint was $\scriptsize y\ge -\displaystyle \frac{3}{2}x+9$, we would shade the region above the line.

The region where all three separate regions overlap is called the feasible region. It is in this region that the solution to our problem lies.

We could explicitly show that we are only interested in the natural numbers by plotting these points within the feasible region (see Figure 5).

Step 5: Graph the objective function
Our objective function is $\scriptsize 2\ 400x+1\ 200y=C$.
\scriptsize \begin{align*}2\ 400x+1\ 200y&=C\\ \therefore 1\ 200y & =-2\ 400x+C\\ \therefore y & =\displaystyle \frac{{-2\ 400}}{{1\ 200}}x+\displaystyle \frac{C}{{1\ 200}}\\ \therefore y&=-2x+\displaystyle \frac{C}{{1\ 200}}\end{align*}

Now we cannot really graph this linear function because we don’t yet know what the value of $\scriptsize C$ is. But remember, $\scriptsize C$ is what we are trying to minimise, for a maximum number of bicycles produced. In other words, we are trying to find the lowest value of $\scriptsize C$ that will make our objective function pass through one of the possible solution points with the largest coordinates within the feasible region.

So, we start with any line with a gradient of $\scriptsize -2$ and move this line up and down to find the smallest y-intercept value that still lets the objective function pass through one of the points in the feasible region with the largest possible $\scriptsize x$ and $\scriptsize y$ coordinates. The objective function must pass through $\scriptsize (3,4)$ for the y-intercept to be a minimum ($\scriptsize 10$), and $\scriptsize x$ and $\scriptsize y$ to be maximum. The solution is shown below in Figure 6.

We are now in a position to answer the questions.

1. Qhubeka must make three Buffalo bicycles and four Cheetah bicycles per day to minimise costs.
2. The minimum solution to the objective function results in a y-intercept of $\scriptsize (0,10)$. The objective function is $\scriptsize y=-2x+\displaystyle \frac{C}{{1\ 200}}\text{ }$. Therefore:
\scriptsize \begin{align*}\displaystyle \frac{C}{{1\ 200}} & =10\\\therefore C & =12\ 000\end{align*}The minimum cost is $\scriptsize \text{R}12\ 000$.

### Note

If you have an internet connection, visit a simulation of this linear programming solution.

There is a slider to change the value of $\scriptsize C$ in order to find the minimum or maximum solution to the objective function.

Let’s look at another example.

### Example 1.2

A TVET college class wants to raise funds to help buy new workshop tools. To raise money, they decide to host a cake sale and sell two different types of cakes – chocolate cake and carrot cake.

The class estimates that they can sell at most $\scriptsize 60$ chocolate cakes and $\scriptsize 50$ carrot cakes.

Each chocolate cake takes $\scriptsize 50\ \min$ to bake and each carrot cake takes $\scriptsize 80\ \min$ to bake. In total, the class calculates that they have $\scriptsize 4\ 400\min$ to bake all the cakes.

Each chocolate cake costs $\scriptsize \text{R}30$ to make and each carrot cake costs $\scriptsize \text{R}40$ to make and they have a total of $\scriptsize \text{R2}\ 400$ to spend on ingredients.

They can sell each chocolate cake for $\scriptsize \text{R3}0$ profit and each carrot cake for $\scriptsize \text{R6}0$ profit.

1. Assuming they can sell all the cakes they bake, how many of each type of cake should they bake to maximise their profit?
2. What will this maximum profit be?

Solution

Step 1: Assign variables
Let the number of chocolate cakes be $\scriptsize x$.
Let the number of carrot cakes be $\scriptsize y$.

We cannot have fractions of cakes or negative numbers of cakes. Therefore $\scriptsize \{x|x\in \mathbb{N}\}\text{ }$ and $\scriptsize \{y|y\in \mathbb{N}\}\text{ }$.

Step 2: Express the constraints

• $\scriptsize x\le 60$ (at most $\scriptsize 60$ chocolate cakes can be sold)
• $\scriptsize y\le 50$ (at most $\scriptsize 50$ carrot cakes can be sold)
• $\scriptsize 50x+80y\le 4\ 400$ (each chocolate cake takes $\scriptsize 50\ \min$ and each carrot cake takes $\scriptsize 80\ \min$ to bake and they have a total of $\scriptsize 4\ 400\ \min$ to bake).
• $\scriptsize 30x+40y=2\ 400$ (each chocolate cake costs $\scriptsize \text{R}30$ and each carrot cake costs $\scriptsize \text{R}40$ and they have a total of $\scriptsize \text{R}2\ 400$ to spend)

Step 3: Determine the objective function
$\scriptsize 30x+60y=P$, where $\scriptsize P$ is profit.

Step 4: Graph the constraints
\scriptsize \begin{align*}50x+80y\le 4\ 400\\\therefore 80y\le -50x+4\ 400\\\therefore y\le -\displaystyle \frac{{50}}{{80}}x+\displaystyle \frac{{4\ 400}}{{80}}\\\therefore y\le -\displaystyle \frac{5}{8}x+55\end{align*}

\scriptsize \begin{align*}30x+40y & \le 2\ 400\\\therefore 40y & \le -30x+2\ 400\\\therefore y & \le -\displaystyle \frac{{30}}{{40}}x+\displaystyle \frac{{2\ 400}}{{40}}\\\therefore y & \le -\displaystyle \frac{3}{4}x+60\end{align*}

The graphed constraints are shown in Figure 7.

Step 5: Graph the objective function
\scriptsize \begin{align*}30x+60y & =P\\\therefore 60y & =-30x+p\\\therefore y & =-\displaystyle \frac{{30}}{{60}}x+\displaystyle \frac{P}{{60}}\\\therefore y & =-\displaystyle \frac{1}{2}x+\displaystyle \frac{P}{{60}}\end{align*}

An instance of the objective function is graphed in Figure 8.

In this case, we want to maximise the objective function, in other words, we want to find the maximum y-intercept that the graph can have while still passing through one of the possible solution points in the feasible region. From the graph of the feasible region, we can see that this point is $\scriptsize (40,30)$. When the objective function is made to pass through this point its y-intercept is $\scriptsize 50$ (see Figure 9).

1. The class should bake $\scriptsize 40$ chocolate cakes and $\scriptsize 30$ carrot cakes to maximise their profit.
2. $\scriptsize y=-\displaystyle \frac{1}{2}x+\displaystyle \frac{P}{{60}}$
\scriptsize \begin{align*}\displaystyle \frac{P}{{60}} & =50\\\therefore P=3\ 000\end{align*}
The maximum profit they can make is $\scriptsize \text{R3}\ 000$.

### Exercise 1.1

Question taken from Question 2.3 of NC(V) Mathematics Paper 1 March 2014

A clothing company manufactures yellow T-shirts ($\scriptsize x$) and black trousers ($\scriptsize y$) for a day-care school. The following system of inequalities are obtained:
$\scriptsize x\ge 200$
$\scriptsize x+y\le 600$
$\scriptsize x+2y\le 900$
$\scriptsize 50x+100y\le 45\ 000$

1. Sketch the graphs of the given constraints.
2. Indicate the feasible region.
3. Determine the number of t-shirts and pairs of trousers that will yield a maximum profit if $\scriptsize P=30x+40y$.
4. Determine the number of t-shirts and pairs of trousers that will yield a minimum profit if $\scriptsize P=30x+40y$.

The full solutions are at the end of the unit.

## Summary

In this unit you have learnt the following:

• How to express given constraints using variables.
• How to plot these constraints on the Cartesian plane.
• How to determine the feasible region.
• How to determine the objective function.
• How to maximise or minimise the objective function.

# Unit 1: Assessment

#### Suggested time to complete: 15 minutes

Question 1 is based on Question 2.5 from NC(V) Mathematics Paper 1 October 2012

1. An entrepreneur sells apples and bananas at the fruit stand. Suppose $\scriptsize x$ apples and $\scriptsize y$ bananas are sold every hour, and that the following constraints are applicable:
$\scriptsize 10\le x\le 40$
$\scriptsize x+y\le 60$
$\scriptsize 15\le y\le 45$
$\scriptsize 2y+x\ge 60$
1. Sketch the graph with the given constraints.
2. Determine the feasible region.
3. Determine how many apples and bananas should be sold every hour so that the maximum profit can be made if $\scriptsize P=3x+5y$.

Question 2 is taken from Question 3.3 from NC(V) Mathematics Paper 1 October 2014

1. Lesedi is a small company that makes two types of cards, type A ($\scriptsize x$) and type B ($\scriptsize y$). With the available labour and materials, the following are the constraints inequalities:
$\scriptsize x+y\le 200$
$\scriptsize x\ge 40$
$\scriptsize y\ge 10$
$\scriptsize x\le 150$
$\scriptsize y\le 120$
1. Sketch the graph of the given constraints.
2. Determine the feasible region.
3. Find the values of $\scriptsize x$ and $\scriptsize y$ which will maximise the objective equation $\scriptsize P=5x+10y$.
4. Find the values of $\scriptsize x$ and $\scriptsize y$ which will minimise the objective equation $\scriptsize P=5x+10y$ and state the value of $\scriptsize P$ when this function is minimised.

The full solutions are at the end of the unit.

# Unit 1: Solutions

### Exercise 1.1

1. $\scriptsize x\in \mathbb{N}\text{ }$ and $\scriptsize y\in \mathbb{N}\text{ }$
Constraints are:
$\scriptsize x\ge 200$
.
\scriptsize \begin{align*}x+y & \le 600\\\therefore y & \le -x+600\end{align*}
.
\scriptsize \begin{align*}x+2y & \le 900\\\therefore 2y & \le -x+900\\\therefore y & \le -\displaystyle \frac{1}{2}x+450\end{align*}
2. The feasible region is the region bound by points $\scriptsize \text{A},\text{B},\text{C}$ and $\scriptsize \text{D}$.
3. .
\scriptsize \begin{align*} P&=30x+40y\\ \therefore 40y&=-30x+P\\ \therefore y&=-\displaystyle \frac{3}{4}x+\displaystyle \frac{P}{40} \end{align*}
The objective function is maximised when passing through $\scriptsize \text{C}(300,300)$. Therefore, $\scriptsize 300$ t-shirts and $\scriptsize 300$ pairs of trousers will yield a maximum profit.
4. The objective function is minimised when passing through $\scriptsize \text{A}(200,0)$. Therefore, $\scriptsize 200$ t-shirts and zero pairs of trousers will yield a minimum profit.

Back to Exercise 1.1

### Unit 1: Assessment

1. .
1. $\scriptsize x\in \mathbb{N}\text{ }$ and $\scriptsize y\in \mathbb{N}\text{ }$
Constraints are:
$\scriptsize 10\le x\le 40$
\scriptsize \begin{align*}x+y & \le 60\\\therefore y & \le -x+60\end{align*}
$\scriptsize 15\le y\le 45$
\scriptsize \begin{align*}&2y+x\ge 60\\& \therefore y\ge -\displaystyle \frac{1}{2}x+30\quad \text{Remember that because }y\ge \text{ you need to take the region above the line}\end{align*}
2. The feasible region is the region bound by points $\scriptsize \text{A},\text{B},\text{C},\text{D},\text{E}$ and $\scriptsize \text{F}$.
3. .
\scriptsize \begin{align*} P&=3x+5y\\ \therefore 5y&=-3x+P\\ \therefore y&=-\displaystyle \frac{3}{5}x+\displaystyle \frac{P}{5} \end{align*}
The objective function is maximised when passing through $\scriptsize \text{F}(15,45)$. Therefore, selling $\scriptsize 15$ apples and $\scriptsize 45$ bananas will yield a maximum profit.
2. .
1. $\scriptsize x\in \mathbb{N}\text{ }$ and $\scriptsize y\in \mathbb{N}\text{ }$
Constraints are:
\scriptsize \begin{align*}x+y & \le 200\\\therefore y & \le -x+200\end{align*}
$\scriptsize x\ge 40$
$\scriptsize y\ge 10$
$\scriptsize x\le 150$
$\scriptsize y\le 120$
2. The feasible region is the region bound by points $\scriptsize \displaystyle \text{A},\text{B},\text{C},\text{D}$ and $\scriptsize \text{E}$.
3. .
\scriptsize \begin{align*} P&=5x+10y\\ \therefore 10y&=-5x+P\\ \therefore y&=-\displaystyle \frac{1}{2}x+\displaystyle \frac{P}{10} \end{align*}
The objective function is maximised when passing through $\scriptsize \text{E}(80,120)$. Therefore, $\scriptsize x=80$ and $\scriptsize y=120$.
4. The objective function is minimised when passing through $\scriptsize \text{B}(40,10)$. Therefore, $\scriptsize x=40$ and $\scriptsize y=10$. When minimised, the objective function has a y-intercept of $\scriptsize (0,30)$.
\scriptsize \begin{align*}\displaystyle \frac{P}{{10}} & =30\\\therefore P & =300\end{align*}
Therefore $\scriptsize P=300$ is the value of $\scriptsize P$ when the function is minimised.

Back to Unit 1: Assessment