Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

simplex-algorithmus :-(
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> simplex-algorithmus :-(
 
Autor Nachricht
hit-kid
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 02.01.2005
Beiträge: 13

BeitragVerfasst am: 02 Jan 2005 - 16:21:19    Titel: simplex-algorithmus :-(

kann mir jemand den simplex-algorithmus an einem nachvollziehbaren beispiel erklären? insbesondere die schritte ab dem simplex-tableau verstehe ich überhaupt nicht ...

würde mich über hilfe sehr freuen,

jan Crying or Very sad
Gast







BeitragVerfasst am: 02 Jan 2005 - 17:34:04    Titel:

http://de.wikipedia.org/wiki/Simplex-Verfahren
hit-kid
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 02.01.2005
Beiträge: 13

BeitragVerfasst am: 02 Jan 2005 - 18:08:39    Titel:

das hatte ich mir extra ausgedruckt und dann nicht mehr nachvollziehen können Sad
Thomas_Da
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 21.11.2004
Beiträge: 352
Wohnort: Darmstadt

BeitragVerfasst am: 02 Jan 2005 - 18:22:48    Titel:

Es ist Dir sicherlich klar, dass wir Dir den kompletten Simplex-Algorithmus hier nicht besser erklären können, als eine durchdachte Beschreibung dies erledigen kann Crying or Very sad

Schreib vielleicht mal ein Beispiel auf, bei dem man Dir helfen soll.
hit-kid
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 02.01.2005
Beiträge: 13

BeitragVerfasst am: 03 Jan 2005 - 01:27:03    Titel: Beispiel

Zielfunktion: -3Y1 + Y2 - 5 => max
Nebenbedingung: -2Y1 + Y2 + Y3 = 1 und - Y1 + 2Y2 + Y4 = 5

Eingetragen ins Simplex-Tableau müsste das ja dann so aussehen:



Und wie geht es dann weiter? Dann muss ich doch die pivotspalte und -zeile auswählen .. aber nach welchen Gesichtspunkten? Könnt Ihr mir das weitere Vorgehen und die Lösung erklären?

JAN
Thomas_Da
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 21.11.2004
Beiträge: 352
Wohnort: Darmstadt

BeitragVerfasst am: 03 Jan 2005 - 09:19:11    Titel:

Von den CB habe ich noch nichts gehört, sonst sieht das Tabelau gut aus.

Gemäß der oben angegebenen Internetseite:
Zitat:
Verbesserung der Lösung mittels einer Simplex-Iteration

In einer Simplex-Iteration wird eine Basisvariable gegen eine Nichtbasisvariable ausgetauscht. Man spricht daher auch von einem Austauschschritt.

In Frage kommen Nichtbasisvariable mit negativem Zielfunktionskoeffizienten.

Damit ist gemeit min negativen Koeffizienten im Tabelau, also die Variablen, bei denen in der letzten Zeile eine negative Zahl steht.
Im Anfangstabelau sind y3 und y4 Basisvariablen mit den Mengen y3=1 und y4=5; y1, y2 sind nicht in der Basis und die Mengen sind 0. Nun bedeutet der negative Koeffizient, dass bei einer Erhöhung der Menge, der Zielfunktionswert von aktuell -5 erhöht werden kann. (Überlege es Dir mal an der Zielfunktion.
Zitat:
Unter diesen sucht man diejenige Basisvariable, deren Austausch den größten Zuwachs für die Zielfunktion bringt.

Hier gibt es nur bei y2 einen negativen Eintrag, ansonsten nimmt man die Variable mit kleinstem Wert, also größtem Betrag - minus drei würde also eher genommen werden als minus 2.

Welche Zeile man nehmen muss steht anscheinend nicht hier Sad
Man bildet von allen Zeilen in denen ein positiver Koeffizient in der ausgewählten Spalte (Pivotspalte) steht den Quotienten XB/aBj, wobei j der Index der ausgewählten Spalte ist.
Die Zeile mit kleinstem Quotienten ist nun die Pivotzeile.
1/1 < 5/2 Daher ist die erste Zeile Pivotzeile.

[Bei keinem positiven Eintrag in der Spalte gibt es keine optimale Lösung glaube ich, wg. Unbeschränktheit. Für den Simplex, wie er hier beschrieben ist, müssen alle XB positiv sein.]
Zitat:
Sei j die Nummer der Spalte der auszutauschenden Nichtbasisvariable und B die Nummer der Zeile der auszutauschenden Basisvariablen. Ein Austauschschritt entspricht exakt einem Schritt beim Lösen eines linearen Gleichungssystems, bei dem man die Zeile B nach der Variablen Yj auflöst und dann Yj in die restlichen Gleichungen einsetzt. Seien aik die (Matrix)Elemente des Simpextablaus. Dann heißt aBj das Pivotelement des Simplextableaus. Die Spalte j heißt Pivotspalte, die Zeile B heißt Pivotzeile.

Das neue Tabelau ergibt sich wie folgt:
Zunächst die erste Zeile:
y1 0 -2 1 1 0 1
Die Zeile muss so multipliziert werden, dass das fette Element eine 1 wird.
In den anderen Zeilen dieser Spalte müssen nun 0en generiert werden, in dem die erste Zeile mit einem Faktor multipliziert zu der jeweiligen Spalte hinzuaddiert wird.
y4 0 3 0 -2 1 3
__ _ 1 0 1 0 -4
Da nun (bis auf den Zielfunktionswert) kein Element der letzen Zeile negativ ist, kann die Lösung (-4) nicht verbessert werden.
Code:
y1 0 -2 1  1 0  1
y4 0  3 0 -2 1  3
      1 0  1 0 -4

Man kann ablesen, dass die Basisvariable y1 den Wert 1 besitzt (siehe XB). Weil und y4 den Wert 3. y2 und y3 sind nicht in der Basis mit den Werten 0.
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 03 Jan 2005 - 22:19:28    Titel:

Ich habe mal eine sehr hilfreiche Erklärung für Simplex gehört, die ich euch nicht vorenthalten möchte:

Die Menge der zulässigen Lösungen bildet einen als Schnitt von Halbräumen und affinen Unterräumen einen konvexen Polytop, dessen aufspannende Punkte gerade die zulässigen Basislösungen sind. Das Ding kann mal sich leicht als "unreguläres mehrdimensionales n-Eck" vorstellen. Es ist klar, dass nur die Ecken des Polytops Lösungen sein können. Beim Simplex Verfahren beginnt man an einem der "Ecken" und bewegt sich entlang der Kanten des Polytops mit jedem Schritt zur nächsten Ecke, die die Kostenfunktion gegenüber der letzten Ecke minimiert.

Ich fand die Erklärung sehr einleuchtend. Schribt mal was Ihr davon haltet.
Thomas_Da
Full Member
Benutzer-Profile anzeigen
Full Member


Anmeldungsdatum: 21.11.2004
Beiträge: 352
Wohnort: Darmstadt

BeitragVerfasst am: 03 Jan 2005 - 22:56:46    Titel:

Die Erklärung ist richtig und bis auf den Begriff affiner Unterräum leicht verständlich. (Vielleicht ist dem einen oder anden auch der Begriff konvexes Polytop nicht geläufig.

Besser wäre natürlich eine Zeichnung (für den Fall zweier Variablen), an der man zeigen kann, dass man vom Ursprung (x1=0, x2=0; einer ersten zulässigen Lösung) so an den Ecken des Vielecks "entlangläuft", bis man die optimale Lösung erreicht hat.

Dann kann man vielleicht noch Zeigen, dass es Fälle mit keiner, einer und meheren (unendlich vielen) optimalen Lösungen geben kann.
hit-kid
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 02.01.2005
Beiträge: 13

BeitragVerfasst am: 04 Jan 2005 - 19:05:07    Titel:

thomas, danke für deine mühe. von dieser n-eck-sache hab ich auch schon gehört, bzw. das auch schon grafisch skizziert gesehen. ich versuche jetzt in ruhe nochmal die schritte durchzugehen und zu versuchen dahinter zu steigen.
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> simplex-algorithmus :-(
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum