Übungsaufgabe b8520901 Ungarische Methode

Übungsaufgabe b8520901 (Ungarische Methode)

Hallo Zusammen,

sitze hier gerade vor einem etwas größerem Problem. Nachdem ich mir eingebildet habe, die Ungarische Methode verstanden zu haben, versuchte ich mich an folgender Aufgabe:
https://www.fernuni-hagen.de/BWLOR/assets/uebung/b8520901.pdf
Nun ist da ja die Lösung mit dabei, allerdings stellt sich für mich die Frage, wie die Lösung aussieht wenn ich den ersten Durchbruch nicht in Spalte 3' sondern in Spalte 4' ansetze. Sollte doch prinzipiell möglich sein, im Skript steht ja nichts dazu irgendeine Reihenfolge einzuhalten. Mach ich dies nämlich wie gerade beschrieben, also zuerst 4 statt 3, dann fahre ich mich in den weiteren Schritten irgendwie fest und komme nicht mehr weiter, und das sollte denke ich eigentlich nicht der Fall sein, oder?

Vielen Dank für Eure Hilfe.

MfG Pat

Also, bei Schritt 3:M1 der Ungarischen Methode (852 KE 2 S.96) ist zwar keine exakte Reihenfolge für die Auswahl der neuen unabhängigen Null vorgeschrieben, es empfiehlt sich aber spaltenweise von links nach rechts zu suchen. So ist das bei Schritt 2 z.B. explizit vorgegeben.

Allerdings sollte auch bei einer anderen Reihenfolge das Ergebnis stimmen!
Das Tableau sieht bei abweichender unabhängiger Null (grün statt rot) wie folgt aus:
[
>0 . 00 . 01 . 33 . 17 | 42
95 . >0 . 83 . 08 . 79 | 89
40 . 00 . 96 . 11 . 43 | 75
20 . 00 . 24 . 13 . 39 | 22
00 . 08 . 00 . >0 . 00 | 00
---------------------------
00 . 08 . 00 . 00 . 00 |


Die Markierungen erfolgen analog der Musterlösung:
M1: Zunächst Zeilen 3 (-) versehen und Spalte 2 mit (3). Dann Zeile 4 (-).
M2: Zeile 2 erhält die Marke (2').

[
>0 . 00 . 01 . 33 . 17 | 42
95 . >0 . 83 . 08 . 79 | 89 (2')
40 . 00 . 96 . 11 . 43 | 75 (-)
20 . 00 . 24 . 13 . 39 | 22 (-)
00 . 08 . 00 . >0 . 00 | 00
---------------------------
00 . 08 . 00 . 00 . 00 |
. . (3)


Es folgt Schritt 5 mit η = 8
[
>0 . 08 . 01 . 33 . 17 | 42
87 . >0 . 75 . 00 . 71 | 97
32 . 00 . 88 . 03 . 35 | 83
12 . 00 . 16 . 05 . 31 | 30
00 . 16 . 00 . >0 . 00 | 00
---------------------------
00 . 16 . 00 . 00 . 00 |


Und wieder Schritt 3 die Markierung...
M1: Zeile 3 (-) und Spalte 2 (3); Zeile 4 (-)
M2: über Spalte 2 bekommt Zeile 2 (2')
M1: über Zeile 2 bekommt Spalte 4 (2)
M2: über Spalte 4 bekommt Zeile 5 (4')
M1: Spalte 1 (5); Spalte 3 (5) DURCHBRUCH -> Schritt 4 !!
[
>0 . 08 . 01 . 33 . 17 | 42
87 . >0 . 75 . 00 . 71 | 97 (2')
32 . 00 . 88 . 03 . 35 | 83 (-)
12 . 00 . 16 . 05 . 31 | 30 (-)
00 . 16 . 00 . >0 . 00 | 00 (4')
---------------------------
00 . 16 . 00 . 00 . 00 |
(5) .(3) .(5) .(2)


Im nächsten Tableau sind die alten UN mit > gekennzeichnet und die neuen mit #. Schritt 4 bereitet auch häufig Probleme. Deswegen hier noch mal der Pfad in Matrix-Schreibweise, wobei das + anzeigt, dass das Element in die Menge der UN aufgenommen wurde und das -, dass es entfernt wurde:
53+ -> 54- -> 24+ -> 22- -> 32+
Anzumerken ist noch, dass Element 11 sowohl vor Schritt 4 als auch danach eine unabhängige Null ist.
[
>0 . 08 . 01 . 33 . 17 | 42
87 . >0 . 75 . #0 . 71 | 97 (2')
32 . #0 . 88 . 03 . 35 | 83 (-)
12 . 00 . 16 . 05 . 31 | 30 (-)
00 . 16 . #0 . >0 . 00 | 00 (4')
---------------------------
00 . 16 . 00 . 00 . 00 |
(5) .(3) .(5) .(2)


Das Tableau ist somit identisch mit dem ersten auf Seite 4 der Musterlösung. Wie du siehst, ist die Auswahlreihenfolge irrelevant.

Vielen Dank für die ausführliche Erklärung, habe meinen Denkfehler nun gefunden

vielleicht kann jemand helfen:
warum wird denn bei dieser Aufgabe die u_i nicht neu berechnet? Das u_j hingegen schon. Man kann die Lösung am Ende ablesen - dort wo die UN (unabhängige 0) sind, kann man in der Ausgangsmatrix alles ablesen. Dass das u_i nicht geändert wird, macht logisch Sinn, denn es sind die mimimalsten Zeiten, die die Schwimmer schwimmen können - dennoch: müssten diese nicht auch angepasst werden wie im Algorithmus unter Schritt 5 erklärt?!

Vanessa,

ich verstehe deine Frage nicht so ganz.


Du hast natürlich Recht, die Zeiten der Schwimmer bleiben bestehen. Sie werden nur in Bewertungszahlen transformiert, welche sich dann im Laufe des Verfahrens ändern.
Und das tun sie doch auch alle bis auf u_5.

Worauf genau bezieht sich jetzt deine Frage? Oder hast du vor lauter Bäumen den Graphen nicht gesehen oder wie das nochmal hieß 😉?

Wir sollten vielleicht alle mal einen Ruhetag einlegen, bevor es in den Endspurt geht? 🙄

Liebe Grüße

robin,
ich hatte ein paar Tage pause 😉 zum einem war/bin ich krank und zum andern noch ne andere Klausur gestern geschrieben.
aber du hast recht. ich hab den Graphen nicht gesehen 😕 es wird angepasst...
sorry 😱ops