Linear Programming - Constraints and Objectives

Certain real-world problems arise where, subject to constraints on time and materials, the cost of production (or alternatively the profit produced from production) of manufactured goods and/or services needs to be optimised. 

Such problems are referred to as linear programming problems when the constraints can be conceived as linearly varying quantities.

1. A typical problem

The best way to examine the linear programming technique is to consider a hypothetical example. 

Imagine a recycling company that needs to buy two types of waste bins. The 'Bin-it' bin costs $$100$100 each but the 'Fill-it-up' bin costs twice as much, and the amount available for purchases has to be no more than $$1400$1400. The Bin-it bins take up $6$6 square metres of factory yard space and can hold $8$8 cubic metres of recyclable waste. The more expensive bins take up $8$8 square metres of space but can hold $12$12 cubic metres of waste. The yard is fairly small, confined to $72$72 square metres of useable area. How many of each bin type should you buy to maximise the total recycling storage?

2. Defining the variables

The first thing you might notice is that the information in the question is dense, and can be off-putting on a first read. So its a good first strategy to simply re-read the question.

The last sentence provides the question - how many of each type to buy. So we can define two variables, say $x$x and $y$y as follows:

Let $x$x be the number of Bin-it bins

Let $y$y be the number of Fill it up bins 

3. Identifying the constraints

If we had lots of money and lots of space we could buy lots of bins of each type. From what we are told, however, we are constrained by both money and space. The next task then is to develop some mathematical expressions that summarise these constraints.  

Note first that if we were to buy $x$x Bin-it bins, the cost would be $$100x$100x, and if we were to buy $y$y Fill-it-up bins the cost of those would be $$200y$200y. This means that the total cost of $x$x Bin-it bins and $y$y Fill-it-up bins would be the sum $100x+200y$100x+200y, and this must not exceed our limit of $$1400$1400. Our first constraint then is given as $100x+200y\le1400$100x+200y≤1400.

Secondly, our yard space is limited. From what we are told, buying $x$x Bin-it bins will take up $6x$6x metres of yard space and buying $y$y Fill-it-up bins will take up $8y$8y metres of yard space. Since there is a maximum space of $72$72 square metres, we can write $6x+8y\le72$6x+8y≤72. 

Finally, we note the obvious that the quantities $x$x and $y$y cannot be negative numbers. We can write these constraints as $x\ge0$x≥0 and $y\ge0$y≥0. 

So in summary the constraints are listed in the table:

 

$100x+200y\le1400$100x+200y≤1400	(1)
$6x+8y\le72$6x+8y≤72	(2)
$x\ge0$x≥0	(3)
$y\ge0$y≥0	(4)

 

4. Identifying the objective function

We now need to identify what is the objective function. We need to maximise the storage of recycling material. If we call the total storage $S$S, then since $x$x Bin-it bins store $8x$8x cubic metres, and $y$y Fill-it-up bins store $12y$12y cubic metres, then we can write:

$S=8x+12y$S=8x+12y

Worked Examples

Question 1

Question 2

Question 3