Ungarische Methode // Beispiel 9.2 (grafische Lösung)

Ich versuch mal selbst die Diskussion fortzuführen.

Kann es sein, dass gar kein so großes Geheimnis dahinter steckt sondern Vm einfach die Menge ist, bei der auf Seite 87 KE2 eine Ford-Fulkerson Markierung stattgefunden hat aber eben kein Breakthrough.

Dann wären das eben genau Knoten 2,3 und 1'.
Kann das jemand bestätigen.
Vu ist dann einfach der Rest.

Danach werden alle Pfeile, die von den 3 Knoten abgehen betrachtet, also in dem Fall nur von Knoten 2 und 3, weil bei 1' ja nichts weg geht.
Hier werden nun alle Pfeile mit cij_stricj > 0 notiert. Von allen cij_strich wird nun das Minimum gesucht, welches im Beispiel 1 ist und danach werden nach den Formeln die Knotenpotentiale geändert.

Vm ist die markierte Menge. Vu die unmarkierte. Deswegen m und u.
Es sind nur die drei Knoten markiert auf Seite 87 (nicht die mit der Raute, die mit den Klammern). Das ist Vm.
Alles richtig.

Ja, genau das. Seite 87 finden die Markierungen entlang der fetten Pfeile statt. Vm vereint dabei die "m"arkierten Knoten, Vu die "u"nmarkierten Knoten. Der Rest ist so, wie Du sagst.

Ok, danke für die schnellen Antworten. Das hat mich mit den Rauten immer verwirrt.
Jetzt bin ich grad noch an der Übung 9.1, das bekomm ich soweit hin, nur könnt ihr mir sagen, warum beim 1. Mal alle Vm Potentiale um 1 erhöht werden und bei der 2. Potentialänderung alle Vu um 1 reduziert? Ist das reine Willkür, was gerade weniger Rechenarbeit macht? Auf Seite 88 steht ja ein "oder" zwischen beiden Varianten.

Gruß, Nico

Ich hänge auch gerade bei der Aufgabe. Mir ist total unklar wie ich die Knotenpotentiale bei der Aufgabe 9.1 ändern soll.

Reine Willkür...

happydidi schrieb:

Hallo zusammen. Ich hänge auch gerade bei der Aufgabe. Mir ist total unklar wie ich die Knotenpotentiale bei der Aufgabe 9.1 ändern soll. 🙁

Zum Vergrößern anklicken....

Ok, ich versuch mal zu helfen. Bist du schon an der Stelle bei der du merkst, dass du keine Verbindung zu Knoten 3' hinbekommst, also quasi einen Non-Breakthrough? Du endest quasi damit, dass nur Knoten 2,3 und 1' mit Ford-Fulkerson markiert sind. Das sind nun deine Vm. Nun gehst du genau so vor wie im Beispiel davor. Du addierst quasi zu den Potentialen der Knoten 2,3 und 1' den kleinsten Cij_strich Wert, der von den Vm Knoten weg geht. Das ist meiner Meinung nach der 3-4 Pfeil mit 1.
Also erhältst du für die neuen Potentiale

Knoten 2: 3
Knoten 3: 5
Knoten 1': 1

Jetzt nur noch die C_strich ändern und zwar so:
Von allen unmarkierten Knoten zu Markierten, also bsplw. von 1 zu 1' 1 dazu addieren.
Von allen markierten Knoten zu Unmarkierten eins wegnehmen. Bsplw. von 2 nach 2, 3 oder 4.

Und dann bekommst du aber immer noch keinen NBT und musst das Ganze noch einmal durchführen. Ich würds dir gerne einscannen, um es leichter verständlich zu machen. Bin aber grad schon in München wegen Montag.

danke schön. Bis dahin habe ich das verstanden. Aber komme jetzt noch nicht ganz weiter mit dem zweiten Mal durchführen. Warum bekomme ich jetzt bei Konten4 3 und Konten2' -1 und Knoten3' -2. Also ja überall einen weniger. Warum rechne ich jetzt -? Weil die nicht markiert waren? Warum genau diese Knoten nun????

Du kannst laut Seite 88 selbst entscheiden, ob du alle Vm +1 oder alle Vu -1 machst. Hier wurde immer der wenigste Rechenaufwand betrieben.
Beim zweiten NTB Schritt hast du ja, wenn du alles richtig gemacht hast mit Ford-Fulkerson Knoten 1,2,3 und 1',4' markiert. Hier nimmst du also um Rechenaufwand zu sparen die geringere Knotenmenge Vu (4,2',3') und subtrahierst 1. Man könnte hier genauso wieder alle Vm +1 nehmen. Hab ich jetzt nicht ausprobiert, aber dürfte auf dasselbe rauskommen.
Verstanden?

Danach gibts dann den gewünschten BT.

Ahso 😀
Ja die Knoten habe ich so markiert!
Dann habe ich es verstanden! Vielen Dank!
Und viel Glück am Montag!

Wünsch ich dir auch. Schön, dass ich helfen konnte.

wirnico schrieb:

Du kannst laut Seite 88 selbst entscheiden, ob du alle Vm +1 oder alle Vu -1 machst. Hier wurde immer der wenigste Rechenaufwand betrieben.
Beim zweiten NTB Schritt hast du ja, wenn du alles richtig gemacht hast mit Ford-Fulkerson Knoten 1,2,3 und 1',4' markiert. Hier nimmst du also um Rechenaufwand zu sparen die geringere Knotenmenge Vu (4,2',3') und subtrahierst 1. Man könnte hier genauso wieder alle Vm +1 nehmen. Hab ich jetzt nicht ausprobiert, aber dürfte auf dasselbe rauskommen.
Verstanden?

Danach gibts dann den gewünschten BT.

Zum Vergrößern anklicken....

Mir ist der zweite NTB Schritt noch nicht klar. Wieso markiere ich die Knoten 1,2,3 und 1',4'???
Vielleicht steh ich auch nur aufm Schlauch!

fribayseller schrieb:

Mir ist der zweite NTB Schritt noch nicht klar. Wieso markiere ich die Knoten 1,2,3 und 1',4'???
Vielleicht steh ich auch nur aufm Schlauch!

Zum Vergrößern anklicken....

Man fängt ja immer bei dem Knoten an, der noch keine Zuordnung hat. Also bei dem, der noch keine 0|1 Verbindung irgendwo hin hat.

1. Diesen markiere ich mit (-,1), in unserem Fall ist das Knoten 3
2. Nun schaue ich wo reduzierte Kosten gleich 0 sind. ich schaue nach Verbindungen mit 0|0. Davon gibt es hier zwei. Einmal nach 1' und einmal nach 4'
3. 1' wird mit (3+,1) und 4' mit (3+,1') markiert
4. Nun schaue ich mit welchen Knoten 1' und 4' bereits verbunden sind. Dies sehe ich an Pfeilen mit 0|1 die eingehen. Das ist bei 1' der Pfeil von 2 kommend und bei 4' der Pfeil von 1 kommend.
5. Jetzt markiere ich Knoten 1 mit (4-,1) und Knoten 2 mit (1-,1).
6. Jetzt geht nichts mehr, weil keine ausgehenden 0|0 mehr von Knoten 1 und 2.
7. übrig bleibt jetzt die Menge Vu mit 4,2' und 3'. Mit denen führe ich die Potentialänderung durch. Außerdem die Potentialänderung der reduzierten Kosten, aber das wurde ja oben schon geklärt

Hoffe es ist jetzt klar.

Ich bekomme noch graue Haare mit diesem Modul 😡

kann mir jemand weiterhelfen?
laut dem Algorithmus müssen die reduzierten Kosten entweder plus oder minus n gerechnet werden, wenn sie in den Mengen Vm, bzw Vu enthalten sind.
also muss ich doch bei den Pfeilen <2,2'>, <2,3'>, <2,4'>, <3,2'>, <3,3'>, <3,4'> cij+ n rechnen und bei den Pfeilen <1,1'> und <4,1'> cij-n
alle anderen bleiben gleich weil die Knoten nicht in den Mengen Vm bzw Vu enthalten sind. aber das stimmt nicht mit der Lösung überein....

wo ist schon wieder mein denkfehler 🙁🙁:unsure

Vanessa,

Leider hänge ich bei der graphischen Methode noch einen Schritt früher, vielleicht kannst du mir kurz helfen, dann schau ich mir dein Problem an 🙂

Wie läuft denn die Zuordnung ab? D.h. Woher weiß ich, wann ich einen Knoten zuordnen kann/darf wenn die reduzierten Kosten = 0 sind und wann darf ich nicht direkt zuordnen? Und wie verfahre ich dann weiter (Schritt 9.3)?

Danke im Voraus

xxankaxx
wenn ich es richtig verstanden habe, dann läuft es folgendermaßen ab:

• du beginnst bei Knoten 1 und gehst von 1 zu einem knoten auf einem weg mit cji=0 (hier 1') und markierst beide mit einer raute - du hast sie zugeordnet.
• dann schaust du dir knoten 2 an. der einzige mögliche weg mit cij=0 geht zu 1' - da warst du aber gerade schon und deshalb kannst du diesen nicht markieren oder zuordnen (2 bleibt "unmarkiert", also ohne raute)
• nun Knoten 3: auch hier ist die einzige Möglichkeit zu 1' , was wieder nicht geht und auch 3 bleibt unmarkiert
• Knoten 4: hier hast du die Wahl zwischen 2' und 3' -> hier wurde 3' gewählt und beide markiert

wir haben 1, 1', 4, 3' markiert und schreiben nun an einen beliebigen unmarkierten Knoten (also 2 oder 3) (-,1)
und "laufen" auf den wegen mit cij=0 bis wir nicht mehr weiter kommen. D.h.:
2 -> 1' (erhöhung von Knoten 2 um 1: (2+,1))
1' -> 1 (Verringerung von Knoten 1' um 1 (1-,1)
1 -> 2' (1+,1)
2' -> kein cij=0 übrig und wir müssen anhalten.

...
ich hoffe das stimmt soweit 🙂 aber so konnte ich es mir zusammenreimen

Vanessa,

Du meinst auf Seite 88 unten?
Da sind die Rechenzeichen +/- doch gerade anders herum?
Dann stimmt´s auch mit der Abbildung 9.5 auf Seite 89 überein.

Zur Vorgehensweise an sich kann ich noch nichts sagen, soweit bin ich noch nicht gediehen. Setz mich heute noch mal dran, morgen und übermorgen muss ich dann auch endlich mal was für "Planen mit mathematischen Modellen" machen. Bin ich noch gar nicht zu gekommen, schätze ich aber auch leichter ein als den Krempel hier!

Gruß
Robin

@robin "Planen mit mathematischen Modellen" war glaube ich einfacher. Hab ich letztes Semester geschrieben - ich war zwischenzeitlich auch verzweifelt, aber lange nicht so schlimm wie bei diesem Mal.

Ich sitze nun wieder seit 3h über diesem Algorithmus und ich verstehe es einfach nicht.
was passiert in abb. 9.3 zu abb. 9.4? warum hat man den Fluss (xij=1) vom ersten geändert und geht nun einen anderen weg ab?
was ist der unterschied zwischen den zugeordneten und den markierten? wann kann ich markieren, wann zuordnen und überhaupt??
es ist mir ein rätsel...alles ein rätsel

ok
ich habs geschafft sowohl die Beispielsaufgabe als auch die Übungsaufgabe nach zu rechnen 🙇
ich weiß nicht ob es nun reines glück war, oder was los ist. ich versuche es morgen früh gleich nochmal. Blöd, dass so langsam die zeit sehr knapp wird

)
die letzte beiden Tage laufen. Wollte mich soeben nochmal an die Aufgaben machen. und ich glaube mein größtes Problem ist die
"Ford-Fulkerson-Markierung" und die Markierung mit (-,1)
funktioniert das mit der markierung so wie ich oben geschrieben habe? wenn man mehrere zur Auswahl hat, kann man dann frei wählen? Ist das Willkür oder gibt es ein Schema, dass ich noch nicht erkannt habe?

oder muss man immer wenn man die Auswahl hat das größere uj zuerst wählen?
und beim Semiweg darf man zum einen nur xij = 0 mit +1 und xij = 1 mit -1 begehen. aber gibt es hier sonst noch einen trick?

Vanessa,

hier geht es ja um ein Zuordnungs-Problem. Allen Knoten "links" darf immer nur genau ein Knoten "rechts" zugeordnet sein. Dabei müssen für jede Verbindung die reduzierten Kosten null sein.
Zu Abb. 9.3: Die gewählten Verbindungen sind willkürlich gewählt. Möglich wäre z.B. auch: 1->2´, 2->3´, 4->3´ oder 1->4´, 2->1´,4->2´. Damit hätten wir in der Ausgangslösung dann schon jeweils drei Zuordnungen.
Diese Zuordnungen sind im Kurs mit einer Raute gekennzeichnet.

Durch Flussänderungen lösen wir Verbindungen und stellen neue her. Dabei ändern sich eben auch die Rauten. Sie zeigen uns durch ihr Fehlen nur an, welche Knoten noch nicht zugeordnet sind. Bei einer Flussänderung müssen wir von einem freien Knoten "links" zu einem freien Knoten "rechts" gelangen.
Dann besteht eben eine neue Verbindung, was Sinn und Zweck des Ganzen ist. Dabei ändern wir nebenläufig bestehende Verbindungen auf unserem Weg. Gelingt das Vorhaben nicht, muss eben eine Potentialänderung durchgeführt werden.

Für den Weg der Markierungen (mit den Klammern, nicht den Rauten) gelten auch gewisse Regeln. Er findet auch immer auf den fetten Pfeilen (red. Kosten...) statt.
Wir starten immer mit einem - (für einen freien Knoten besteht keine Verbindung, wir wollen ja gerade eine herstellen), darauf muss rechts ein + folgen (der rechte Pfeil ist schon verbunden, sonst hätten wir die beiden ja schon einander zugeordnet).
Für diese neue Verbindung muss die alte des rechten Knoten gekappt werden.
Dieser Schritt ist also vorgegeben und führt zum linken Knoten der alten Verbindung (0/1 auf dem Pfeil), dort eben -.
Dieser linke Knoten ist jetzt wieder frei und kann über einen 0/0 Pfeil beliebig verbunden werden.

In Abb. 9.3 hätte man auch Knoten 4´ mit (1+,1) markieren können, um einen Breakthrough zu erreichen. Ist der rechts erreichte Knoten also frei (ohne Raute), endet die Flussänderung, ansonsten muss wieder umverteilt werden (der Knoten ist nicht frei, es besteht also eine alte Zuordnung, diese muss wieder gelöst werden).

Das setzt sich solange fort, bis eben rechts ein bislang freier Knoten erreicht ist. Damit ist eine neue Zuordnung für den Ausgangs-, wie auch den Endknoten unserer Reise gefunden worden. Dafür wurden andere Zuordnungen geändert, nach rechts geht die Reise immer auf 0/0 Pfeilen, diese sind wählbar. Die Reise nach links ist durch die 0/1 Pfeile vorgegeben.

Zu Abb. 9.5: Ich gehe von 3 nach 2´, von 2´nach 1 und von 1 zu 4´. Ich markiere also nur 4 Knoten und erhalte als abweichende optimale Zuordnung: 1->4, 2->1, 3->2, 4->3. z_min ebenfalls 13.