Linear optimization: Phases of the Simplex method 1

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche

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.

Different Phases:

Phase 0 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow

Phase 0' Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow 
Phase 1 Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Rightarrow 
Phase 2

Phase 0: equations

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Phase 0

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


Phase 0': Free variables

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Phase 0'

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.


and are the variables which have to be optimized. In the last line, that represents the non negativity conditions, in the adjoining tableau only is mentioned and therefore restricted. Hence is a free variable.



Phase 1: Minimizing the infeasibility

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden
Phase 1

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. A simplex iteration is again required after finding the pivot element.


In the given example the third constraint is representing the actual phase. The restriction has a negative sign for each value, because this line was multiplicated by -1 due to the infeasible initial solution.


Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): y_3: ~30x_1+30x_2 \ge 600 \Rightarrow -30x_1-30x_2\le -600



Phase 2: Optimization

If an optimal solution is not found by correcting the three Phases above, more simplex iterations are probably required. On the one hand an optimal solution is reached, where only positive values stand in the objective function coefficients. Moreover all elements on the right hand side have to be positive as well. On the other hand it can be shown that no feasible solution exists, if the algorithm is not able to replace a negative value in the objective function coefficients.

Short reminder of how to do the simplex optimization process

  1. Selection of the Pivot element
  2. Exchange basic variables (BV) and corresponding non basic variables (NBV)
  3. Calculate elements of the Pivot row and the Pivot column
  4. Calculate remaining columns
  5. Check, whether another iteration is necessary


Excourse

Primal degeneracy
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

The pivot row is free to choose, because there is more than one valid option. Thereby you have to decide whether you select the first or the second row as a pivot row in the given example.

Dual degeneracy
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

The pivot column is free to choose, because you have to decide between two or more different column, which contain the same negative value. In tableau above you can choose between column one or two, by the greatest change method or just randomly decide.

Example

The following example illustrates the different phases of the simplex.

Linear Program:

costs
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 10x_1 + 20x_2 + 40000x_3 \rightarrow min!


constraints
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1+ 2x_2-1760x_3 \le 8800
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1+x_2 \ge 12000 \Rightarrow -x_1-x_2 \le -12000
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1-2x_2=0
not negativity condition
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1 \ge 0
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_2 \ge 0



Step by Step solution
By using the LP we create a first tableau
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden




Eliminate Phase 0
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden


The equation in the last row, that contains , has to be dealt with. The slack variable has to leave the basis. It's row becomes the pivot row. The pivot column has to be the column where is located, because it's the only possible value. "-2" or "0" are not allowed to become the pivot element, because dividing by "0" is prohibited and "-2" would generate a negative right hand side. Therefore "1" (yellow marked) is left and becomes the pivot element.



Simplex iteration 
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden


After the simplex iteration we obtain the tableau shown above. When the slack variable has moved into the non-basis, it is blocked until the end of the optimization process. Thus the blocked column cannot be a pivot column again.



Eliminate Phase 0'
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden


By choosing the coulumn of as a pivot column you start eliminating the free variables and transporting them to the basis. The only possible pivot element is "-1760" in the first row, where is located. The zeroes in the lines below the corresponding column are strictly prohibited to use as pivot element. Normally this pivot element should have a positive sign, but in this special case there is a negative one. A simplex iteration is still possible though. It only creates a negative right hand side, which is to be dealt with in phase 1.



Simplex iteration
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden


After the iteration the variable is now in the basis. It's row is also blocked and therefore cannot be used again as a pivot row in the following optimization process. As mentioned above another negative right hand side is generated, which can be dealt with in the step of eliminating phase 1.



Eliminating Phase 1
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden


The row in that the negative right hand side is located, becomes the new pivot row. Thereby we pick the row of as a pivot row, because the first one is blocked for pivotization throughout the steps above, where was set to a blocked status. It is useful to pick a pivot element with a negative sign to get rid of the negative sign of the right hand side. Therefore the pivot coulumn is the coulumn of and the pivot element is "-3".



Simplex iteration
Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

After the iteration, one can recognize that the right hand side in the column of has a positive sign again. Therefore the solution is already optimal, because the objective function coefficients only consists of positive values. This makes the optimization step (Phase 2) obsolete and we are finished with the optimization process.

Sources

OR-script

OR-wiki : https://bisor.wiwi.uni-kl.de/orwiki/Phasen_des_Simplex-Algorithmus

OR-tutorium

Authors

Lucas Bertram, Niklas Drawert, Simon Liesenfeld