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

Version vom 25. Juni 2013, 14:41 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

[[Datei:]]

Sources

OR-Tutorium,

Authors

Lucas Bertram, Niklas Drawert, Simon Liesenfeld