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

Eine Indexmenge mit heißt eine Basis oder eine Basismenge von , wenn invertierbar ist. Die Menge heißt dann die zu gehörende Nichtbasismenge.

Eine Lösung des Gleichungssystems heißt eine Basislösung, wenn für alle gilt.

Eine Basislösung heißt zulässig, wenn für alle gilt.

Beispiel

Betrachtet man als Beispiel das Ungleichungssystem

mit den Vorzeichenbeschränkungen und . Die ersten beiden Ungleichungen in Verbindung mit den Vorzeichenbeschränkungen bilden den Einheitswürfel im . Die dritte Ungleichung beschreibt den Halbraum, dessen Grenze durch die Punkte und geht und die Null enthält, wenn ist. Ist ist die beschriebene Menge leer, ist , so ist die dritte Ungleichung redundant. Durch Einführung von Schlupfvariablen ergibt sich die Standardform

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

  1. Die Menge ist keine Basis, da sie zu wenig Elemente enthält. Setzt man , so gilt zwar , aber 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 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 eine Basis, und es gilt . Die zur Basis gehörende Nichtbasismenge wäre dann .
  2. Die Menge hat zwar drei Elemente, aber der Rang der Matrix ist nur zwei, sie ist also nicht invertierbar.
  3. Der Vektor kann keine zulässige Basislösung sein, da er nicht löst.
  4. Der Vektor für löst zwar , 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 , so löst der Vektor das Gleichungssystem und erlaubt eine Aufteilung der Indizes in Basismenge und Nichtbasismenge , 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 Ist eine Basis und eine Nichtbasis, die entsprechende zulässige Basislösung ist .

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.