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?
- Let x be the number of widget X produced.
- Let y be the number of widget Y produced.
These are the non negativity constraints
6 hours of X plus 4 hours of Y must total less than 1700
At most, 400 of each item can be produced
The feasible area is shown on the graph below.
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).
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:
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:
See the other D1 notes:
- Sorting algorithms
- Packing algorithms
- Graphs and networks
- Minimum connector problems
- The shortest path
- Route inspection
- The travelling salesman problem
- Linear programming
- The simplex algorithm