Linear optimization: Phases of the Simplex method 1: Unterschied zwischen den Versionen

Version vom 25. Juni 2013, 19:33 Uhr

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

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 ${\displaystyle y_{i}}$. This means that this structure variable (slack variable) has become 0

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.

${\displaystyle x_{1}}$ and ${\displaystyle x_{2}}$ are the variables which have to be optimized. In the last line, that represents the non negativity conditions, in the adjoining tableau only ${\displaystyle x_{1}}$ is mentioned and therefore restricted. Hence ${\displaystyle x_{2}}$ is a free variable.

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. 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 ${\displaystyle y_{3}}$ 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 to reach the optimal solution, where not negative values stand in the non-basis.

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 1200

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

Eliminate Phase 0

The equation in the spot of ${\displaystyle y_{3}}$ has to be dealt with. The slack variable ${\displaystyle y_{3}}$ has to leave the basis. It's row becomes the pivot row. The pivot coulumn has to be the coulumn where ${\displaystyle x_{1}}$ is located because it's the only worth that is possible. -2 or 0 are not allowed to be the pivot element so 1 is left and becomes the pivot element. (yellow hinted)

Simplex iteration with found Pivot element

After the simplex iteration the tableau looks like this. When the slack variable is changed into the non basis it is blocked for the rest of the optimization. This fact is marked by the red font color.

Eliminate Phase 0'

By choosing the coulumn of ${\displaystyle x_{3}}$ as a pivot coulumn you start eliminating the free variables and transport it to the basis. The only possible pivot element is -1760 in the row of ${\displaystyle y_{1}}$. 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.

Simplex iteration with found Pivot element

After the iteration variable ${\displaystyle x_{3}}$ is now in the basis. It's row also gets blocked and can not be used again in the optimization process. Also another negative right side is generated, which has to be dealt with in the step of eliminating phase 1.

Eliminating Phase 1

The row in that the negative right side is located, gets pivot row again. In this case we pick the row of ${\displaystyle y_{2}}$. It is useful to pick a pivot element with a negative sign to get rid of the negative sign of the right side. Therefore the pivot coulumn is the coulumn of ${\displaystyle x_{2}}$ and the pivot element is -3.

Simplex iteration with found Pivot element

After the iteration one can recognize that the right side in the coulumn of ${\displaystyle x_{3}}$ has a positive sign again. Therefore it has not to be dealt with in addition. The solution is already optimal because of the positive values in the non basis. This makes the optimization step (Phase 2) obsolete and the optimization is done in this point.

Sources

OR-script,OR-wiki,OR-tutorium

Authors

Lucas Bertram, Niklas Drawert, Simon Liesenfeld