2-Phasen Simplex < Operations Research < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:26 Fr 09.10.2009 | | Autor: | MrPink |
Hallo Leute, hätte mal ein kurze Frage:
Für ein Projekt bin ich gerade dabei einen 2 Phasen Simplex zur Minimierung einer Zielfunktion zu implementieren.
Ich mache es analog zu diesem Beispiel:
http://statistik.wu-wien.ac.at/~leydold/MOK/HTML/node164.html#SECTION05480000000000000000
Das Problem ist nun folgendes: Die Erste Phase läuft soweit gut. Allerdings kommt es danach noch oft vor, dass ich noch Hilfsvariablen als Basisvariablen habe. Wie kann ich diese entfernen?
Für den Fall, dass mein Zielfunktionswert nach der ersten Phase = 0 ist, und es keine Hilfsvariablen mehr in der Basis gibt, sind meine Ergebnisse prüfbar korrekt !!! Sobald aber eine Hilfsvariable in der Basis ist, stimmen die Werte vorne und hinten nicht :-( Die sollen da raus 
Kann mir das jemand kurz erklären, oder habt ihr ein Beispiel dafür parat ? Alles was ich finden konnte ist immer ohne Beispiel, bzw. dort steht durch "geeignette umformungsschritte" ....
Vielen Dank im Voraus!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:09 Sa 10.10.2009 | | Autor: | piet.t |
Hallo,
wenn in deiner Phase 1 der Zielfunktionswert = 0 ist, aber noch Hilfsvariablen h in der Basis sind, dann haben wir es ja mit einer degenerierten Lösung zu tun (da die Basisvariable h = 0 ist).
In diesem Fall darf der Phase-1-Algorithmus noch nicht abbrechen, sondern muss noch weitere Pivotschritte durchführen, die allerdings den Zielfunktionswert (der ja bereits optimal ist) nicht verändern dürfen.
Daher braucht man hier ein etwas andere Vorgehen bei der Suche nach dem Pivotelement.
Mit dem Tableau-Simplex kenne ich mich nicht so großartig aus, aber hier mal ein Vorschlag (ohne Gewähr für Richtigkeit):
Pivotzeile soll die Zeile j sein, in der der Wert von h steht. Der Konstanteneintrag dieser Zeile ist also 0.
Wählt man nun die Pivotspalte so, dass
1.) Der Eintrag in Zeile j > 0 ist und
2.) Die Pivotspalte nicht zu einer Hilfsvariablen gehört (sonst haben wir ja nichts gewonnen, da eine andere Hilfsvariable in die basis aufgenommen würde)
so bekommt man als Pivotzeile automatisch die Zeile j: weil der Koeffizient = 0 ist gibt es bestimmt keinen kleineren, nicht-negativen Eintrag.
Eine solche Spalte sollte man hoffentlich immer finden, aber da bin ich mir jetzt nicht ganz sicher.
Führt man nun den Pivot-Schritt aus, so verläßt h die Basis und wird durch eine Nicht-Hilfsvariable ersetzt. War h die letzte Hilfsvariable in der Basis, so ist man nun mit Phase 1 fertig, ansonsten führt man dieses Verfahren erneut durch.
Probier's einfach mal so (oder so ähnlich) aus und schreib mal kurz, ob es geholfen hat.
Gruß
piet
|
|
|
|
