The Simplex Algorithm

Question 1

Describe how the Simplex Algorithm works:

Answer 1

The simplex algorithm gets us to start at some vertex (BFS) and go to a different BFS along an edge that corresponds to an adjacent BFS and keep doing that, always improving the cost until we achieve the minimum cost.

Look at all neighbouring BFS’s, where only 1 LI active constraint is different. If that improves the objective, follow that edge to the new BFS. Do that until you find a point where no adjacent feasible solution improves the objective value. At that point you can say you’ve achieved an optimal solution.

Question 2

Describe the steps of the Simplex Algorithm:

Answer 2

1) Start at a BFS - one corner of the polyhedron
2) if the objective is minimising, move along an edge and look for a decrease in the objective function

Question 3

What is a positive orthant?

Answer 3

A region where all the coordinates of points are ≥ 0

Question 4

What is the definition of a feasible direction?

Answer 4

• Let x ∈ P, a vector d ∈ Rn is a feasible direction if at x if there is a θ > 0 such that x + θd ∈ P.
• a direction we can move in, in our polytope and feasibility is maintained

Question 5

What is the increase in cost by following a vector d/a feasible direction?

Answer 5

if our starting point is C^T * x, the new point = C^T(x + θd)
- this expands to C^Tx + C^T*θd

• difference between the two points = C^Tx, so C^Tx + C^Tθd - C^Tx = C^T*d (θ = 1)

Question 6

What is a degenerate solution?

Answer 6

Where one of the basic variables in the BFS = 0
- in 2D this looks like 3 constraints being active at the same time (when only 2 are actually part of the feasible region)
- this looks like one of the components of the direction vector being negative

Question 7

What might happen if we follow a degenerate solution?

Answer 7

We’ll get stuck in an infinite loop when trying to move to a new BFS

Question 8

How do you know if your solution is optimal?

Answer 8

If none of the reduced costs of the basic variables = 0

Question 9

If the BFS is optimal and nondegenerate what do we know?

Answer 9

That the reduced costs are all non-negative

Question 10

What must be true if the current solution is not optimal, and there are multiple choices for the next pivot element:

Answer 10

• ## if there is only one choice for a pivot element then only one reduced cost must be negative, if there are multiple choices then multiple reduced costs must be negative

Question 11

What must be true if the the optimal cost is −∞

Answer 11

• if all the components of a direction are negative in the table (non-negative in actuality because it’s flipped) meaning we can infinitely decrease the objective.
• the reduced cost is negative
• and all the decision variables remain positive

Question 12

What must be true if the current solution is optimal?

Answer 12

• The reduced costs are all non negative
• The basic variables are all non negative

Question 13

How do we constrain θ to maintain feasibility when following basic direction d

Answer 13

dj = x + θd, to maintain feasibility this has to be ≥ 0, so θ ≤ - xj / dj

Question 14

What are 3 types of elementary row operations used?

Answer 14

• swapping rows
• multiplying a row by a non-zero constant
• adding a scalar multiple of one row to another

Question 15

What do we have to do for any negative value in our direction vector?

Answer 15

ensure that θ ≤ - xj / dj

• so if we look at all of our negative components we take the smallest one as our step size (for moving in direction dj)

Question 16

Describe the 5 steps of one iteration of the Simplex Algorithm:

Answer 16

1) start with basic columns A1,…Am and a BFS x
2) compute the reduced costs for non basic indices. If all are non negative the current solution

Question 17

What is the difference between the full simplex tableau and the two phase simplex method?

Answer 17

• Full simplex tableau starts off with a BFS in the table (assumes one exists, hence we solve for the BFS with slack variables first), constraints are already in form that allows for identifying a BFS
• two phase simplex is where we start off by creating artificial variables, and obtain feasible starting solution in phase 1

Question 18

What is Bland’s pivoting rule?

Answer 18

• For the entry column choose the variable xi with the smallest index i
• For the exiting row (pivot element) choose the basic variable xi with the minimum ratio test (if there’s a draw choose the basic variable with smallest index i)

Question 19

Why do we use Bland’s pivoting rule?

Answer 19

• prevents cycles and thus the simplex algorithm terminates after a finite number of iterations

Question 20

What are the two steps of two phase Simplex:

Answer 20

1) Introduce artificial variables to get an initial BFS
2) find optimal solution for new objective with cost 0 for the original LP

Question 21

What is true if after phase 1 of two phase simplex the objective isn’t 0?

Answer 21

That the original LP is feasible

Question 22

What is the steepest descent rule?

Answer 22

For a simplex tableau you choose the next entry column by choosing the non-basic variable with the most negative reduced cost

Question 23

What is the smallest subscript rule?

Answer 23

For a simplex tableau you choose the exit row/pivot element based on the one with the smallest subscript

Question 24

What is the end state of the tableau after phase 1 of two phase simplex if the original LP is feasible?

Answer 24

The objective cost = 0, all reduced costs are non-negative and none of the artificial variables are in the basis. (The basic variables will have reduced cost = 0)

Question 25

What happens if simplex terminates but the basis still contains an artificial variable?

Answer 25

- we manipulate the tableau to remove it, by deviating from the pivoting rule. - swap in a non-artificial variable

Question 26

if after completing the first phase of two phase simplex and there is still an artificial variable in it, what do we look for to determine what to do next?

Answer 26

- if all the components of the artificial variable's row are 0, the original constraint including it, is redundant and can be removed from the LP - if there's not a nonzero component, pivot so that a non artificial variable enters the basis.

Question 27

How do we perform phase 2 of 2 phase simplex?

Answer 27

1) We remove the columns of the tableau for the artificial variables 2) set the reduced costs as the coefficients from the original problem 3) Now perform row operations to make the reduced costs = 0 4) then perform pivots until all the reduced costs are non-negative

Question 28

What do you do if it says formulate (no need to solve) the optimisation problem for finding an initial basic feasible solution:

Answer 28

Write out the new objective and LP with the new artificial variables: minimise c1x1 + c2x2 + c3x3 + c4x4 + c5x5 subject to x1 + 2x2 + 3x3 + x4 + x5 = 10 2x1 + x2 + x3 + 3x4 + 2x5 = 8 x1 + 3x2 + 2x3 + 5x4 + x5 = 12 3x1 + x2 + 4x3 + x4 + 6x5 = 14 x1, x2, x3, x4, x5 ≥ 0 becomes: minimise: x6 + x7 + x8 + x9 subject to x1 + 2x2 + 3x3 + x4 + x5 + x6 = 10 2x1 + x2 + x3 + 3x4 + 2x5 + x7 = 8 x1 + 3x2 + 2x3 + 5x4 + x5 + x8 = 12 3x1 + x2 + 4x3 + x4 + 6x5 + x9 = 14 x1, x2, x3, x4, x5, x6, x7, x8, x9 ≥ 0

Question 29

For there to be multiple choices for the next pivot element what must be true?

Answer 29

1) The reduced cost must negative 2) at least two of the elements must be positive (in the table, negative in actuality) 3) their rations must be the same, e.g. 4/2 and 2/1 both = 2

Question 30

What is the Big-M method?

Answer 30

- It compresses two phase simplex into one phase - by introducing artificial variables with M coefficients (which represent very large constants) into the objective - we look for a solution that doesn't include M/the artificial variables

Question 31

What exam question could we get asked involving the Big-M method:

Answer 31

- setting up the initial tableau - this involves setting the reduced costs of all basic variables to 0

Question 32

When does the big-m method terminate?

Answer 32

When all the reduced costs are non-negative

Question 33

When is the LP infeasible using the big-m method?

Answer 33

If after solving the LP, removing the artificial variables from the basis, an M coefficient is in the solution (e.g. is attached to a basic variable)

Question 34

What are the steps to solve this problem: Compute the basic feasible solution x for basic indices B(1) = 2, B(2) = 4. Derive the basic direction d corresponding to the non-basic variable x3. What is the maximum θ ≥ 0 such that x + θd is feasible? What do you notice?

Answer 34

1) use matrix manipulation to solve for the bfs 2) the rows will give the basic directions for each variable 3) select the column corresponding to the variable x4, and multiply it by -1 4) this gives the basic direction (0 -d2 -d3 1) 5) Now solve the sum x + θd to find the max value for θ