Revision:Linear Programming

TSR Wiki > Study Help > Subjects and Revision > Revision Notes > Mathematics > Linear Programming

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

Formulating the problem

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

Example

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

Constraints

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

Graphically

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:

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:

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

Also See

See the other D1 notes:

1. Algorithms
2. Sorting algorithms
3. Packing algorithms
4. Graphs and networks
5. Minimum connector problems
6. The shortest path
7. Route inspection
8. The travelling salesman problem
9. Linear programming
10. The simplex algorithm

Comments