BWL-Lexikon.de
  • Home
  • Grundlagen
    • Aufbau eines Betriebs
    • Definitionen
    • Organisation
    • Personalwirtschaft
    • Planung und Entscheidung
    • Produktionsfaktoren
    • Unternehmensführung
  • BWL
    • Rechtsformen
    • Rechnungswesen
      • Finanzbuchhaltung
      • Kostenarten
      • Jahresabschluss
    • Marketing
    • Logistik
      • Logistik Kennzahlen
      • Beschaffung
      • Lagerverfahren
      • Materialarten
    • Kennzahlen
      • Bilanzkennzahlen
      • Produktivitätskennzahlen
      • Rentabilitätskennzahlen
      • Kennzahlen der GuV
  • VWL
    • Makroökonomie
    • Mikroökonomie
  • Fehler gefunden?

Du bist hier: Startseite » Alle Lektionen » Aufbau eines Betriebs » Planung und Entscheidung » Operations Research » Ungarische Methode

Ungarische Methode

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

Die ungarische Methode wird in der linearen Optimierung angewendet, speziell zur Lösung von gewichteten Zuordnungsproblemen in bipartiten Graphen.

Wir zeigen dir im folgenden Kapitel, was die ungarische Methode ist und wie sie angewendet wird. Außerdem erläutern wir dir, warum die ungarische Methode wichtig ist. Mit unseren Übungsaufgaben kannst du zum Abschluss deinen Wissensstand überprüfen.

Synonym: Kuhn-Munkres-Algorithmus

Inhalt dieser Lektion

  • Warum ist die ungarische Methode wichtig?
  • Was versteht man unter der ungarischen Methode?
    • Beispiel: Anwendung der ungarischen Methode
  • Übungsfragen

Warum ist die ungarische Methode wichtig?

Mit der ungarischen Methode können lineare Optimierungsprobleme gelöst werden, die bei gewichteten Zuordnungen in bipartiten Graphen entstehen. Mit ihr kann die eindeutige Zuordnung von Objekten aus zwei Gruppen so optimiert werden, dass die Gesamtkosten minimiert werden bzw. der Gesamtgewinn maximiert werden kann. Dies kann in unterschiedlichsten Fällen der betrieblichen Praxis der Fall sein, beispielsweise bei der Abstimmung von Dienst- und Urlaubsplänen oder auch in der Logistikplanung.

Was versteht man unter der ungarischen Methode?

Die ungarische Methode ist ein Algorithmus zur Lösung linearer Optimierungsprobleme. Um dies zu erreichen, wird zuerst die Ausgangsmatrix reduziert. Dabei werden sowohl die Spaltenelemente um das Spaltenminimum als auch die Zeilenelemente um das Zeilenminimum reduziert.

Anschließend erfolgt die Zuordnung. Dafür wird zuerst eine Zelle mit dem Eintrag „0“ gesucht, die in keiner weiteren Zeile oder Spalte eine Null aufweist. Auch bei den weiteren Zuordnungen muss beachtet werden, dass jede Zeile und jede Spalte immer genau eine eindeutige Zuordnung ergibt. Die optimale Lösung ist erreicht, wenn genau n Zuordnungen gefunden sind.

Beispiel: Anwendung der ungarischen Methode

Beispiel
In der „Bäckerei Backfrisch“ gibt es insgesamt vier Angestellte. Um den Kunden eine optimale Versorgung mit frischen Brötchen zu bieten, hat die Bäckerei auch sonntags geöffnet.

Dazu muss immer jeweils ein Kollege am Sonntag arbeiten, wobei sich innerhalb eines Monats alle abwechseln. Zu Beginn des Monats wird der Dienstplan erstellt, bei dem jeder seine Präferenzen angeben kann, an welchem Sonntag er arbeiten möchte.

Diese werden in folgender Matrix eingetragen:

Ungarische Methode - Beispiel: Gegebene Matrix
Ungarische Methode – Beispiel: Gegebene Matrix

Eine 1 steht dabei für die höchste Präferenz, eine 4 für die niedrigste Präferenz.

Anschließend wird mit der Reduktion der Spaltenelemente um das Spaltenminimum begonnen. Das bedeutet: Alle Einträge in den Spalten werden um das Minimum reduziert. Da 1 in jeder Spalte das Minimum darstellt, wird von allen Einträgen 1 subtrahiert.

So erhalten wir folgende Matrix:

Ungarische Methode - Beispiel: Reduktion um das Spaltenminimum
Ungarische Methode – Beispiel: Reduktion um das Spaltenminimum

Anschließend werden analog dem vorherigen Vorgehen die Zeilenelemente um das jeweilige Zeilenminimum reduziert.

So ergeben sich folgende Einträge in der Matrix:

Ungarische Methode - Beispiel: Reduktion um das Zeilenminimum
Ungarische Methode – Beispiel: Reduktion um das Zeilenminimum

Sind sowohl Spalten- als auch Zeilenelemente entsprechend reduziert, erfolgt die Zuordnung. Dafür wird zuerst nach einer Zeile oder Spalte gesucht, in der nur eine null enthalten ist. In unserem Beispiel sehen wir, dass die Spalte „Kollege Schmidt“ nur eine Null enthält.

Diese können wir uns markieren:

Ungarische Methode - Beispiel: Auswahl - Schritt 1
Ungarische Methode – Beispiel: Auswahl – Schritt 1

Da in jeder Zeile und spalte für die Anwendung der ungarischen Methode immer nur eine null enthalten sein darf, können wir die zweite null in der Zeile „1. Sonntag“ streichen:

Ungarische Methode - Beispiel: Auswahl - Schritt 2
Ungarische Methode – Beispiel: Auswahl – Schritt 2

Dadurch bleibt in der Spalte „Kollege Meier“ nur ein Eintrag mit null übrig. Dieses Vorgehen wiederholen wir analog bei den weiteren Zeilen und Spalten.

So erhalten wir:

Ungarische Methode - Beispiel: Finale Matrix
Ungarische Methode – Beispiel: Finale Matrix

Anhand der markierten Einträge können wir nun erkennen, an welchem Tag wer arbeiten muss, damit die persönlichen Präferenzen bestmöglich erfüllt werden:

Ungarische Methode - Beispiel: Übersicht der Auswahl
Ungarische Methode – Beispiel: Übersicht der Auswahl

Die bestmögliche Arbeitsaufteilung unter Berücksichtigung der persönlichen Präferenzen der Angestellten ist nun dank der ungarischen Methode gefunden. Mit dieser Lösung können sich alle arrangieren und die Kunden erhalten jeden Sonntag 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:

Fertig

Ergebnis

Könnte dich auch interessieren:

Delphi Methode: Einsatzbereiche

Delphi Methode

Als Delphi-Methode wird ein Verfahren zur Abschätzung zukünftiger Entwicklungen bezeichnet, bei dem in einem mehrstufigen Verfahren Experten auf dem jeweiligen … weiterlesen >>

Graphentheorie

Graphentheorie

Die Graphentheorie als mathematische Methode befasst sich mit der Untersuchung von Graphen als Darstellung von einer Vielzahl von Problemen. Insbesondere … weiterlesen >>

Gerichtete Graphen - Beispiel

Gerichtete / ungerichtete Graphen

Gerichtete und ungerichtete Graphen sind Elemente der Graphentheorie, einer mathematischen Methode zur Lösung einer Vielzahl von algorithmischen Problemen. Der Unterschied … weiterlesen >>

Hamiltonkreis

Hamiltonkreis

Wird jeder Knoten in einem Graphen durch einen geschlossenen Pfad durchlaufen und sind Anfangs- und Endpunkt identisch, so spricht man … weiterlesen >>

Vollständig bipartiter Graph

Bipartiter Graph

Ein Graph wird dann als bipartit bezeichnet, wenn die enthaltenen Knoten in zwei Teilmengen aufteilbar sind, deren Knoten untereinander keine … weiterlesen >>

Nichts passendes dabei?

Erkunde andere Fachbereiche oder benutze die Suchfunktion. Falls Du keine Antwort auf Deine Frage findest, schick uns gerne eine Nachricht, wir versuchen dann passenden Content für Dich zu schaffen.

Zur Übersicht
Oder lieber die Suche benutzen?
  • Eselsbrücke
  • |
  • Buchungssatz
  • |
  • Formeln
  • |
  • Beispiele
  • |
  • Grafiken
  • |
  • Definition
  • |
  • Übungsfragen
  • © BWL-Lexikon.de
  • Datenschutz
  • Impressum
  • Cookie Einstellungen
Fehler gefunden?

Danke, dass du dir die Zeit nimmst, uns dein Feedback zu geben. Bitte beschreibe so genau wie möglich wo du einen Fehler gefunden hast.