De Hongaarse methode is een algoritme dat het mogelijk maakt om de kosten te minimaliseren in een optimalisatieprobleem op basis van lineaire programmering.
Het doel van de Hongaarse methode is om de minimale kosten te vinden van een reeks taken die door de meest geschikte mensen moeten worden uitgevoerd.
Het maakt gebruik van lineaire programmering (PL) om een reeks stappen uit te voeren die kunnen worden geautomatiseerd. Zo hebben tools zoals de statistische software R (onder andere) verschillende zeer nuttige pakketten voor deze optimalisatieproblemen.
Oorsprong van de Hongaarse methode
De maker ervan was de Hongaarse wiskundige (vandaar de naam) Harold W. Kuhn in 1955. Een andere wiskundige, James Munkres, herzag het in 1957. Met deze evolutie heeft het andere namen gekregen, zoals het Munkres- of Kuhn-Munkres-toewijzingsalgoritme. .
Aan de andere kant heeft deze methode een precedent in twee auteurs, Dénes König en Jenő Egerváry, zowel Joden als Hongaren. De eerste ontwikkelde de grafentheorie waarop dit algoritme is gebaseerd. De tweede generaliseerde de stelling van König en stelde Kuhn in staat de methode te ontwikkelen.
Stappen van de Hongaarse methode
De te volgen stappen maken het mogelijk om de Hongaarse methode op een eenvoudige manier uit te voeren met behulp van een spreadsheet. Bovendien zal dit schema dat we laten zien ons in staat stellen om op een globale manier het proces te zien dat we in het laatste voorbeeld in detail zullen ontwikkelen.
- Als voorbereidende stappen moet je mensen (rijen) toewijzen aan een reeks projecten (kolommen). Daarnaast is het noodzakelijk om de verschillende kosten van elk project te berekenen, afhankelijk van wie het uitvoert en een matrix (C) op te bouwen met deze informatie.
- In de matrix (C) zoeken we de minimumwaarde van elke rij. We trekken dit af van alle elementen in de rij en voeren dezelfde bewerking uit met de kolommen. Er verschijnt een nieuwe matrix (C`) met de resultaten van de vorige bewerkingen.
- Vervolgens maken we de «graph of equalities», waarmee we de taken en projecten met de laagste kosten kunnen kiezen. Het optimum zou die elementen zijn waarvan het resultaat nul was. Als het waar is dat er geen element is met een nulwaarde die aan meer dan één rij is toegewezen, eindigt het algoritme.
- Anders moet er een nieuwe opdracht worden gemaakt. Er wordt een nieuwe matrix gemaakt waarop een reeks aanpassingen wordt aangebracht, zoals we in het voorbeeld zullen zien. We maken de grafiek opnieuw en gaan door totdat we een matrix hebben met ten minste één nul in elke rij en in niet-herhalende posities.
- Met deze informatie hebben we al de mensen en projecten toegewezen (de nullen) die het probleem optimaliseren. Als een taak al in een vorige rij is toegewezen, wordt deze in de volgende weggegooid. Om de minimale kosten te berekenen, tellen we de kosten van de initiële matrix op die op de positie van deze nullen verschijnen.
Hongaarse methode voorbeeld
Laten we eens kijken naar een eenvoudig voorbeeld van de Hongaarse methode van. Laten we ons voorstellen dat we drie arbeiders hebben en dat ze aan drie projecten moeten worden toegewezen. We maken de initiële matrix (C) en de kostenwaarden in elke cel. Hiervoor moet u gebruik maken van de informatie die beschikbaar is in het bedrijf. Zodra we dit allemaal hebben, beginnen we met het proces. Een rekenblad kan helpen.
We berekenen de minima van elke rij en trekken deze af van de elementen van die rij en doen hetzelfde met de kolommen (stap 1 en 2). In de resulterende matrix (C`) trekken we lijnen zo dat ze alle nullen bedekken en elkaar op hun beurt snijden (stap 3). We zien dat er twee regels zijn, maar de grootste waarde van het aantal rijen of kolommen is drie. We moeten doorgaan.
Nu kiezen we het kleinste van de onbedekte getallen, in dit voorbeeld is dat twee (donkerblauw). We trekken het af van de vorige en voegen het toe aan degenen die zich bevinden waar de lijnen elkaar kruisen. In ons geval zijn het er nog twee (E3, T1). We blijven zitten met een nieuwe matrix (stap 4). We tekenen de lijnen opnieuw en tellen. Er zijn drie regels, hetzelfde als het aantal rijen of kolommen. Het algoritme is klaar.
We beginnen met de rij of kolom met de minste nullen (E1, T1). Als een taak al is toegewezen, kan deze niet opnieuw worden toegewezen, bijvoorbeeld met E2 kunt u de eerste nul van T1 niet gebruiken, omdat deze taak aan E1 is toegewezen. De totale kosten, in de Hongaarse methode, zijn de som van de kosten van de oorspronkelijke matrix (stap 1) op dezelfde positie als de gekozen nullen (stap 5).