7. Simplex Algorithm

Question 1

How can inequalities be transformed into equations?

Answer 1

Using slack variables

Question 2

What are slack variables?

Answer 2

Represent the amount of ‘slack’ between an actual quantity and the maximum possible value of that quantity

Question 3

What 2 things does the simplex algorithm allow you to do?

Answer 3

1. Determine if a particular vertex (on the edge of feasible region) is optimal
2. Decide which adjacent vertex you should move to in order to increase the value of the objective function

Question 4

Where does the simplex method start?

Answer 4

From a basic feasible solution, at the origin

Question 5

How does the simplex method progress with each iteration?

Answer 5

Moves to an adjacent point within the feasible region until optimal solution is found

Question 6

First step to solving a maximising linear programming problem using a simplex tableau

Answer 6

Draw the tableaux.

Basic variable column on the left, column for each variable (including slacks) and a value column.

One row for each constraint and bottom row for objective function.

Question 7

Second step to solving a maximising linear programming problem using a simplex tableau

Answer 7

Create the initial tableau.

Enter coefficients of variables in appropriate row and column.

Question 8

Third step to solving a maximising linear programming problem using a simplex tableau

Answer 8

Look along objective row for most negative entry which indicates the pivot column

Question 9

Fourth step to solving a maximising linear programming problem using a simplex tableau

Answer 9

Calculate the θ values for each of the constraint rows where θ = (term in value column) / (term in pivot column)

Question 10

Fifth step to solving a maximising linear programming problem using a simplex tableau

Answer 10

Select the row with the smallest, positive θ value to become the pivot row

Question 11

Sixth step to solving a maximising linear programming problem using a simplex tableau

Answer 11

The element in the pivot row and the pivot column is the pivot

Question 12

Seventh step to solving a maximising linear programming problem using a simplex tableau

Answer 12

Divide row found in step 5 by the pivot and change basic variable at start of row to variable at top of pivot column. This is now the pivot row.

Question 13

Eighth step to solving a maximising linear programming problem using a simplex tableau

Answer 13

Use pivot row to eliminate pivot’s variable from other rows. Pivot column now contains one 1 and zeros.

Question 14

Ninth step to solving a maximising linear programming problem using a simplex tableau

Answer 14

Repeat steps 3 to 8 until there are no more negative numbers in the objective row.

Question 15

Tenth step to solving a maximising linear programming problem using a simplex tableau

Answer 15

Tableau is now optimal and non-zero values can be read off using basic variable column and value column.

Question 16

Name the 2 ways solving a minimising linear programming problem is different to maximising

Answer 16

1. First, define a new objective function that is the negative of the original objective function.
2. After you have maximised this new objective function, write solution as the negative of this value, which minimises original objective function.

Question 17

What are the 5 steps to the two-stage simplex method that include >= constraints?

Answer 17

1. Use slack, surplus and artificial variables, as necessary, to write all constraints as equations.
2. Define a new objective function to minimise sum of all artificial variables.
3. Use simplex method to solve this problem.
4. If minimum sum of artificial values is 0, the solution is a basic feasible solution of the original problem, which is then the starting point for the second stage. Use the simplex method again to solve the problem.
5. If the minimum sum is not 0 then the original problem has no feasible solution.

Question 18

What 2 methods can be used to solve linear programming problems with >= constraints?

Answer 18

1. Two-stage simplex method

2. Big-M method

Question 19

What does the Big-M method do?

Answer 19

Uses an arbitrarily large number, M, in the objective function. Its purpose is to drive the artificial variables towards 0.

Question 20

What are the 5 steps to the Big-M method?

Answer 20

1. Introduce a slack variable for each constraint of the form <=.
2. Introduce a surplus variable and an artificial variable for each constraint of the form >=.
3. For each artificial variable, subtract M(a1, a2, a3…) from the objective function
4. Eliminate the artificial variables from your objective function so the variables remaining in your objective function are non-basic variables
5. Formulate an initial tableau, and apply the simplex method normally