Ungarische Methode

Enthält: Beispiele · Definition · Grafiken · Übungsfragen

Die ungarische Meth­ode wird in der lin­earen Opti­mierung angewen­det, speziell zur Lösung von gewichteten Zuord­nung­sprob­le­men in bipar­titen Graphen.

Wir zeigen dir im fol­gen­den Kapi­tel, was die ungarische Meth­ode ist und wie sie angewen­det wird. Außer­dem erläutern wir dir, warum die ungarische Meth­ode wichtig ist. Mit unseren Übungsauf­gaben kannst du zum Abschluss deinen Wis­sens­stand über­prüfen.

Syn­onym: Kuhn-Munkres-Algo­rith­mus

Warum ist die ungarische Methode wichtig?

Mit der ungarischen Meth­ode kön­nen lin­eare Opti­mierung­sprob­leme gelöst wer­den, die bei gewichteten Zuord­nun­gen in bipar­titen Graphen entste­hen. Mit ihr kann die ein­deutige Zuord­nung von Objek­ten aus zwei Grup­pen so opti­miert wer­den, dass die Gesamtkosten min­imiert wer­den bzw. der Gesamt­gewinn max­imiert wer­den kann. Dies kann in unter­schiedlich­sten Fällen der betrieblichen Prax­is der Fall sein, beispiel­sweise bei der Abstim­mung von Dienst- und Urlaub­splä­nen oder auch in der Logis­tik­pla­nung.

Was versteht man unter der ungarischen Methode?

Die ungarische Meth­ode ist ein Algo­rith­mus zur Lösung lin­ear­er Opti­mierung­sprob­leme. Um dies zu erre­ichen, wird zuerst die Aus­gangs­ma­trix reduziert. Dabei wer­den sowohl die Spal­tenele­mente um das Spal­ten­min­i­mum als auch die Zeilenele­mente um das Zeilen­min­i­mum reduziert.

Anschließend erfol­gt die Zuord­nung. Dafür wird zuerst eine Zelle mit dem Ein­trag “0” gesucht, die in kein­er weit­eren Zeile oder Spalte eine Null aufweist. Auch bei den weit­eren Zuord­nun­gen muss beachtet wer­den, dass jede Zeile und jede Spalte immer genau eine ein­deutige Zuord­nung ergibt. Die opti­male Lösung ist erre­icht, wenn genau n Zuord­nun­gen gefun­den sind.

Beispiel: Anwendung der ungarischen Methode

Beispiel
In der “Bäck­erei Back­frisch” gibt es ins­ge­samt vier Angestellte. Um den Kun­den eine opti­male Ver­sorgung mit frischen Brötchen zu bieten, hat die Bäck­erei auch son­ntags geöffnet.

Dazu muss immer jew­eils ein Kol­lege am Son­ntag arbeit­en, wobei sich inner­halb eines Monats alle abwech­seln. Zu Beginn des Monats wird der Dien­st­plan erstellt, bei dem jed­er seine Präferen­zen angeben kann, an welchem Son­ntag er arbeit­en möchte.

Diese wer­den in fol­gen­der Matrix einge­tra­gen:

Ungarische Methode - Beispiel: Gegebene Matrix
Ungarische Meth­ode — Beispiel: Gegebene Matrix

Eine 1 ste­ht dabei für die höch­ste Präferenz, eine 4 für die niedrig­ste Präferenz.

Anschließend wird mit der Reduk­tion der Spal­tenele­mente um das Spal­ten­min­i­mum begonnen. Das bedeutet: Alle Ein­träge in den Spal­ten wer­den um das Min­i­mum reduziert. Da 1 in jed­er Spalte das Min­i­mum darstellt, wird von allen Ein­trä­gen 1 sub­trahiert.

So erhal­ten wir fol­gende Matrix:

Ungarische Methode - Beispiel: Reduktion um das Spaltenminimum
Ungarische Meth­ode — Beispiel: Reduk­tion um das Spal­ten­min­i­mum

Anschließend wer­den ana­log dem vorheri­gen Vorge­hen die Zeilenele­mente um das jew­eilige Zeilen­min­i­mum reduziert.

So ergeben sich fol­gende Ein­träge in der Matrix:

Ungarische Methode - Beispiel: Reduktion um das Zeilenminimum
Ungarische Meth­ode — Beispiel: Reduk­tion um das Zeilen­min­i­mum

Sind sowohl Spal­ten- als auch Zeilenele­mente entsprechend reduziert, erfol­gt die Zuord­nung. Dafür wird zuerst nach ein­er Zeile oder Spalte gesucht, in der nur eine null enthal­ten ist. In unserem Beispiel sehen wir, dass die Spalte “Kol­lege Schmidt” nur eine Null enthält.

Diese kön­nen wir uns markieren:

Ungarische Methode - Beispiel: Auswahl - Schritt 1
Ungarische Meth­ode — Beispiel: Auswahl — Schritt 1

Da in jed­er Zeile und spalte für die Anwen­dung der ungarischen Meth­ode immer nur eine null enthal­ten sein darf, kön­nen wir die zweite null in der Zeile “1. Son­ntag” stre­ichen:

Ungarische Methode - Beispiel: Auswahl - Schritt 2
Ungarische Meth­ode — Beispiel: Auswahl — Schritt 2

Dadurch bleibt in der Spalte “Kol­lege Meier” nur ein Ein­trag mit null übrig. Dieses Vorge­hen wieder­holen wir ana­log bei den weit­eren Zeilen und Spal­ten.

So erhal­ten wir:

Ungarische Methode - Beispiel: Finale Matrix
Ungarische Meth­ode — Beispiel: Finale Matrix

Anhand der markierten Ein­träge kön­nen wir nun erken­nen, an welchem Tag wer arbeit­en muss, damit die per­sön­lichen Präferen­zen best­möglich erfüllt wer­den:

Ungarische Methode - Beispiel: Übersicht der Auswahl
Ungarische Meth­ode — Beispiel: Über­sicht der Auswahl

Die best­mögliche Arbeit­saufteilung unter Berück­sich­ti­gung der per­sön­lichen Präferen­zen der Angestell­ten ist nun dank der ungarischen Meth­ode gefun­den. Mit dieser Lösung kön­nen sich alle arrang­ieren und die Kun­den erhal­ten jeden Son­ntag im Monat frische Brötchen.

Übungsfragen

#1. Was versteht man unter der ungarischen Methode?

#2. Wie wird die ungarische Methode angewendet?

#3. “Die ungarische Methode dient der Lösung von Zuordnungsproblemen in nicht bipartiten Graphen.” — diese Aussage ist:

#4. “Mit der ungarischen Methode kann die Zuordnung von Elementen zweier Gruppen in einem Graphen optimiert werden.” — Diese Aussage ist:

#5. “Die optimale Lösung des Zuordnungsproblems ist erreicht, wenn durch die ungarische Methode genau n Zuordnungen gefunden wurden.” — diese Aussage ist:

Fer­tig

Ergebnis

Nichts passendes dabei?

Erkunde andere Fach­bere­iche oder benutze die Such­funk­tion. Falls Du keine Antwort auf Deine Frage find­est, schick uns gerne eine Nachricht, wir ver­suchen dann passenden Con­tent für Dich zu schaf­fen.

Zur Übersicht
Oder lieber die Suche benutzen?