HONGAARSE METHODE: WAARUIT BESTAAT HET, VOORBEELD - DUDAS - 2026

De Hongaarse methode is een algoritme dat wordt gebruikt bij toewijzingsproblemen wanneer u de kosten wilt minimaliseren. Dat wil zeggen, het wordt gebruikt om de minimale kosten te vinden door meerdere mensen aan verschillende activiteiten toe te wijzen op basis van de laagste kosten. Elke activiteit moet aan een andere persoon worden toegewezen.

Een toewijzingsprobleem is een speciaal type lineair programmeerprobleem, waarbij het doel is om de kosten of tijd van het voltooien van een aantal taken door meerdere mensen te minimaliseren.

Bron: pixabay.com

Een van de belangrijke kenmerken van het toewijzingsprobleem is dat er slechts één taak (of werknemer) aan een machine (of project) wordt toegewezen.

Deze methode is ontwikkeld door de Hongaarse wiskundige D. Konig. Om deze reden staat het bekend als de Hongaarse methode voor toewijzingsproblemen. Het is ook bekend als het toewijzingsalgoritme van Kuhn-Munkres.

Elk toewijzingsprobleem kan eenvoudig worden opgelost door deze methode toe te passen die uit twee fasen bestaat:

- Met de eerste fase worden rijreducties en kolomreducties uitgevoerd.

- In de tweede fase wordt de oplossing iteratief geoptimaliseerd.

Wat is de Hongaarse methode?

De Hongaarse methode bestaat uit vier stappen. De eerste twee stappen worden slechts één keer uitgevoerd, terwijl de stappen 3 en 4 worden herhaald totdat een optimale toewijzing is gevonden.

Een vierkante matrix van de orde n bij n wordt beschouwd als invoergegevens, die alleen niet-negatieve elementen mogen bevatten.

Als voor een bepaald probleem het aantal rijen in de matrix niet gelijk is aan het aantal kolommen, moet een dummy-rij of een dummy-kolom worden toegevoegd, afhankelijk van het geval. De toewijzingskosten voor die dummy-cellen worden altijd als nul toegewezen.

Stap 1: trek de minima van elke rij af

Voor elke rij in de array wordt het element met de laagste waarde geselecteerd en afgetrokken van elk element in die rij.

Stap 2: trek de minima van elke kolom af

Op dezelfde manier wordt het item met de laagste waarde geselecteerd voor elke kolom en afgetrokken van elk item in die kolom.

Stap 3: bedek alle nullen met een minimum aantal regels

Alle nullen in de matrix die voortvloeien uit stap 2, moeten worden bedekt met een minimum aantal horizontale en verticale lijnen, hetzij door rijen of kolommen.

Als in totaal n regels nodig zijn om alle nullen te bedekken, waarbij n gelijk is aan de grootte n maal n van de matrix, zal er een optimale verdeling zijn tussen de nullen en daarom stopt het algoritme.

Ga anders verder met stap 4 als er minder dan n regels nodig zijn om alle nullen in de array te bedekken.

Stap 4: maak extra nullen aan

Het kleinste element van de matrix (k genaamd) dat niet wordt bedekt door een van de lijnen gemaakt in stap 3, wordt geselecteerd.

De waarde van k wordt afgetrokken van alle elementen die niet door lijnen worden bedekt. Vervolgens wordt de waarde van ka opgeteld bij alle elementen die vallen onder het snijpunt van twee lijnen.

Items die onder één regel vallen, blijven ongewijzigd. Nadat u deze stap heeft uitgevoerd, keert u terug naar stap 3.

Optimale toewijzing

Nadat het algoritme in stap 3 is gestopt, wordt een reeks nullen gekozen zodat voor elke rij en elke kolom slechts één nul is geselecteerd.

Als er in dit selectieproces geen enkele nul in een rij of kolom staat, wordt een van die nullen gekozen. De resterende nullen in die kolom of rij worden verwijderd en hetzelfde wordt ook herhaald voor de andere opdrachten.

Als er geen enkele nultoewijzing is, zijn er meerdere oplossingen. De kosten blijven echter hetzelfde voor verschillende sets opdrachten.

Alle toegevoegde rijen of kolommen worden verwijderd. De nullen die in deze definitieve matrix worden gekozen, komen dus overeen met de ideale toewijzing die vereist is in de oorspronkelijke matrix.

Voorbeeld

Laten we eens kijken naar een bedrijf waar vier activiteiten zijn (A1, A2, A3, A4) die moeten worden uitgevoerd door vier werknemers (T1, T2, T3, T4). Per werknemer moet één activiteit worden toegewezen.

De volgende matrix toont de kosten om een ​​bepaalde werknemer aan een bepaalde activiteit toe te wijzen. Het doel is om de totale kosten van de taak die uit deze vier activiteiten bestaat, te minimaliseren.

Stap 1: trek de minima van elke rij af

U begint met het aftrekken van het element met de minimumwaarde in elke rij van de andere elementen in die rij. Het kleinste element in de eerste rij is bijvoorbeeld 69. Daarom wordt 69 afgetrokken van elk element in de eerste rij. De resulterende matrix is:

Stap 2: trek de minima van elke kolom af

Op dezelfde manier wordt het element met de minimumwaarde van elke kolom afgetrokken van de andere elementen van die kolom, waardoor de volgende matrix wordt verkregen:

Stap 3: bedek alle nullen met een minimum aantal regels

Nu gaan we het minimum aantal lijnen (horizontaal of verticaal) bepalen dat nodig is om alle nullen in de matrix te bedekken. Alle nullen kunnen worden bedekt met behulp van 3 regels:

Aangezien het aantal benodigde regels drie is en kleiner dan de grootte van de matrix (n = 4), gaan we verder met stap 4.

Stap 4: maak extra nullen aan

Het kleinste element dat niet door de lijnen wordt bedekt, wordt geselecteerd, waarvan de waarde 6 is. Deze waarde wordt afgetrokken van alle elementen die niet worden bedekt en dezelfde waarde wordt toegevoegd aan alle elementen die worden bedekt door het snijpunt van twee lijnen. Dit resulteert in de volgende matrix:

Zoals aangegeven in de Hongaarse methode, moet stap drie opnieuw worden uitgevoerd.

Stap 3 (herhalen)

Opnieuw wordt het minimum aantal regels bepaald dat nodig is om alle nullen in de matrix te bedekken. Deze keer zijn vier regels vereist:

Omdat het aantal benodigde regels 4 is, gelijk aan de grootte van de matrix (n = 4), hebben we een optimale verdeling tussen de nullen in de matrix. Daarom stopt het algoritme.

Optimale toewijzing

Zoals de methode aangeeft, komt de selectie van de volgende nullen overeen met een optimale toewijzing:

Deze selectie van nullen komt overeen met de volgende optimale allocatie in de oorspronkelijke kostenmatrix:

Daarom moet werknemer 1 activiteit 3 ​​uitvoeren, werknemer 2, activiteit 2, werknemer 3, activiteit 1 en werknemer 4 moet activiteit 4 uitvoeren. De totale kosten van deze optimale toewijzing zijn 69 + 37 + 11 + 23 = 140.

Referenties

1. Hongaars algoritme (2019). Het Hongaarse algoritme. Genomen uit: hungarianalgorithm.com.
2. Onderzoek (2019). Het Hongaarse algoritme gebruiken om toewijzingsproblemen op te lossen. Genomen uit: study.com.
3. Wisdom Jobs (2018). Hongaarse methode voor het oplossen van een opdrachtprobleem - kwantitatieve technieken voor management. Genomen uit: wisdomjobs.com.
4. Geeks for Geeks (2019). Hongaars algoritme voor toewijzingsprobleem. Ontleend aan: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Hongaars maximum-matching-algoritme. Briljant. Overgenomen van: brilliant.org.