L2 - The Simplex Model Flashcards
What is the standard form of a linear program?
maxX(Ubar) = cxT
s.t. ATx(Ubar) <= b(Ubar)
Where x is a vector of objects to be contained. A is the matrix of values at each constraint. and b is the vector of limits
How many solutions can you get a linear program?
- one unique solution
- no solution –> if the feasible region is empty
- an infinite number of solutions
- Can happen when the feasible region is unbounded
What is the feasible region?
Set of points that satisfy the constraints
S = {x:AxT(Ubar) <= b(Ubar)}
You also always want the constraints wrote with this inequality
What are the basic variables?
- The set of basic variables (B) is the set of variable that appears in the optimal solution
- it is called the basis –> your x’s that everything is based off –> anything that is a function of the x variables is called no basic
- it matches the managerial insight about what is in the optimal production plan
What is the first step of the Simplex method?
This is called the Starting Dictionary (tableau)
w is the slack variables –> difference between the RHS variables and Ax(Ubar)
- The equation and variables we are trying to maximise (zeta) are called non-basic and the slack variables w are called basic variables
- If a slack variable is null at the end of optimisation then it is said you are using all of the available resources
at the start, we set both x1 and x2 equal to zero to give us our initial maximum profit when we don’t produce anything (zero profit)
cWhat is pivoting in the Simplex method?
—Pivoting means that we change our basis B by inserting a variable that is currently non-basic.
—Why? Because inserting the non-basic variable, we increase our profit
—In our example, what variable should we pivot on?
- X2 because it is associated with a larger positive coefficient than x1
What is the final dictionary?
- When we have pivoted both x1 and x2 out so the slack variables w are in the objective function and are now non-basic (= 0 )
- as all the slack variable are equal to 0 we can figure out the total profit and values of each of the x variables.
How to complete an optimisation using the simplex pivot method?
- Find objective function and all constraints
- Re-write this into a dictionary form
- Pivot out which ever has the highest coefficient in the objective function
- Test in both slack variable which has the lowest (most stringent constraint) when rearranged
- Sub into the chosen slack variable and sub into all other functions
- If the profit function still contains positive variable it has not been maximised so pivot out the other positive variable using the same method
constraints are binding if the slack variable (w’s) are equal to zero (non-basis) and are in the objective function
What is initialisation?
- The simplex method is written in the for Ax <= b
- the vector of bs must be >= 0 for the simplex to start –> this means that the origin will be in the feasible region
- if some are negative –> the simplex method cannot start
- Mathematically there is a solution to the objective function but the simplex algorithm won’t work
- To get the simplex method to work you need to initialise the constraints using an auxiliary problem
- this is done by maximising a negative variable (which would be zero) then taking this away from all of our constraints –> makes all the right-hand sides positive
- this is us the same value as our original linear program
What is the 2nd reason of failure of the simplex method?
- Called Degeneracy
- Happens when pivoting out a variable does not change the optimal solution - you have equivalent bases or one basic variable is equal to zero (or equal to the initial variable)
- Not the same as having multiple optimal solutions
- may mean than a constraint and its slack variable is non-binding –> three constraints are mathematically binding but geometrically it is not (it can be removed but the optimal solution will not change)
- Degeneracy will mean the dictionary will start cycling among dictionaries (end up back at the start)
- To stop the simplex cycling you need to add some additional rules to solve degeneracy
- Bland’s rule –> choose the variables which have the smallest index (x1, x2, ,x5 pick x1) and choose the constraint that is closer to the top.
How can you identify unboundedness?
- Happens when testing the variable that you want to pivot out and all the ratios are negative
- Hence the entering variable can be increased indefinitely to produce an arbitrarily large objective value
3 situations that can happen in the simplex?
- Unboundedness - none of the ratios is positive, solution in infinite.
- Initialisation - one of the RHS is negative in the starting problem additional step before starting the simplex which
- Degeneracy - a dictionary in which we have a basic variable, is null. Then the simplex can start cycling and then you need some additional rule to exit the cycle (bland’s rule)
