Permissible basic solution

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. ${\displaystyle A}$ ${\displaystyle m\times n}$ ${\displaystyle m}$ ${\displaystyle b}$ ${\displaystyle K}$ ${\displaystyle A_{K}}$ ${\displaystyle K}$

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. ${\displaystyle B\subset \{1,\dots ,n\}}$ ${\displaystyle |B|=m}$ ${\displaystyle A}$ ${\displaystyle A_{B}}$ ${\displaystyle N:=\{1,\dots ,n\}\setminus B}$ ${\displaystyle B}$

A solution to the system of equations is called a basic solution if applies to all . ${\displaystyle Ax=b}$ ${\displaystyle x_{j}=0}$ ${\displaystyle j\in N}$

A basic solution is called permissible if applies to all . ${\displaystyle x_{j}\geq 0}$ ${\displaystyle j\in B}$

example

Consider the inequality system as an example

${\displaystyle {\begin{aligned}x_{1}&&\leq 1\\&x_{2}&\leq 1\\x_{1}+&x_{2}&\leq \gamma \end{aligned}}}$

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 ${\displaystyle x_{1},x_{2}\geq 0}$ ${\displaystyle \gamma \in \mathbb {R} }$ ${\displaystyle \mathbb {R} ^{2}}$ ${\displaystyle (0,\gamma )}$ ${\displaystyle (\gamma ,0)}$ ${\displaystyle \gamma \geq 0}$ ${\displaystyle \gamma <0}$ ${\displaystyle \gamma >2}$

${\displaystyle {\begin{pmatrix}1&0&1&0&0\\0&1&0&1&0\\1&1&0&0&1\end{pmatrix}}\cdot x={\begin{pmatrix}1\\1\\\gamma \end{pmatrix}}}$

${\displaystyle x_{i}\geq 0\,,\,i=1,\dots ,5}$

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)) ${\displaystyle A}$ ${\displaystyle b}$

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 . ${\displaystyle B=\{1,2\}}$ ${\displaystyle \gamma =2}$ ${\displaystyle A_{B}\cdot (1,1)^{T}=b}$ ${\displaystyle A_{B}}$ ${\displaystyle A_{B}}$ ${\displaystyle B'=\{1,2,5\}}$ ${\displaystyle A_{B'}\cdot (1,1,0)^{T}=b}$ ${\displaystyle N=\{3,4\}}$
2. The set has three elements, but the rank of the matrix is only two, so it is not invertible. ${\displaystyle B=\{1,3,5\}}$ ${\displaystyle A_{B}}$
3. The vector cannot be a feasible basic solution because it does not solve. ${\displaystyle (1,0,1,0,0)^{T}}$ ${\displaystyle Ax=b}$
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. ${\displaystyle (0{,}5,0{,}5,0{,}5,0{,}5,\gamma -1)^{T}}$ ${\displaystyle \gamma \geq 1}$ ${\displaystyle Ax=b}$
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. ${\displaystyle \gamma =0{,}5}$ ${\displaystyle (-0{,}5,1,1{,}5,0,0)^{T}}$ ${\displaystyle Ax=b}$ ${\displaystyle B=\{1,2,3\}}$ ${\displaystyle N=\{4,5\}}$
6. For is a basis and a non-basis, the corresponding basic feasible solution is . ${\displaystyle \gamma \geq 0}$ ${\displaystyle B=\{3,4,5\}}$ ${\displaystyle N=\{1,2\}}$ ${\displaystyle (0,0,1,1,\gamma )^{T}}$

literature

• Peter Knabner , Wolf Barth : Lineare Algebra. Basics and applications (=  Springer textbook ). Springer Spectrum, Berlin et al. 2013, ISBN 978-3-642-32185-6 .
• Florian Jarre, Josef Stoer: Optimization. Springer, Berlin 2004, ISBN 3-540-43575-1 .