Further Maths - Simplex Algorithm
See Also
Flashcards
2022-03-30
When writing a linear programming problem in standard form for simplex, how can you convert a “minimising” into a “maximising”??
Multiply by $-1$.
What sort of constraints must be used for simplex, $\le$ or $\ge$??
\[\le\]When writing a linear programming problem in standard form for simplex, how can you convert a $f(x, y) \ge …$ into a $\le$ constraint?
Multiply by $-1$
\[-f(x, y) \le ...\]What must be true about all variables in the simplex method?
They must be $\ge$ $0$.
How would you change “maximise $P = 3x + 2y$” for the simplex algorithm?
Rearrange to
\[P - 3x - 2y = 0\]
Where do you look for the pivot value?
Where do you look for the pivot value?In the column with the most negative value on the objective row.
When there are no negatives in the objective row of a simplex tableau, how do you find the optimal solution?
Pick the biggest number.
\[2x + 2y + 5z \le 60\]
How could you rewrite this using a slack variable?
What is true about all the slack variables ($r, s…$) when using the simplex method?
They are greater than or equal to $0$.
How can you spot that $P, R, S$ are basis columns?
How can you spot that $P, R, S$ are basis columns?They contain just one $1$ and the rest are $0$.
How can you read off the solution represented by a tableau?
How can you read off the solution represented by a tableau?Look for the values of the basis variables.
What is the value of the basis variable $r$ here?
What is the value of the basis variable $r$ here? The variable $x$ here is non-basic. What does that mean its value is?
The variable $x$ here is non-basic. What does that mean its value is?
$z$ has been identified as the pivot column. What are you dividing and trying to minimise in order to find the pivot row?
$z$ has been identified as the pivot column. What are you dividing and trying to minimise in order to find the pivot row?The final value (e.g. $60$) and the non-negative values in the pivot column (e.g. $5$).
When determining the pivot row by dividing $60/5$ or $56/2$, are you looking for the biggest number or the smallest number?
When determining the pivot row by dividing $60/5$ or $56/2$, are you looking for the biggest number or the smallest number?The smallest number.
Once you’ve found the pivot value (here $5$), what do you do when constructing the next tableau?
Once you’ve found the pivot value (here $5$), what do you do when constructing the next tableau?Write that row but divide all entries by the pivot value.
When constructing a new tableau in the simplex algorithm, what are you effectively doing?
Trying to turn a non-basic variable into a basic variable.
You’re creating a new tableau in the simplex algorithm in order to turn $z$ into a basic variable. This means that you’re going to need just one $1$ and the rest of the entries are going to be $0$. What do you add together to make the top row have a zero?
You’re creating a new tableau in the simplex algorithm in order to turn $z$ into a basic variable. This means that you’re going to need just one $1$ and the rest of the entries are going to be $0$. What do you add together to make the top row have a zero?2022-03-31
What trick can you use to prevent errors when working out the rows of a new tableau in the simplex algorithm?
Write zeroes where you know they should exist.
2022-04-06
What do you do if there is a division by zero in the objective column in simplex?
Ignore it.
\[x + y \ge 800\]
How would you rewrite this for two-stage simplex?
\[x + y - s _ 1 + a = 800\]
What is the name of a variable like $s _ 1$?
A surplus variable.
Why must artificial variables be introduced in two-stage simplex?
So that there is a basic variable in that row.
What additional objective function do you have for two-stage simplex?
Maximise $I = -(a _ 1 + a _ 2 + a _ 3 + \ldots)$
Why is the first step of minimising the artificial variables necessary in two-stage simplex?
Minimising the artificial variables gets you to a point in the feasible region.
Why do greater than or equal to constraints like $x \ge 0$ cause an issue when using the simplex algorithm?
Because it means the origin is not in the feasible region.
When can you remove the artificial variables in two-stage simplex and move onto the next stage?
When they are all basic variables.
What is the advantage of the big M method?
You can do both stages of two-stage simplex at once.
What do you subtract from the initial objective function when using the big M method?
When can you remove the artificial variable columns when using the big M method?
When the $M$ terms are only in the artificial variable columns.
Once there are only $M$s in the artificial variable columns, what can you do?
Remove the columns.
How can you find an expression for $A$ when subtracting $MA$ from the objective function?
$A$ is equal to the sum of the artificial variables.
How can you get a solution to a linear programming problem using the big M method if there is still $M$ in the columns?
$M$ might be in all the non-basic columns, which will be $0$.
Once there’s only $M$s in non-basic columns, what do you do?
Rewrite the tableau with the artificial columns removed.
What do you do if there is a negative number during the ratio test for simplex?
Ignore it.
2022-04-30
\[3x - 2y - 2z \ge 0\]
Yuck, greater-than constraints in simplex are annoying. Why can you multiply both sides by $-1$ in this case to get a less-than constraint?
Because the origin is still in the feasible region.
\[-x-y \le -1\]
Why does this need to be changed to a greater-than constraint in order to use simplex?
Because it means that the origin is not in the feasible region.
What is the golden rule for knowing whether to use a surplus and artificial variable for a constraint in simplex?
“Does this take the origin out of the feasible region?”
2022-05-03
Why can’t simplex be used here?
Why can’t simplex be used here?Because the only negative value in the objective row is in column $z$, and all values in this column are negative and so are ignored when doing the ratio test.
How could you determine the profit equation given this tableau?
How could you determine the profit equation given this tableau?