Frage zu Modul/Klausur Frage zu Stepping Stone

uried · 5 März 2013

Frage zum Stepping-Stone-Algo., auch wenn noch nie in KLausuren dran:

Wer kann mir Schritt 3 V) {Ändern der Knotenpotentiale} erklären? Jedesmal wenn ich glaube es verstanden zu haben und mache eine andere Aufgabe, scheitere ich genau an diesem Punkt? Die Erläuterungen im Skript der vorherigen Seiten helfen mir nicht wirklich. :cry:

MIJM · 6 März 2013

Hallo,

ich mache es jetzt einfach so.
Beim ersten Schritt rechnet man doch mit u1=0 in der ersten Zeile, berechnet dann die anderen ui und uj.
Die Lösung, die dann herauskommt, nehme ich einfach als neue Ausgangslösung und fange quasi mit dem ersten Schritt von Stepping wieder an; also u1=0 in der ersten Zeile, Berechnung der anderen ui und uj usw. Habe das Beispiel im Skript eben so gerechnet und komme auf die richtige Lösung.
Werde es nochmal an anderen Aufgaben versuchen, müsste aber gehen.
Gruß

uried · 6 März 2013

MIJM schrieb:
Hallo,

ich mache es jetzt einfach so.
Beim ersten Schritt rechnet man doch mit u1=0 in der ersten Zeile, berechnet dann die anderen ui und uj.
Die Lösung, die dann herauskommt, nehme ich einfach als neue Ausgangslösung und fange quasi mit dem ersten Schritt von Stepping wieder an; also u1=0 in der ersten Zeile, Berechnung der anderen ui und uj usw. Habe das Beispiel im Skript eben so gerechnet und komme auf die richtige Lösung.
Werde es nochmal an anderen Aufgaben versuchen, müsste aber gehen.
Gruß

Wenn es so einfach wäre. Im Bsp. im Skript S. 53 wurde das Potential von 1,3' geändert, es ändert sich u.a ui mit i=1.
Im nächsten Schritt wird Potential von 2,1' geändert, es ändert sich aber uj mit 1'. Irgendwie habe ich hier einen Hänger.
Im übernächsten Schritt wieder ui. Klar kann man, wenn man ein ui oder uj hat, den Rest ableiten. Aber wo fängt man an? Wann nimmt man ui oder uj?

MIJM · 6 März 2013

Also dann mal am besten von Anfang an.
Seite 52 zeigt das Transporttableau mit zulässiger Anfangslösung.
Dann setzt man u(i )=0 für i=1.
Jetzt muss auf allen Feldern auf denen eine Transportmenge steht gelten: c(ij)quer=c(ij)-u(i)+u(j).
In Feld 11 steht eine Transportmenge, nämlich 3 bei Kosten von 4: 4-0+?=0, also u(j)=-4 für j=1.
In Feld 14 steht eine Transportmenge, nämlich 1 bei Kosten von 5: 5+0-?=0, also u(j)=-5 für j=4.
Jetzt kann man mit Feld 24 weitermachen: 6-?-5=0, also u(i)=1 für i=2,
dann Feld 34: 2-?-5=0, also u(i)=-3 für i=3,
dann Feld 23: 8-1+?=0, also u(j)=-7 für j=3,
dann Feld 32: 8-(-3)+?=0, also u(j)=-11 für j=2.
Damit hat man dann alle u(i) und u(j).
Nun berechnet man die c(ij)quer in den Feldern ohne Transportmengenangaben als c(ij)quer=c(ij)-u(i)+u(j).
Ist kein negatives c(ij)quer dabei ist man fertig und hat eine optimale Lösung,
wenn nicht sucht man das negativste c(ij)quer und verteilt um.
Nach dieser Umverteilung hat man einen neuen Transportplan.
Setze nun wieder u(i)=0 für i=1 und fange von vorne an.

uried · 7 März 2013

MIJM schrieb:
...
Nach dieser Umverteilung hat man einen neuen Transportplan.
Setze nun wieder u(i)=0 für i=1 und fange von vorne an.

Der Anfang war schon klar. Aber wenn nach der Potentialänderung wieder mit u(i)=0 für i=1 angefangen wird, warum stehen dann in den Tableaus S. 57 ff. (die ja die Fortsetzung deines Bsp. darstellen) dann u(i) ungleich 0 für i=1?

MIJM · 7 März 2013

Ich habe selbst Probleme, die neuen u(j) und u(i) herauszufinden. Vielleicht bekomme ich das bis Sonntag noch hin, da muss man parallel wohl die Bäume hinmalen wie in Abb. 7.11 und 7.12 und da bekommt man dann raus, wo man dieses delte u addieren oder subtrahieren muss um einen neuen Anfang zu machen.
Deshalb mache ich es so: das Transporttableau was ich nach dem ersten Schritt heraushabe nehme ich einfach wieder als Anfangstableau, setze mein u(i)=0 für i=1 und mache den ersten Schritt nochmal.
Man kommt dabei immer zur richtigen Lösung.

uried · 7 März 2013

MIJM schrieb:
Ich habe selbst Probleme, die neuen u(j) und u(i) herauszufinden. Vielleicht bekomme ich das bis Sonntag noch hin, da muss man parallel wohl die Bäume hinmalen wie in Abb. 7.11 und 7.12 und da bekommt man dann raus, wo man dieses delte u addieren oder subtrahieren muss um einen neuen Anfang zu machen.
Deshalb mache ich es so: das Transporttableau was ich nach dem ersten Schritt heraushabe nehme ich einfach wieder als Anfangstableau, setze mein u(i)=0 für i=1 und mache den ersten Schritt nochmal.
Man kommt dabei immer zur richtigen Lösung.

Danke, hat mir erst einmal weitergeholfen. Die c_quer stimmen überein, die ui und uj können ja nicht mit dem Skript übereinstimmen, da wir wieder mit ui=0 für i=1 angefangen haben.
Bei nur einer Potentialänderung kommt es hin, wenn wir statt 0 für ui den Wert des Potentials mit entgegengesetzten VZ eintragen. Später müsste man für ui die Summe aller Potentialänderungen (natürlich mit entgeg. VZ) eintragen, damit man mit dem Skript übereinstimmt.
Klingt jeodch sehr stümperhaft und unmathematisch.

Ottokarotto · 9 März 2013

B0711 ist eine SteppingStone Aufgabe, ich denke, wenn Stepping-Stone, dann kann es nur in diesem Umfang sein,
denn alles andere würde den Zeitrahmen sprengen. Anhand der Lösung kann man es ganz gut nachvollziehen. Hier sieht man dann auch, welche u_i und u_j sich ändern....
Im Prinzip muß man m.E. für die ui und uj "nur" schauen, welche MAtrixelemente sich geändert haben, und wie die durch die reduzierten Kosten zusammenhängen und ggfs anpassen.
Nicht sehr wissenschaftlich ausgedrückt, hoffe aber, daß es für Montag reicht ;) ... auf das Bier am Münchner bahnhof inkl Currywurst vom Yormaz freue ich mich jetzt schon