Linear Programming

HideShow resource information

formulating the problem

The Decision Variable:

  • you must include the units of the quantities e.g. x = ml of orange juice not just x = orange juice 

The Constraints:

  •  These will be equations or inequalities 
  • Write the constraint out in words first before attempting the equations
  •   Non- negativity constraints: can your decision variable be negative values (not in most cases)
  •   Integer constraints: do your values have to be whole numbers if so you must put in your constraints as integers. Such as when your problem involves people

The Objective Function:

  • This will be to minimise (costs) or maximise (profit)
  • You must use one of these words before your equations


1 of 3

Solving the Problem

There are two methods: 

  • the vertex method 
  • the ruler method

For either you must plot, line and shade for very constraint __ for     and --- for < >

  • Remember that you shade the side of the line that you don’t want. The feasible region will be left unshaded

The Ruler Method:

  • draw a line onto the graph to represent the objective function
  • do this by setting the objective function equal to a sensible number and finding where they cross the axes 
  • move the rule parallel to the objective function until it reaches the optimal vertex of the feasible region  
  • - if maximising this will be the furthest vertex from the origin that you get to
  • - if minimising  this will be the closest vertex to the origin that you get to
  • once you’ve identified this vertex workout its coordinate by solving simultaneous equations 
2 of 3

Solving the Problem

The vertex method 

  • Workout the value of x and y at each corner of the feasible region
  • If you don’t know the coordinates use the simultaneous equations of the lines that meet there
  • Work out the objective function of each vertex, choose the best one as your answer (depending on whether you need to minimise or maximise

 If the answer needs to an integer consider all the possible integer pairs around this coordinate, but inside the feasible region. 

3 of 3


No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all Networks, algorithms and problem solving resources »