Linear Programming Flashcards
When is linear programming used?
For optimising the value of an algebraic function e.g. maximising profit/ minimising cost
Product X uses 2kg of wood and 1kg of paint. Product Y uses 4kg of wood and 3kg of paint. Each day 30kg of wood and 15kg of paint are available. What are the constraints on this problem?
2x+4y=<30
x+3y=<15
Once the constraints have been decided, how do you solve a linear programming problem?
Graph the constraints, shading out the areas excluded by them. Test the points (usually the corners) within the unshaded region to see which values of x and y optimise the objective.
If the values of x and y must be integers, but the graphs intersect at decimal values, what should you do?
Pick the point closest to the point of intersection where both x and y are integers
In blending problems (the amounts are as percentages), how do you adapt the way you form the constraints?
Express the percentages as decimals in the constraint inequalities
If you have simplified the constraints to make the graphs simpler to draw, what must you remember to do?
Use the un-simplified constraints when finding the optimum values of x and y to input into the objective function
What is the objective function?
The function which is to be optimised, usually expressed as P=ax+by
Why can’t linear programming optimise objective functions with three or more terms?
Because it is not possible to draw a 3D graph
What is used if you need to optimise a function with three or more terms?
The Simplex algorithm
Why are slack variables used in the Simplex Algorithm?
To change the inequalities into equations
How do you choose the pivot in a simplex tableau?
Look at all the columns which have a negative value in their top rows. For each value in these columns, divide the right-hand side of the equation by this value. The value which produces the smallest positive value of this division is the pivot
How do you perform the simplex algorithm on a simplex tableau once the pivot row has been found?
Divide the pivot row by the value of the pivot and write these new values into the new tableau. Perform functions with multiples of the pivot row OR the new row to transform all the remaining rows such that the value in the pivot column is zero; write these new rows into the new tableau.
How do you read the results from a simplex tableau?
Look through the x column. If there is a 1 in the column, the value in the corresponding “RHS” column is the value of x. If there is no 1, the value of x is zero. Repeat for all non-slack variables. Use the values of each variable to find the optimum value of the objective.
