www.wikidata.de-de.nina.az

Zulässige Basislösung Eine zulässige Basislösung ist ein Begriff aus der Linearen Optimierung der insbesondere beim Simp

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 Bearbeiten

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 Bearbeiten

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 Bearbeiten

  • 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.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Eine zulassige Basislosung ist ein Begriff aus der Linearen Optimierung der insbesondere beim Simplex Verfahren verwendet wird Eine zulassige Basislosung entspricht genau den Ecken des Polyeders der die Restriktionsmenge beschreibt Da in der Linearen Optimierung die Optimallosungen immer in den Ecken angenommen werden ist die Optimallosung immer unter den zulassigen Basislosungen zu finden Definition BearbeitenGegeben sei A displaystyle A nbsp eine m n displaystyle m times n nbsp Matrix mit vollem Rang m displaystyle m nbsp sowie ein Vektor b displaystyle b nbsp mit nichtnegativen Eintragen Fur eine Indexmenge K displaystyle K nbsp sei A K displaystyle A K nbsp die Matrix die aus den Spalten besteht deren Index in K displaystyle K nbsp enthalten ist Eine Indexmenge B 1 n displaystyle B subset 1 dots n nbsp mit B m displaystyle B m nbsp heisst eine Basis oder eine Basismenge von A displaystyle A nbsp wenn A B displaystyle A B nbsp invertierbar ist Die Menge N 1 n B displaystyle N 1 dots n setminus B nbsp heisst dann die zu B displaystyle B nbsp gehorende Nichtbasismenge Eine Losung des Gleichungssystems A x b displaystyle Ax b nbsp heisst eine Basislosung wenn x j 0 displaystyle x j 0 nbsp fur alle j N displaystyle j in N nbsp gilt Eine Basislosung heisst zulassig wenn x j 0 displaystyle x j geq 0 nbsp fur alle j B displaystyle j in B nbsp gilt Beispiel BearbeitenBetrachtet man als Beispiel das Ungleichungssystem x 1 1 x 2 1 x 1 x 2 g displaystyle begin aligned x 1 amp amp leq 1 amp x 2 amp leq 1 x 1 amp x 2 amp leq gamma end aligned nbsp mit den Vorzeichenbeschrankungen x 1 x 2 0 displaystyle x 1 x 2 geq 0 nbsp und g R displaystyle gamma in mathbb R nbsp Die ersten beiden Ungleichungen in Verbindung mit den Vorzeichenbeschrankungen bilden den Einheitswurfel im R 2 displaystyle mathbb R 2 nbsp Die dritte Ungleichung beschreibt den Halbraum dessen Grenze durch die Punkte 0 g displaystyle 0 gamma nbsp und g 0 displaystyle gamma 0 nbsp geht und die Null enthalt wenn g 0 displaystyle gamma geq 0 nbsp ist Ist g lt 0 displaystyle gamma lt 0 nbsp ist die beschriebene Menge leer ist g gt 2 displaystyle gamma gt 2 nbsp so ist die dritte Ungleichung redundant Durch Einfuhrung von Schlupfvariablen ergibt sich die Standardform 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 x 1 1 g displaystyle begin pmatrix 1 amp 0 amp 1 amp 0 amp 0 0 amp 1 amp 0 amp 1 amp 0 1 amp 1 amp 0 amp 0 amp 1 end pmatrix cdot x begin pmatrix 1 1 gamma end pmatrix nbsp x i 0 i 1 5 displaystyle x i geq 0 i 1 dots 5 nbsp Wir bezeichnen die Matrix mit A displaystyle A nbsp und den Vektor auf der rechten Seite mit b displaystyle b nbsp Die Matrix hat vollen Rang und die rechte Seite ist positiv fast immer Die Menge B 1 2 displaystyle B 1 2 nbsp ist keine Basis da sie zu wenig Elemente enthalt Setzt man g 2 displaystyle gamma 2 nbsp so gilt zwar A B 1 1 T b displaystyle A B cdot 1 1 T b nbsp aber A B displaystyle A B nbsp kann schon alleine aufgrund der Dimensionierung nicht invertierbar sein Dies lasst sich vermeiden indem man ein weiteres Element in die Basismenge aufnimmt so dass A B displaystyle A B nbsp quadratisch und invertierbar ist und einfach die Komponente des neuen Elements in der Basislosung auf Null setzt da die Losbarkeit nicht durch die Hinzunahme beeinflusst wird So ware zum Beispiel B 1 2 5 displaystyle B 1 2 5 nbsp eine Basis und es gilt A B 1 1 0 T b displaystyle A B cdot 1 1 0 T b nbsp Die zur Basis gehorende Nichtbasismenge ware dann N 3 4 displaystyle N 3 4 nbsp Die Menge B 1 3 5 displaystyle B 1 3 5 nbsp hat zwar drei Elemente aber der Rang der Matrix A B displaystyle A B nbsp ist nur zwei sie ist also nicht invertierbar Der Vektor 1 0 1 0 0 T displaystyle 1 0 1 0 0 T nbsp kann keine zulassige Basislosung sein da er nicht A x b displaystyle Ax b nbsp lost Der Vektor 0 5 0 5 0 5 0 5 g 1 T displaystyle 0 5 0 5 0 5 0 5 gamma 1 T nbsp fur g 1 displaystyle gamma geq 1 nbsp lost zwar A x b displaystyle Ax b nbsp kann aber keine zulassige Basislosung sein da er zu viele Eintrage enthalt die sich von der Null unterscheiden Deshalb ist ein Aufteilen in eine zweielementige Nichtbasismenge mit Eintragen Null und in eine dreielementige Basismenge mit Elementen ungleich null nicht moglich Setzt man g 0 5 displaystyle gamma 0 5 nbsp so lost der Vektor 0 5 1 1 5 0 0 T displaystyle 0 5 1 1 5 0 0 T nbsp das Gleichungssystem A x b displaystyle Ax b nbsp und erlaubt eine Aufteilung der Indizes in Basismenge B 1 2 3 displaystyle B 1 2 3 nbsp und Nichtbasismenge N 4 5 displaystyle N 4 5 nbsp es handelt sich also um eine Basislosung Es handelt sich aber nicht um eine zulassige Basislosung da der erste Eintrag kleiner Null ist Fur g 0 displaystyle gamma geq 0 nbsp Ist B 3 4 5 displaystyle B 3 4 5 nbsp eine Basis und N 1 2 displaystyle N 1 2 nbsp eine Nichtbasis die entsprechende zulassige Basislosung ist 0 0 1 1 g T displaystyle 0 0 1 1 gamma T nbsp Literatur BearbeitenPeter 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 Abgerufen von https de wikipedia org w index php title Zulassige Basislosung amp oldid 214306954