Basislösungen < Gleichungssysteme < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo,
Bin in einer Aufgabe über den Begriff Basislösung gestolpert. Hat jemand einen Link bzw. eine Erklärung parat was es damit in Bezug auf LGS auf sich hat?
Im Arens kann ich leider nichts dazu finden...
Vielen Dank,
lg
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:54 Do 14.07.2011 | | Autor: | abakus |
> Hallo,
>
> Bin in einer Aufgabe über den Begriff Basislösung
> gestolpert. Hat jemand einen Link bzw. eine Erklärung
> parat was es damit in Bezug auf LGS auf sich hat?
> Im Arens kann ich leider nichts dazu finden...
Hallo,
leider kann ich dir die Frage nicht beantworten.
Bei einer bekannten Suchmaschine gibt es aber einige Treffer zu dem Begriff. Ich werde mich mal in das Thema einlesen.
Gruß Abakus
>
> Vielen Dank,
> lg
|
|
|
| |
|
http://de.wikipedia.org/wiki/Simplex-Verfahren#Basen.2C_Basisl.C3.B6sungen_und_Ecken
Ich kenn mich mit dem Simplex-Verfahren nicht wirklich aus, aber vielleicht sagt dir der Wiki-Artikel ja was. ;)
"Solch eine Basislösung ist also eine zulässige Lösung des Gleichungssystems Ax = b mit höchstens m Nicht-Null-Einträgen."
|
|
|
| |
|
Mhm, ne das sagt mir garnichts... Aber danke!
Im Bronstein ist etwas dazu drinnen... anscheinend werden da alle 3 (im Falle eines Gleichungssystems mit 3 Variablen) einzeln mal Null gesetzt.
Aber so ganz blicke ich da noch nicht durch, bräuchte ein ausführliches Beispiel...
|
|
|
| |
|
Also ich verstehe den Wiki-Artikel so:
Du hast ein unterbestimmtes Gleichungssystem
Ax = b mit A eine $n [mm] \times [/mm] m$ Matrix und m > n.
Als Beispiel:
$A = [mm] \pmat{1 & 1 & 0 \\ 1 & 0 & 1}$
[/mm]
Nun nehmen wir einige Spalten von A, sodass diese Spalten eine invertierbare Matrix bilden (also eine Basis des zugehörigen Vektorraums).
Als Beispiel nehme ich jetzt mal die zweite und dritte Spalte.
$B = [mm] \pmat{1 & 0 \\ 0 & 1}$
[/mm]
Betrachten wir nun wieder das Gleichungssystem
Ax = b
Dieses hat ja - da unterbestimmt - mehrere Lösungen.
Eine Basislösung bezüglich der Basis B wäre eine Lösung, die nur eben diese Basis benutzt.
Also
x = [mm] $\vektor{0\\ a \\ b}$ [/mm] für beliebige a und b.
Nehmen wir mal zum noch schöneren Beispiel:
$b = [mm] \vektor{3 \\ 5}$
[/mm]
Dann wäre $x = [mm] \vektor{0 \\ 3 \\ 5}$ [/mm] eine Basislösung zur Basis B.
$y = [mm] \vektor{3 \\ 0 \\ 2}$ [/mm] wäre eine Basislösung zur Basis $C = [mm] \pmat{1 & 0 \\ 1 & 1}$ [/mm] (erste und dritte Spalte von A; ist auch eine Basis).
Also eine Basislösung zu einer Basis, die sich aus Spalten der LGS-Matrix zusammensetzt ist eine Lösung, die eben die Vektoren dieser Spalten-Basis benutzt und an allen anderen Stellen Nullen hat; also diese praktisch wegfallen lässt.
Das tolle ist, dass es zu einer gegeben Basis genau eine eindeutig bestimmte Basislösung ist.
Und jetzt nochmal die für Lottozahlengucker altbekannte Ansage:
Diese Angaben sind ohne Gewähr.
Das was ich hier erzähle habe ich mir aus dem Wiki-Artikel da (siehe Link im anderen Post) zusammengereimt.
Es erscheint mir logisch und ganz schön und ich hoffe es hilft dir erstmal ein wenig weiter bei deinen Aufgaben, aber du solltest dennoch auf die Antwort von jemandem warten, der es ganz sicher weiß, bevor du irgendwas abgibst oder so. ;)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 07:48 Fr 15.07.2011 | | Autor: | Stoecki |
Basislösungen stammen tatsächlich aus dem Simplexalgorithmus. du hast eine lineare Funktion gegeben, die in den reellen Raum abbildet (also was in der Form [mm] c^T [/mm] x, wobei beides reelle Vektoren sind)
Gesucht ist nun das Maximum oder Minimum dieser Zielfunktion nter der Bedingung, dass ein gewisses System von Gleichungen und ungleichungen der Form Ax = b und x [mm] \ge [/mm] 0 eingehalten wird.
Die durch diese Nebenbedingungen definierte Menge heißt Polyeder (also Vieleck). Man kann nun zeigen, das eine lineare Zielfunktion ihr Optimum immer ein einer Ecke (also einer 0-dimensionalen Seitenfläche) annimmt. Und diese werden durch die so genannten Basislösungen bestimmt.
Wie Schadowmaster bereits richtig geschrieben hat, nimmt man hierzu eine invertierbare Teilmatrix. Oft schreibt man obige Nebenbedingungen dann als [mm] A_B x_b [/mm] + [mm] A_N x_N [/mm] =b, für x [mm] \ge [/mm] 0
B ist dann die Menge der Basisindices und N die Menge aller nicht-Basisindices. [mm] A_B [/mm] muss dann diese invertierbare Teilmatrix sein, [mm] A_N [/mm] ist dann der Rest der matrix. Um eine Ecke zu bestimmen setzt du alle Werte von x, die einen Index in N haben auf 0 und berechnest eine Lösung von [mm] A_B [/mm] x = b. Damit ist klar, dass dieses x dann diese Gleichung erfüllt. Ist dabei x [mm] \ge [/mm] 0 heißt diese Lösung primal zulässig. (Primal, da es zu jedem solchen Problem noch ein sog duales Problem gibt, welches an die Zielfunktion eine Schranke liefert)
Ich hoffe es hilft dir weiter.
Gruß Bernhard
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:39 Do 14.07.2011 | | Autor: | leduart |
Hallo
post doch die aufgabe, bei der du drüber gestolpert bist, dann wirds vielleicht klarer.
Gruss leduart
|
|
|
|
