Branch&Bound bei Rundreise für Dummies

Ok anhand des Übungsbeispiels 2.6

Die Anwendung der ungarischen Methode ist Dir klar, oder? In der Ergebnismatrix bekommst Du 6 Unhabhängigen Nullen.


wenn Du Dir die Kostenmatrix mit den Unabh. Nullen ansiehst...

Zeile 1 Spalte 3 ist markiert - es führt also ein Weg von 1 nach 3 dann sieh mal nach wie es weitergeht - Zeile 3 - da ist die Unabh. Null in Spalte 1. Ein Zyklus 1-3-1. Da ich aber 6 Orte habe, ist das keine Rundreise.

der nächste Zyklus ist: 2-4-5-6-2

Der Zielfunktionswert berechnet sich einfach aufgrund der zwei Zyklen aus dem ursprünglichen Tableau Z= 11

Der kürzere Zyklus wird aufgebrochen. Du setzt also 1-3 und 3-1 auf unendlich.

Hier wird ein Strich an den Stellen eingefügt.

Jetzt ermittelst Du die Schranken.

Für den Teilzyklus 1,3 suchst Du Dir das Minimum der 1. Zeile (7,5,3,3) - also 3 und das Minimum der 3 Spalte (2,1,4,0) = 0 die beiden Werte werden addiert 3+0=3

Das gleiche Spiel für Teilzyklus 3,1. Hier kommt der Wert 0 raus.

Den Teilzyklus mit dem kleineren Wert behandelst Du weiter - hier also 3,1. Der Strich wird eingefügt und die ungarische Methode wird ein weiteres Mal angewandt. Die unabhängigen Nullen werden bestimmt und nun prüfst Du, ob Du jetzt eine Rundreise hast, wenn ja dann bestimmst Du noch den Zielfunktionswert. Hier ist der dann 13. Eine Verschlechterung um 2 (die 3 ist meiner Ansicht nach ein Druckfehler) Weniger als die Schranke von Teilzyklus 1 und damit optimal.

Ahja! Habs & Danke!
Kann es folglich sein, dass auf S.41 in der ersten Matrix Zeile 3 Spalte 2 um (mal wieder!!) einen Druckfehler handelt? Da sollte doch eine zwei stehen (bzw. in der zweiten Matrix eine 1)?!

Desweitern finde ich es ein wenig irritierend, dass sie sagen sie reduzieren (S.41) nach der ungarischen Methode Spalte 1 und Zeile 3 um 1. Was ist denn daran ungarische Methode?? Sie reduzieren doch nur! Klar in der U.M. muss man auch reduzieren, aber nur weil ich irgendwo eine Zeile mal reduzieren kann man doch nicht sagen "nach der Ungarischen Methode"?!?!


Wo wir gerade dabei sind, würde ich gerne die Schritte der Ungarischen Methode aufführen, um mögl Fehler aufzudecken. Denn irgendwie ist bei mir immer eine Zeile/Spalte ,oder Teile davon ,um 1 zu hoch/niedrig:
1.Schauen ob Spalten = Zeilen
2. kleinste Zahl spaltenweise subtrahieren
3. kleinste Zahl x>0 zeilenweise subtrahieren. Wenn x=0 mach ich nichts
4. geringstmgl. Anzahl an Decklinien legen, sodass alle 0 durch mind. eine Linie bedeckt sind. (ist bei mir fast immer Zeilen/Spaltenanzahl😡)
5. Wenn der, bei mir seltene ,Fall eintritt, dass Decklinien ungleich Spaltenanzahl: niedrigster Wert aus den nichtbedeckten Feldern von den anderen n.bed.Feldern abziehen. Dieser Wert wird im Gegenzug zu den mehrfachbedeckten Feldern addiert. Einfachbedeckte Felder bleiben unberücksichtigt.
6. Und zum Schluß Kennzeichne ich eine 0 die in einer Spalte oder Zeile alleine steht und kürze in der Zeile oder Spalte die übrigen 0en. Dann 0* in der Originalmatrix ablesen und addieren.

Wo ist der Fehler??

Spontan fällt mir ein, dass im Skript immer mit der Reduktion der Zeilen begonnen wird, dann erst die Spalten.

handschuhfach schrieb:

Ahja! Habs & Danke!
Kann es folglich sein, dass auf S.41 in der ersten Matrix Zeile 3 Spalte 2 um (mal wieder!!) einen Druckfehler handelt? Da sollte doch eine zwei stehen (bzw. in der zweiten Matrix eine 1)?!

Zum Vergrößern anklicken....

Also bei mir steht in der ersten Matrix in der Zeile 3, Spalte 2 eine 2. In der 2. Matrix steht an der Stelle ein -, weil c31=unendlich gesetzt ist. Oder was meinst Du?😕

handschuhfach schrieb:

Desweitern finde ich es ein wenig irritierend, dass sie sagen sie reduzieren (S.41) nach der ungarischen Methode Spalte 1 und Zeile 3 um 1. Was ist denn daran ungarische Methode?? Sie reduzieren doch nur! Klar in der U.M. muss man auch reduzieren, aber nur weil ich irgendwo eine Zeile mal reduzieren kann man doch nicht sagen "nach der Ungarischen Methode"?!?!

Zum Vergrößern anklicken....

Die Reduktion ist Schritt 1 der ungarischen Methode (852 KE 2, S75). Und hier berechnet man ja auch die reduzierte Matrix.

handschuhfach schrieb:

Wo wir gerade dabei sind, würde ich gerne die Schritte der Ungarischen Methode aufführen, um mögl Fehler aufzudecken. Denn irgendwie ist bei mir immer eine Zeile/Spalte ,oder Teile davon ,um 1 zu hoch/niedrig:
1.Schauen ob Spalten = Zeilen
2. kleinste Zahl spaltenweise subtrahieren
3. kleinste Zahl x>0 zeilenweise subtrahieren. Wenn x=0 mach ich nichts
4. geringstmgl. Anzahl an Decklinien legen, sodass alle 0 durch mind. eine Linie bedeckt sind. (ist bei mir fast immer Zeilen/Spaltenanzahl😡)

Zum Vergrößern anklicken....

Abgedeckt sind durch die Markierungen eigentlich primaer die unabhaengigen Nullen. Wenn Du alles abdecken kannst, muesste Du genau n unabhaengige Nullen haben. Wie markierst Du denn?

handschuhfach schrieb:

5. Wenn der, bei mir seltene ,Fall eintritt, dass Decklinien ungleich Spaltenanzahl: niedrigster Wert aus den nichtbedeckten Feldern von den anderen n.bed.Feldern abziehen. Dieser Wert wird im Gegenzug zu den mehrfachbedeckten Feldern addiert. Einfachbedeckte Felder bleiben unberücksichtigt.

Zum Vergrößern anklicken....

Ausserdem wird eta zu den Knotenpotentiale der markierten Zeilen und Spalten addiert.

handschuhfach schrieb:

6. Und zum Schluß Kennzeichne ich eine 0 die in einer Spalte oder Zeile alleine steht und kürze in der Zeile oder Spalte die übrigen 0en. Dann 0* in der Originalmatrix ablesen und addieren.

Wo ist der Fehler??

Zum Vergrößern anklicken....

Ich vermute, Dein Fehler liegt irgendwo bei der Markierung. Die Zeile ohne unabhaengige Null wird mit (--) markiert (auf Seite 77 in Tab 8.5 wurde danach zunaechst die Zeile 3 mit (--) markiert). Dann schaut man in welcher Spalte eine 0 steht, die nicht zu UN gehoert und markiert sie (im Beispiel ist das die erste Spalte, die wird demnach mit (3) markiert). Wenn in dieser Spalte wieder eine 0 aus UN steht, markiert man die entsprechende Zeile(hier ist eine unabhaengige Null in Zeile 2. Deshalb wird diese Zeile mit (1') markiert). Steht in dieser Zeile eine 0, die nicht zu UN gehoert, wird die entsprechende Spalte markiert (was hier nicht mehr der Fall ist), usw.

Gruss,
Ulrike

Zeilenweise? Komisch in drei verschiedenen Lehrbüchern wird zuerst spaltenweise reduziert. (lerne zum Teil aus anderen Büchern, weil ich das Skript teilweise sehr unverständlich finde). Aber gut, wenn der Prof Rödder zeilenweise will, mach ich das. Markieren tu ich nach dem Prinzip wenn eine 0 in einer Spalte oder Zeile als Einzige steht bekommt sie eine Markierung. So hab ichs bisher gemacht. Muss mir jetzt mal in Ruhe Deine Vorgehensweise anschauen. Schon mal danke fürs bisherige Feedback!

handschuhfach schrieb:

Zeilenweise? Komisch in drei verschiedenen Lehrbüchern wird zuerst spaltenweise reduziert. (lerne zum Teil aus anderen Büchern, weil ich das Skript teilweise sehr unverständlich finde). Aber gut, wenn der Prof Rödder zeilenweise will, mach ich das. Markieren tu ich nach dem Prinzip wenn eine 0 in einer Spalte oder Zeile als Einzige steht bekommt sie eine Markierung. So hab ichs bisher gemacht. Muss mir jetzt mal in Ruhe Deine Vorgehensweise anschauen. Schon mal danke fürs bisherige Feedback!

Zum Vergrößern anklicken....

Ob man erst spaltenweise und dann zeilenweise oder andersherum reduziert sollte doch eigentlich aufs selbe raus kommen.