The Simplex Algorithm Flashcards
Describe how the Simplex Algorithm works:
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.
Describe the steps of the Simplex Algorithm:
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
What is a positive orthant?
A region where all the coordinates of points are ≥ 0
What is the definition of a feasible direction?
- 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
What is the increase in cost by following a vector d/a feasible direction?
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)
What is a degenerate solution?
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
What might happen if we follow a degenerate solution?
We’ll get stuck in an infinite loop when trying to move to a new BFS
How do you know if your solution is optimal?
If none of the reduced costs of the basic variables = 0
If the BFS is optimal and nondegenerate what do we know?
That the reduced costs are all non-negative
What must be true if the current solution is not optimal, and there are multiple choices for the next pivot element:
- ## 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
What must be true if the the optimal cost is −∞
- 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
What must be true if the current solution is optimal?
- The reduced costs are all non negative
- The basic variables are all non negative
How do we constrain θ to maintain feasibility when following basic direction d
dj = x + θd, to maintain feasibility this has to be ≥ 0, so θ ≤ - xj / dj
What are 3 types of elementary row operations used?
- swapping rows
- multiplying a row by a non-zero constant
- adding a scalar multiple of one row to another
What do we have to do for any negative value in our direction vector?
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)
Describe the 5 steps of one iteration of the Simplex Algorithm:
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
What is the difference between the full simplex tableau and the two phase simplex method?
- 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
What is Bland’s pivoting rule?
- 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)
Why do we use Bland’s pivoting rule?
- prevents cycles and thus the simplex algorithm terminates after a finite number of iterations
What are the two steps of two phase Simplex:
1) Introduce artificial variables to get an initial BFS
2) find optimal solution for new objective with cost 0 for the original LP
What is true if after phase 1 of two phase simplex the objective isn’t 0?
That the original LP is feasible
What is the steepest descent rule?
For a simplex tableau you choose the next entry column by choosing the non-basic variable with the most negative reduced cost
What is the smallest subscript rule?
For a simplex tableau you choose the exit row/pivot element based on the one with the smallest subscript
What is the end state of the tableau after phase 1 of two phase simplex if the original LP is feasible?
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)
What happens if simplex terminates but the basis still contains an artificial variable?
- we manipulate the tableau to remove it, by deviating from the pivoting rule.
- swap in a non-artificial variable
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?
- 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.
How do we perform phase 2 of 2 phase simplex?
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
What do you do if it says formulate (no need to solve) the optimisation problem for finding an initial basic feasible solution:
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
For there to be multiple choices for the next pivot element what must be true?
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
What is the Big-M method?
- 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
What exam question could we get asked involving the Big-M method:
- setting up the initial tableau
- this involves setting the reduced costs of all basic variables to 0
When does the big-m method terminate?
When all the reduced costs are non-negative
When is the LP infeasible using the big-m method?
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)
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?
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 θ
