LOP - Simplex-Algorithmus

[quote=Silvana]Welche Spalte man wählt, scheint ja egal zu sein...

Ich meine, dass es die Spalte mit dem kleinsten Wert in der Zielfunktion ist.
Gruß

Was ist denn dabei eigentlich die Frage?
Um was geht es denn, kannst du das näher erläutern (z.B. mit Beispiel)?

p

Also gut, hier ein Beispiel:

Das Ausgangstableau sieht so aus:

2 3 1 0 12
3 5 0 1 14
-1 -5 0 0 0

Welche Spalte wählt man? (Ich dachte, das wäre egal?) und welches Element ist dann Pivotelement ?

Grüßle
Silvana

Wenn die Zielfunktion die erste Zeile ist, dann nimmst du Spalte 2, da hier der Engpaß ist (5x< 14 kleinstes x).

Zielfunktion ist die letzte Zeile, aber welches Element in der Spalte wird dann Pivotelement?

Immer noch die 5 aus der zweiten Zeile, da sie der Engpaß in der Restriktionsbedingung ist.
Schau dir die beiden ersten Zeilen an und forme sie als Restriktionsbedingung um:
Für Zeile 1: 2*x1+ 3*x2 < 12
Für Zeile 2: 3*x1+ 5*x2 < 14
x2 ist somit Engpaß, und zwar das in Zeile 2, da bei x=0 nämlich 5*x2<14
den kleinsten x-Wert bringen würde.
Versuche dir das an den Beispielen Seite 52 ff klar zu machen (hihi, neue Rechtschreibreform).

Silvana,

bei weniger übersichtlichen Tableaus sollte die Spalte gewählt werden, deren negativer Zielfunktionskoeffizient betragsmäßig am größten ist.

In diesem Fall wäre das die -7 also die zweite Spalte.

In diesem übersichtlichen Beispiel kann man sich allerdings überlegen, das die Wahl der ersten Spalte in einem einzigen Schritt zur optimalen Lösung führt, während man bei Wahl der zweiten Spalte zwei Schritte benötigt.
Deshalb wird hier die erste Spalte gewählt.

Die 0,5 wird m.E. wegen des Vorzeichens ausgewählt.
Du musst die Pivotzeile ja durch das Pivotelement dividieren. Damit wäre, bei Wahl der -1,5 als Pivotelement, die RHS in dieser Zeile negativ ( ).
Um in den Zielfunktionskoeffizienten der ersten Spalte auf Null zu bekommen, ist die erste Zeile dann mit 4 zu multiplizieren und zur letzten Spalte hinzuzuaddieren. Damit würde der Wert der Zielfunktion sinken. Dies ist aber nicht erwünscht, da der Wert zu maximieren ist.

Gruß
Joachim

Für x2 =0 folgt:

-1,5 x1 < 4 sowie
0,5 x1 < 4

Und was sehen wir? In der obigen Gleichung könnte x1 gegen unendlich streben und die Restriktion wäre erfüllt, eine Restriktion stellt lediglich die untere Gleichung dar. Hier könnte x1 höchstens 8 geben.
Übrigens als Anhaltspunkt: x> 0, da es keine negativen Faktoreinsätze gibt.

So, der Thread muß nach oben: ;)
Das lösen eines Simplex-Tableaus ist mir eigentlich völlig klar. (Zumindest wenn gerry in seinen Ausfführungen in #7 die Zielfunktion mit (-1) multiplizierte, denn mir sagt mein Mathebuch, dass eine negative Zielfunktion bereits die optimale Lösung darstellt). Nur beim Aufstellen blicke ich nicht ganz durch: Aufgrund der Restriktionen enstehen positive und negative Einheitsvektoren an den Stellen der Stützvariablen, dann müssen die Transformationsregeln beachtet werden, wodurch evtl. negative Einheitsvektoren neu entstehen oder verschwinden.
Was sich mir beim besten Willen nicht erschließen will ist das 2-Phasen Tableau. Die Lösung erfolgt wieder wie beim 1-Phasen modell über pivotisieren, aber wann stelle ich ein 2 Phasen modell auf?
Vermutung: wenn nach Aufstellung des Gleichungssystemsems und Anwendung der Transformationsregeln nicht genug Einheitsvektoren auftreten, dann müssen zwei Phasen gerechnet werden.

Kann man das so zusammenfassen? (Jetzt wo ich den Gedanken mal schriftlich formuliert habe, entwickelt er für mich einen gewissen charme...)

Gruß Crix

Nach Betrachtung des Beispiels auf CD glaube ich es verstanden zu haben.

Du hast mit deiner Vermutung tatsächlich recht, es hängt mit der Zahl der Einheitsvaktoren zusammen, oder vereinfacht:
Entscheidend ist die Anzahl der Hilfsvektoren h, die du aus den Restriktionsbedingungen erhälst, also für Ax>= b und Ax=b.