rechnerische Lösung duales LOP

25.06.2012, 16:36

Nini2012

rechnerische Lösung duales LOP

Meine Frage:
Wie kann ich ein duales LOP rechnerisch lösen, ohne der Simplex 2 Phasen Methode?
Mein Beispiel beinhaltet eine zu minimierende Zielfunktion und zwei Nebenbedingungen mit zwei Variablen x1 und x2.

Meine Ideen:
Ich dachte erst daran, die eine Nebenbedingung nach x1 aufzulösen und dann in die zweite Nebenbedingung einzusetzen. Dann kann ich beide Variablen ausrechnen. Aber die Zielfunktion bleibt dann unberücksichtigt. Wie funktioniert das?

25.06.2012, 19:38

Mystic

Auf diesen Beitrag antworten »

RE: rechnerische Lösung duales LOP
Dazu müsstest du vorher

1. das primale oder duale LOP angeben, denn ohne ein handfestes Beispiel tut man sich schwer...
2. sagen, ob ihr typischerweise bei einem primalen Problem maximiert oder minimiert...

25.06.2012, 20:47

Nini2012

Auf diesen Beitrag antworten »

RE: rechnerische Lösung duales LOP
Also es handelt sich im primal eine zu maximierende Zielfunktion. Umgewandelt ins Dual erhalte ich die zu minimierende Zielfunktion:
$\begin{eqnarray*} Z= 4u1+ 3u2 \end{eqnarray*}$

und diese Nebenbedingungen:
$\begin{eqnarray*} u1+ u2\geq 6 \end{eqnarray*}$
$\begin{eqnarray*} -3u1+ u2\geq -6 \end{eqnarray*}$

Die Aufgabenstellung:
Beschreiben Sie den rechnerischen Lösungsweg für das duale LOP, der ohne die 2-Phasen-Methode auskommt. Erläutern Sie dazu den Zusammenhang zwischen den optimalen Lösungen dualer LOP-Aufgaben.

25.06.2012, 21:20

Mystic

Auf diesen Beitrag antworten »

RE: rechnerische Lösung duales LOP
Aha, das primale LOP sieht also dann so aus:

$\begin{eqnarray*} z=6x_1-6x_2=Max! \end{eqnarray*}$

sowie den NB

$\begin{eqnarray*} x_1-3x_2\le 4 \end{eqnarray*}$
$\begin{eqnarray*} x_1+x_2 \ \le 3 \end{eqnarray*}$

Ist das richtig?

Wenn ja, dann wäre mal duale LOP richtig aufgestellt und du müsstest im ersten Schritt es folgendermaßen umformulieren:

$\begin{eqnarray*} z=-4u_1-3u_2=Max! \end{eqnarray*}$

$\begin{eqnarray*} -u_1-u_2\le -6 \end{eqnarray*}$
$\begin{eqnarray*} 3u_1-u_2 \ \le 6 \end{eqnarray*}$

bzw. nach Einführung der Schlupfvariablen $\begin{eqnarray*} u_3 \end{eqnarray*}$ und $\begin{eqnarray*} u_4 \end{eqnarray*}$ zu

$\begin{eqnarray*} -u_1-u_2+u_3 = -6 \end{eqnarray*}$
$\begin{eqnarray*} 3u_1-u_2 +u_4 =\ 6 \end{eqnarray*}$

Sind wir soweit noch d'accord? Augenzwinkern

25.06.2012, 21:31

Nini2012

Auf diesen Beitrag antworten »

RE: rechnerische Lösung duales LOP
Oui - d'accord!
Also das primale LOp ist richtig, das duale auch - jedenfalls wenn man die Zielfunktion in Max umwandelt. Dass man dann die Nebenbedingungen auch wieder umdreht ist mir allerdings neu. Für Simplex haben wir bei einem Min. Problem immer nur die Zielfunktion in Max umgewandelt und die NB gelassen, wie sie waren.

Oder ist das schon der erste Schritt für die rechnerische Lösung (eben ohne Simplex)?

25.06.2012, 21:47

Mystic

Auf diesen Beitrag antworten »

RE: rechnerische Lösung duales LOP

Zitat:

Original von Nini2012
Oder ist das schon der erste Schritt für die rechnerische Lösung (eben ohne Simplex)?

Das dient den Vorbereitungen für die duale Simplexmethode... Noch eine Frage, macht ihr die Tableaus in Langform (=mit Spalten der Basisvariablen) oder in Kurzform(=Spalten der Basisvariablen werden weggelassen)... Ich persönlich mache lieber letzteres aber richte mich natürlich nach dir... Augenzwinkern

25.06.2012, 21:52

Nini2012

Auf diesen Beitrag antworten »

RE: rechnerische Lösung duales LOP
Also wir machen dann wohl die Langform!

Nur damit wir uns nicht falsch verstehen - die Aufgabe soll ja OHNE Simplex gelöst werden... aber ich sollte nicht so ungeduldig sein, vielleicht hilft das gerade um den anderen Weg zu erklären Augenzwinkern

25.06.2012, 21:56

Mystic

Auf diesen Beitrag antworten »

RE: rechnerische Lösung duales LOP

Zitat:

Original von Nini2012
Nur damit wir uns nicht falsch verstehen - die Aufgabe soll ja OHNE Simplex gelöst werden... aber ich sollte nicht so ungeduldig sein, vielleicht hilft das gerade um den anderen Weg zu erklären Augenzwinkern

Oh, das habe ich dann wohl überlesen... Ich sehe nur, dass ihr das ohne 2-Phasen-Simplex machen solltet... Also dann ganz ohne Simplexmethode überhaupt? verwirrt

Edit: Kann es sein, dass eine graphische Lösung (zusammen mit finaler Rechnung natürlich!) gemeint ist?

25.06.2012, 22:07

Nini2012

Auf diesen Beitrag antworten »

RE: rechnerische Lösung duales LOP
Hammer

Ok, ich hab nun begriffen, was gemeint ist mit der unten genannten Aufgabenstellung. Ich habe immer an Simplex und 2 Phasen Methoden gleichbedeutend gedacht. Ok, es geht also nur darum, wie man das Ergebnis vom dualen LOP errechnen kann, ohne 2 Phasen Modell mit komplizierten Hilfsschlupfvariablen...also dann weiß ich, wie ichs machen muss: Das primale LOP ausrechnen mit Simplex ("einphasig") und dann unten in der Zielfunktionszeile das Ergebnis für das duale LOP ablesen. Richtig?

25.06.2012, 22:23

Mystic

Auf diesen Beitrag antworten »

RE: rechnerische Lösung duales LOP
Ja, das könnte tatsächlich so gemeint sein...

25.06.2012, 22:26

Nini2012

Auf diesen Beitrag antworten »

RE: rechnerische Lösung duales LOP
Ok - ich mach das jetz so, erscheint mir logisch.
Vielen Dank trotzdem - ohne das Hin und Her hier wär ich bestimmt nicht drauf gekommen! Freude

25.06.2012, 22:36

Mystic

Auf diesen Beitrag antworten »

RE: rechnerische Lösung duales LOP
Ok, mach das... Auf den ersten Blick und ohne jede Rechnung sollte ja als Lösung für das primale Problem x=3,y=0 rauskommen, damit z größtmöglich wird, denn das ist der größte Wert für x und der kleinst für y... Der optimale z-Wert dafür, also 18, müsste für das duale Problem gleich sein...

Neue Frage »

Antworten »

rechnerische Lösung duales LOP

Verwandte Themen