Simplex Algorithm

Question 1

Formulating a problem

Answer 1

Form as a table

Add a slack variable and make them equal to the maximum

Question 2

Tableau

Answer 2

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

Question 3

Setting up the initial tableau

Answer 3

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

Question 4

Solving the problem

Answer 4

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

Question 5

Simplex answers

Answer 5

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

Question 6

Setting up equations

Answer 6

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 =

Question 7

Two-step simplex set up

Answer 7

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

Question 8

Two-step simplex tables

Answer 8

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

Question 9

Surplus variable definition

Answer 9

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

Question 10

Big M Method

Answer 10

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

Question 11

Big M minimise

Answer 11

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

Question 12

Simplex minimise P

Answer 12

Maximise Q = -P