Linear optimization: Phases of the Simplex method 1: Unterschied zwischen den Versionen
[unmarkierte Version] | [unmarkierte Version] |
Zeile 96: | Zeile 96: | ||
[[Datei:2k.jpg|center|]] | [[Datei:2k.jpg|center|]] | ||
[[Datei:3k.jpg|center|]] | [[Datei:3k.jpg|center|]] | ||
− | [[Datei: | + | [[Datei:4k_1.jpg|center|]] |
[[Datei:5k.jpg|center|]] | [[Datei:5k.jpg|center|]] | ||
[[Datei:6k.jpg|center|]] | [[Datei:6k.jpg|center|]] |
Version vom 25. Juni 2013, 15:15 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
Inhaltsverzeichnis
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
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.
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
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 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
- has to leave the basis
- it's row becomes the pivot row
Sources
OR-script,OR-wiki,OR-tutorium
Authors
Lucas Bertram, Niklas Drawert, Simon Liesenfeld