Linear optimization: Phases of the Simplex method 2
Inhaltsverzeichnis
The 4 Phases of the Simplex Algorithm:
Phase 0: blocked variables
Phase 0’: free variables
Phase 1: invalid initial solution
Phase 2: optimation
Phase 0: blocked variables
The simplex algorithm slack variables y_i are introduced to convert inequalities into equations. Their task in the initial solution, in which all the structural variables x_j are zero, is to accept the value of the right to satisfy the equation.
In some cases equations can act as constraints. In these cases the structure variable assumes the value zero in order to satisfy the equation. It is therefore identified as a blocked variable, which shouldn’t be in the base, and thus it has to leave.
In order to achieve this, as long as disabled variables are in the basis, these lines are chosen as pivot rows. Every column can be selected as a pivot column, which has no locked variable as a non-basic variable and contains a non-zero element in the pivot row. In the following, the panel is converted according to the calculation rules for phase second.
Phase 0’: free variables
In some case the nonnegativity constraints for individual variables doesn’t apply. These variables are referred as free variables and they need to be in the base.
In order to achieve this, as long as free variables are non-basic, select this column as the pivot column. As pivot line, each line can be selected that has no free variable as a basic variable in the pivot column and contains a non-zero element. In the following, the panel is converted according to the calculation rules for phase second
When a free variable is once in the base, this line may be chosen as pivot row never more, otherwise they leave the base again.
Phase 1: invalid initial solution
In some cases, it may be that restrictions have a negative right in the initial solution, and so the nonnegativity constraints are violated, because, as already mentioned, the structure variables x_i assume the value zero in the initial solution. Thereby the slack variables y_i take the negative value of the right side. Panels of this type are referred to as invalid initial solutions.
In order to obtain a feasible initial solution pivot row and pivot column are chosen so that the values of the right-hand side take positive values when translated. As pivot row, the row with a negative right-hand side is selected, as pivot column a column with a negative value in the pivot row. When converted by the calculation rules for Phase 2 the negative element of the right-hand side is divided by the negative pivot element, if the new element of the right-hand side takes a positive value. This approach is being continued until all values of the right-hand side are positive and one has found a feasible starting solution. Are there any lines with negative on the right side, but no negative column elements in these lines, so you cannot perform any more conversions and thus it is impossible to find a feasible starting solution.
Phase 2: optimation
1. Select the pivot column:
Selection of the NBV that needs to be transformed by
Steepest-UNIT-ASCENT: Column with absolutely the greatest negative target solution coefficient
GREATEST CHANGE: Column with absolutely the greatest product of
negative target solution and the smallest positive ratio of right
side and the element of the corresponding column
2. Selection of the pivot row: Select the row containing the smallest positive ratio of right side element and the pivot column
3. Pivot element: the intersection of the pivot column and pivot row
4. Exchange of non-basic variable and basic variable
5. Conversion of simplex tableau to the calculation rules
6. Go to 1, if the solution isn’t optimal
Example
Start-Tableau
Eliminating Phase 0:
In the last row, we have a equation, but we use a inequation. Therefore we have to put y_3 into the non basic. For thus we choose a pivot element. Our pivot element consist of a pivot row, the last row, where the equation is, and a pivot column. The pivot column is the column x_1, because it is prohibit to divide through “0” and it isn’t favourable to divide through a negative number.
Simplex Iteration
Now y_3 is blocked and in the non basic row. x_1 change into the basic column.
Eliminating Phase 0‘:
x_2 isn’t eliminated. It can be take all possibilities, e.g. negative numbers. But this is wrong. x_2 have to be ≥ 0. To get the restriction we have to block x_2 and switch it into the basic. For this iteration we choose the x_2 column as our pivot column. Now we need a Pivot row to get our pivot element. We can only use the row y_1.
Simplex Iteration
Now x_2 is blocked and in the basic row. y_1 change into the non basic column.
Eliminating Phase 1:
In this tableau we have negative numbers in the right column, but we use positive numbers. Therefore we need a pivot element. We take the Pivot row y_2, because here is a negative number at the right side and in the matrix. Then we take the Column with y_1.
Simplex Iteration
Phase 2:
After the iterations we get the solution of the start tableau.
Sources
OR-wiki : https://bisor.wiwi.uni-kl.de/orwiki/Phasen_des_Simplex-Algorithmus
OR-tutorium
OR-script
