Dualer Simplexalgorithmus - Lösung Dual -> Primal?

Neue Frage »

mari08 Auf diesen Beitrag antworten »
Dualer Simplexalgorithmus - Lösung Dual -> Primal?
Hallöchen,

also ich habe eine Frage bezüglich Simplexalgorithmus in Verbindung mit Dualität.

Also wir haben hier Aufgaben bei denen ist ein Lineares Optimierungsproblem mit Nebenbedingungen und Zielfunktion gegeben. Dieses wird bei uns eigentlich immer minimiert. So und dieses wird doch primales LOP genannt oder?

So und die Aufgabe ist nun die Optimallösung zu finden mit Hilfe des dualen Simplexalgorithmus. Was heißt das genau? Heißt das einfach "nur" ich erstelle mir zu dem primalen LOP das dazugehörige duale LOP und löse es ganz normal mit dem Simplexalgorithmus? Wenn ja dann ist das soweit klar.

Nur jetzt kommt das aber. Wenn ich die Lösung für das duale LOP habe, wie komme ich dann zur Optimallösung des primalen LOP's ? Denn es ist ja lediglich der Zielfunktionswert der gleiche (von primalen und dualen LOP). Aber der Rest, wie bekomme ich den raus?

Vielen Dank im Voraus für Denkanstöße...

smile
marodeur Auf diesen Beitrag antworten »
RE: Dualer Simplexalgorithmus - Lösung Dual -> Primal?
ist u eine optimallösung vom dualen System, so gelangt man zu der zugehörigen lösung im primalen system wie folgt:

für jede komponente in u die nicht 0 ist, gilt im primalen system die zugehörige schlupfvariable ist 0, d.h. die entsprechende zeile der restriktionen wird mit gleichheit erfüllt. dies gilt entsprechend auch für eine primale lösung und die dazugehörige duale lösung.

dies ist eine implikation, keine äquivalenzaussage!

weiterhin gilt für optimallösungen x (primal) und u (dual):

und

dann bekommt man ein gleichungssystem raus, dieses müsstest du dann lösen können.
mari08 Auf diesen Beitrag antworten »

Das hört sich ja schonmal gut an, bist ein Schatz Mit Zunge

Habe es gleich mal probiert.

Aber ich glaube das Gleichungssystem was ich am Ende aufstelle ist noch nicht ganz korrekt weil es ist nicht lösbar.

Also meine primale Aufgabe sieht so aus:








soll maximiert werden.

So, dann habe ich dazu das duale LOP aufgestellt und gelöst.

Für das duale LOP ergibt sich folgende Lösung:






Der Zielfunktionswert ist 19!

So, nun möchte ich mit dieser Lösung des dualen Problems auf die Lösung des primalen Problems kommen.

Also nach deiner Antwort dachte ich mir, fasse ich drei Gleichungen zu einem LGS zusammen, weil ich ja drei Variablem brauche. Zum Beispiel:

(Das ist die zweite NB mit 0,5 multipliziert also mit y_2)
(Die kann ich neben weil y_2 ist ungleich 0 und dann ist die Schlupfvariable 0 und deshalb ist die Gleichung erfüllt)
(Die gilt aus dem selben Grund, also y_4 ist ungleich 0 und die Schlupfvariable ist deshalb 0)

So, aber leider ist das LGS nicht richtig lösbar. Es gibt zwei allgemeine Lösungen und x_3 ist sogar beliebig. Das kann ja nicht sein oder?

Also ich denke ich habe das mit dem aufstellen des LGS noch nicht richtig gemacht. Wo liegt mein Fehler?
marodeur Auf diesen Beitrag antworten »

mal so rein hypothetisch, da stimmt was nicht mit der aufgabe. das problem ist offensichtlich unbeschränkt. haste dich mit den ungleichheitszeichen vermacht? oder soll z minimiert werden?

dein gleichungssystem klappt nicht, weil 2 zeilen linear abhängig sind, da hst du was nicht richtig gewählt.

also nimm mal statt der ersten deiner gleichungen folgende:

(da der zielfunktionswert ja gleich ist, und du die zielfunktion ja hast)

dann solltest du das Gleichungssystem auflösen können.
mari08 Auf diesen Beitrag antworten »

Du hast recht, die eigentliche Aufgabe soll minimiert werden. Also werde ich noch einmal nachrechnen. Und mit dem LGS ist jetzt eigentlich klar, ich wusste halt nicht was ich noch nehmen soll, weil es sind ja nur zwei Gleichungungen da gewesen die ich nehmen kann (weil nur zwei y ungleich 0 waren). Und wenn ich die eine noch halbiere ist das ja keine neue wie du richtig sagst. Aber wenn ich die Zielfunktion noch mit ins Bot holen kann dann funktioniert das ja...

Vielen Dank soweit. Freude
marodeur Auf diesen Beitrag antworten »

es muss nicht immer "aufgehen" es kann antürlich auch auftreten, dass eine ganze kante (oder mehr) des zulässigen bereiches als lösung in frage kommen kann. das ist dann eine konvexkombination der optimalen ecken.
 
 
mari08 Auf diesen Beitrag antworten »

Ja, aber das sind alte Klausuraufgaben, ich denke die werden immer aufgehen ;-)
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »