Aufgabe:
die ungarische Methode dachte ich eigentlich verstanden zu haben. Die Zeilen- und Spaltenreduktion erscheinen mir auf den ersten Blick relativ simpel. Nun habe ich folgende Aufgabe, bei der ich mich ein wenig schwer tue.
Folgende Matrix ist gegeben:
b | 1 | 2 | 5 | a |
3 | 2 | a | c | 2 |
4 | 5 | 9 | 9 | 2 |
5 | b | 2 | 2 | a |
b | c | 1 | b | 5 |
Die Zeilenreduktion kann ich ja eigentlich nicht durchführen, solange ich nicht weiß, was a, b und c sind.
Daher wird die Zeilenreduktion in der Aufgabe auch vorgegeben:
b-1 | 0 | 1 | 4 | a-1 |
2 | 0 | a-2 | c-2 | 0 |
2 | 3 | c | 7 | 0 |
3 | a | 0 | 0 | a-2 |
b-1 | b | 0 | b-1 | a |
Die Frage lautet:
Bestimmen Sie die optimale Zuordnung mit Hilfe der ungarischen Methode. Wie lautet der Zielfunktionswert der
optimalen Zuordnung? Welche Werte haben a, b und c?
Problem/Ansatz:
Diese Zeilenreduktion kann ich leider nicht nachvollziehen. Wieso wird in Zeile 3, Spalte 3 aus der 9 eine c? Ich kann mir dies nur erklären, dass es in dieser Aufgabe einfach vorgegeben ist, und man von alleine nicht drauf kommen würde. Das würde einiges erklären.
Ich entnehme der Matrix nach Zeilenreduktion sofort, dass c = 7 sein muss. Denn nach der Zeilenreduktion müsste in der Zeile 2 die Zahl 2 subtrahiert werden. Vorher stand dort eine 9, jetzt müsste da eine 7 stehen. Da aber c steht, ergibt dies c = 7.
Durch die letzte Zeile erhalte ich a = 4, da dort vorher eine 5 stand und nun die 1 das kleinste Element ist.
Das b in Zeile 5 Spalte 2 gibt an, dass b = c-1 sein muss, da vorher eine c stand. Also erhalte ich b = 6.
Es ergibt sich nun folgende Matrix:
5 | 0 | 1 | 4 | 3 |
2 | 0 | 2 | 5 | 0 |
2 | 3 | 7 | 7 | 0 |
3 | 4 | 0 | 0 | 2 |
5 | 6 | 0 | 5 | 4 |
Hieraus müsste noch die Spaltenreduktion durchgeführt werden:
Dann ergibt sich:
3 | 0 | 1 | 4 | 3 |
0 | 0 | 2 | 5 | 0 |
0 | 3 | 7 | 7 | 0 |
1 | 4 | 0 | 0 | 2 |
3 | 6 | 0 | 5 | 4 |
Ich wähle nun die 0 aus Zeile 5. Nun muss ich es ja die 0en so markieren, dass immer nur eine 0 pro Spalte und Zeile markiert sind. Hier habe ich ja nun mehrere Möglichkeiten.
Beispielsweise könnte ich es so wählen, um die optimale Lösung zu erhalten:
Zeile 5, Spalte 3
Zeile 4, Spalte 4
Zeile 3, Spalte 1
Zeile 2, Spalte 5
Zeile 1, Spalte 2
Damit hätte ich genau eine 0 pro Zeile/Spalte markiert.
Weiter weiß ich dann alleridngs nicht mehr, ich habe auch das Gefühl, dass ich etwas falsch mache.