Hallo, ich habe ein Problem mit einem Simplex-Starttableau, hier ist es erst einmal:

Zitat

3 4 | 1 0 | 100
2 8 | 0 1 | 200
-----+------+-------
-3 -3 | 0 0 | 0

Das erste Problem beginnt damit, dass beide Deckungsbeiträge in der letzen Zeile -3 aufweisen.
Das zweite Problem liegt darin, dass auch die Quotienten, wenn man sich für die zweite -3 entscheidet, gleich sind: Denn 100:4 ist genauso 25 wie 200:8.

Man hat also massig Auswahl für einen Einstieg in die erste Iteration.

Nun mein Problem:
Wenn man sich dafür entscheidet, mit der ersten Zeile zu beginnen, also aus der 3 oder der 4 eine 1 zu machen, dann erhält man als Ergebnis einen Gesamtgewinn von 100.
Wenn man sich dafür entscheidet, aus der 8 eine 1 zu machen (rechnerisch kann man so starten), dann erhält man als Ergebnis 300, egal wie man weiterrechnet.

Kann mir jemand sagen, ob es Beschränkungen gibt, wie man starten darf?

Danke und Gruß

Hi Ingo,

Du hast offensichtlich eine Mehrdeutigkeit, und das gleich mehrfach. Die mehrfache Mehrdeutigkeit ist in der Wirklichkeit sehr selten, aber in Prüfungsaufgaben öfters anzutreffen.

Grundsätzlich kannst Du Dir Simplex wie einen Baum vorstellen. Jede Mehrdeutigkeit ist eine Gabelung der Äste. Du mußt, willst Du ein Ergebnis, immer alle Äste untersuchen, denn sie reichen unterschiedlich weit - sie erbringen, formaler gesagt, nur Pareto-Optima. Es gibt meines Wissens keien Möglichkeit vorher zu wissen, welcher Ast weiter und welcher nicht so weit reicht. Die Methode, alle Äste zu prüfen, ist Backtracking. Man merkt sich jede Mehrdeutigkeit und kehrt nach volsltändiger Berechnung eines Weges zur letzten Gabelung zurück und nimmt dort den anderen Weg. Nur ein Ve rgleich er erzielten Endergebnisse verschafft letzte Gewißheit über das absolut (und nicht nur relativ) optimale Ergebnis.

Hallo Harry,

das ist ja mal eine Antwort, die mir weiterhilft.

Man muss zur Bestimmung des Ergebnisses bei Mehrdeutigkeit also immer alle Varianten bis zum bitteren Ende durchspielen. Das ist ja übel, es verkompliziert einen Lösungsalgorithmus erheblich.

Danke und viele Grüße

Ingo

Hi Ingo,

mein XLS-Simplex-Rechner in http://www.zingel.de/zip/08lpg.zip kann auf Mehrdeutigkeiten nur aufmerksam machen; Du müßtest dann den jeweiligen Stand der Rechnung zwischenspeichern und die Anzahl der möglichen Fortsetzungen in einer Variable vermerken; dann könnte jeder Weg bis zum Ende ausgekostet werden.

Ja, das ist sackstandig das zu programmieren!

Hallo Harry,

ich habe übrigens gerade deinen Aufsatz "Lineares Optimieren mit der Simplex-Methode" gelesen. Hat mir gut gefallen. :!:

Gruß Ingo