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 $A$, eine $m\times n$ Matrix mit vollem Rang $m$ sowie ein Vektor $b$ mit nichtnegativen Einträgen. Für eine Indexmenge $K$ sei $A_K$ die Matrix, die aus den Spalten besteht, deren Index in $K$ enthalten ist.

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

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

Eine Basislösung heißt zulässig, wenn $x_j\ge 0$ für alle $j\in B$ gilt.

Beispiel

Betrachtet man als Beispiel das Ungleichungssystem

$\begin{array}{ccc}{x}_1& & \le 1\\ & x_2& \le 1\\ x_1+& x_2& \le \gamma \end{array}$

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

$\left(\begin{array}{ccccc}1& 0& 1& 0& 0\\ 0& 1& 0& 1& 0\\ 1& 1& 0& 0& 1\end{array}\right)\cdot x=\left(\begin{array}{c}1\\ 1\\ \gamma \end{array}\right)$

$x_i\ge 0,i=1,\dots ,5$

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

1. Die Menge $B=\{1,2\}$ ist keine Basis, da sie zu wenig Elemente enthält. Setzt man $\gamma =2$, so gilt zwar $A_B\cdot (1,1{)}^T=b$, aber $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 $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 $B^{\prime }=\{1,2,5\}$ eine Basis, und es gilt $A_{B^{\prime }}\cdot (1,1,0{)}^T=b$. Die zur Basis gehörende Nichtbasismenge wäre dann $N=\{3,4\}$.
2. Die Menge $B=\{1,3,5\}$ hat zwar drei Elemente, aber der Rang der Matrix $A_B$ ist nur zwei, sie ist also nicht invertierbar.
3. Der Vektor $(1,0,1,0,0{)}^T$ kann keine zulässige Basislösung sein, da er nicht $Ax=b$ löst.
4. Der Vektor $(0.5,0.5,0.5,0.5,\gamma -1{)}^T$ für $\gamma \ge 1$ löst zwar $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 $\gamma =0,5$, so löst der Vektor $(-0.5,1,1.5,0,0{)}^T$ das Gleichungssystem $Ax=b$ und erlaubt eine Aufteilung der Indizes in Basismenge $B=\{1,2,3\}$ und Nichtbasismenge $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 $\gamma \ge 0$ Ist $B=\{3,4,5\}$ eine Basis und $N=\{1,2\}$ eine Nichtbasis, die entsprechende zulässige Basislösung ist $(0,0,1,1,\gamma {)}^T$.

Literatur

• Vorlage:Literatur
• Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2004, ISBN 3-540-43575-1.