0.10 Linear programming

Introduction

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 might want toknow how many crops to plant during a season in order to maximise yield (produce) or a stock broker might want to know how much to invest in stocks in order to maximise profit. These are examples of optimisation problems, where by optimising we mean finding the maxima or minima of a function.

You will see optimisation problems of one variable in Grade 12, where there were no restrictions to the answer. You will be required to find the highest (maximum) or lowest (minimum) possible value of some function. In this chapter we look at optimisation problems with two variables and where the possible solutions are restricted.

Terminology

There are some basic terms which you need to become familiar with for the linear programming chapters.

Decision variables

The aim of an optimisation problem is to find the values of the decision variables. These values are unknown at the beginning of the problem. Decision variables usually represent things that can be changed, for example the rate at which water is consumed or the number of birds living in a certain park.

Objective function

The objective function is a mathematical combination of the decision variables and represents the function that we want to optimise (i.e. maximise or minimise). We will only be looking at objective functions which are functions of two variables. For example, in the case of the farmer, the objective function is the yield and it is dependent on the amount of crops planted. If the farmer has two crops then the objective function $f(x,y)$ is the yield, where $x$ represents the amount of the first crop planted and $y$ represents the amount of the second crop planted. For the stock broker, assuming that there are two stocks to invest in, the objective function $f(x,y)$ is the amount of profit earned by investing $x$ rand in the first stock and $y$ rand in the second.

Constraints

Constraints , or restrictions , are often placed on the variables being optimised. For the example of the farmer, he cannot plant a negative number of crops, therefore the constraints would be:

Other constraints might be that the farmer cannot plant more of the second crop than the first crop and that no more than 20 units of the first crop can be planted. These constraints can be written as:

Constraints that have the form

or

are called linear constraints. Examples of linear constraints are:

Feasible region and points

Constraints mean that we cannot just take any $x$ and $y$ when looking for the $x$ and $y$ that optimise our objective function. If we think of the variables $x$ and $y$ as a point $(x,y)$ in the $xy$ -plane then we call the set of all points in the $xy$ -plane that satisfy our constraints the feasible region . Any point in the feasible region is called a feasible point .

For example, the constraints

mean that only values of $x$ and $y$ that are positive are allowed. Similarly, the constraint