Zulässige Basislösung

Eine zulässige Basislösung i​st ein Begriff a​us der Linearen Optimierung, d​er insbesondere b​eim Simplex-Verfahren verwendet wird. Eine zulässige Basislösung entspricht g​enau den Ecken d​es Polyeders, d​er die Restriktionsmenge beschreibt. Da i​n der Linearen Optimierung d​ie Optimallösungen i​mmer in d​en Ecken angenommen werden, i​st die Optimallösung i​mmer unter d​en zulässigen Basislösungen z​u finden.

Definition

Gegeben sei ${\displaystyle A}$, eine ${\displaystyle m\times n}$ Matrix mit vollem Rang ${\displaystyle m}$ sowie ein Vektor ${\displaystyle b}$ mit nichtnegativen Einträgen. Für eine Indexmenge ${\displaystyle K}$ sei ${\displaystyle A_{K}}$ die Matrix, die aus den Spalten besteht, deren Index in ${\displaystyle K}$ enthalten ist.

Eine Indexmenge ${\displaystyle B\subset \{1,\dots ,n\}}$ mit ${\displaystyle |B|=m}$ heißt eine Basis oder eine Basismenge von ${\displaystyle A}$, wenn ${\displaystyle A_{B}}$ invertierbar ist. Die Menge ${\displaystyle N:=\{1,\dots ,n\}\setminus B}$ heißt dann die zu ${\displaystyle B}$ gehörende Nichtbasismenge.

Eine Lösung des Gleichungssystems ${\displaystyle Ax=b}$ heißt eine Basislösung, wenn ${\displaystyle x_{j}=0}$ für alle ${\displaystyle j\in N}$ gilt.

Eine Basislösung heißt zulässig, wenn ${\displaystyle x_{j}\geq 0}$ für alle ${\displaystyle j\in B}$ gilt.

Beispiel

Betrachtet m​an als Beispiel d​as Ungleichungssystem

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

mit den Vorzeichenbeschränkungen ${\displaystyle x_{1},x_{2}\geq 0}$ und ${\displaystyle \gamma \in \mathbb {R} }$. Die ersten beiden Ungleichungen in Verbindung mit den Vorzeichenbeschränkungen bilden den Einheitswürfel im ${\displaystyle \mathbb {R} ^{2}}$. Die dritte Ungleichung beschreibt den Halbraum, dessen Grenze durch die Punkte ${\displaystyle (0,\gamma )}$ und ${\displaystyle (\gamma ,0)}$ geht und die Null enthält, wenn ${\displaystyle \gamma \geq 0}$ ist. Ist ${\displaystyle \gamma <0}$ ist die beschriebene Menge leer, ist ${\displaystyle \gamma >2}$, so ist die dritte Ungleichung redundant. Durch Einführung von Schlupfvariablen ergibt sich die Standardform

${\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}$

Wir bezeichnen die Matrix mit ${\displaystyle A}$ und den Vektor auf der rechten Seite mit ${\displaystyle b}$. (Die Matrix hat vollen Rang und die rechte Seite ist positiv(fast immer))

1. Die Menge ${\displaystyle B=\{1,2\}}$ ist keine Basis, da sie zu wenig Elemente enthält. Setzt man ${\displaystyle \gamma =2}$, so gilt zwar ${\displaystyle A_{B}\cdot (1,1)^{T}=b}$, aber ${\displaystyle A_{B}}$ kann schon alleine aufgrund der Dimensionierung nicht invertierbar sein. Dies lässt sich vermeiden, indem man ein weiteres Element in die Basismenge aufnimmt, so dass ${\displaystyle A_{B}}$ quadratisch und invertierbar ist, und einfach die Komponente des neuen Elements in der Basislösung auf Null setzt, da die Lösbarkeit nicht durch die Hinzunahme beeinflusst wird. So wäre zum Beispiel ${\displaystyle B'=\{1,2,5\}}$ eine Basis, und es gilt ${\displaystyle A_{B'}\cdot (1,1,0)^{T}=b}$. Die zur Basis gehörende Nichtbasismenge wäre dann ${\displaystyle N=\{3,4\}}$.
2. Die Menge ${\displaystyle B=\{1,3,5\}}$ hat zwar drei Elemente, aber der Rang der Matrix ${\displaystyle A_{B}}$ ist nur zwei, sie ist also nicht invertierbar.
3. Der Vektor ${\displaystyle (1,0,1,0,0)^{T}}$ kann keine zulässige Basislösung sein, da er nicht ${\displaystyle Ax=b}$ löst.
4. Der Vektor ${\displaystyle (0{.}5,0{.}5,0{.}5,0{.}5,\gamma -1)^{T}}$ für ${\displaystyle \gamma \geq 1}$ löst zwar ${\displaystyle Ax=b}$, kann aber keine zulässige Basislösung sein, da er zu viele Einträge enthält, die sich von der Null unterscheiden. Deshalb ist ein Aufteilen in eine zweielementige Nichtbasismenge mit Einträgen Null und in eine dreielementige Basismenge mit Elementen ungleich null nicht möglich.
5. Setzt man ${\displaystyle \gamma =0{,}5}$, so löst der Vektor ${\displaystyle (-0{.}5,1,1{.}5,0,0)^{T}}$ das Gleichungssystem ${\displaystyle Ax=b}$ und erlaubt eine Aufteilung der Indizes in Basismenge ${\displaystyle B=\{1,2,3\}}$ und Nichtbasismenge ${\displaystyle N=\{4,5\}}$, es handelt sich also um eine Basislösung. Es handelt sich aber nicht um eine zulässige Basislösung, da der erste Eintrag kleiner Null ist.
6. Für ${\displaystyle \gamma \geq 0}$ Ist ${\displaystyle B=\{3,4,5\}}$ eine Basis und ${\displaystyle N=\{1,2\}}$ eine Nichtbasis, die entsprechende zulässige Basislösung ist ${\displaystyle (0,0,1,1,\gamma )^{T}}$.

Literatur

• Peter Knabner, Wolf Barth: Lineare Algebra. Grundlagen und Anwendungen (= Springer-Lehrbuch). Springer Spektrum, Berlin u. a. 2013, ISBN 978-3-642-32185-6.
• Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2004, ISBN 3-540-43575-1.