• Guten Start ins Wintersemester 2024/2025

rein-ganzzahliger Alg. von GOMORY

Cobra

Cobra

Unser Sponsor SAP 4 Students
Unser Sponsor
rein-ganzzahliger Alg. von GOMORY

Hallo,
habe mal wieder eine Frage (okay, einige mehr)😕.
Auf Seite 48/49 (853) steht, dass man, falls das Ausgangsproblem nicht dual zulässig ist, man eine Zusatzrestriktion x1+x2+...+xn <= M waehlt, wobei M hinreichend gross sein muss. Nur, wie waehle ich M? Wie gross muss ich es waehlen?
Ferner heisst es, dass das Problem dual zulässig ist, wenn cj>=0 ist. Im Beispiel 3.2 sind doch alle cj>=0. Waere es dann nicht auf jeden Fall dual zulaessig?
Bei der Erklaerung des Verfahrens und bei dem Algorithmus taucht auf einmal ein delta zs und delta zj auf. Was ist denn das? Damit weiss ich natuerlich auch nicht, wie man alpha j bestimmt.
Na ja, das letzte Problem ist dann die Uebungsaufgabe 3.2. Ist das Problem nun dual zulaessig? Alle cj sind doch >=0, oder? Wenn nicht, wie waehle ich denn das M fuer die Zusatzrestriktion?
Vielen Dank fuer Eure Hilfe!
Gruss,
Ulrike
 
Ulrike,
ich probier's mal wieder:
Cobra schrieb:
Auf Seite 48/49 (853) steht, dass man, falls das Ausgangsproblem nicht dual zulässig ist, man eine Zusatzrestriktion x1+x2+...+xn <= M waehlt, wobei M hinreichend gross sein muss. Nur, wie waehle ich M? Wie gross muss ich es waehlen?
Zum Vergrößern anklicken....
M muss einfach so groß sein, dass die damit eingefügte Restriktion keinen "Einfluss" auf die Lösung hat. Wenn Du es Dir bildlich in einer x1x2-Ebene vorstellst, ist die Restriktion x1+x2<=M ja eine Gerade von links oben (bei M auf der x2-Achse) nach rechts unten (bei M auf der x1-Achse). Jetzt wählst Du das M so groß, dass diese Gerade auf alle Fälle außerhalb des ganzen (eingezeichneten) möglichen Lösungsraums ist.
Cobra schrieb:
Ferner heisst es, dass das Problem dual zulässig ist, wenn cj>=0 ist. Im Beispiel 3.2 sind doch alle cj>=0. Waere es dann nicht auf jeden Fall dual zulaessig?
Zum Vergrößern anklicken....
Dual zulässig ist ein Problem, wenn die Kriteriumszeile (also die "erste" Zeile des Pivottableaus, das sind die cj) nichtnegativ ist (vgl. 851, KE2, Seite 13). In Beispiel 3.2 sind die cj beide negativ (nämlich -1 bzw. -2) und werden erst durch den eingezeichneten Pivot-Schritt positiv.
Cobra schrieb:
Bei der Erklaerung des Verfahrens und bei dem Algorithmus taucht auf einmal ein delta zs und delta zj auf. Was ist denn das? Damit weiss ich natuerlich auch nicht, wie man alpha j bestimmt.
Zum Vergrößern anklicken....
... an diesen Algorithmus kann ich mich jetzt auch nicht mehr wirklich erinnern🙁 . Allerdings habe ich in mein Skript mit Bleistift geschrieben, dass delta zj der Wert in der Zielfunktionszeile bei Spalte j ist. Ich hoffe mal, dass das stimmt - dann kann man ja delta zs und alpha j ausrechnen.
Ich weiß aber noch, dass ich ewig mit diesen Schnittebenenverfahren gekämpft habe, sie kurz vor der Klausur endlich verstanden hatte und dann nichts davon drankam😎 !
Gruß Petra
 
Petra,
vielen Dank wiederum fuer Deine Erklaerung.
Wenn es ein 2-dimensionales Problem ist, kann ich anhand der Graphik ja ausprobieren, welches M ich brauche. Nur, was mache ich wenn ich X1 bis x3 oder mehr habe? Dann kann ich keine Graphik mehr malen.Wie bestimme ich M?
Kannst Du mir auch noch erklaeren, wie die Uebungsaufgabe 3.2 geht?
Was soll ich eigentlich mal ohne Deine Hilfe tun?
Grusss,
Ulrike
 
Ulrike,
Cobra schrieb:
Wenn es ein 2-dimensionales Problem ist, kann ich anhand der Graphik ja ausprobieren, welches M ich brauche. Nur, was mache ich wenn ich X1 bis x3 oder mehr habe? Dann kann ich keine Graphik mehr malen.Wie bestimme ich M?
Zum Vergrößern anklicken....
Ich glaube, da machst Du Dir viel zu viele Gedanken. Es wird in keiner Klausur eine Aufgabe mit fünf oder mehr Variablen und "wilden" Nebenbedingungen drankommen. Du kannst ja M ruhig um einiges zu gross wählen, das schadet nichts. Auch bei drei Variablen und vielleicht auch drei oder vier Restriktionen kann man durch Hinschauen erkennen, wie gross man M etwa wählen muss (und dann kannst Du ja immer noch ein bisschen zugeben...🙂 ). Das taucht übrigens noch in einigen Algorithmen bei der Graphentheorie auf, dass die Schritte nicht ganz exakt gegeben sind, sondern man durch Hinschauen und logisches Denken weiterkommt (z.B. wenn man einen Weg in einem Netzwerk vom Start zum Ziel suchen muss).
Cobra schrieb:
Kannst Du mir auch noch erklaeren, wie die Uebungsaufgabe 3.2 geht?
Zum Vergrößern anklicken....
Die muss ich jetzt erst mal selbst lösen (da freut man sich ja mal wieder über die ausführliche Musterlösung auf den blauen Seiten...😡 ). Ich melde mich dann nochmal!
Cobra schrieb:
Was soll ich eigentlich mal ohne Deine Hilfe tun?
Zum Vergrößern anklicken....
Vielen Dank für die Blumen😀 ! Ich werde mich bemühen, möglichst oft zu helfen, und außer einer Woche Urlaub an Pfingsten und zwei Wochen im Sommer sollte ich auch meistens online sein!

Gruss Petra
 
Ulrike,
Cobra schrieb:
Kannst Du mir auch noch erklaeren, wie die Uebungsaufgabe 3.2 geht?
Zum Vergrößern anklicken....
...ich geb's auf, ich kann es auch nicht😡 😡 😡 . Komischerweise habe ich in meinem Skript bei diesem Algorithmus auch gar keine eigenen Markierungen aus meiner eigenen Klausurvorbereitung. Das kann eigentlich nur bedeuten, dass ich ihn damals schon nicht verstanden habe...🙁. Entweder bin ich also auch zu doof, oder es ist vielleicht doch ein Fehler im Skript? Ich kann auch absolut nicht verstehen, wie man auf Seite 53 Mitte auf die Schnittrestriktion kommt, so wie ich den Algorithmus verstehe, müsste dort doch -x1-1/4x4+s= -3/4 stehen????? Vielleicht kann uns ja ein anderer weiterhelfen!
Auf jeden Fall kommt man in der Übungsaufgabe auch mit einem ganz gewöhnlichen Simplex zu einer richtigen, ganzzahligen Lösung.
Die nächsten Algorithmen sind bei mir wieder voller Bleistiftmarkierungen, die scheine ich also verstanden zu haben...
Gruss Petra
 
Das "merkwürdige" an dieser Aufgabe ist, dass es unendlich viele reelle und mehrere ganzzahlige Lösungen gibt. Die Zielfunktion liegt nämlich auf einer der Restriktionsgeraden. Wenn man Glück hat und "richtig herum" pivotisiert, bekommt man sofort eine ganzzahlige Lösung heraus. Insofern eine recht unglückliche Aufgabe.

Am besten versuchst Du das Beispiel 3.2 (bei mir auf Seite 53) nachzuvollziehen, das klappt besser und hat eine eindeutige Lösung.
....

Zu Gommery:

Wie Petra schon schrieb, sind die Deltas die jeweiligen Werte der Zielfunktionskoeffizienten.

Zur Primalen/Dualen Zulässigkeit kannst Du Dir (bei einem Max-Problem) noch folgende ökonomische Interpretation vorstellen:

Primal zulässig ist jede Lösung, die mit den vorhandenen gegebenen Produktionsfaktoren (Rohstoffen/Maschinenstunden etc.) irgendeinen Output produziert. Eine Primale Lösung berechnet also quasi den Output.
Optimalität ist erreicht, wenn der Output maximal ist.

Dual zulässig ist jede Lösung, die einen Faktoreinsatz ermittelt, der (richtig kombiniert) einen (vorgegebenen) Output erzeugt. Dualität stellt also quasi die Produktionsfunktion korrekt dar und ermittelt die notwendigen Faktoreneinsätze.
Optimalität ist erreicht, wenn die Produktionsfaktoren auch tatsächlich vorhanden sind (also die Nebenbedingungen eingehalten sind).

Damit wird dann auch klar, dass eine primal und dual zulässige Lösung gleichzeitig den maximalen Output bei gegebene Faktoren ermittelt.

MfG
Thomas
 
damit Ihr nicht noch weiter Zeit unnütz verschwendet (es sei denn, einer von Euch strebt eine wissenschaftliche Laufbahn in Operations Research an oder möchte später an der Weiterentwicklung professioneller Optimierungssoftware wie z. B. Xpress, Cplex, beteiligt sein):

Das erste Wort des Abschnitts 5.2 ist auch gleich das entscheidende: "RUNDUNGSFEHLER können ...". Wie soll bei den Modellen, die Ihr manuell in Tableaus errechnet, ein Rundungsfehler auftreten? Keiner von uns schreibt z. B. für den Bruch "1/13" in sein Tableau gerundet und damit ungenau0,0769239769239769. D. h. Rundungsfehler und hieraus resulierende Folgeprobleme können bei der Art und Weise, wie wir Iterationen durchführen, gar nicht entstehen.

Der Abschnitt 5.2 ist definitiv klausurirrelevant. Von daher kann ich nur dringend empfehlen, keine weitere Minute in diesen Abschnitt zu investieren.

Beste Grüße
loddar
 
ermsech schrieb:
Entweder bin ich also auch zu doof
Zum Vergrößern anklicken....
Das glaube ich nicht. Was soll ich dann ohne Deine Hilfe tun? 😀
ermsech schrieb:
Ich kann auch absolut nicht verstehen, wie man auf Seite 53 Mitte auf die Schnittrestriktion kommt, so wie ich den Algorithmus verstehe, müsste dort doch -x1-1/4x4+s= -3/4 stehen?????
Zum Vergrößern anklicken....
wegen h<1 sind nach 8. alle [hyrs]=-1
ermsech schrieb:
Auf jeden Fall kommt man in der Übungsaufgabe auch mit einem ganz gewöhnlichen Simplex zu einer richtigen, ganzzahligen Lösung.
Zum Vergrößern anklicken....
Ja, die Loesung (0,8,0) bekomme ich raus, wenn ich das richtige Element waehle.
ermsech schrieb:
Die nächsten Algorithmen sind bei mir wieder voller Bleistiftmarkierungen, die scheine ich also verstanden zu haben...
Zum Vergrößern anklicken....
Das ist gut. Ich komme drauf zurueck.
 
loddar schrieb:
Der Abschnitt 5.2 ist definitiv klausurirrelevant. Von daher kann ich nur dringend empfehlen, keine weitere Minute in diesen Abschnitt zu investieren.
Zum Vergrößern anklicken....
...also da wäre ich mir nicht so sicher. Ich halte es zwar auch für unwahrscheinlich, dass dieser Algorithmus drankommt (vor allem deshalb, weil die meisten anderen Themen aus dem Kurs meiner Meinung nach "wichtiger", weil praxisrelevanter sind), aber defintiv ausschließen kann man es meiner Meinung nach nicht. Trotzdem sollte man sich bestimmt nicht an dieser Stelle frustriert festbeißen, offensichtlich hatte ich da ja vor zwei Jahren auch "Mut zur Lücke"...

Gruß Petra
 
Ich schreib einfach mal den Algorithmus am Beispiel 3.2 rein:
wichtig ist, das r und s Nummern der Zeilen bzw. Spalten sind

1. alle RHS negativ?
=> nein

2. Wähle eine Zeile mit negativer RHS und setze r= diese Zeile
=> das ist die Zeile Nr. 1, die für die Variable x3 steht => r=1

4. wähle aus allen Spalten, bei der in Zeile Nr. r=1 negative Werte stehen, die Spalte mit kleinsten Zielfunktionskoeffizienten (das Delta) und setze s=Nr. dieser Spalte
=> in Frage kommen beide Spalten, weil in Zeile 1 beide Werte negativ sind (-4 und -1), in der Zielfunktionszeile stehen 1 und 2, davon der kleinste Wert ist die 1 in Spalte 1 => s=1

6. bestimmen von alpha j
delta zs ist der Zielkoeffizient in Spalte s; wir hatten die erste Spalte gewählt, der Zielkoeffizient ist dort 1; nun wird jeder Zielkoeffizient durch 1 dividiert und das Vorzeichen gedreht, damit ist
alpha1 = -1/1; alpha2 = -2/1

7. h ausrechnen
das Alpha wird nun durch den jeweiligen Wert in der Zeile r geteilt und davon das minimum gewählt
r war bei uns 1 geteilt wird also durch die Werte in Zeile1
=> alpha1 durch -4 und alpha 2 durch -1
davon das minimum ist 1/4=h

8 Schnittrestriktion hinzufügen
h wird nun mit jedem Koeffizienten in Zeile r multipliziert und nur die nächstkleinere ganze Zahl hingeschrieben
r war Zeile 1, die Koeffizienten lauten -4 und -1
= [-4 * 1/4 ]x1 + [-1 * 1/4]x4 +xs= [-3 * 1/4]
= [-1]x1-[1/4]x4+xs=[-3/4] nun die nächstkleinere ganze Zahl
= -1x1 -1x4 +xs = -1 (und da ist die Schnittrestriktion)

9. Pivotisieren
ein dualer Simplexschritt in der hinzugefügten Zeile

10 fertig
MfG
Thomas
 
Dr Franke Ghostwriter
hatte eine Mail an Frau Rudolph vom Lehrstuhl geschrieben bzgl. dieser Zusatzrestriktion bzw der Bestimmung des 'M's und der Uebungsaufgabe 3.2. Ihre Antwort war die folgende:

Die Aufgabe ist leider sehr unglücklich gewählt, da mehrere Schnittrestriktionen eingefügt werden müssen und das - ehrlich gesagt - in einer elenden Rechnerei endet.
Sollte Gomory in der Klausur abgefragt werden, so können Sie davon ausgehen, dass entweder das erste Verfahren anzuwenden ist oder das Problem in der Form formuliert ist das Sum_x_j<=M bereits als Restriktion vorhanden und nach Einfügung einer Schnittrestriktion die ganzzahlige Lösung zu finden ist.

Gruss,
Ulrike
 

Weiter lesen

K
Rein-ganzzahliges Gomory-Verfahren
Antworten
3
Aufrufe
2K
Berno
B
Oben