Den ungarske metoden er en algoritme som gjør det mulig å minimere kostnadene i et optimaliseringsproblem basert på lineær programmering.
Målet med den ungarske metoden er å finne minimumskostnaden for et sett med oppgaver som må utføres av de mest egnede menneskene.
Den bruker lineær programmering (PL) for å utføre en serie trinn som kan automatiseres. Dermed har verktøy som den statistiske programvaren R (blant andre) flere veldig nyttige pakker for disse optimaliseringsproblemene.
Opprinnelsen til den ungarske metoden
Skaperen var den ungarske matematikeren (derav navnet) Harold W. Kuhn i 1955. En annen matematiker, James Munkres, reviderte den i 1957. Med denne utviklingen har den mottatt andre navn som Munkres eller Kuhn-Munkres tildelingsalgoritme.
På den annen side har denne metoden presedens hos to forfattere, Dénes König og Jenő Egerváry, begge jøder og ungarere. Den første utviklet grafteorien som denne algoritmen er basert på. Den andre generaliserte Königs teorem og tillot Kuhn å utvikle metoden.
Trinn i den ungarske metoden
Trinnene som følger, gjør det mulig å utføre den ungarske metoden på en enkel måte ved hjelp av et regneark. I tillegg vil denne ordningen som vi viser, tillate oss å se på en global måte prosessen som vi vil utvikle i detalj i det siste eksemplet.
- Som foreløpige trinn må du tilordne personer (rader) til en serie prosjekter (kolonner). I tillegg er det nødvendig å beregne de forskjellige kostnadene for hvert prosjekt, avhengig av hvem som utfører det og bygge en matrise (C) med denne informasjonen.
- I matrisen (C) ser vi etter minimumsverdien for hver rad. Vi trekker dette fra alle elementene i raden og utfører den samme operasjonen med kolonnene. En ny matrise (C`) vises med resultatene fra forrige operasjoner.
- Deretter lager vi «likhetsgrafen», som lar oss velge oppgaver og prosjekter med lavest kostnad. Det optimale ville være de elementene hvis resultat var null. Hvis det er sant at det ikke er noe element med en nullverdi tildelt mer enn en rad, slutter algoritmen.
- Ellers må det gjøres et nytt oppdrag. Det blir laget en ny matrise som en rekke modifikasjoner blir brukt på, som vi vil se i eksemplet. Vi gjenskaper grafen og fortsetter til vi har en matrise som har minst ett null i hver rad og i ikke-gjentatte posisjoner.
- Med denne informasjonen har vi allerede personene og prosjektene (nollene) som optimaliserer problemet. Hvis en oppgave allerede er tildelt i en forrige rad, kastes den i neste. For å beregne minimumskostnaden legger vi til kostnadene for den opprinnelige matrisen som vises i posisjonen til disse nullene.
Ungarsk metodeeksempel
La oss se på et enkelt eksempel på den ungarske metoden for. La oss forestille oss at vi har tre arbeidere, og de må tildeles tre prosjekter. Vi oppretter den første matrisen (C) og kostnadsverdiene i hver celle. For dette må du bruke informasjonen som er tilgjengelig i selskapet. Når vi har alt dette, begynner vi prosessen. Et regneark kan hjelpe.
Vi beregner minimumene for hver rad og trekker dem fra elementene i den raden og gjør det samme med kolonnene (trinn 1 og 2). I den resulterende matrisen (C`) tegner vi linjer på en slik måte at de dekker alle nuller og i sin tur krysser hverandre (trinn 3). Vi ser at det er to linjer, men den største verdien av antall rader eller kolonner er tre. Vi må fortsette.
Nå velger vi det minste av de avdekkede tallene, i dette eksemplet er det to (mørkeblå). Vi trekker den fra de forrige og legger den til de som ligger der linjene krysser hverandre. I vårt tilfelle er det ytterligere to (E3, T1). Vi sitter igjen med en ny matrise (trinn 4). Vi tegner om linjene og teller. Det er tre linjer, samme som antall rader eller kolonner. Algoritmen er ferdig.
Vi starter med raden eller kolonnen med færrest nuller (E1, T1). Hvis en oppgave allerede er tildelt, kan den ikke tildeles på nytt, for eksempel med E2 kan du ikke bruke det første nullpunktet til T1, siden denne oppgaven ble tildelt E1. Den totale kostnaden, i den ungarske metoden, vil være summen av kostnadene for den opprinnelige matrisen (trinn 1) plassert i samme posisjon som de valgte nullene (trinn 5).