Revision:Linear programming

Linear programming is a method of solving problems involving maximising or minimising conditions that have a linear relationship.

Formulating the problem

  • Define control variables (typically quantities of X and Y)
  • Define the objective function - what is it you are trying to maximise/minimise?
  • Write the constraints as inequalities in terms of the control variables (Often non negativity constraints will be required)
  • Solve graphically


Acme Corp is making two widgets, X and Y. Widget X takes 6 hours to assemble; Acme makes £12 profit on it. Widget Y takes 4 hours to assemble; Acme makes £6 profit on it.

Due to limitations of the availability of components, at most of 400 of each item can be produced. 1700 assembly hours are available. How can profit be maximised?

Control variables

  • Let x be the number of widget X produced.
  • Let y be the number of widget Y produced.

Objective function

Maximise 12x + 6y


  • x \geq 0
  • y \geq 0

These are the non negativity constraints

  • 6x + 4y \leq 1700

6 hours of X plus 4 hours of Y must total less than 1700

  • x \leq 400
  • y \leq 400

At most, 400 of each item can be produced


The feasible area is shown on the graph below.

Linear programming

Profit is maximised at one of the corners of the feasible region (the nodes). To find out which one, consider the objective function. Draw on a line with the gradient of the objective function (in this case, -2). As you move the line closer to the feasible region, which node will be hit first? This point is the one where profit is maximised. (Alternatively, plug the x and y values of the nodes into the objective function and choose the largest value).

Linear programming

In this case profit is maximised at (400, 250). Therefore, 400 of widget X and 250 of widget Y should be made. This would give a profit of £6300:

400 \times 12 + 250 \times 6 = 6300

Blending problems

You may be told that one component must be at least x% of the total product. For example, at least 30% orange juice in a juice drink. In this case formulate it as follows:

0.3x \geq x + y +z

Where x is the quantity of orange juice and x + y+ z is the total quantity of all ingredients.

Also See

See the other D1 notes: