WER KANN SIMPLEX ALGORITHMUS VERKÜRZT?

U

Unregistriert

Das Skript ist so schlecht, da versteht man keine seite dazu! kann ihn nur auf die normale art (pivot spalte / zeile ) lösen, aber nicht verkürzt. wer kann mir bitte weiterhelfen?

11X1 + 14 X2

u.d.N.

2X1 - X2 kleinergleich 45
X1 - 3X2 kleinergleich 110
X1 + X2 kleinergleich 70

zeige mich auch gerne erkenntlich dafür, wenn das jemand lösen könnte ;-)
uniea@daemmig.com
 
M

matthi

Hallo,

ich habe Deine Aufgabe gerade probiert.
Übernehme keine Garantie für die Richtigkeit - man hat ja immer sehr schnell einen Zahlendreher (oder Tippfehler auf dem Taschenrechner) drin.

Ich komme zu folgendem Lösungsweg:


I. Ausgangstableau in der verkürzten Form:

X1 X2 RHS

X3 2 -1 45
X4 1 -3 110
X5 1 1 70
F -11 -4 0


II. Pivotspalte ist X1, Pivotzeile ist X3, Pivotelement hat den Wert 2

X3 X2 RHS

X1 1/2 - 1/2 45/2
X4 - 1/2 - 5/2 175/2
X5 - 1/2 3/2 95/2
F 11/2 -19/2 247,50

Diese Lösung ist zwar eine gültige, aber immer noch nicht optimal. Daher weitere Iteration durchführen:

III. Pivotspalte X2, Pivotzeile X5, Pivotlement hat den Wert 3/2

X3 X5 RHS

X1 1/3 1/3 38 1/3
X4 1/3 1 2/3 166 2/3
X2 -1/3 2/3 31 2/3
F 2 1/3 6 1/3 548 1/3

Die Zielfunktion hat nur noch positive Koeffizienten, das ist eine hinreichende Bedingung um feststellen zu können, dass diese Lösung optimal ist.

X1 = 38 1/3
X2 = 31 2/3

X3, X5 = 0 (offensichtlich werden diese Faktoren voll ausgenutzt)
X4 = 166 2/3 (verbleibende ungenutzte Restkapazität dieser Schranke)



Lösungshinweise:

1. Pivotspalte, Pivotzeile, Pivotelement bestimmen
(genauso wie bei der unverkürzten Form)

2. Im neuen Tableau die zur Pivot-Position zugehörige Basisvariable mit der Nichtvariable vertauschen. Im Beispiel oben verlässt X1 beim ersten Iterationsschritt die Basis und dafür wird X3 in die Basis aufgenommen.

3. Aus dem Pivotelement wird nach dem Iterationsschritt das Reziprok.
Im Beispiel: aus der 2 wird 1/2

4. Nun die Pivotzeile transformieren: aus allen Elementen wird der alte Wert geteilt durch das Pivotelement.

5. Nun die Pivotspalte transformieren: aus allen Elementen wird der alte Wert geteilt durch das Pivotelement MAL MINUS EINS.

6. Es verbleiben im neuen Tableau noch 6 weitere Felder... Diese nach der Standard-Methode berechnen, die aus dem unverkürzten Tableau bekannt ist (Kreis-Regel).

7. Prüfen ob Lösung optimal ist, ggfls. erneute Iteration...


Kann mal jemand diese Lösung bzw. auch den Lösungsweg bestätigen oder korrigieren?

viele Grüsse
Matthias
 
M

matthi

Hab das ganze zusätzlich nochmal in eine Excel-Tabelle abgetippt.

Das schöne daran ist, dass man sich zu jeder Zelle die dahinterliegende Formel ansehen kann.

Außerdem kann man mit den Werten herumspielen und mal testen, was passiert, wenn sich verschiedene Eingangsvariablen ändern (achtung, nur in engen Grenzen: die Entscheidung, was Pivotelement wird, ist "hartkodiert"... Excel hat zwar auch dynamische Funktionen, insbesondere Pivotfunktionen, aber damit kenne ich mich nicht aus).

viele Grüsse
Matthias
 
J

Jürgi

Achtung: Falsche Ergebnisse

Hallo Matti,

ich habe diese Rechung der Klausur März 2003 auch gemacht - allerdings nicht mit dem verkürztem Simplex, sondern herkömmlich.
Dabei kommen glatte Ergebnisse raus.
Xopt = (X0, X1, X2, S1, S2, S3) = (735, 35, 25, 0, 0 ,10).

Den Prozess wie man das macht, habe ich leider trotzdem nicht raus. Aber so gibt es ja auch noch 20 Punkte.

Vielleicht kannst Du es mir ja nochmal erklären, oder mir per Mail mal Deine Excel-Tabelle schicken.

Gruß, Jürgi
 
S

sstachna

Wie funktioniert denn die "kreis-regel" für die restlichen felder ? thx
 
S

sstachna

Und der fehler, den ich beim kurzen überfliegen meine zu sehen, ist, dass matti mit -11 und -4 in der Zielzeile anstatt mit -11 und -14 rechnet, wie in der aufgabenstellung, afaik...
 
Hallo Nicole,

die Beiträge in diesem Thread sind leider alle schon etwas älter, wo hast Du den denn ausgegraben ;).

Ich weiß nicht, ob es Dir hilft, aber ich hab versucht, es hier zu erklären (allerdings ohne Kreisregel etc :eek:).

Wenn Du mit dem verkürzten nicht klarkommst, rechne es lang - fürs Bestehen sollte es auch dann reichen :)
 
Hallo Kerstin,

vielen Dank, werds mir gleich mal anschaun!
War einfach verzweifelt auf der Suche und hab nicht darauf geachtet wie alt die Einträge schon sind!!!

Gruß Nicole
 
Top