Linear optimization: Phases of the Simplex method 1
Linear optimization: Phases of the Simplex method
A linear optimization tableau can be systemized in different Phases that have to be dealt with before the actual optimization step can be used, which is explained by the method of using the simplex algorithm.
The Phases are:
Phase 0: equations
The locked variables are identifyable where equations are written as constraints. This means that the structure variable (slack variable) has to become 0 to solve the equation (locked variable). This structure variable must not stand in the basis, therefore it is urgent for it to leave the basis. The row where this blocked variable is findable becomes the pivot-row . Those coulumns that do not contain blocked variables as a non basis variable become the pivot coulumn. After the pivot element is found, a simplex iteration follows by the simple rules of simplex algorithm.
old constraints:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{j}a_{ij}x_j \le b_i \Rightarrow y_i+\sum_{j}a_{ij}x_j =b_i ;~~y_i \ge 0
new constraints:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{j} a_{ij}x_j = b_i
In the new constraints there are no . This means that this structure variable (slack variable) has become 0
Example tableau:
Phase 0’: free variables
Free variables are variables for which the not negativity conditions are not valid respectivly are not defined. They have to be transfered to the basis as well. As long as free variables are located in the non-basis, the coulumn they stand in becomes a pivot-coulumn. If a free variable is relocated to the basis, it is blocked for the rest of the optimization procedure. This means the basis-row it stands in after the relocation cannot become a pivot-row again. Again a simplex iteration follows the search of the pivot element in this phase.
Phase 1: minimizing the infeasibility
Constraints that contain a ≥ operator in it form an infeasible initial solution. In the simplex tableau this fact is dealt with a multiplication by -1. This means also that a negative right side is generated (infeasible). This often appears in constraints whereas the profit should be higher than a special value for example. The pivot row becomes the row where the negative right side is located. If possible the pivot-coulumn should be a coulumn where the pivot element has a negative sign. (Spezialfall erwähnen!!!) A simplex iteration is again required after finding the pivot element.
Phase 2: Optimization
If an optimal solution is not found by correcting the three Phases above, more simplex iterations are probably required to reach the optimal solution, where not negative values stand in the non-basis.
