OR-Notes

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

Variables

Let

x₁ = number of bags of granulated cement produced per day

x₂ = number of bags of powdered cement produced per day

and note that x₁ >= 0 and x₂ >= 0.

Although (strictly) both x₁ and x₂ 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).

Constraints

• the capacity of the plant is restricted to be 1600 bags per day

x₁ + x₂ <= 1600

• we must produce at least 500 bags of powdered cement per day

x₂ >= 500

• we have a time restriction - one bag of powdered cement takes 0.24 minutes to make and one bag of granulated cement twice as long (i.e. 0.48 minutes). Given that we are working an 8 hour day the time constraint is

0.48x₁ + 0.24x₂ <= 8(60) or 2x₁ + x₂ <= 2000

Objective

Presumably the objective is to maximise profit, which is given by 4x₁ + 3x₂ (£)

The graphical representation of this LP is shown below and the optimal solution occurs at the intersection of x₁ + x₂ = 1600 and 2x₁ + x₂ = 2000 i.e. at x₁ = 400, x₂ = 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).