Linear programming is a way of solving problems to find the 'optimal solution'. For example, how many of each type of cupcake should be made to give maximum profit, given a limit on the amount of flour, eggs and cooking time available.
Vocabulary to know:
-Decision variable - x,y,z The amount of each thing being produced.
-Objective function - The thing you're trying to maximise (or minimise)
-Constraints - The factors that limit the problem (non-negativity constraints are often appropriate).
-Feasible solution - A solution that satisfies all the constraints.

You may be asked to formulate constraints from a wordy problem - just ensure you separate out the information you're given and then work out which way around the inequality sign should go.

When drawing a graph to find the feasible region (ie. if there are only two variables) shade the area you don't want, which will leave you with an unshaded area which satisfies all the constraints.

To find the optimal solution write out all the co-ordinates of the vertices of the feasible region - you may be able to see these by eye or have to solve the equations of each line that intersects simultaneously. Substitute all the co-ordinates into the objective function to get the value of the objective function at each point. Depending on if you're maximising or minimising the value the optimum value will be at the biggest or smallest number. Remember to write a statement giving x= and y=, don't just leave co-ordinates.

If the optimal solution requires that x and y be integer values, calculate the function for all the vertices as above but then look for points with integer values of x and y near to the optimum vertex.

Another way of calculating the optimum solution is to use the simplex method.
To do this use slack variables - these are just a way of turning inequalities into equations (if you know x+y+z is less than or equal to 20 then x+y+z+some variable (s) will equal 20 - even if the variable turns out to be 0). You use a different slack variable for each inequality.

The simplex method works as follows: (see example)
1) Turn the inequalities into equations using slack variables. Move the variables in the objective function onto the other side of the equation to get it equal to 0.
2) Set up a tableau with columns for P, x, y, z and the slack variables and a right-hand-side (RHS) column.
3) Choose a pivot column - this will either be given in the question or should be the a negative value in the top row (the most negative value will tend to solve the problem quicker).
4) Perform a ratio test by dividing each of the values in the RHS column by the corresponding value in the chosen pivot column. Choose the value in the pivot column which gives the smallest number in the ratio test. This is the 'pivot element'.
5) Divide the whole of the pivot row by the pivot element to make the new value of the pivot one - write this new row in a new tableau below the initial tableau.
6) Make all the other values in the pivot column 0 by adding or subtracting multiples of the new pivot row to each of the rows and write these in the new tableau.
7) Keep repeating these steps (4,5,6) until there are no more negative values in the top row.

The optimum value of P will be the RHS value in the top row.
To read off the values of the variables look down the column to find the 1 and across to the RHS value (if all the values in the column are 0s). If the values in the column are all random and jumbled then that variable equals 0.

This method works for the slack variables aswell - to interpret the slack variables in terms of the question look back to what that inequality represented, for example the time or the cost - if the slack variables aren't 0 it means there is spare capacity.

	Created by declanlarkins almost 11 years ago

	Copied by declanlarkins almost 11 years ago

	Copied by declanlarkins almost 11 years ago

OCR AS-Level / A-Level Contains all major spec points. COMPLETED

Mathematics: Decision 1 (Notes 1 of 1)