Basisaustauschverfahren < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:38 Do 20.07.2006 | | Autor: | Heli20 |
Kann mir jemand erklären, wie das Basisaustauschverfahren funktioniert?
Ich soll mittels dieses Verfahrens folgendes Gleichungssystem lösen:
3c+3d=6
b+c-2d=2
a+c-d=0
Das System ist nicht kanonisch, oder? Wenn das so ist, muss man es erst kanonisch machen. Ich weiß leider nicht, wie das geht. . Das ist Teil A. B: Geben sie die zugehörige Basislösung und mindestens eine weitere spezielle Lösung an.
Zu Teil A habe ich schon dieses Viereck aufgestellt:
a b c d r.S
y1 0 0 3 3 6
y2 0 1 1 -2 -2
y3 1 0 1 -1 0
aber komme jetzt nicht weiter!
Vielen Dank im Voraus
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
e-math
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:18 Sa 22.07.2006 | | Autor: | Jonair |
Hey also, die kanonische Form hat folgendes Schema:
A * x [mm] \le [/mm] b
Es gibt außerdem noch die Standardform, die folgendermaßen aussieht:
A * [mm] \le [/mm] b
x [mm] \ge [/mm] 0
Wenn du eine Gleichung mit = -Zeichen hast, kannst du folgendes machen, um sie in kanonische bzw. Standardform zu bringen:
Bsp.: a=3 [mm] \gdw [/mm] (a [mm] \le [/mm] 3 und a [mm] \ge [/mm] 3) [mm] \gdw [/mm] ( a [mm] \le [/mm] 3 und -a [mm] \le [/mm] -3 )
Ist eine Zahl eine reelle Zahl und für sie nicht angegeben, dass sie [mm] \le [/mm] oder [mm] \ge [/mm] 0 ist, dann kannst du folgendes machen:
a [mm] \in \IR
[/mm]
a = [mm] a^{*} [/mm] - [mm] a^{**}
[/mm]
[mm] a^{*}, a^{**} \ge [/mm] 0
Bsp.: a + b = 3
2a - 4b [mm] \le [/mm] -4
a + b + 4c [mm] \ge [/mm] -7
a, b [mm] \ge [/mm] 0
c [mm] \in \IR
[/mm]
Nach Umformung:
a + b [mm] \le [/mm] 3
-a - b [mm] \le [/mm] -3
2a - 4b [mm] \le [/mm] -4
-a - b - [mm] 4(c^{1}-c^{2}) \le [/mm] 7
Beispielaufgabe:
[mm] \bruch{1}{2} x_{1} [/mm] + [mm] x_{2} \ge [/mm] 5
[mm] 2x_{1} [/mm] + [mm] x_{2} \le [/mm] 8
[mm] x_{1},x_{2} \ge [/mm] 0
Umformen:
[mm] -\bruch{1}{2} x_{1} [/mm] - [mm] x_{2} [/mm] + [mm] x_{3} [/mm] = -5
[mm] 2x_{1} [/mm] + [mm] x_{2} [/mm] + [mm] x_{4} [/mm] = 8
[mm] x_{3} [/mm] und [mm] x_{4} [/mm] sind eingefügte Schlupfvariablen und ebenfalls gröer gleich Null
1. Basislösung:
[mm] \vektor{x_{1} \\ x_{2} \\ x_{3} \\ x_{4}} [/mm] = [mm] \vektor{ 0 \\ 0 \\ -5 \\ 8 }
[/mm]
Da [mm] x_{3} [/mm] negativ ist, ist diese Basislösung unzulässig.
Nun stellt man folgendes Tableau auf:
Basisvariable=BV, Basislösung=b
BV [mm]x_{1}[/mm] [mm]x_{2}[/mm] [mm]x_{3}[/mm] [mm]x_{4}[/mm] b
[mm] x_{3}[/mm] [mm]-\bruch{1}{2}[/mm] -1 1 0 -5
[mm] x_{4} [/mm] 2 1 0 1 8
[mm] x_{3}[/mm] [mm]\bruch{2}{3}[/mm] 0 1 1 3
[mm] x_{2} [/mm] 2 1 0 1 8
Hier habe ich jetzt [mm] x_{2} [/mm] zur Basisvariablen gemacht. Dadurch ergibt sich dann folgende Basislösung:
[mm] \vektor{x_{1} \\ x_{2} \\ x_{3} \\ x_{4}} [/mm] = [mm] \vektor{ 0 \\ 8 \\ 3 \\ 0 }
[/mm]
Diese ist auch zulässig, da [mm] x_{2}, x_{3} [/mm] beide nicht negativ sind.
Umformen macht man mit Hilfe folgender Pivotregeln. Als Pivotelement, wird das Element bezeichnet, welches zur neuen Basisvariablen wird. Also hier wäre das Element gemeint, dass in der [mm] x_{2} [/mm] -Spalte und in der [mm] x_{4}-Zeile [/mm] steht. Dieses Element wird 1 und alle anderen Elemente in der Spalte werden 0.
PZ - Pivotzeile
PS - Pivotspalte
a.E. - altes Element
n.E. - neues Element
entspr.E. - entsprechendes Element
PE - Pivoelement
Umrechnungsvorschriften:
1. Pivotelement: n.E. = [mm] \bruch{1}{PE}
[/mm]
Im Bsp.: 1 = [mm] \bruch{1}{1} [/mm] = 1
2. Pivotzeile: n.E. = [mm] \bruch{a.E.}{PE}
[/mm]
Im Bsp.: [mm] x_{1}: [/mm] 2 = [mm] \bruch{2}{1}
[/mm]
[mm] x_{3}: [/mm] 0 = [mm] \bruch{0}{1}
[/mm]
[mm] x_{4}: [/mm] 1 = [mm] \bruch{1}{1}
[/mm]
b: 8 = [mm] \bruch{8}{1}
[/mm]
3. Pivotspalte: n.E. = -1 - [mm] \bruch{a.E.}{PE}
[/mm]
Im Bsp.: [mm] x_{3}: [/mm] 0 = -1 - [mm] \bruch{-1}{1}
[/mm]
4. Restliche Elemente mittels Rechteckregel:
n.E. = a.E. - [mm] \bruch{(entspr.E. PZ) * (entspr.E. PS)}{PE}
[/mm]
Im Bsp.:
Spalte [mm] x_{1} [/mm] Zeile [mm] x_{3}: -\bruch{1}{2} [/mm] - [mm] \bruch{(-1) *(2)}{1} [/mm] = [mm] -\bruch{1}{2} [/mm] -(-2) = [mm] \bruch{3}{2}
[/mm]
Spalte [mm] x_{3} [/mm] Zeile [mm] x_{3}: [/mm] 1 - [mm] \bruch{(-1) *(0)}{1} [/mm] = 1 - 0 = 1
Spalte [mm] x_{4} [/mm] Zeile [mm] x_{3}: [/mm] 0 - [mm] \bruch{(-1) *(1)}{1} [/mm] = 0 - (-1) = 1
Spalte b Zeile [mm] x_{3}: [/mm] -5 - [mm] \bruch{(-1) *(8)}{1} [/mm] = -5 - (-8) = 3
Ich hoffe, dass dir dieses Beispiel mit meinen Erklärungen genügt. Natürlich müssten, nun weitere Umformungen vorgenommen werden, bis man alle Basislösungen ermittelt hat, also alle möglichen Kombinationen Basisvariablen waren.
|
|
|
|
