Lineare Optimierung: Simplexalgorithmus

Wissenschaft Mathematik
#1

Guten Tag an die Leser.

Es geht um die Lösung einer Optimierungsaufgabe mittels Simplexmethode.
Ausgangszustand ist ein Tableau mit den Entscheidungsvariablen x1 bis x3 und B waagerecht und den Schlupfvariablen y1 bis y3 und Z, der Zielfunktion, senkrecht.
Z bildet die Hauptzeile und x2 die Haupspalte.
Im Ergebnistableau tausche ich Z und x2 und kann x2 aus der Spalte B auslesen.
Soweit scheint es mir richtig zu sein. Nur weiter kommen ich nicht, denn alleine mit dem Wert x2 und einer der Schlupfvariablen kann ich noch keine Gleichung lösen: es muss noch x1 oder x3 bekannt sein.

Wenn ich das richtig verstehe, dann muss auf mein Ergebnistableau erneut die Simplexmethode angewandt werden um einen weiteren x-Wert zu ermitteln. Ist das richtig?
Wenn ja, dann brauche ich aber die Z-Zeile. Diese habe ich ja nicht mehr, da Z mit x2 vorher getauscht wurde und nun eine Spalte ist.

Wie wäre das weitere Vorgehen?

Danke vielmals im Voraus.

Vitali

#2

moin;

du willst bei der linearen Optimierung auch keine Gleichung lösen, sondern die optimale Belegung der Variablen, damit die Zielfunktion maximal wird (beim primalen LP).

Die Gleichungen, die du dort stehen hättest, wenn du das Tableau in Gleichungen umformen würdest, sind ja sowieso in jedem Iterationsschritt wahr - beim Ursprungs-LP würden dann eben alle Schlupfvariablen den Wert der Kapazität annehmen, alle anderen den Wert 0.

Weiterhin, der Simplex-Algorithmus ist ein iterativer Algorithmus. Du machst praktisch immer wieder das gleiche (Achtung vor Kreisen), solange eine weitere Steigerung möglich ist, nämlich im Grunde:

  1. Pivotelement herausfinden, d.h. also mit welcher Variable die größte „Steigung“ erzielt werden kann und bei welcher Nebenbedingung sie am stärksten eingeschränkt wird
  2. Die Basis- und Nichtbasisvariablen „um“ das Piotelement tauschen. Dafür kannst du einfach umstellen.

So, wie du das Problem schilderst, nehme ich an, dass du den Simplex-Algorithmus noch nicht angewandt hast. Ich würde dir empfehlen, dir noch einmal jeden „Teilschritt“ des Algorithmus genau anzusehen und es zunächst auf ein Problem in Gleichungssystem-Form anzuwenden, bevor du dich den Tableaus zuwendest.

mfG

#3

Danke für die Antwort.

Deswegen bin ich hier: ich kann den Algorithmus nicht anwenden wenn er mir nicht klar ist.

Daher 2 weitere Fragen zum Verständniss:

  1. Die Zielfunktionszeile und die Spalte mit der rechten Seite der Nebenbed. (bei mir B-Spalte) werden nicht in die Ermittlung der Hauptspalte und -zeile (des Pivotelements) einbezogen. Ist das richtig?

  2. Können schon mal getauschte Zeilen- und Spaltenvariablen in einem weiteren Schritt erneut getauscht werden? Darf das vorkommen? Wenn ja, dann folgendes Szenarion:
    NBV x1 und BV y1 wurde im ersten Schritt getauscht. Das Tableau weist aber noch kein optimales Ergebnis auf. Es wird erneut nach dem Pivotelement gesucht und es befindet sich an der gleichen Stelle im Tableau wie vorher. Also werden x1 und y1 erneut getauscht. Wäre das Ergebnis nicht mehr zu verbessern, wie würde das Ergebnis abgelesen werden? BV sind nach wie vor nur Schlupfvariablen wie im Ausgangszustand und nur für die kann ich in der B-Spalte einen Wert ablesen.

Gruß
Vitali