Den ungerska metoden är en algoritm som gör det möjligt att minimera kostnader i ett optimeringsproblem baserat på linjär programmering.
Syftet med den ungerska metoden är att hitta minimikostnaden för en uppsättning uppgif.webpter som måste utföras av de mest lämpliga personerna.
Den använder linjär programmering (PL) för att utföra en serie steg som kan automatiseras. Således har verktyg såsom den statistiska programvaran R (bland andra) flera mycket användbara paket för dessa optimeringsproblem.
Ursprunget till den ungerska metoden
Dess skapare var den ungerska matematikern (därav namnet) Harold W. Kuhn 1955. En annan matematiker, James Munkres, reviderade den 1957. Med denna utveckling har den fått andra namn som tilldelningsalgoritmen Munkres eller Kuhn-Munkres.
Å andra sidan har denna metod prejudikat hos två författare, Dénes König och Jenő Egerváry, båda judar och ungrare. Den första utvecklade grafteorin som denna algoritm bygger på. Den andra generaliserade Königs teorem och tillät Kuhn att utveckla metoden.
Steg för den ungerska metoden
Stegen att följa gör det möjligt att utföra den ungerska metoden på ett enkelt sätt med hjälp av ett kalkylark. Dessutom kommer detta schema som vi visar att vi på ett globalt sätt kan se den process som vi kommer att utveckla i detalj i det sista exemplet.
- Som preliminära steg måste du tilldela personer (rader) till en serie projekt (kolumner). Dessutom är det nödvändigt att beräkna de olika kostnaderna för varje projekt beroende på vem som utför det och bygga en matris (C) med denna information.
- I matrisen (C) letar vi efter minimivärdet för varje rad. Vi subtraherar detta från alla element i raden och utför samma operation med kolumnerna. En ny matris (C`) visas med resultaten från tidigare operationer.
- Därefter skapar vi «likhetsdiagrammet», vilket gör att vi kan välja de uppgif.webpter och projekt som har lägst kostnad. Det optimala skulle vara de element vars resultat var noll. Om det är sant att det inte finns något element med ett nollvärde tilldelat mer än en rad slutar algoritmen.
- Annars måste ett nytt uppdrag göras. En ny matris görs på vilken en rad modifieringar tillämpas, vilket vi kommer att se i exemplet. Vi återskapar diagrammet och fortsätter tills vi har en matris som har minst en noll i varje rad och i icke-upprepande positioner.
- Med denna information har vi redan de personer och projekt som tilldelats (nollorna) som optimerar problemet. Om en uppgif.webpt redan har tilldelats i en tidigare rad tas den bort i nästa. För att beräkna minimikostnaden lägger vi till kostnaderna för den ursprungliga matrisen som visas i positionen för dessa nollor.
Ungerskt metodexempel
Låt oss titta på ett enkelt exempel på den ungerska metoden. Låt oss föreställa oss att vi har tre arbetare och de måste tilldelas tre projekt. Vi skapar den ursprungliga matrisen (C) och kostnadsvärdena i varje cell. För detta måste du använda informationen som finns i företaget. När vi har allt detta börjar vi processen. Ett kalkylark kan hjälpa till.
Vi beräknar miniminivåerna för varje rad och subtraherar dem från elementen i den raden och gör detsamma med kolumnerna (steg 1 och 2). I den resulterande matrisen (C`) ritar vi linjer på ett sådant sätt att de täcker alla nollor och i sin tur skär varandra (steg 3). Vi ser att det finns två rader, men det största värdet på antalet rader eller kolumner är tre. Vi måste fortsätta.
Nu väljer vi det minsta av de otäckta siffrorna, i det här exemplet är det två (mörkblå). Vi subtraherar det från de tidigare och lägger till det till de som ligger där linjerna korsar varandra. I vårt fall är det ytterligare två (E3, T1). Vi sitter kvar med en ny matris (steg 4). Vi ritar om linjerna och räknar. Det finns tre rader, samma som antalet rader eller kolumner. Algoritmen är klar.
Vi börjar med raden eller kolumnen med färsta nollor (E1, T1). Om en uppgif.webpt redan har tilldelats kan den inte omfördelas, till exempel med E2 kan du inte använda den första nollan av T1, eftersom denna uppgif.webpt tilldelades E1. Den totala kostnaden, i den ungerska metoden, kommer att vara summan av kostnaderna för den ursprungliga matrisen (steg 1) som ligger i samma position som de valda nollorna (steg 5).