Ungarischer Algorithmus oder wie Mathematik bei der Zuweisung von Aufgaben hilft

Hallo Freunde! In diesem Artikel möchte ich über einen interessanten Algorithmus aus der Disziplin „Operational Research“ sprechen, nämlich über die ungarische Methode und wie man mit ihrer Hilfe Zuordnungsprobleme löst. Ich werde auf die Theorie eingehen, in welchen Fällen und für welche Aufgaben dieser Algorithmus anwendbar ist. Ich werde sie anhand meines erfundenen Beispiels Schritt für Schritt analysieren und meine bescheidenen Umrisse des Codes für seine Implementierung in der Sprache R teilen.

Ein paar Worte zur Methode

Um nicht viel Theorie mit mathematischen Begriffen und Definitionen zu malen, schlage ich vor, einige Optionen für die Konstruktion des Zuordnungsproblems in Betracht zu ziehen, und ich denke, Sie werden sofort verstehen, in welchen Fällen wir die ungarische Methode anwenden werden:

• Die Aufgabe, Mitarbeiter für Positionen zu ernennen. Es ist notwendig, die Arbeitnehmer auf Positionen zu verteilen, damit maximale Effizienz erreicht wird oder die Arbeitskosten minimal sind.
• Zuordnung von Maschinen zu Produktionsabschnitten. Die Verteilung der Maschinen, damit während ihres Betriebs die Produktion so rentabel wie möglich ist oder die Kosten für deren Wartung minimal sind.
• Die Auswahl der Kandidaten für verschiedene Stellen wird geschätzt. Wir werden dieses Beispiel unten analysieren.

Wie Sie sehen, gibt es viele Optionen, für die die ungarische Methode anwendbar ist, und ähnliche Aufgaben ergeben sich in vielen Tätigkeitsbereichen.

Infolgedessen sollte die Aufgabe so gelöst werden, dass ein Ausführender (Person, Maschine, Werkzeug, ...) nur eine Arbeit ausführen kann und jede Arbeit nur von einem Ausführenden ausgeführt wird.

Eine notwendige und ausreichende Bedingung zur Lösung eines Problems ist sein geschlossener Typ. Das heißt, wenn die Anzahl der Interpreten = die Anzahl der Werke (N = M). Wenn diese Bedingung nicht erfüllt ist, können Sie fiktive Darsteller oder fiktive Arbeiten hinzufügen, für die die Werte in der Matrix Null sind. Dies hat keinen Einfluss auf die Lösung des Problems, sondern gibt ihm nur den erforderlichen geschlossenen Typ.

Schritt-für-Schritt-Algorithmus anhand eines Beispiels

Problemstellung: Lassen Sie eine wichtige wissenschaftliche Konferenz planen. Um dies durchzuführen, müssen Sie Ton, Licht und Bilder einrichten, Gäste registrieren und sich auf Pausen zwischen den Vorstellungen vorbereiten. Es gibt 5 Organisatoren für diese Aufgabe. Jeder von ihnen hat bestimmte Schätzungen der Leistung einer bestimmten Arbeit (angenommen, diese Schätzungen werden als arithmetischer Durchschnitt der Bewertungen seiner Mitarbeiter festgelegt). Es ist notwendig, die Organisatoren so zu verteilen, dass ihre Gesamtpunktzahl maximal ist. Die Aufgabe hat folgende Form:


Wenn das Problem maximal gelöst ist (wie in unserem Fall), muss in jeder Zeile der Matrix das maximale Element gefunden, von jedem Element der entsprechenden Zeile subtrahiert und die gesamte Matrix mit -1 multipliziert werden. Wenn das Problem auf ein Minimum gelöst ist, muss dieser Schritt übersprungen werden.


In jeder Zeile und in jeder Spalte sollte nur eine ausgewählte Null vorhanden sein. (d. h. wenn Null gewählt wurde, werden die verbleibenden Nullen in dieser Zeile oder in dieser Spalte nicht mehr berücksichtigt). In diesem Fall ist dies nicht möglich:


( Wenn das Problem auf ein Minimum gelöst ist, müssen Sie mit diesem Schritt beginnen ). Wir setzen die Lösung weiter fort. Matrixreduktion um Zeilen (suchen Sie nach dem minimalen Element in jeder Zeile und subtrahieren Sie es von jedem Element):


Weil Da alle minimalen Elemente Null sind, hat sich die Matrix nicht geändert. Wir führen die Reduzierung der Spalten durch:


Wieder sehen wir so aus, dass in jeder Spalte und in jeder Zeile nur eine ausgewählte Null vorhanden ist. Wie unten zu sehen ist, ist dies in diesem Fall unmöglich. Ich habe zwei Optionen für die Auswahl von Nullen vorgestellt, aber keine davon ergab das gewünschte Ergebnis:


Wir setzen die Entscheidung weiter fort. Kreuzen Sie Zeilen und Spalten an, die keine Elemente enthalten ( WICHTIG! Die Anzahl der Kreuzungen sollte minimal sein ). Unter den verbleibenden Elementen suchen wir nach dem Minimum, subtrahieren es von den verbleibenden Elementen (die nicht durchgestrichen sind) und addieren es zu den Elementen, die sich am Schnittpunkt der durchgestrichenen Zeilen und Spalten befinden (was grün markiert ist, wird dort subtrahiert; was golden markiert ist, wird dort zusammengefasst; was nicht übermalt ist - nicht anfassen):


Wie Sie jetzt sehen können, gibt es in jeder Spalte und Zeile nur eine ausgewählte Null. Wir vervollständigen die Lösung des Problems!


Ersetzen Sie in der Anfangstabelle die Position der ausgewählten Nullen. Auf diese Weise erhalten wir den optimalen oder optimalen Plan, in dem die Organisatoren auf die Arbeit verteilt sind und sich die Summe der Schätzungen als maximal herausstellt:


Wenn Sie das Problem lösen und es immer noch unmöglich ist, Nullen so zu wählen, dass in jeder Spalte und Zeile nur eine vorhanden ist, wiederholen wir den Algorithmus an der Stelle, an der die Reduzierung um Zeilen durchgeführt wurde (das minimale Element in jeder Zeile).

Implementierung der Programmiersprache R.

Der ungarische Algorithmus wird mithilfe von Rekursionen implementiert. Ich hoffe, dass mein Code keine Schwierigkeiten verursacht. Zuerst müssen Sie drei Funktionen kompilieren und dann die Berechnungen starten.

Die Daten zur Lösung des Problems stammen aus der Datei example.csv mit der folgenden Form:



Das Ergebnis des Programms:

Abschließend

Vielen Dank, dass Sie sich die Zeit genommen haben, meinen Artikel zu lesen. Ich werde alle unten verwendeten Links bereitstellen. Ich hoffe, Sie haben etwas Neues für sich gelernt oder Ihr altes Wissen aktualisiert. Alles Erfolg, viel Glück!

Verwendete Ressourcen

1. Gestürmte Wikipedia
2. Und andere gute Seiten
3. Betont für mich einige Informationen aus diesem Artikel.