J E Beasley

OR-Notes are a series of introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

A full list of the topics available in OR-Notes can be found here.

Linear programming tutorial solution



x1 = number of bags of granulated cement produced per day

x2 = number of bags of powdered cement produced per day

and note that x1 >= 0 and x2 >= 0.

Although (strictly) both x1 and x2 should only take integer values they are likely to be quite large and so we will let them take fractional values and ignore any fractional parts in the numerical solution.

Note too that the question explicitly asks us to formulate the problem as an LP rather than as an integer program (IP).


x1 + x2 <= 1600

x2 >= 500

0.48x1 + 0.24x2 <= 8(60) or 2x1 + x2 <= 2000


Presumably the objective is to maximise profit, which is given by 4x1 + 3x2 (£)

The graphical representation of this LP is shown below and the optimal solution occurs at the intersection of x1 + x2 = 1600 and 2x1 + x2 = 2000 i.e. at x1 = 400, x2 = 1200.

Hence the cement manufacturer should produce 400 bags of granulated cement and 1200 bags of powdered cement per day giving a profit of £5200 (per day).

Note here that it so happened that at the optimal solution the variables were integer and so we did not have to worry about any fractional parts (this was just good luck and we could not have forecast this beforehand).