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

# Unit 1: Solve linear programming problems by optimising a function

Dylan Busa

### Unit outcomes

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

• Determine the linear constraints for a given problem.
• Sketch the linear constraints.
• Find the feasible region.
• Use a search line to optimise the constraints.

## What you should know

Before you start this unit, make sure you can:

## Introduction

In level 3 subject outcome 2.4 we were introduced to Qhubeka, the bicycle company that makes and donates bicycles to children in rural areas to make things such as getting to and from school easier and quicker.

We saw how, given a set of constraints, we could optimise how many of each of two types of bicycles the company should make in order to achieve the lowest costs. We called these kinds of problems optimisation problems – considering several given constraints that all need to be taken into account to find an optimal solution.

We also saw that an excellent way to solve optimisation problems was using a graphical technique called linear programming. Linear programming involves:

1. assigning variables to the unknowns which we would like to optimise (in the Qhubeka example this was the number of each type of bicycle that should be produced to minimise costs)
2. determining and expressing the various constraints in terms of these variables (usually as inequalities)
3. sketching these constraints on a graph
4. determining the feasible region (the set of all the variables that obey or fulfil all the constraints at the same time)
5. determining the objective function or search line to optimise the constraints,
6. finding the optimal solution.

In level 3, the expressions for the constraints were always given to you. In this unit, you will need to interpret the given information to determine and express these constraints for yourself. Other than that, everything is the same as you learnt in level 3.

### Did you know?

Linear programming is just one of many mathematical modelling techniques. A mathematical model is simply a description of a real-world system or problem using mathematical concepts and language that helps to solve problems, make decisions or predict what might happen in the future.

Watch this informative video that describes mathematical modelling in a little more detail,
“What is Math Modeling?”.

What is Math Modeling? (Duration: 3.12)

## Solve optimisation problems graphically using linear programming

The best way to learn how to solve optimisation problems using linear programming is to work through a few examples before trying some questions on your own.

### Example 1.1

A group of learners plans to sell hamburgers and chicken burgers at a rugby match. Their butcher has a total of $\scriptsize 300$ hamburger patties and $\scriptsize 400$ chicken burger patties. Each burger needs to be sold in a packet but there are only $\scriptsize 500$ packets available. Based on past events, the group predicts that demand is likely to be such that the number of chicken burgers sold will be at least half the number of hamburgers sold.

1. Write the constraint inequalities and draw a graph of the feasible region.
2. Looking at the cost of ingredients, the group plans to make a profit of $\scriptsize \text{R}3.00$ on each hamburger and $\scriptsize \text{R}2.00$ on each chicken burger sold. Write an equation which represents the total profit $\scriptsize P$.
3. How many of each type of burger should the group plan to sell if they want to maximise their profits?

Solutions

1. We need to write down mathematical expressions of the constraints and draw the feasible region.

Step 1: Assign variables
In this problem, there are two types of burgers to be sold and we want to find out how many of each kind should be made and sold. We need to assign a variable to each type of burger. You can assign any variables you like but, because we will be sketching linear functions, it is often simplest to use $\scriptsize x$ and $\scriptsize y$.
.
Let the number of hamburgers be $\scriptsize x$.
Let the number of chicken burgers be $\scriptsize y$.
.
In both cases, the values of $\scriptsize x$ and $\scriptsize y$ are limited to natural numbers. We cannot sell a fraction of a burger. Therefore $\scriptsize \{x|x\in \mathbb{N}\}$ and $\scriptsize \{y|y\in \mathbb{N}\}$.
.
Step 2: Express the constraints
In level 4, you need to interpret the information given to you to express your own mathematical statements of the constraints.
.
We know that the butcher only has $\scriptsize 300$ hamburger patties and $\scriptsize 400$ chicken burger patties. Therefore, our first two constraints are $\scriptsize x\le 300$ and $\scriptsize y\le 400$.
.
We also know that the total number of burgers sold is limited by the number of packets available. Therefore, our next constraint is $\scriptsize x+y\le 500$.
.
Finally, the group makes a prediction that at least half as many chicken burgers as hamburgers will be sold. Therefore, our final constraint is $\scriptsize x\le 2y$ (or $\scriptsize \displaystyle \frac{1}{2}x\le y$).
.
Step 3: Graph the constraints
It is time to start graphing our constraints so that we can optimise the objective function. Here they are again.

• $\scriptsize x\le 300$
• $\scriptsize y\le 400$
• $\scriptsize x+y\le 500$
• $\scriptsize x\le 2y$

Here are these constraints graphed. The feasible region is that contained by points $\scriptsize A$, $\scriptsize B$, $\scriptsize C$, $\scriptsize D$ and $\scriptsize E$.

2. Now, if a profit of $\scriptsize \text{R}3.00$ is made on each hamburger sold and a profit of $\scriptsize \text{R}2.00$ is made on each chicken burger sold, the profit equation will be $\scriptsize P=3x+2y$
3. To find the maximum profit (the optimum solution), we need to graph our profit function (also called the objective function or the search line) to find what the maximum values for $\scriptsize x$ and $\scriptsize y$ are such that the objective function is still within the feasible region.
.
To sketch the objective function/search line, it is normally best to get the function into standard form.
\scriptsize \begin{align*}P & =3x+2y\\\therefore 2y & =-3x+P\\\therefore y & =-\displaystyle \frac{3}{2}x+\displaystyle \frac{P}{2}\end{align*}
.
In this form, we can see that to maximise the value of $\scriptsize P$ we need to maximise the value of the y-intercept of this straight line. We do not yet know what the value of $\scriptsize P$ is but we do know that the gradient of the graph is $\scriptsize m=-\displaystyle \frac{3}{2}$. Therefore, we need to sketch any straight line with $\scriptsize m=-\displaystyle \frac{3}{2}$ and then move this line up or down until we get the greatest y-intercept while still having the line pass through at least one point in the feasible region.
.
Here is the objective function/search line graphed such that the profit is maximised. In order to maximise $\scriptsize P$, while still remaining in the feasible region, the objective function must pass through the point $\scriptsize C(300,200)$.

We can either substitute the values for $\scriptsize x$ and $\scriptsize y$ from $\scriptsize C$ into the objective function or we can read off the y-intercept of the function and hence determine the value of $\scriptsize P$.
.
Substituting $\scriptsize C(300,200)$:
\scriptsize \begin{align*}P&=3(300)+2(200)\\&=900+400\\&=1\ 300\end{align*}
.
y-intercept is $\scriptsize 650$
\scriptsize \begin{align*}\therefore \displaystyle \frac{P}{2}&=650\\\therefore P&=1\ 300\end{align*}
.
This means that to make a maximum profit, the group must sell $\scriptsize 300$ hamburgers and $\scriptsize 200$ chicken burgers. This will generate a maximum profit of $\scriptsize \text{R}1\ 300.00$.

### Note

If you would like to play with an interactive version of the solution to Example 1.1, please visit this link.

### Example 1.2

Question adapted from NC(V) Mathematics Level 4 Paper 1 October 2013 question 4.5

A patient is required to take at least $\scriptsize 18$ grams of protein, $\scriptsize 6$ milligrams of vitamin C, and $\scriptsize 5$ milligrams of iron per meal which consists of two types of food, A and B. Type A contains $\scriptsize 9$ grams of protein, $\scriptsize 6$ milligrams of vitamin C and no iron per mass unit. Type B contains $\scriptsize 3$ grams of protein, $\scriptsize 2$ milligrams of vitamin C and $\scriptsize 5$ milligrams of iron per mass unit. The energy value of A is $\scriptsize 800$ kilojoules and that of B is $\scriptsize 400$ kilojoules per mass unit. A patient is not allowed to have more than $\scriptsize 4$ mass units of A and $\scriptsize 5$ mass units of B. There are $\scriptsize x$ mass units of A and $\scriptsize y$ mass units of B on the patient’s plate. The patient cannot eat a fraction of a mass unit of either type of food.

1. Write down all the constraints with respect to the above information in terms of $\scriptsize x$ and $\scriptsize y$.
2. What is the kilojoule intake per meal?
3. Represent the constraints graphically.
4. Deduce from the graphs the values of $\scriptsize x$ and $\scriptsize y$ that give the minimum kilojoule intake per meal for the patient.

Solutions

1. We are told that the mass units of food type A are $\scriptsize x$ and the mass units of food type B are $\scriptsize y$. We are also told that the patient can have at most $\scriptsize 4$ mass units of A and $\scriptsize 5$ mass units of B. Therefore, $\scriptsize x\le 4$ and $\scriptsize y\le 5$. Remember, however, that we cannot have fractions of mass units. Therefore, $\scriptsize x\in \mathbb{N}$ and $\scriptsize y\in \mathbb{N}$.
.
We are also told about the nutrient content of each food and how much of each nutrient the patient needs. The patient needs at least $\scriptsize 18$ grams of protein per meal. Food type A gives $\scriptsize 9$ grams and food type B gives $\scriptsize 3$ grams. Therefore, $\scriptsize 9x+3y\ge 18$.
.
The patient needs at least 6 milligrams of vitamin C per meal. Food type A gives $\scriptsize 6$ milligrams and food type B gives $\scriptsize 2$ milligrams. Therefore, $\scriptsize 6x+2y\ge 6$.
.
Finally, the patient needs at least $\scriptsize 5$ milligrams of iron per meal. Food type A gives $\scriptsize 0$ milligrams and food type B gives $\scriptsize 5$ milligrams. Therefore, $\scriptsize 5y\ge 5$
2. Food type A has $\scriptsize 800$ kilojoules and food type B has $\scriptsize 400$ kilojoules. Therefore, the total energy ($\scriptsize \displaystyle E$) intake is $\scriptsize E=800x+400y$.
3. It makes it easier to sketch the constraints if they are all in standard form.
\scriptsize \begin{align*}9x+3y & \ge 18\\\therefore 3y & \ge -9x+18\\\therefore y & \ge -3x+6\end{align*}
\scriptsize \begin{align*}6x+2y & \ge 6\\\therefore 2y & \ge -6x+6\\\therefore y & \ge -3x+3\end{align*}
\scriptsize \begin{align*}5y & \ge 5\\\therefore y & \ge 1\end{align*}
Here are these constraints graphed. The feasible region is that contained by points $\scriptsize A$, $\scriptsize B$, $\scriptsize C$ and $\scriptsize D$.
4. We have an equation for the kilojoule intake (the objective function) and we are asked to find the minimum intake. In other words, we need to minimise the function. If we write the objective function in standard form, we will see that the minimum value for $\scriptsize E$ corresponds to the minimum y-intercept that the function or search line can achieve while still passing through the feasible region. Here is the objective function in standard form.
\scriptsize \begin{align*} E&=800x+400y\\ \therefore 400y&=-800x+E\\ \therefore y&=-2x+\displaystyle \frac{E}{400} \end{align*}
Here is a plot of the objective function. We can see that the minimum value is achieved when the function passes through $\scriptsize A$.However, we need to remember that $\scriptsize x\in \mathbb{N}$ and $\scriptsize y\in \mathbb{N}$. Point $\scriptsize A$ represents a value of $\scriptsize x$ that is not an integer, therefore, we need to move the objective function so that it passes through the next available point in the feasible region where both coordinates are integers. This is represented by point $\scriptsize E(2,1)$.

Once again, we can determine what the minimum value of $\scriptsize E$ is by substituting the coordinates of point $\scriptsize E$ into the objective function or by determining the y-intercept and then using the fact that the y-intercept is equal to $\scriptsize \displaystyle \frac{E}{{400}}$.
.
Substituting $\scriptsize E(2,1)$:
\scriptsize \begin{align*}E&=800(2)+400(1)\\&=1\ 600+400\\&=2\ 000\end{align*}
.
y-intercept is $\scriptsize 5$
\scriptsize \begin{align*}\therefore \displaystyle \frac{E}{{400}} & =5\\\therefore E & =2\ 000\end{align*}
The minimum kilojoule intake the patient can have is $\scriptsize 2\ 000$ kilojoules and this corresponds to eating $\scriptsize 2$ mass units of food type A and $\scriptsize 1$ mass unit of food type B.

### Note

If you would like to play with an interactive version of the solution to example 1.2, please visit this link.

### Exercise 1.1

Question 1 adapted from NC(V) Mathematics Level 4 Paper 1 November 2016 question 3

1. A small sugar company produces brown sugar and white sugar. In order for the company to be economically viable, it must produce at least $\scriptsize 200$ boxes of sugar daily. The company can produce a maximum of $\scriptsize 500$ boxes of sugar daily. At least $\scriptsize 100$ boxes of brown sugar are to be produced per day. At least $\scriptsize 50$ boxes and at most $\scriptsize 300$ boxes of white sugar must be produced daily.
.
Let $\scriptsize x$ be the number of boxes of brown sugar and $\scriptsize y$ be the number of boxes of white sugar that are produced each day.

1. Write down all the algebraic inequalities (in terms of $\scriptsize x$ and $\scriptsize y$) which describe the constraints related to the production of sugar.
2. Represent the inequalities in a. graphically and clearly indicate (shade and label) the feasible region.
3. A profit of $\scriptsize \text{R}20.00$ is made on a box of brown sugar and profit of $\scriptsize \text{R}30.00$ on a box of white sugar. Use this information to draw, on the graph for b., a profit search-line.
4. Use the profit search-line to calculate the minimum and maximum profit the company can make each day.

Question 2 adapted from NC(V) Mathematics Level 4 Paper 1 November 2015 question 5

1. A transport company uses buses and minibuses to transport a minimum of $\scriptsize 400$ passengers and a maximum of $\scriptsize 600$ passengers each day. At least $\scriptsize 200$ passengers per day must be transported by bus. The number of passengers travelling by bus cannot be more than three times the number of passengers travelling by minibus. Let $\scriptsize x$ represent the number of passengers transported by bus and $\scriptsize y$ be the number of passengers transported by minibus.
1. Determine the constraints, in terms of $\scriptsize x$ and $\scriptsize y$, under which the transport company operates.
2. Represent the constraints graphically and clearly indicate the feasible region.
3. The profit per day per passenger travelling by bus is $\scriptsize \text{R}2.00$ and the profit per day per passenger travelling by minibus is $\scriptsize \text{R}1.60$. Determine from your graph by means of a search line, the values of $\scriptsize x$ and $\scriptsize y$ that will yield a maximum profit.
4. Calculate the maximum possible profit per day.

The full solutions are at the end of the unit.

## Summary

In this unit you have learnt the following:

• How to determine and express the constraints for a given problem as linear inequalities.
• How to sketch the constraints on a Cartesian plane.
• How to find and mark the feasible region.
• How to define the objective function (or search line) from given information
• How to use this objective function (or search line) to determine the optimal solution.

# Unit 1: Assessment

#### Suggested time to complete: 15 minutes

Question 1 adapted from NC(V) Mathematics Level 4 Paper 1 November 2012 question 1.3

1. A carpenter makes two types of tables, A and B.
• He has $\scriptsize 400\ {{\text{m}}^{2}}$ of floor space available.
• Each table A requires $\scriptsize 30\ {{\text{m}}^{2}}$ of floor space and each table B requires $\scriptsize 40\ {{\text{m}}^{2}}$ of floor space.
• He does not have enough skilled labourers to make more than $\scriptsize 8$ tables of type A and $\scriptsize 6$ of type B.
• According to public demand he has to make at most two type A tables for each type B table.
.
Let $\scriptsize x$ be the number of tables of type A and $\scriptsize y$ the number of tables of type B.
1. Write the constraints with respect to the above information in terms of $\scriptsize x$ and $\scriptsize y$.
2. Represent graphically ALL the constraint inequalities and clearly indicate the feasible region.
3. If the profit made on each table is the same, determine by means of a search line, how many of each type of table should be made for maximum profit.

Question 2 adapted from NC(V) Mathematics Level 4 Paper 1 November 2011 question 1.3

1. Jackson’s clothing factory manufactures jackets and jerseys. A maximum of $\scriptsize 60$ jackets and $\scriptsize 40$ jerseys can be manufactured daily while in total not more than $\scriptsize 70$ pieces of clothing can be manufactured per day. It takes $\scriptsize 5$ hours to manufacture a jacket and $\scriptsize 10$ hours to manufacture a jersey, while there are at most $\scriptsize 500$ working hours available per day.
.
Let $\scriptsize x$ represent the number of jackets and $\scriptsize y$ represents the number of jerseys manufactured per day.

1. Write down the constraints with respect to the above information in terms of $\scriptsize x$ and $\scriptsize y$.
2. Represent all the constraint inequalities on the grid and clearly indicate the feasible region.
3. If the profit is $\scriptsize \text{R}15$ on a jacket and $\scriptsize \text{R}25$ on a jersey, give the equation that indicates the profit.
4. Using the search line method, determine how many jackets and how many jerseys should be manufactured in order to obtain the maximum profit?
5. Determine the maximum profit.

Question 3 adapted from NC(V) Mathematics Level 4 Paper 1 October 2014 question 5

1. A trucking company wants to purchase a maximum of $\scriptsize 15$ new trucks that will provide at least $\scriptsize 36$ tons of additional shipping capacity. A model A truck holds $\scriptsize 2$ tons and costs $\scriptsize \text{R}150\ 000$. A model B truck holds $\scriptsize 3$ tons and costs $\scriptsize \text{R}240\ 000$.
.
Let $\scriptsize x$ be the number of model A trucks and let $\scriptsize y$ be the number of model B trucks.

1. Write down the constraints that represent the above information.
2. Represent the system of constraints on the grid indicating the feasible region by means of shading.
3. How many trucks of each model should the company purchase in order to provide the additional shipping capacity at minimum cost?
4. Calculate the minimum cost.

The full solutions are at the end of the unit.

# Unit 1: Solutions

### Exercise 1.1

1. .
1. Number of boxes of brown sugar is $\scriptsize x$, $\scriptsize x\in \mathbb{N}$
Number of boxes of white sugar is $\scriptsize y$, $\scriptsize y\in \mathbb{N}$
Minimum number of boxes of sugar: $\scriptsize x+y\ge 200$
Maximum number of boxes of sugar: $\scriptsize x+y\le 500$
Minimum number of boxes of brown sugar: $\scriptsize x\ge 100$
Minimum number of boxes of white sugar: $\scriptsize y\ge 50$
Maximum number of boxes of white sugar: $\scriptsize y\le 300$
2. The feasible region is bound by points $\scriptsize A$, $\scriptsize B$, $\scriptsize C$, $\scriptsize D$, and $\scriptsize E$.
3. .
\scriptsize \begin{align*}P&=20x+30y\\ \therefore 30y&=-20x+P\\ \therefore y&=-\displaystyle \frac{2}{3}x+\displaystyle \frac{P}{30} \end{align*}
4. Minimum profit occurs when the objective function or search line passes through $\scriptsize B(150,50)$. Therefore, the minimum profit is:
\scriptsize \begin{align*}P&=20(150)+30(50)\\&=3\ 000+1\ 500\\&=4\ 500\end{align*}

Maximum profit occurs when the objective function or search line passes through $\scriptsize D(200,300)$. Therefore, maximum profit is:
\scriptsize \begin{align*}P&=20(200)+30(300)\\&=4\ 000+9\ 000\\&=13\ 000\end{align*}

Visit the interactive solution.
.
2. .
1. Passengers transported by bus is $\scriptsize x$, $\scriptsize x\in \mathbb{N}$
Passengers transported by minibus is $\scriptsize y$, $\scriptsize y\in \mathbb{N}$
Minimum number of passengers per day: $\scriptsize x+y\ge 400$
Maximum number of passengers per day: $\scriptsize x+y\le 600$
Minimum number of bus passengers: $\scriptsize x\ge 200$
Bus passengers cannot be more than three times minibus passengers: $\scriptsize x\le 3y$
2. Feasible region is bound by points $\scriptsize A$, $\scriptsize B$, $\scriptsize C$ and $\scriptsize D$.
3. .
\scriptsize \begin{align*}P & =2x+1.6y\\\therefore 1.6y & =-2x+P\\\therefore y & =-\displaystyle \frac{2}{{1.6}}x+\displaystyle \frac{P}{{1.6}}\\\therefore y & =-\displaystyle \frac{5}{4}x+\displaystyle \frac{P}{{1.6}}\end{align*}
Maximum profit will occur when the objective function or search lines passes through point $\scriptsize B(450,150)$.
4. The maximum profit is:
\scriptsize \begin{align*}P&=2(450)+1.6(150)\\&=900+240\\&=1\ 140\end{align*}
.
Visit the interactive solution.
.

Back to Exercise 1.1

### Unit 1: Assessment

1. .
1. Table type A is $\scriptsize x$, $\scriptsize x\in \mathbb{N}$
Table type B is $\scriptsize y$, $\scriptsize y\in \mathbb{N}$
Floor space available: $\scriptsize 30x+40y\le 400$
Maximum type A tables: $\scriptsize x\le 8$
Maximum type B tables: $\scriptsize y\le 6$
At most two type A tables for each type B table: $\scriptsize 2x\ge y$
2. Feasible region is bound by points $\scriptsize A$, $\scriptsize B$, $\scriptsize C$, $\scriptsize D$ and $\scriptsize E$.
3. .
\scriptsize \begin{align*}P & =x+y\\\therefore y & =-x+P\end{align*}
Maximum profit occurs when the objective function or search line passes through $\scriptsize C(8,4)$. Therefore, $\scriptsize 8$ units of table A and $\scriptsize 4$ units of table B should be made to maximise profit.

.
Visit the interactive solution.
.
2. .
1. Number of jackets is $\scriptsize x$, $\scriptsize x\in \mathbb{N}$
Number of jerseys is $\scriptsize y$, $\scriptsize y\in \mathbb{N}$
Maximum jackets: $\scriptsize x\le 60$
Maximum jerseys: $\scriptsize y\le 40$
Maximum pieces of clothing: $\scriptsize x+y\le 70$
Working hours available: $\scriptsize 5x+10y\le 500$
2. Feasible region is bound by points $\scriptsize A$, $\scriptsize B$, $\scriptsize C$, $\scriptsize D$, $\scriptsize E$ and $\scriptsize F$.
3. $\scriptsize P=15x+25y$
4. .
\scriptsize \begin{align*} P&=15x+25y\\ \therefore 25y&=-15x+P\\ \therefore y&=-\displaystyle \frac{3}{5}x+\displaystyle \frac{P}{25}\end{align*}
Profit is at a maximum when the objective function of the search line passes through $\scriptsize D(40,30)$.
5. .
\scriptsize \begin{align*} P&=15(40)+25(30)\\&=600+750\\&=1~350\end{align*}
The maximum profit is $\scriptsize \text{R}1\ 350.00$.
.
Visit the interactive solution.
.
3. .
1. Number of model A trucks is $\scriptsize x$, $\scriptsize x\in \mathbb{N}$
Number of model B trucks is $\scriptsize y$, $\scriptsize y\in \mathbb{N}$
Maximum number of trucks: $\scriptsize x+y\le 15$
Minimum shipping capacity: $\scriptsize 2x+3y\ge 36$
2. Feasible region is bound by points $\scriptsize A$, $\scriptsize B$ and $\scriptsize C$.
3. The total cost of the trucks will be $\scriptsize C=150\ 000x+240\ 000y$. To plot and minimise this objective function we get it into standard form.
\scriptsize \displaystyle \begin{align*}C & =150\ 000x+240\ 000y\\\therefore 240\ 000y & =-150\ 000x+C\\\therefore y & =-\displaystyle \frac{5}{8}x+\displaystyle \frac{C}{{240\ 000}}\end{align*}
Cost is at a minimum when the objective function passes through $\scriptsize B(9,6)$. $\scriptsize 9$ model A trucks and $\scriptsize 6$ model B trucks should be purchased to minimise the cost.
4. .
\scriptsize \begin{align*}C&=150~000(9)+240~000(6)\\&=1~350~000+1~440~000\\&=2~790~000\end{align*}
The minimum cost will be $\scriptsize \text{R}2\ 790\ 000$.
.
Visit the interactive solution.
.

Back to Unit 1: Assessment