Simplex Algorithm Flashcards Preview

A Level Further Maths Decision 1 > Simplex Algorithm > Flashcards

Flashcards in Simplex Algorithm Deck (11)
Loading flashcards...

Formulating a problem

Form as a table
Add a slack variable and make them equal to the maximum



Basic Variable | Variables | Slack Variables | Value | Row Ops


Setting up the initial tableau

Rewrite the maximise P = ... as P - ... = 0
Write in the coefficients of every variable/slack variable in the columns and P in the basic variable


Solving the problem

Identify the most negative value in the profit equation and label as your pivot
Calculate value/pivot for each row and choose the smallest positive value
Divide the entire row by the pivot and write the variable of the pivot in that rows basic variable box
Add/subtract multiples of that row from others so the pivot column contains a 0
Repeat until there are no negatives in the pivot row


Simplex answers

Where a variable has one 1 and the others 0, it takes the value of the output of the row with a 1
Where a variable has more than 1 non-zero, it is 0


Setting up equations

When the sign is <= add a slack variable and set the sign to =
When the sign is >= subtract a surplus variable, add an artificial variable and set the sign to =


Two-step simplex set up

1. Change your inequalities to equations
2. Minimise a1 + a2 + ... so maximise I = -a1 - a2 - ...
3. Rearrange the inequalities in terms of -a1, -a1... and substitute in
4. Rearrange the I equation so it is equal to a number


Two-step simplex tables

1. Carry out the simplex regularly with the I row
2. If at the end I = 0, it is possible, delete the artificial columns as they are 0 and the I row and use simplex for the Profit function
3. If I is not equal to 0, then the artificial variables are non-zero and it can't be solved


Surplus variable definition

The amount by which a solution exceeds the minimum value of a quantity


Big M Method

Let M represent an arbitrarily large number
1. Set up each constraint by adding slack, surplus, artificial variables
2. Subtract M(a1+a2+…) from the objective
3. Rearrange to equal a number and group each coefficient
4. Solve as you would a regular simplex problem
Can be solved in a calculator by using M as 1000 e.g


Big M minimise

Add M(a1+a2+…) instead of subtracting