Linear Programming Flashcards
Which region should be shaded?
The region that does not satisfy the inequality.
What is the feasible region for a linear programming problem?
The region left unshaded (satisfies all inequalities).
How can you minimise/maximise the objective for a linear programming problem?
Find the optimum vertex:
- use the objective line method (use a ruler, draw AT LEAST ONE objective line)
- use the vertex testing method (test the value of the objective at each vertex)
How can you adjust a linear programming problem in order to use the simplex algorithm?
Turn the constraints into equations by introducing slack variables, and then displaying on a simplex tableau.
What are basic variables in a simplex tableau?
Appear only once in their column, have a value when in the final tableau.
What are non-basic variables in a simplex tableau?
Have coefficients in more than one row, have a value of 0 when in the final tableau.
How is the pivot column of a simplex tableau determined?
The pivot column is the column with the most negative value in the top row (objective row).
How is the pivot row of a simplex tableau determined?
The pivot row has the smallest positive ratio (non-zero).
ratio is the value of that row divided by the coefficient of the pivot column in that row
What are two cases for the optimal tableau?
If there are no negative values in the top row.
If all ratios in the pivot column are negative or 0, you cannot continue, the tableau is not feasible and there is no solution.
How can the simplex algorithm be used when the objective is to be Minimised?
If you need to minimise P, you can think of this as maximising -P.
What is a rule for setting up a simplex tableau involving the constants on the right side of the equations?
The constants must be non-negative.
What should you do if two ratios in the pivot column are tied?
Either can be used, but protocol is to use the one higher up the tableau.
What should you do if the tableau gives decimal values, but shouldn’t?
Test all nearby integer values for the decimal answers, making sure they satisfy the constraints, and plug them in to the objective function to see which one gives the best answer.
