What are structure variables

The simplex method is a method to solve problems of linear planning (see linear planning). Starting from the origin, the simplex method examines the corner points of the admissible solution space in order to determine the maximum of the objective function.


example

To maximize z with z + (-300) x1 + (-500) x2 = 0 under the constraints:

x1 + 2 x2 <= 170,
x1 + x2 <= 150,
x2 <= 180,
x1> = 0 and
x2> = 0.

The first three constraints are transformed into equations by introducing slip variables:

x1 + 2 x2 + y1 = 170,
x1 + x2 + y2 = 150 and
x2 + y3 = 180.

The yi must be greater than or equal to zero.


terminology

Structure variable - are the variables whose values ​​make up a solution (in the example x1 and x2),
Slip variables - are variables that are introduced when the constraints are transformed (y1, y2 and y3),
Non-base variables - are set to zero to determine the base variables.


Formula symbol

n - number of non-basic variables (in the example 2),
m - number of basic variables (3),
a [0,1], ... a [0, n] - coefficients of the objective function (-300, -500),
a [1,0], ..., a [m, 0] - right sides of the restrictions (170, 150, 180),
a [1,1], ... a [m, n] - coefficients of the restrictions ((1, 2), (1, 1), (0, 1)),
a * [i, j] - coefficients after the simplex step.

 
Simplex step (Steepest Unit Ascent)

1. Determine s such that a [0, s] is the smallest number of the a [0, j] (1 <= j <= n).
2. If a [0, s]> = 0, the solution has been found. If the choice is not clear, there is a dual degeneracy. You then choose one of the options.
3. Determine r such that a [r, 0] / a [r, s] is the smallest positive number of the a [i, 0] / a [i, s] (1 <= i <= m).
4. If all quotients are less than or equal to zero, there is no solution (primal degeneracy). If the choice is not clear, one chooses randomly from the possibilities (primal degeneracy).
5. Calculate the new coefficients:
• a * [r, s] = 1 / a [r, s] (pivot element),
• a * [i, s] = - a [i, s] / a [r, s] (pivot column except pivot element, i.e. for i <> r),
• a * [r, j] = a [r, j] / a [r, s] (pivot line except pivot element, i.e. for j <> s),
• a * [i, j] = a [i, j] - a [i, s] a [r, j] / a [r, s] (all other elements, i.e. i <> r and j <> s ).
6. Swap the r-th basic variable for the s-th non-basic variable.

In the greatest change variant of the simplex method, the pivot column for which a [r, 0] / a [r, s] * a [0, s] is maximum (r is selected as in 3 depending on s) ).


Equations as restrictions

Equations as restrictions are initially treated like inequalities (insertion of a slack variable). However, the associated slack variable is noted as locked, it must not be included in the base (since it must remain zero).


Missing nonnegativity conditions

If the condition v> = 0 does not apply to a variable v, this variable is called free. Free variables are to be brought into the base.


Invalid initial solution

Because the structure variables are identical with the non-basic variables before the first simplex step, the structure variables become zero. If this tuple of values ​​is not one of the possible solutions, one speaks of an inadmissible initial solution. This is always the case when restriction equations with a> = exist (negative right-hand side). The line concerned is then selected as the pivot line.


degeneration

If the choice of the pivot column is not clear, one speaks of dual degeneracy. If the choice of the pivot line is not clear or not possible, one speaks of primal degeneration.