Permissible basic solution

from Wikipedia, the free encyclopedia

A permissible basic solution is a term from linear optimization that is used in particular in the simplex method . A feasible basic solution corresponds exactly to the corners of the polyhedron that describes the restriction set. Since in linear optimization the optimal solutions are always accepted in the corners, the optimal solution can always be found among the permissible basic solutions.

definition

Given a matrix with full rank and a vector with nonnegative entries. For an index set, let be the matrix that consists of the columns whose index is contained in.

An index set with is called a base or a base set of if it is invertible. The set is then called the non-base set to which it belongs.

A solution to the system of equations is called a basic solution if applies to all .

A basic solution is called permissible if applies to all .

example

Consider the inequality system as an example

with the sign constraints and . The first two inequalities in connection with the sign constraints form the unit cube im . The third inequality describes the half-space whose boundary goes through the points and and which contains zero if is. If the set described is empty , then the third inequality is redundant. The standard form results from the introduction of slip variables

We denote the matrix with and the vector on the right with . (The matrix has full rank and the right side is positive (almost always))

  1. The set is not a basis because it contains too few elements. If one sets , the following applies , but cannot be inverted due to the dimensioning alone. This can be avoided by adding another element to the basic set, so that it is quadratic and invertible, and simply setting the component of the new element in the basic solution to zero, since the solvability is not influenced by the addition. For example, there would be a base, and it applies . The non-base set belonging to the base would then be .
  2. The set has three elements, but the rank of the matrix is only two, so it is not invertible.
  3. The vector cannot be a feasible basic solution because it does not solve.
  4. The vector for solves, but cannot be a valid basic solution because it contains too many entries that differ from zero. Therefore, a division into a two-element non-base set with entries zero and a three-element base set with elements not equal to zero is not possible.
  5. If one sets , the vector solves the system of equations and allows a division of the indices into a basic set and a non- basic set , so it is a basic solution. However, it is not a valid basic solution because the first entry is less than zero.
  6. For is a basis and a non-basis, the corresponding basic feasible solution is .

literature