WER KANN SIMPLEX ALGORITHMUS VERKÜRZT?

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

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

Danke matthi!

andi

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

Matthias, wenn du willst kannst du auch ganz einfach die Excel - Datei hier hinstellen. Einfach auf dieses Thema antworten, indem du auf "Antworten" klickst (https://www.studienservice.de/newreply.php?do=newreply&noquote=1&p=9725), also nicht über "Direkt antworten". Und dann auf Anhänge verwalten klicken.

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

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...

habe auch Riesenprobleme damit. Vielleicht könnte mir ja Deine Excel-Liste helfen. Könntest Du mir diese per mail zukommenlassen?
[email protected].
Wäre supernett und vielleicht sehr hilfreich.

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 😱).

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

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