# Further Maths - Simplex Algorithm

> Source: https://ollybritton.com/notes/a-level/further-maths/topics/simplex/ · Updated: 2024-08-24 · Tags: further-maths, a-level, school, decision

## See Also
- [Further Maths - Linear Programming](https://ollybritton.com/notes/a-level/further-maths/topics/linear-programming/)

## 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
$$

##### ![PHOTO WHERE PIVOT COLUMN](where-pivot-column.png) 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??
$$
2x + 2y + 5z + r = 60
$$

##### What is true about all the slack variables ($r, s...$) when using the simplex method??
They are greater than or equal to $0$.

##### ![PHOTO BASIS COLUMNS](basis-columns.png) How can you spot that $P, R, S$ are basis columns??
They contain just one $1$ and the rest are $0$.

##### ![PHOTO BASIS COLUMNS](basis-columns.png) How can you read off the solution represented by a tableau??
Look for the values of the basis variables.

##### ![PHOTO BASIS COLUMNS](basis-columns.png) What is the value of the basis variable $r$ here??
$$
60
$$

##### ![PHOTO BASIS COLUMNS](basis-columns.png) The variable $x$ here is non-basic. What does that mean its value is??
$$
0
$$

##### ![PHOTO FIND PIVOT ROW](find-pivot-row.png) $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$).

##### ![PHOTO FIND PIVOT ROW](find-pivot-row.png) 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.

##### ![PHOTO PIVOT IDENTIFIED](pivot-identified.png) 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.

![PHOTO NEW TABLEAU](new-tableau.png)

##### 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.

##### ![PHOTO HOW TO MAKE NEW ROW SIMPLEX](how-to-make-new-row-simplex.png) 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??
$$
r_1 + 5r_{a2}
$$

### 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
$$

##### $$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??
$$
-MA
$$

##### 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
##### ![PHOTO SIMPLEX TRICKY](paste-16093ea352c3aefeda35145c325ec3869a356946.jpg) 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.

##### ![PHOTO SIMPLEX TRICKY](paste-16093ea352c3aefeda35145c325ec3869a356946.jpg) How could you determine the profit equation given this tableau??
$$
P + \frac{78}{5}x - \frac{91}{5}z + \frac{12}{5}t = \frac{84}{5}
$$

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt