Den ungarske metode er en algoritme, der gør det muligt at minimere omkostningerne i et optimeringsproblem baseret på lineær programmering.
Målet med den ungarske metode er at finde de minimale omkostninger ved et sæt opgaver, der skal udføres af de mest egnede mennesker.
Det bruger lineær programmering (PL) til at udføre en række trin, der kan automatiseres. Således har værktøjer såsom den statistiske software R (blandt andre) flere meget nyttige pakker til disse optimeringsproblemer.
Oprindelse af den ungarske metode
Dens skaber var den ungarske matematiker (deraf navnet) Harold W. Kuhn i 1955. En anden matematiker, James Munkres, reviderede den i 1957. Med denne udvikling har den modtaget andre navne såsom Munkres eller Kuhn-Munkres tildelingsalgoritme.
På den anden side har denne metode præcedens hos to forfattere, Dénes König og Jenő Egerváry, begge jøder og ungarere. Den første udviklede grafteorien, som denne algoritme er baseret på. Den anden generaliserede Königs sætning og tillod Kuhn at udvikle metoden.
Trin til den ungarske metode
De følgende trin gør det muligt at udføre den ungarske metode på en enkel måde ved hjælp af et regneark. Derudover vil denne ordning, som vi viser, give os mulighed for på en global måde at se den proces, som vi vil udvikle i detaljer i det sidste eksempel.
- Som indledende trin skal du tildele personer (rækker) til en række projekter (kolonner). Derudover er det nødvendigt at beregne de forskellige omkostninger ved hvert projekt afhængigt af, hvem der udfører det og oprette en matrix (C) med denne information.
- I matrixen (C) ser vi efter minimumsværdien af hver række. Vi trækker dette fra alle elementerne i rækken og udfører den samme operation med kolonnerne. En ny matrix (C`) vises med resultaterne af de tidligere operationer.
- Dernæst opretter vi «ligestillingsgrafen», som giver os mulighed for at vælge de opgaver og projekter med de laveste omkostninger. Det optimale ville være de elementer, hvis resultat var nul. Hvis det er rigtigt, at der ikke er noget element med en nulværdi tildelt mere end en række, slutter algoritmen.
- Ellers skal der foretages en ny opgave. Der laves en ny matrix, som en række ændringer anvendes til, som vi vil se i eksemplet. Vi genskaber grafen og fortsætter, indtil vi har en matrix, der har mindst et nul i hver række og i ikke-gentagne positioner.
- Med denne information har vi allerede de personer og projekter, der er tildelt (nuller), der optimerer problemet. Hvis en opgave allerede er tildelt i en forrige række, kasseres den i den næste. For at beregne minimumsomkostningerne tilføjer vi omkostningerne til den indledende matrix, der vises i placeringen af disse nuller.
Ungarsk metodeeksempel
Lad os se på et simpelt eksempel på den ungarske metode til. Lad os forestille os, at vi har tre arbejdere, og de skal tildeles til tre projekter. Vi opretter den indledende matrix (C) og omkostningsværdierne i hver celle. Til dette skal du bruge de tilgængelige oplysninger i virksomheden. Når vi har alt dette, begynder vi processen. Et regneark kan hjælpe.
Vi beregner minimum for hver række og trækker dem fra elementerne i den række og gør det samme med kolonnerne (trin 1 og 2). I den resulterende matrix (C`) tegner vi linjer på en sådan måde, at de dækker alle nuller og til gengæld skærer hinanden (trin 3). Vi ser, at der er to linjer, men den største værdi af antallet af rækker eller kolonner er tre. Vi er nødt til at fortsætte.
Nu vælger vi det mindste af de udækkede tal, i dette eksempel er det to (mørkeblå). Vi trækker det fra de foregående og føjer det til dem, der er placeret, hvor linjerne krydser hinanden. I vores tilfælde er det yderligere to (E3, T1). Vi står tilbage med en ny matrix (trin 4). Vi tegner linjerne igen og tæller. Der er tre linjer, det samme som antallet af rækker eller kolonner. Algoritmen er færdig.
Vi starter med rækken eller kolonnen med de færreste nuller (E1, T1). Hvis en opgave allerede er tildelt, kan den ikke tildeles igen, for eksempel med E2 kan du ikke bruge det første nul på T1, da denne opgave blev tildelt E1. De samlede omkostninger i den ungarske metode vil være summen af omkostningerne ved den oprindelige matrix (trin 1) placeret i samme position som de valgte nuller (trin 5).