Chapter 4 - Simplex method Flashcards
When, and by who, was the simplex method developed?
1947 by George Dantzig
The simplex method is widely used. Why?
Simplex is a solver for LP problems. LP problems occur in a large number of applications. Therefore, LP is common.
Simplex is used specifically, because it is very efficient. GIven the standard form model, simplex will efficiently determine how to progress the search in a manner that only explore a very small subset of the total amount of possible solutions, namely the corner points feasible solutions only.
“what” is the simplex method?
An algebraic procedure, but with underlying geometric concepts.
What is the “optimality test”?
Optimality test goes like this:
Consider any LP problem that posesses at least one optimal solution. If a CPF solution has no adjacent CPF solutions that are BETTER, then this current CPF solution is optimal.
ex:
Z = 30 + 3x_1 - 5/2 x_4
We see here that increasing x_1 vs x_4 will yield the answer. Since x_4 has a negative rate of change/improvement, the task becomes trivial. However, formally, x_1 is the “entering basic variable”
Geometrically, we say that Z(a, b) is not optimal because moving in the direction of x_1 will increase Z and do nothing with x_4. Extra geometrically we say “moving along the edge between the current point and some other point”.
In conclusion, the optimality test is about: If there are no adjacent BFS that are better than the current BFS, then the current BFS is optimal.
There are 6 solution concepts, name them
1) The simplex method focus solely on CPF solutions. For any problem that contains an optimal solution, we only have to find the “best” CPFS. This is much of the power of simplex. We only consider an extremely small subset of all possible points.
2) Iterative process
3) Whenever possible, initialization should choose the origin as the starting point, meaning all decision variables equal to zero.
4) Given a CPFS it is MUCH QUICKER to find information about its adjacent CPFS than any other CPFS. Therefore, we always move to adjacent CPFS. We dont “search” for the points, we calculate them using the shared constraint boundaries.
5) When a CPFS is found, simplex considers the rate of change of any possible adjacent direction. Then it picks the best one.
6) The optimality test at some CPFS consists of checking whether there are ANY possible adjacent edge/direction that gives Z a positive rate of change.
Given an LP problem in “our standard form”, what is the first step?
The first step is to convert the model into a set of linear equations by using slack variables. This is simple:
Say we have: x_1 <= 10
Then we must add a variable, x_2, such that the shite becomes an equality:
x_1 + x_2 = 10
We must also include the non-negativity constraint.
When we have included slack variables, what do we call our model+
augmented (utvided).
if a slack variable equals 0 in the current solutions, what does this mean?
It means that the solution lies directly on the constraint boundary for the corresponding functional constraint.
if a slack variable is greater than 0, what does it mean+
It means that the solution is within the feasible region.
What is an augmented solution?
An augmented solution is any solution that is augmented to include the slack variables as well.
What is a basic solution?
A basic solution is a corner-point solution that is augmented to include the slack variables
What is a BFS?
BFS = Basic Feasible Solution. Augmented corner-point feasible solution. CFS with slack variables.
Elaborate on degrees of freedom
Degrees of freedom refer to the number of variables that exceeds the number of equations in our model.
They are called degrees of freedom since they are essentially free to be any value and the system of equations will be solved. However, we are not interested in a solution to the system. We want the best solution.
Although we can select any value for the free variables, we force them to be zero. This is because we want to consider corner-points.
The number of free variables are related to the number of non-basic variables, in that they are the same number. What variables we choose to be the free variables is completely arbitrary. However, it is worth noting that some variables as 0 will produce systems that cannot be solved. In such cases, we must try something else (try another combination of free variables).
The variables that are chosen to be “free variables” are called non-basic variables. Simplex set them to be 0.
What are the properties of basic solutions?
1) Each variable in a basic solution will be either basic or non-basic.
2) The number of basic variables equals the number of functional constraints (now equations).
3) The nonbasic variables are set equal to zero.
4) The values of the basic variables are obtained as the simultaneous solution of the system of equations.
5) If the basic variables satisfy non-negativity, the basic solution is BFS (Basic Feasible Solution)
How to tell if two BFS are adjacent?
Two basic-feasible solutions are adjacent if their set of non-basic variables is equal for all but one variable.
This is due to the fact that if we want to move to an adjacent BFS, then one, and only one, non-basic variable will change. If not, they are not adjacent.
What happens when we move from one BFS to another?
One of the non-basic variables will be turned into a basic variable, and one of the basic variables will be turned into a non-basic variable.
Give the outline of the simplex method
1) Initialization: Identify an initial solution
2) Perform the optimality test to determine if this init solution is optimal. If YES, then STOP. if NO then CONTINUE
3) Step 1 of iteration) Determine which direction to move.
4) Step 2 of iteration) Determine where to stop to reach the next solution.
5) Step 3 of iteration) Solve system for this new equation.
6) Return to the optimality test
WHat is the difference between original form and augmented form of a model?
THe augmented form includes slack variables. This means that the augmented matrix contains equalities and not inequalities etc.
Elaborate on the initialization step of the algebraic simplex method
Recall this:
A problem/model consisting of n variables and r constraints that is in our standard form, will introduce slack variables equal to the number of constraints. Therefore, the augmented model will require (n+r) variables, but the number of constraints (now turned to equations) remains the same.
We know that the number of non-basic variables is then (n+r)-r=n. This means, we will always have a set of nonbasic variables that has the same size as the number of decision variables from the original problem. This allows us to always pick exactly the set of decision variables as our initial starting point, given that there are no constraints violating this.
When we pick this init point as the origin (since we set value equal to 0), we then solve the remaining system to get the values of the slack variables.
On the degrees of freedom: Recall that we get n degrees of freedom because there are n more variables than equations. Therefore, we can solve the system by choosing ANY value for these free variables.
when we solve the augmented model using Gauss, what are we actually doing/finding?
We are finding out how much gap there is between the point given by the values of the decision variables and every constraint-border, given by the slack variables.
At first, we want to pick (0,0,…) as the nonbasic variable set. Since there are n decision variables, we get n nonbasic variables. Therefore, we are finding out how much slack there is in each constraint from this point.
Elaborate on the optimality test
Say we have been given the objective function:
Z = 3x_1 + 5x_2
If we are at point (0,0) it is easy to see that Z is 0.
Since both variables give a positive contribution by increasing them, we see that Z is currently not optimal.
Elaborate on determining the direciton of movement (Step 1 of iteration)
We consider the current shape/form of the objective function. The objective function will change along with the procedure.
We look at the different parts of the objective function, and find the variable that has the largest positive coefficient. This represent the direction with the greatest rate of improvement.
The important part is that we always only change one non-basic variable by moving to an adjacent node. This means that we control the movement. If we have 2 decision variables that are non-basic, moving in either of those directions will only change one of them. Likewise, if we have a combination of slack variables and decision variables as non-basic variables, if we move to an adjacent node, we only change on non-basic variable. This is key. We choose one non-basic to be “entering basic”, and force the ohthers to remain at zero.
IMP: We choose one NONBASIC variable to increase/move along. The variable we choose is called the “entering basic variable”, because when we have moved as much as we can in this direction, this variable has turned to a basic variable.
Elaborate on how we determine how “far” to move in a speicfic direction given that we have chosen a variable to move along
Recall that we have chosen a nonbasic variable to move along. We want to move all the way until we reach a constraint boundary. The idea is to move until one of the basic variables becomes 0. At this point, the decision variables will indicate a point that is a BFS (CPF + augmented), and it will be better than the point we previously explored, according to the objective function.
Given the nonbasic variable we have chosen, we want to check how far it can be changed. Therefore, we find all constraints involving the chosen nonbasic variable, and see how far it can be increased without violating the constraint. to do this, we use the non-negativity constraints.
Say the equation is like this, and we have chosen x_2 as the nonbasic to increase:
2x_2 + x_4 = 12
Then we use the nonnegativty constraint of x_4 >= 0
Thus we get:
x_4 = 12 - 2x_2 >= 0
This gives us…:
12 >= 2x_2
6 >= x_2
Therefore, we know that x_2 must be smaller than, or equal to, 6.
We do this for every constraint involving x_2.
Then we pick the smallest number, and use it as the max length we can move/increase the variable.
We also see how choosing x_2=6 makes x_4 = 0. Therefore, we want to pick x_4 as the leaving basic variable.
Recall that x_2 is now no longer a nonbasic variable.
IMPORTANT: When we check the constraints to figure out how far we can move, we must always use the most up-to-date equations given by gauss. Or do we?
Consider the second step of each iteration in the simplex method. Recall what it is.
Elaborate on how to perform it
The second step of each iteration in the simplex method is about figuring out the value of the entering basic variable.
We perform this step by considering every constraint that includes the “entering basic variable” and utilizing the fact that all variables should be non-negative.
IMP: Since we have solved the system prior, we have a linear system of equations where every basic variable is a function of the non-basic variables. This makes us able to use the fact that this variable should be nonneg. We then take every equation where the “entering basic variable” is included, and applies the fact that the basic variable in this equation should be non negative. This allows us to find the largest allowed value for the entering basic variable from this specific constraint.
Give the procedure of simplex by simplex tableau
The simplex tableau consists of 6 column parts:
1) Basic variable column
2) Equation number
3) Z column
4) A column per variable
5) Right side of equations
6) Ratio column
The simplex tableau has rows per basic variable, Z included.
First we use the optimality test. This is just checking to see if Z can be improved.
Then if this is not an optimal solution ,we start the iteration. We determine an “entering basic variable” that is the variable from the objectice function with the highest rate of improvement. Then we but a “box” around the column in the tableau below this coefficient that represent the entering basic variable from the objective function. We call this the “pivot column”.
Now we determine the leaving basic variable by the minimum ratio test. To do this, we use each entry in the pivot column that is greater than 0, and use this coefficiant as a divider that we use to divide its corresponding “b” (right side) value. so, if the right side value is 12, and the element in the pivot column at one of the rows is 2, then the ratio is 6. Thus the name “minimum ratio test”.
The row that has the smallest number at “ratio” will be called the “pivot row”. We draw a box around this as well. There will be a single number that now is in both boxes. this number is called the “pivot number”.
We use this pivot number in a single iteration. First we get it to be equal to 1 by dividng the row by itself. Then we use this row to eliminate the coefficients in the pivot column in the other rows, including the objective function row.
Then we perform the optimality test.
What is the purpose of the pivot column?
The pivot column is the column below the “entering basic variable” from the first row (objective function row).
The purpose of the pivot column is to identify all places where this variable is included in the constraints so that we can check for boundaries. We do this to include every case, so that we dont accidently miss one in the MRT.
What do we do if there is a tie for the entering basic variable?
Entering basic variable is chosen by inspection of the objective function.
There is no way to tell what to do if they are equal.
Therefore, we pick one arbitrarily.
IMPORTANT:
Elaborate deeply on the simplex tableau method
We use a schematic approach that helps us make the correct calculations. the tableau relies on patterns instead of having to understand what you’re doing.
NB: I can definitely see how using the tableau will make you forget what the hell you’re doing.
Anyways, here is the approach:
We need to transform the model into a system of linear equations. To do this, we use slack variables. Recall how n variables and r constraints will turn to become (n+r) variables and r constraints/equations.
First we need to set up the tableau itself. This involves creating a table consisting of the following columns:
1) Basic variables
2) Equation number (used to explain gauss-ops)
3) Z-column
4) One column per variable we have that is not Z
5) The right hand side value of the equations (b-vector)
6) Ratio column, to display the results of the minimum ratio test
Then we select basic variables and non-basic variables. We automatically choose the decision variables to be our nonbasic variables.
Then we fill the values we have initially into the system.
Then we perform the first optimality test. Check to see if Z = … has positive parameters so that Z can be increased. If yes, then we start the iteration. If no, then the current set of decision variable-values is the optimal solution.
Then we find the “entering basic variable”. The entering basic variable will be the variable that has the coefficient with the largest value, so that increasing this variable will lead to the biggest possible increase in Z.
We use this “entering basic variable” to mark a column on the simplex tableau, which we call the “pivot column”. The pivot column will consist of all entries in the column BELOW the variable we have picked as the entering basic variable.
Then we find the “leaving basic variable”. We need this variable to make the “pivot row”. We find this variable by applying the minimum ratio test with the values that are not 0 in the pivot column we just found.
When we mark the pivot row, we will, because of the already-marked pivot column, get a single coefficient as the “pivot number”. This is a number we want to transform to 1 by dividing this row on itself. Then we use this “1” to eliminate the number on all other places in the pivot column. So, the result should be that the pivot row is the only row that now has a value in the pivot-column position.
Along with the system-solving, we update the basic-variables-set by exchanging the leaving-basic-variable and the entering-basic-variable.
Now that we have solved the system, we can apply the optimality test again. Then the same process applies as before.
Elaborate on tie-breaking related to “entering basic variables”
There is no way of predicting the better choice. Therefore, we can make arbitrary choice.
What happens if the minimum ratio test only gives negative values or tries to divide on 0?
Basically, it means that no variable qualifies as the leaving basic variable.
Recall that we pick “leaving basic variable” based on the one that reach its boundary first. If no one reach boundary first, it graphically means that we are just extending further and further out into the feasible region.
Of course, this means that Z is unbounded.
Typically, the model is wrong. We very rarely find cases where the actual real life scenario is unsolvable due to unbounded feasible region.
Think about what unbounded Z actually means. When maximizing, it means that we have unlimited resources or something similar. This rarely makes sense.
Explain CPS vs CPFS
A corner-point solution is just a point indicating that constraint boundaries are intersecting there. This point can be in or out of the feasible region.
A Corner-point feasible solution is also an intersection between constraint boundaries, but this one is a valid solution, as it doesnt violate any constraints.
Recall the definition of adjancency of CPF
There are two definitions that are essentially the same:
1) If we have “n” decision variables, then any two CPFS’ that share at least (n-1) constraint boundaries will always be adjacent.
2) Two BFS/CPFS’ are adjacent if their set of non-basic (or set of basic) variables is identical but for one variable.
Why can we be certain that we always have n nonbasic variables with value 0?
Because we are only interested in corner points. Due to the nature of corners (intersections) and slack variables, we can be certain that this is the case.
Say we have 3 decision variables and 3 constraints, where each constraint place a limit on the decision variable. In the space, this will create a prism. When considering the furthest out point on this prism, we can see that it lies on the boundary of all 3 constraints. Therefore, at this point, all slack variables are equal to 0. Therefore, our augmented values set looks like this: {x,y,z,0,0,0}
Moving there will require 3 iterations, as there are 3 edges we have to move along.
{0,0,0,a,b,c}
{x,0,0,0,b,c}
{x,y,0,0,0,c}
{x,y,z,0,0,0}
Looks something like this.
IMP: When we do the minimum ratio test, what are we really doing?
We have at this point already found our “entering basic variable”. This would be the variable with the largest growth factor in regards to Z.
Let us say our entering basic variable is x_2. We essentially want to move from a current BFS to an adjacent BFS. However, we dont know how far to move.
So, we do this:
We use the slack variables to figure out what happens if we keep increasing the “entering basic variable”. At some point, increasing the “entering basic variable” will make our “cursor” hit the adjacent BFS. At this point, since it is a BFS, we know that the point will be at a place where one or more boundaries are at the limit. Therefore, their corresponding slack variables will be 0. So, the question is, how can we figure out how far out this point is?
Say we have these two relevant constraints:
x_4 = 12 - 2x_2
x_5 = 18 - 2x_2
We utilize the fact that x_4 and x_5 must be nonnegative.
x_4 = 12 - 2x_2 >= 0 which leads to 2x_2 <= 12
This gives us: x_2 <= 6
Same for the other one gives: x_2 <= 9
These numbers say the following:
“as we increase a nonbasic variable, we reach a point where the slack variable is 0. If we keep increasing the variable, the slack variable will become negative. So, essentiually, it tells us that if we want x_4 to be nonnegative, we must keep x_2 smaller than or equal to 6.
Since x_5 has the x_2 bound on 9, we naturally use the tightest one.
IT IS VERY IMPORTANT to understand the connection between MRT and the variable placing the tightest constraint on it. In this example, it was the variable x_4 that placed the tightest bound. Therefore, we use x_3 as the leaving basic variable. Why is it the leaving basic variable? It is the leaving basic variable since it is the first variable to reach the value of 0 as x_2 is increased. We dont want to increase beyond this point.
How do we find the values of the basic variables?
We solve the system of equations.
The set of their corresponding solved values is called a “basis”.
What is “kanonisk form”? (proper form from Gaussian elimination)
Refers to the case where every equation only has a single basic variable, and this has the coefficient of 1.
How many constraints will be involved in each BFS?
If there are n decision variables, there will be at least “n” constraints in all BFS’. However, the maximum can be equal to the number of constraints + the number of decision variables.
At a general level, what could the slack variable represent (in real life?
Could be the amount of resources left.
Hva er en bindende restriksjon?
En bindende restriksjon er en restriksjon som er på formen “likhet”. Det er det vi får av å bruke slakk variabler slik at vi går fra ubundet til bundet.
What is the formal definition of adjacency for CPF solutions?
For any LP problem with n decision variables, two CPF solutions are adjacent if they share (n-1) constraint boundaries. The line segment connecting two adjacent nodes is called an “edge”.
why are we interested in adjacency?
We are interested in adjacency because of their relation to optimal solutions. The general property is that if any LP problem that possesses at least one optimal solution, if a CPF solution has no adjacent CPF solutions that are better (measured by Z), then it MUST be an optimal solution. This is basically the optimality test we perform.
Geometrically, given a 2D problem, how do we solve it?
Initialization: We pick (0,0) as starting point. This is our initial CPF solution that we examine. Because of the non-negativity constraints (Wyndor) we know that (0,0) is a CPF.
Optimality test: We conclude that there are adjacent solutions that are better. Therefore, we move.
Iteration 1) Move to a better adjacent CPF, by performing the following 3 steps:
1) Consider the two edges that emanate from the current CPF.
Choose to move along the edge that improve Z the fastest.
2) Stop at the first new constraint boundary. IF we were to move further, we would no longer have a corner-point feasible solution to examine.
3) Solve for the intersection of the new set of constraint boundaries. We are at a point where we have a CPF solution lying on the boundaries of some of the constraints. We solve for the decision variables.
ex: x_1 = 0, 2x_2 = 12
Gives: x_1 = 0, x_2 = 6
Thus, our new point is (0,6)
Optimality test: Conclude that (0,6) is not optimal. Continue new iteration.
*******@
This is what we do, geometrically:
We pick an initial point that is a CPF solution. Then we progress by picking the “best” edge (according to Z), stopping at the first constraint boundary on this edge (further movement moves us outside of the feasible region), solve the system of equations (relevant constraints) to find the point we’re at. Then we perform an optimality test to see if we need to iterate more or not.
How many edges will emanate from a CPF solution?
maximum of n. Can be less. C
What is required for the problem to possess CPF solution(s)?
The feasible region MUST be bounded. This means that the area is fixed, so we cannot continue to move further and further out to infinity.
Why do we need algebraic form?
Multiple reasons. Firstly, computers cant do it graphically. Therefore, we need to use a language they can understand.
Secondly, the scale of problems quickly makes it extremely difficult to solve graphically. Therefore, we need a systematic language (algebra) to solve such complex cases.
The algebraic language of the simplex method is designed to make it manageable.
Elaborate on the algebraic procedure
The algebraic procedure is essentially structured around solving systems of equations. This is why we take the problem (in standard form) and convert it to its corresponding equality form. We do this by using slack-variables to represent the inequality-slack.
The transformed standard-form problem is now called “augmented form”. Augment means “utvided”.
It is important to understand that the augmented form and the standard form represent exactly the same problem. However, the augmented form is much more easy to handle due to our knowledge of solving linear systems of equations.
What happens if a slack-variable is 0 on some current solution?
This simply means that the solution lies on the boundary of the equation-constraint that this slack-variable is used in. Every slack variable is unique for a constraint initially.
Also, a slack-variable-value greater than 0 means that the solution is feasible. Less than 0 means that solution is infeasible, as the solution lies on the “infeasible” side of the constraint boundary corresponding to the slack variable of interest.
How do we deal with equalities in our model? As constraints
Say we work in 2D. An equality is a line segment. As constraints, this means that our solutions (feasible) are restricted to this line segment. However, it is therefore difficult to start the simplex method, as we dont really know where to begin (origin is not feasible).
The whole points is that when we have equality-constraints, we dont know where to start the simplex method. Consider the first image, where tf do we start?
However, when we use the artificial variable (constant ‘a’ in the second picture), we can essentially extend the feasible region.
By changing the artificial variable, we change the feasible region so that we can find the origin.
EXTIMP: Explain the indirect effect on Z when changing a non-basic variable that is equal to zero in the final tableau.
Second part: Explain how the indirect effect helps us find the sensitivity area of objective function coefficients.
Understanding this card is enough to understand everything about finding the sensitivity area of objective function coefficients algebraically.
The OG objective function does not contain this variable. However, changing the variable-value from 0 to 1 will still impact the objective function with a value equal to the coefficient of the variable we just changed.
What happens here, is the indirect effect. When we change say x3 from 0 to 1, we will also make impacts at variables that are defined by that just-varied variable. For instance, if x1 is equal to 10 - 3x3, then this value is (before we change x3) x1=10. But, when we increase x3 to 1, we also change x1 to 10-3=7.
This effect will happen to every variable that use the x3-variable in its ‘definition’/constraint.
When we add together all the indirect effects (remember to multiply with the original coefficients of the objective function), we should (if calculated correctly) get a number that is exactly equal to the coefficient of the x3 variable in the objective function row of the final simplex tableau. Therefore, the indirect effect is camouflaged inside of the tableau.
END OF INDIRECT – START OF DELTA
We can use the indirect effect as a starting point to quickly determining the delta-values so that we can calculate the sensitive area of the objective function coefficients.
EXAMPLE: Say we have the case like the image shows.
The indirect effect applies like it always does. However, when we are trying to find the sensitive area of c_j, we usually approach it with a “new” cj that is equal to cj+∆. We replace ALL old coefficients from the beginning of the simplex method with this new one, and solve like normal, and watch the ∆-values propagate downward and get their final values that we can use directly. However, we can avoid solving the iterations AGAIN if we have done it once with the original values.
The indirect effect from changing slack1, s1, comes in the form of BOTH x1 and x2. x1 will be changed by 2/5, and multiplied by 1 due to the objective function coeff. x2 will be changed by -1/5 and multiplied by 1.5 as 1.5 is the c2 coeff. The sum 2/5-1.5/5 = 0.1, which is what the tableau shows.
BUT: Now we did not include the ∆’s when we multiplied by the coefficient weights of the objective function. What we really should do now, is this:
∆Z = ∆x1 c1new + ∆x2 c2 (we only change one c-coefficient at a time)
∆Z = ∆x1 (c1old+∆c1) + ∆x2c2
∆Z = 2/5 (1 + ∆) - 1/5 (1.5)
∆Z = 2/5 + 2/5∆ - 3/10
∆Z = 1/10 + 2/5∆
There, we have found the coefficient of the delta-value without iterating all the shit.
So, when finding deltas for objective function coefficients, we are just looking at the indirect effect of what WOULD happen if we change the non-basic variables from 0 to 1. IMPORTANT: The reason why only the coeffiecients from a single row is included in the final delta coeff, is because we only associate a single delta in the objective function. If we look at c1, we give this one a delta. Therefore, it does not make sense to talk about delta for x2.
Given these, deltas, we find the sensitivity area by comparing every delta-case with being greater than or equal to 0. Since there are 3 delta values, we get 2 inequalities to solve (dont need the RHS):
1) 1/10 + 2/5∆ >= 0
2) 1/4 - 1/5 ∆ >= 0
We get:
∆ >= -1/4
∆ <= 1/2
Then we include the c1 value, which is 1:
0.75 <= c1 <= 1.5
This is the sensitivity area for c1.
Same procedure for every other objective coefficient as well.
We dont need RHS value for the sensitivity analysis, but the pattern is still the same. I believe the intuition goes like this:
(c1+∆)x1 = c1x1 + ∆x1
Since x1=2, we get: 2+2∆
From c2x2, we get: 1.5 times 3 = 4
Therefore, the sum is: = 4 + 2 + 2∆ = 6 + 2∆
