Die ungarische Methode ist ein Algorithmus, der die Kostenminimierung in einem Optimierungsproblem basierend auf linearer Programmierung ermöglicht.
Das Ziel der ungarischen Methode besteht darin, die minimalen Kosten für eine Reihe von Aufgaben zu ermitteln, die von den am besten geeigneten Personen ausgeführt werden müssen.
Es verwendet lineare Programmierung (PL), um eine Reihe von Schritten auszuführen, die automatisiert werden können. So haben Werkzeuge wie die Statistiksoftware R (unter anderem) mehrere sehr nützliche Pakete für diese Optimierungsprobleme.
Ursprung der ungarischen Methode
Sein Schöpfer war der ungarische Mathematiker (daher der Name) Harold W. Kuhn im Jahr 1955. Ein anderer Mathematiker, James Munkres, überarbeitete ihn 1957. Mit dieser Entwicklung hat er andere Namen wie den Munkres- oder Kuhn-Munkres-Zuordnungsalgorithmus erhalten.
Andererseits hat diese Methode einen Präzedenzfall bei zwei Autoren, Dénes König und Jenő Egerváry, beide Juden und Ungarn. Der erste entwickelte die Graphentheorie, auf der dieser Algorithmus basiert. Der zweite verallgemeinerte Satz von König und erlaubte Kuhn, die Methode zu entwickeln.
Schritte der ungarischen Methode
Die folgenden Schritte ermöglichen die einfache Durchführung der ungarischen Methode mithilfe einer Tabelle. Darüber hinaus wird uns dieses Schema, das wir zeigen, erlauben, den Prozess, den wir im letzten Beispiel im Detail entwickeln werden, auf globale Weise zu sehen.
- Zunächst müssen Sie Personen (Zeilen) einer Reihe von Projekten (Spalten) zuordnen. Darüber hinaus ist es notwendig, die unterschiedlichen Kosten jedes Projekts je nach Ausführung zu berechnen und mit diesen Informationen eine Matrix (C) zu erstellen.
- In der Matrix (C) suchen wir den Minimalwert jeder Zeile. Wir ziehen dies von allen Elementen in der Zeile ab und führen die gleiche Operation mit den Spalten durch. Es erscheint eine neue Matrix (C`) mit den Ergebnissen der vorherigen Operationen.
- Als nächstes erstellen wir den «Gleichheitsgraphen», der es uns ermöglicht, die Aufgaben und Projekte mit den niedrigsten Kosten auszuwählen. Das Optimum wären diejenigen Elemente, deren Ergebnis Null wäre. Wenn es wahr ist, dass kein Element mit einem Nullwert mehr als einer Zeile zugewiesen ist, endet der Algorithmus.
- Andernfalls muss eine neue Zuordnung vorgenommen werden. Es wird eine neue Matrix erstellt, an der eine Reihe von Änderungen vorgenommen werden, wie wir im Beispiel sehen werden. Wir erstellen den Graphen neu und fahren fort, bis wir eine Matrix haben, die mindestens eine Null in jeder Zeile und an sich nicht wiederholenden Positionen hat.
- Mit diesen Informationen haben wir bereits die Personen und Projekte zugewiesen (die Nullen), die das Problem optimieren. Wenn in einer vorherigen Zeile bereits eine Aufgabe zugewiesen ist, wird sie in der nächsten verworfen. Um die minimalen Kosten zu berechnen, addieren wir die Kosten der Anfangsmatrix, die an der Stelle dieser Nullstellen erscheinen.
Beispiel einer ungarischen Methode
Schauen wir uns ein einfaches Beispiel der ungarischen Methode an. Stellen wir uns vor, wir haben drei Arbeiter und sie müssen drei Projekten zugewiesen werden. Wir erstellen die Anfangsmatrix (C) und die Kostenwerte in jeder Zelle. Dazu müssen Sie die im Unternehmen verfügbaren Informationen verwenden. Sobald wir all dies haben, beginnen wir den Prozess. Eine Tabellenkalkulation kann helfen.
Wir berechnen die Minima jeder Zeile und subtrahieren sie von den Elementen dieser Zeile und machen dasselbe mit den Spalten (Schritte 1 und 2). In der resultierenden Matrix (C`) zeichnen wir Linien so, dass sie alle Nullstellen überdecken und sich wiederum schneiden (Schritt 3). Wir sehen, dass es zwei Zeilen gibt, aber der größte Wert der Anzahl der Zeilen oder Spalten ist drei. Wir müssen weitermachen.
Nun wählen wir die kleinste der aufgedeckten Zahlen, in diesem Beispiel sind es zwei (dunkelblau). Wir ziehen es von den vorherigen ab und fügen es zu denen hinzu, die sich dort befinden, wo sich die Linien schneiden. In unserem Fall sind es noch zwei (E3, T1). Wir haben eine neue Matrix (Schritt 4). Wir ziehen die Linien neu und zählen. Es gibt drei Zeilen, die der Anzahl der Zeilen oder Spalten entsprechen. Der Algorithmus ist fertig.
Wir beginnen mit der Zeile oder Spalte mit den wenigsten Nullen (E1, T1). Wenn eine Aufgabe bereits zugewiesen ist, kann sie nicht neu zugewiesen werden, zB bei E2 kann die erste Null von T1 nicht verwendet werden, da diese Aufgabe E1 zugewiesen wurde. Die Gesamtkosten sind bei der ungarischen Methode die Summe der Kosten der ursprünglichen Matrix (Schritt 1), die sich an derselben Position wie die ausgewählten Nullstellen befindet (Schritt 5).