Linear optimization: Phases of the Simplex method 4

The simplex algorithm, developed by George Dantzig in 1947, solves LP problems by constructing a feasible solution at a vertex of the polytope and then walking along a path on the edges of the polytope to vertices with non-decreasing values of the objective function until an optimum is reached for sure.

The Simplex – Algorithm is made up of four Phases:

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

Phase 1: invalid initial solution

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

Phase 2: Optimization

Phase 0: locked variables

Simplex Algorithm is used to tranfer an inequation to an equation, by bringing slack variables in it. To solve the equation (locked variable) slack variables have to become zero. The locked variable can't be in the basis. So it has to leave the basis. The pivot-row is the row were you can find the blocked variable. The other rows without any blocked variables become the pivot column. With these elements we solve the equation by following the rules of simplex algorithm.

Phase 0`: free variables

In some cases there may be variables, were a non negativity condition is not valid. Therefore they need to be transfered to the basis. The optimisation prodecure would be blocked if there is a free variable located to a basis. The column without a free variable has to be chosen as the pivot - column. A pivot-row could be any row wich has no free variable as a basis variable. Once a free variable has been in a basis, this row can never be pivot- row again.

Phase 1: invalid initial solution

The restrictions have negative rights in the initial solution in some cases, therfore the nonnegativity constraints is violated because the structure variables $x_{i}$ assume the value zero in the initial solution. A $/ge$ operator is an infeasible initial solution. The fact simplex tableau is treated with a multiplication by -1. The negative right side is generated incredibly. This often seems in restriction during the profit should be higher than a special value. Pivot row and pivot column should be chosen so that the values of the right-hand side take positive values when translated.

Phase 2: Optimization

Choosing of the Pivot element:

Steepest-UNIT-ASCENT: Column with absolutely the greatest negative target solution coefficient

GREATEST CHANGE: Column with absolutely the greatest product of

Exchange basic variables (BV) and in accordance non basic variables (NBV)
Invoice of elements of the Pivot row and the Pivot gap
Conversion of simplex tableau to the calculation rules
Check, whether another iteration is requied
Go to 1, if the solution isn’t optimal

Example

profit: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): -350x_1 -260x_2 \Rightarrow max

constraints: 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

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): x_1 \le 10 \Rightarrow -x_1 + 10 \ge 0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 0,5x_1 + x_2 \le 20 \Rightarrow -x_1 -2 x_2 + 40 \ge 0

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): 200x_1 + 100x_2 \le 2400 \Rightarrow -2x_1 - x_2 + 24 \ge 0

Start tableau