D1, C7 - This Simplex Algorithm

Question 1

How do you turn inequalities into equations when formulating linear programming problems (what is added)

Answer 1

Add a slack variable

Question 2

Rewrite the inequality x1 + 3x2 + 5x3 <= 23 using the slack variable, r

Answer 2

x1 + 3x2 + 5x3 + r = 23

Question 3

What does the simplex algorithm do

Answer 3

Finds the optimal solution to a linear programming problem

Question 4

When would we use the simplex method

Answer 4

When you have more than 2 variables (x, y, z, …)

Question 5

What are the steps of the simplex algorithm

Answer 5

1) Write in standard form
2) Set up tableau
3) Are there -ve’s on bottom row (No = optimal solution, yes –> step 4)
4) Select largest -ve as pivot column
5) Are there -ve’s in pivot column (No = optimal solution, yes = step 6)
6) Select pivot element and do pivot operations
7) Return to step 3 and repeat

Question 6

What is the significance of slack variables in graphical representations of linear programming problems

Answer 6

The borders of the feasible region are when all of the variables (including slack) are equal to zero [x, y, r, s = 0]

Question 7

How would you write the following in the ‘standard form’ for the simplex algorithm?
P = 3x + 2y
5x + 7y >= 70

Answer 7

P - 3x - 2y = 0
5x + 7y + r = 70

Question 8

How would you write an equation for minimising P = 3x - y in ‘standard form’

Answer 8

Multiply all by -1 to make it a ‘maximising’ equation
-P = -3x + y
Q + 3x - y = 0

Question 9

How do you find integer solutions to maximising functions

Answer 9

Consider the box of integer coordinate points around the optimal solution
If all constraints are valid, coordinate is correct

Question 10

When more than one integer coordinate point satisfy all of the constraints, how do you determine the optimal solution

Answer 10

Sub in all values into maximising function and highest value of P is maximising coordinate

Question 11

When do we use the two-stage simplex method

Answer 11

When we have >= constraints

Question 12

What happens to slack variables in the two-stage simplex method

Answer 12

They become surplus variables
(subtracted from inequality)
…-s1 …-s2 …-s3

Question 13

How do you avoid surplus variables being negative

Answer 13

Add on an artificial variable
…+a1 …a2 …+a3

Question 14

What are the steps of the two-stage simplex algorithm

Answer 14

Stage 1
1) Slack variables become surplus variables
2) To avoid surplus variables becoming -ve, add artificial variables
3) Create a temporary objective function I, to minimise sum of the artificial variables (a1 + a2 + a3 + …)
4) Apply simplex algorithm to get I = 0, if I not equal to 0, no feasible solution

Stage 2
1) Remove artificial variables from tableau and apply the simplex algorithm

Question 15

What happens if I cannot be equal to 0

Answer 15

No feasible solution to two-stage simplex algorithm

Question 16

Use surplus and artificial variables to write the following inequalities as equations:
3x - 27 >= 7
4x + 5y - 3z >=9

Answer 16

3x - 2y - s1 + a1 = 7
4x + 5y - 3z - s2 + a2 = 9

Question 17

What is equivalent to minimising I = a1 + a2

Answer 17

Maximising I = -(a1 + a2)

Question 18

Maximise P = 3x - 2y + z, subject to
x + y + 2z <= 10
2x - 3y + z >= 5
x + y >= 8
x, y, z >= 0
What would the equation for minimising I equal

Answer 18

Formulae containing artificial variables:
2x - 3y + z - s2 + a1 = 5
x + y - s3 + a2 = 8
Minimise sum of artificial variables:
I = a1 + a2
Equivalent to maximising:
I = -(a1 + a2)
a1 = 5 - 2x + 3y - z + s2
a2 = 8 - x - y + s3
Max I = -(13 - 3x + 2y - z + s2 + s3)
Max I - 3x + 2y - z + s2 + s3 = -13

Question 19

What does M stand for

Answer 19

An arbitrarily big number

Question 20

How is the Big-M method different to the two-stage simplex method

Answer 20

You can reduce the two-stage method to one stage

Question 21

How would you write maximise P = 3x - 2y using the Big-M methos

Answer 21

Max P = 3x - 2y - M(a1 + a2 + …)

Question 22

When will the maximum of P occur when using the Big M method

Answer 22

When M(a1 + a2 + …) = 0
(sum of artificial variables = 0)

Question 23

When maximising and minimising P do you add or subtract M(sum of artificial variables)

Answer 23

Max –> - M(a1 + …)
Min –> + M(a1 + …)

Question 24

Using the Big M method how would you write out:
Maximise P = x - y + z subject to:
2x + y + z <= 20
x - 2y - z <= 7
x >= 4
x, y, z >= 0

Answer 24

2x + y + z + S1 = 20
x - 2y - z + S2 = 7
x - S3 + a1 = 4
Max P = x - y + z - M(a1)

Question 25

How would you rearrange Max P + x - y + z - M(a1) if you know
x - S3 + a1 = 4

Answer 25

a1 = 4 - x + S3
P = x - y + z - M(4 - x + S3)
P = (1 + M)x - y + z - 4M - MS3
P - (1+M)x + y - z + MS3 = - 4M

Question 26

If you pivot value is 1, how would you get -(1+M) to equal 0 using multiples of the pivot value

Answer 26

-(1+M) + (1+M)1
Row 2 + (1+M)Row 1

Question 27

Which column do you pick as your pivot if multiple have the same -ve value

Answer 27

It doesn’t matter

Question 28

Is (-1 + M) negative

Answer 28

No, M is huge