Zulässige Basislösung

Begriff aus der Linearen Optimierung

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.

DefinitionBearbeiten

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.

BeispielBearbeiten

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  .

LiteraturBearbeiten