We think you are located in South Africa. Is this correct?

Introduction

Chapter 12: Linear programming

12.1 Introduction

  • This chapter has been included for enrichment/projects.

In everyday life people are interested in knowing the most efficient way of carrying out a task or achieving a goal. For example, a farmer wants to know how many hectares to plant during a season in order to maximise the yield (produce), a stock broker wants to know how much to invest in stocks in order to maximise profit, an entrepreneur wants to know how many people to employ to minimise expenditure. These are optimisation problems; we want to to determine either the maximum or the minimum in a specific situation.

To describe this mathematically, we assign variables to represent the different factors that influence the situation. Optimisation means finding the combination of variables that gives the best result.

Worked example 1: Mountees and Roadees

Investigate the following situation and use your knowledge of mathematics to solve the problem:

Mr. Hunter manufactures bicycles. He produces two different models of bicycles; strong mountain bikes called Mountees and fast road bikes called Roadees. He cannot produce more than Mountees on a day and he can manufacture a maximum of Roadees a day. He needs technician to assemble a Mountee and technicians to assemble a Roadee. The company has technicians in the assembly department. The profit on a Mountee is and on a Roadee. The demand is such that he can sell all the bikes he manufactures.

Determine the number of each model of bicycle that must be manufactured in order to make the maximum profit.

Assign variables

In this situation there are two variables that we need to consider: let the number of Mountees produced be and let the number of Roadees produced be .

Organise the information given

Write down a summary of the information given in the problem so that we consider all the different components in the situation.

Draw up a table

Use the summary to draw up a table of all the possible combinations of the number of Mountees and Roadees that can be manufactured per day:

Note that there are possible combinations.

Consider the limitation of the number of technicians

It takes technician to assemble a Mountee and technicians to assemble a Roadee. There are a total of technicians in the assembly department, therefore we can write that .

With this limitation, we are able to eliminate some of the combinations in the table where :

These combinations have been excluded as possible answers. For example, gives technicians.

Consider the profit on the bicycles

We can express the profit () per day as: . Notice that a higher profit is made on a Roadee.

By substituting the different combinations for and , we can find the values that give the maximum profit:

Write the final answer

Therefore the maximum profit of is obtained if Mountees and Roadees are manufactured per day.

Exercise 12.1 See solutions

Furniture store opening special:

As part of their opening special, a furniture store has promised to give away at least prizes with a total value of at least . They intend to give away kettles and toasters. They decide there will be at least units of each prize. A kettle costs the company and a toaster costs .

Determine how many of each prize will represent the cheapest option for the company. Calculate how much this combination of kettles and toasters will cost.

Use a suitable strategy to organise the information and solve the problem.

In this situation there are two variables that we need to consider: let the number of kettles produced be and let the number of toasters produced be .

Write down a summary of the information given in the problem so that we consider all the different components in the situation.

Use the summary to draw up a table of the number of kettles and toasters that are needed. We will consider multiples of 5 to simplify the calculations:

We need to have at least kettles and toasters together.

With this limitation, we are able to eliminate some of the combinations in the table where :

These combinations have been excluded as possible answers.

We can express the minimum cost as: .

By substituting the different combinations for and , we can find the value that gives the minimum cost.

We are looking for a pair of values that give the minimum cost. We can easily check the non-multiples of 5 for kettles and toasters to confirm that kettles and toasters meet the minimum cost.

For example if kettles and toasters are given away, the cost will be . And if kettles and toasters are given away, the cost will be .

The minimum cost of can be obtained if kettles and toasters are given away. This will result in a cost of .

See solutions

Optimisation using graphs

A more efficient way to solve optimisation problems is using graphs.

We write the limitations in the situation, called constraints, as inequalities. Some constraints can be modelled by an equation, which needs to be maximised or minimized. We sketch the inequalities and indicate the region above or below the line that is to be considered in determining the solution. This method of solving optimisation problems is called linear programming.

Worked example 2: Optimisation using graphs

Consider again the example of Mr. Hunter who manufactures Mountees and Roadees:

Mr. Hunter manufactures bicycles. He produces two different models of bicycles; strong mountain bikes called Mountees and fast road bikes called Roadees. He cannot produce more than Mountees on a day and he can manufacture a maximum of Roadees a day. He needs technician to assemble a Mountee and technicians to assemble a Roadee. The company has technicians in the assembly department. The profit on a Mountee is and on a Roadee. The demand is such that he can sell all the bikes he manufactures.

Determine the number of each model of bicycle that must be manufactured in order to make a maximum profit.

Assign variables

In this situation there are two variables that we need to consider: let the number of Mountees produced be and let the number of Roadees produced be .

Notice that the values of and are limited to positive integers; Mr. Hunter cannot sell negative numbers of bikes nor can he sell a fraction of a bike.

Organise the information

We can write these constraints as inequalities:

We also know that . This is called the objective function, sometimes also referred to as the search line, because the objective (goal) is to determine the maximum value of .

Solve using graphs

We represent the number of Mountees manufactured daily on the horizontal axis and the number of Roadees manufactured daily on the vertical axis. Since and are positive integers, we only use the first quadrant of the Cartesian plane. Note that the graph only includes the integer values of between and and between and .201c56771900cd7d4c6711bed6f20fd8.png

For the number of technicians in the assembly department . If we make (represented on the -axis) the subject of the inequality we get .ba82faee1adc3e5ef613872538bcc3c5.png

The arrows indicate the region in which the solution will lie, where . This area is called the feasible region.706fc630d35e6b72cecc77356e27b526.png

We substitute the possible combinations into the profit equation , and find the combination that gives the maximum profit.

Write the final answer

Therefore the maximum profit is obtained if Mountees and Roadees are manufactured per day.

Worked example 3: Optimisation using graphs

Solve the “furniture store opening special” problem using graphs:

As part of their opening special, a furniture store has promised to give away at least prizes. They intend to give away kettles and toasters. They decide there will be at least units of each prize. A kettle costs the company and a toaster costs .

Determine how many of each prize will represent the cheapest option for the company. Calculate how much this combination of kettles and toasters will cost.

Assign variables

In this situation there are two variables that we need to consider: let the number of kettles be and the number of toasters be , with .

Organise the information

We can write the given information as inequalities:

We make the subject of the inequality:

Solve using graphs

Represent the constraints on a set of axes:e590fb4f3c56fdf071615c86a0693e25.png

We shade the feasible region as shown in the diagram. Remember that in this situation only the points with integer coordinates inside or on the border of the feasible region are possible solutions. The combination giving the minimum cost will lie towards or on the lower border of the feasible region, which gives us many points to consider. To find the optimum value of , we use the graph of the objective function

To draw the line, we make the subject of the formula

We see that the gradient of the objective function is , but we do not know the exact value of the -intercept (). To find the minimum value of , we need to determine the position of the objective function where it first touches the feasible region and also gives the lowest -intercept.f4f974926f1f9ac7aaa06fe39593254a.png

We indicate the gradient of the objective function on the graph (the green search line). Keeping the gradient the same, we “slide” the objective function towards the lower border of the feasible region and find that it touches the feasible region at point . This optimum position of the objective function is indicated on the graph by the dotted line passing through point .

We substitute the coordinates of into the cost equation :

The minimum cost can also be determined graphically by reading off the coordinates of the -intercept of the objective function in the optimum position:

Write the final answer

Therefore the minimum cost to the company is with kettles and toasters.