0 Daumen
159 Aufrufe

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:

b125a
32ac2
45992
5b22a
bc1b5

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-1014a-1
20a-2c-20
23c70
3a00a-2
b-1b0b-1a


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:

50143
20250
23770
34002
56054


Hieraus müsste noch die Spaltenreduktion durchgeführt werden:
Dann ergibt sich:

30143
00250
03770
14002
36054


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.

Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community