Zulässige Basislösung

Eine zulässige Basislösung ist ein Begriff aus der Linearen Optimierung, der insbesondere beim Simplex-Verfahren verwendet wird. Eine zulässige Basislösung entspricht genau den Ecken des Polyeders, der die Restriktionsmenge beschreibt. Da in der Linearen Optimierung die Optimallösungen immer in den Ecken angenommen werden, ist die Optimallösung immer unter den zulässigen Basislösungen zu 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 man als Beispiel das 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.