UNGARSK METODE: HVA BESTÅR DEN AV, EKSEMPEL - DUDAS - 2026

Den ungarske metoden er en algoritme som brukes i tildelingsproblemer når du vil minimere kostnadene. Det vil si at den brukes til å finne minimumskostnadene ved å tildele flere personer til forskjellige aktiviteter basert på minst mulig kostnad. Hver aktivitet må tilordnes en annen person.

Et tildelingsproblem er en spesiell type lineært programmeringsproblem, der målet er å minimere kostnadene eller tiden for å fullføre et antall jobber av flere personer.

Kilde: pixabay.com

En av de viktige egenskapene til tildelingsproblemet er at bare en jobb (eller arbeider) er tilordnet en maskin (eller prosjekt).

Denne metoden ble utviklet av den ungarske matematikeren D. Konig. Av denne grunn er det kjent som den ungarske metoden for oppgaveproblemer. Det er også kjent som tildelingsalgoritmen Kuhn-Munkres.

Ethvert tildelingsproblem kan enkelt løses ved å bruke denne metoden som består av to faser:

- Med den første fasen blir radreduksjoner og kolonneduksjon gjennomført.

- I den andre fasen er løsningen optimalisert på iterativ basis.

Hva er den ungarske metoden?

Den ungarske metoden består av fire trinn. De to første trinnene utføres bare en gang, mens trinn 3 og 4 gjentas til en optimal tildeling er funnet.

En firkantet matrise av rekkefølge n etter n blir betraktet som inndata, som bare må inneholde ikke-negative elementer.

For et gitt problem, hvis antall rader i matrisen ikke er lik antall kolonner, må en dummy-rad eller en dummy-kolonne legges til, avhengig av tilfelle. Tildelingskostnadene for disse dummycellene tildeles alltid som null.

Trinn 1: Trekk minima fra hver rad

For hver rad i matrisen blir elementet med den laveste verdien valgt og trukket fra hvert element i den raden.

Trinn 2: trekke minimumsnivået fra hver kolonne

Tilsvarende blir elementet med den laveste verdien valgt for hver kolonne og trukket fra hvert element i den kolonnen.

Trinn 3: dekk alle nuller med et minimum antall linjer

Alle nuller i matrisen som følge av trinn 2 må dekkes ved hjelp av et minimum antall horisontale og vertikale linjer, enten med rader eller kolonner.

Hvis det er nødvendig med totalt n linjer for å dekke alle nullene, der n er lik størrelsen n ganger n av matrisen, vil det være en optimal fordeling mellom nullene og derfor stopper algoritmen.

Hvis ikke, er det behov for mindre enn n linjer for å dekke alle nuller i matrisen, fortsett til trinn 4.

Trinn 4: lag ekstra nuller

Det minste elementet i matrisen (kalt k) som ikke er dekket av en av linjene laget i trinn 3, er valgt.

Verdien av k trekkes fra alle elementer som ikke er dekket av linjer. Deretter blir verdien av ka lagt til alle elementene som dekkes av skjæringspunktet mellom to linjer.

Elementer som er dekket av en enkelt linje blir liggende. Etter å ha utført dette trinnet, går du tilbake til trinn 3.

Optimal tildeling

Etter at algoritmen er stoppet i trinn 3, velges et sett med nuller slik at hver rad og hver kolonne bare har en null valgt.

Hvis det ikke er noen null på rad eller kolonne i denne valgprosessen, vil en av disse nullene bli valgt. De resterende nullene i den kolonnen eller raden blir fjernet, og gjentar det samme for de andre oppgavene også.

Hvis det ikke er en eneste nulloppgave, er det flere løsninger. Kostnadene vil imidlertid forbli de samme for forskjellige oppdragssett.

Eventuelle dummy rader eller kolonner som er lagt til blir fjernet. Nullene som er valgt i denne endelige matrisen tilsvarer dermed den ideelle oppgaven som kreves i den opprinnelige matrisen.

Eksempel

La oss vurdere et selskap hvor det er fire aktiviteter (A1, A2, A3, A4) som må utføres av fire arbeidere (T1, T2, T3, T4). Det må tildeles én aktivitet per arbeidstaker.

Følgende matrise viser kostnadene ved å tilordne en viss arbeider til en viss aktivitet. Målet er å minimere de totale kostnadene for oppgaven som består av disse fire aktivitetene.

Trinn 1: Trekk minima fra hver rad

Du starter med å trekke fra elementet med minimumsverdien i hver rad fra de andre elementene i den raden. For eksempel er det minste elementet i den første raden 69. Derfor trekkes 69 fra hvert element i den første raden. Den resulterende matrisen er:

Trinn 2: trekke minimumsnivået fra hver kolonne

På samme måte trekkes elementet med minimumsverdien for hver kolonne fra de andre elementene i den kolonnen, og oppnår følgende matrise:

Trinn 3: dekk alle nuller med et minimum antall linjer

Nå skal vi bestemme minimum antall linjer (horisontalt eller vertikalt) som kreves for å dekke alle nullene i matrisen. Alle nuller kan dekkes med tre linjer:

Siden antallet linjer som kreves er tre og det er mindre enn størrelsen på matrisen (n = 4), fortsetter vi med trinn 4.

Trinn 4: lag ekstra nuller

Det minste elementet som ikke er dekket av linjene, er valgt, hvis verdi er 6. Denne verdien trekkes fra alle elementene som ikke er dekket, og denne samme verdien blir lagt til alle elementene som er dekket av skjæringspunktet mellom to linjer. Dette resulterer i følgende matrise:

Som antydet i den ungarske metoden, må trinn tre utføres igjen.

Trinn 3 (gjenta)

Igjen bestemmes minimum antall linjer for å dekke alle nullene i matrisen. Denne gangen kreves det fire linjer:

Fordi antall linjer som kreves er 4, lik størrelsen på matrisen (n = 4), har vi en optimal fordeling mellom nullene i matrisen. Derfor stopper algoritmen.

Optimal tildeling

Som metoden indikerer, tilsvarer valget av følgende nuller en optimal tildeling:

Dette valget av nuller tilsvarer følgende optimale fordeling i den opprinnelige kostnadsmatrisen:

Derfor må arbeidstaker 1 utføre aktivitet 3, arbeider 2, aktivitet 2, arbeider 3, aktivitet 1, og arbeider 4 må utføre aktivitet 4. Den totale kostnaden for dette optimale oppdraget er 69 + 37 + 11 + 23 = 140.

referanser

1. Ungarsk algoritme (2019). Den ungarske algoritmen. Hentet fra: hungarianalgorithm.com.
2. Studie (2019). Bruke den ungarske algoritmen for å løse oppgaveproblemer. Hentet fra: study.com.
3. Visdomsjobber (2018). Ungarsk metode for å løse oppgaveproblemer - kvantitative teknikker for ledelse. Hentet fra: expressionjobs.com.
4. Geeks for Geeks (2019). Ungarsk algoritme for tildelingsproblem. Hentet fra: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Ungarsk maksimal matchende algoritme. Strålende. Hentet fra: brilliant.org.