Results are out! Find what you need...fast. Get quick advice or join the chat
  • 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.

Contents

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 12x + 6y

Constraints

  • 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

Graphically

The feasible area is shown on the graph below.

Image:Linear Programming 1.jpg

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).

Image:Linear Programming 2.jpg

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:

  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

Try Learn together, TSR's study area

177,211
essays

22,239
mindmaps

25,482
revision notes

11,741
quizzes

create
a study planner

thousands
of discussions


New on TSR

Vote for your favourite Christmas film

Win a bundle of Xmas DVDs

Article updates