Herleitung der Rechenregeln für das Austauschverfahren

27.06.2006, 13:28

Lenchen83

Herleitung der Rechenregeln für das Austauschverfahren

Hallo zusammen,

wie im Betreff schon beschrieben habe ich Probleme mit der Herleitung der Rechenregeln für das Austauschverfahren.

Also die Herleitung beginnt ja damit, dass ich die Zeile in der das Pivotelement ist nach dem x in der Spalte des Pivotelementes auflöse.

$\begin{eqnarray*} y_1= a_{11} x_1+a_{12}x_2+... +a_{1\alpha} x_\alpha+...+a_{1n} x_n+ a_{10} \end{eqnarray*}$

$\begin{eqnarray*} y_\beta= a_{\beta 1}x_1+ a_{\beta 2}x_2+... +a_{\beta \alpha}x_\alpha+ ...+ a_{\beta n}x_n+ a_{\beta 0} \end{eqnarray*}$

$\begin{eqnarray*} y_m= a_{m1}x_1+ a_{m2}x_2+...+a_{m\alpha}x_\alpha+...+a_{mn}x_n+ a_{m0} \end{eqnarray*}$

ich gehen nun davon aus, dass ich dieses ganze in Tabellenform vor mir liegen habe (wusste nicht, wie ich sowas mit dem Formeleditor mache)

und nun möchte ich $\begin{eqnarray*} y_\beta \end{eqnarray*}$ und $\begin{eqnarray*} x_\alpha \end{eqnarray*}$ austauschen.

Also die ersten beiden Austauschregeln, dass das neue Pivotelement durch $\begin{eqnarray*} \frac{1}{p} \end{eqnarray*}$ wobei p:= $\begin{eqnarray*} a_{\beta \alpha} \end{eqnarray*}$ berechnet wird und dass die neue Pivotzeile durch die alte Pivotzeile: -p berechnet wird habe ich verstanden. Das liegt ja einfach daran, dass man die Zeile $\begin{eqnarray*} y_\beta \end{eqnarray*}$ nach $\begin{eqnarray*} x_\alpha \end{eqnarray*}$ umformt.

Aber dann weiter, macht es mir Probleme. Wie komme ich darauf, dass die neue Pivotspalte durch alte Pivotspalte:p berechnet wird? Und wodurch kommt die vierte Austauschregel: neuer Platz= alter Platz + zugehöriges Element der Pivotspalte mal zugehöriges Element der Kellerzeile zustande?

Wäre nett, wenn ihr mir weiterhelfen könntet. Habe auch schon bei google nach einer Herleitung gesucht, aber leider nichts Vernünftiges gefunden.

Lg Lenchen

27.06.2006, 14:03

Ben Sisko

Auf diesen Beitrag antworten »

RE: Herleitung der Rechenregeln für das Austauschverfahren
Hallo Lenchen,

"Austauschverfahren", hier meinst du den Basistausch im Simplex-Algorithmus, wenn ich recht sehe, oder?

Was genau ist deine Frage? Warum diese Rechenregeln einen Basistausch bewirken? Warum durch einen so bewirkten Basistausch der Zielfunktionswert besser (genauer: nicht schlechter) wird?

Hast du ein Skript dazu (sodass du konkretere Fragen stellen könntest)?

Gruß vom Ben

27.06.2006, 14:39

Lenchen83

Auf diesen Beitrag antworten »

Hallo

ich meine nicht direkt das Silmplexverfahren ist meiner Meinung nach eine "Untergruppe" vom Austauschverfahren.

Also ich habe ein Script und da steht das Simplexverfahren unter dem Punkt "Anwendungen des Austauschverfahrens"

http://img528.imageshack.us/img528/8778/austauschverfahren9et.jpg
Und meine Frage ist eigentlich "nur" wie kommen die Regeln zum Austauschen zustande, die hat sich ja irgendjemand mit Grund ausgedacht.

also R1 und R2 ist mir klar(oben beschrieben).

Bemerkung: Ich habe oben $\begin{eqnarray*} \alpha \end{eqnarray*}$ und $\begin{eqnarray*} \beta \end{eqnarray*}$ genommen, weil die anderen beiden Buchstaben nicht im Formeleditor zu sehen waren.

27.06.2006, 20:44

Lenchen83

Auf diesen Beitrag antworten »

Hmm ist denn keiner hier, der mir helfen kann??? verwirrt

Das wäre ja seehr schade traurig

28.06.2006, 00:07

Ben Sisko

Auf diesen Beitrag antworten »

Ihr habt den Satz doch sicher bewiesen, oder? Es sind halt gerade die Rechenregeln, die Äquivalenz von (3.1) und (3.2) herbeiführen.

In welchem Rahmen behandelt ihr denn das Austauschverfahren, welche Vorlesung, wofür benutzt ihr es?
In der Optimierung kann man noch ein wenig verdeutlichen, was dort überhaupt passiert (geometrisch).

Gruß vom Ben

PS: Gab's noch andere Beispiele für die Anwendung als das Simplex-Verfahren?

28.06.2006, 00:25

Lenchen83

Auf diesen Beitrag antworten »

Welchen Satz meinst du haben wir bewiesen?

Also das Austauschverfahren kam in einer Veranstaltung, die "Lineare Algebra" hieß vor. Ich benötige es nun, da es Thema meiner Prüfung ist. In der Sprechstunde unterhielten wir uns halt über Inhalte und da meinte er, dass er zum Beispiel auch fragen könnte, wie das Austauschverfahren hergeleitet wird.

Weitere Anwendung für das Austauschverfahren waren:
- Unabhängigkeit linearer Funktion
- Lösung linearer algebraischer Gleichungssysteme
- Vektoren
- Matrizen
- Determinanten
und das Simplexverfahren stand halt noch als Punkt unter diesen Anwendungen, aber das haben wir in der Veranstaltung nicht durchgenommen, also das Inhaltsverzeichnis enthält den Punkt noch, aber die Seite dazu wurde nicht zum Download zur Verfügung gestellt.

28.06.2006, 01:18

Ben Sisko

Auf diesen Beitrag antworten »

Wusste gar nicht, was man alles damit machen kann Augenzwinkern

Aber eigentlich vereinfacht es das Ganze, ich hatte schon viel weiter gedacht.

Zitat:

Original von Lenchen83
Also die ersten beiden Austauschregeln, dass das neue Pivotelement durch $\begin{eqnarray*} \frac{1}{p} \end{eqnarray*}$ wobei p:= $\begin{eqnarray*} a_{\beta \alpha} \end{eqnarray*}$ berechnet wird und dass die neue Pivotzeile durch die alte Pivotzeile: -p berechnet wird habe ich verstanden. Das liegt ja einfach daran, dass man die Zeile $\begin{eqnarray*} y_\beta \end{eqnarray*}$ nach $\begin{eqnarray*} x_\alpha \end{eqnarray*}$ umformt.

Aber dann weiter, macht es mir Probleme. Wie komme ich darauf, dass die neue Pivotspalte durch alte Pivotspalte:p berechnet wird? Und wodurch kommt die vierte Austauschregel: neuer Platz= alter Platz + zugehöriges Element der Pivotspalte mal zugehöriges Element der Kellerzeile zustande?

In den anderen Zeilen willst du ja $\begin{eqnarray*} x_\alpha \end{eqnarray*}$ aus der Gleichung entfernen und dafür $\begin{eqnarray*} y_\beta \end{eqnarray*}$ hineinbekommen. Dazu setzt du einfach deine Pivotzeile (die ja $\begin{eqnarray*} x_\alpha=\dots \end{eqnarray*}$ lautet) ein in das $\begin{eqnarray*} x_\alpha \end{eqnarray*}$ dieser Zeile. Ausmultiplizieren und zusammenfassen ergibt die Rechenregeln (für $\begin{eqnarray*} x_\alpha \end{eqnarray*}$ ist nichts zusammenzufassen, weil nur ein Summand, daher ist die Rechenregel für die Pivotspalte noch ein wenig einfacher als für den Rest der Zeile).

Alles klar?

Gruß vom Ben

Edit: Mach dir vielleicht ein Beispiel mit m=n=2 oder 3, dann erkennst du eigentlich alles, was passiert.

28.06.2006, 12:46

Lenchen83

Auf diesen Beitrag antworten »

aaah ja

nun habe ich es verstanden smile

Vielen Dank!

LG Lenchen

Neue Frage »

Antworten »

Herleitung der Rechenregeln für das Austauschverfahren

Verwandte Themen