UNGERSK METOD: VAD BESTÅR DET AV EXEMPEL - DUDAS - 2025

Den ungerska metoden är en algoritm som används i allokeringsproblem när du vill minimera kostnaden. Det vill säga det används för att hitta minimikostnaderna genom att tilldela flera personer till olika aktiviteter baserat på lägsta kostnad. Varje aktivitet måste tilldelas en annan person.

Ett allokeringsproblem är en speciell typ av linjärt programmeringsproblem, där målet är att minimera kostnaden eller tiden för att slutföra ett antal jobb av flera personer.

Källa: pixabay.com

En av de viktigaste kännetecknen för tilldelningsproblemet är att endast ett jobb (eller arbetare) tilldelas en maskin (eller projekt).

Denna metod utvecklades av den ungerska matematikern D. Konig. Av denna anledning är det känt som den ungerska metoden för tilldelningsproblem. Det är också känt som allokeringsalgoritmen Kuhn-Munkres.

Alla tilldelningsproblem kan lätt lösas genom att använda denna metod som består av två faser:

- Med den första fasens radreduceringar och kolumnreduktioner genomförs.

- I den andra fasen optimeras lösningen på iterativ basis.

Vad är den ungerska metoden?

Den ungerska metoden består av fyra steg. De två första stegen utförs endast en gång, medan steg 3 och 4 upprepas tills en optimal allokering hittas.

En kvadratmatris av ordning n för n betraktas som inmatningsdata, som endast måste innehålla icke-negativa element.

För ett givet problem, om antalet rader i matrisen inte är lika med antalet kolumner, måste en dummy-rad eller en dummy-kolumn läggas till, beroende på fall. Allokeringskostnaderna för dessa dummyceller fördelas alltid som noll.

Steg 1: subtrahera minima för varje rad

För varje rad i matrisen väljs och subtraheras elementet med det lägsta värdet från varje element i den raden.

Steg 2: subtrahera minima från varje kolumn

På samma sätt väljs objektet med det lägsta värdet för varje kolumn och subtraheras från varje objekt i den kolumnen.

Steg 3: täck alla nollor med ett minimum antal rader

Alla nollor i matrisen som härrör från steg 2 måste täckas med ett minimum antal horisontella och vertikala linjer, antingen med rader eller kolumner.

Om totalt n linjer krävs för att täcka alla nollor, där n är lika med storleken n gånger n på matrisen, kommer en optimal fördelning mellan nollorna att erhållas och därför stoppar algoritmen.

Annars, om mindre än n rader krävs för att täcka alla nollor i matrisen, fortsätt till steg 4.

Steg 4: skapa extra nollor

Det minsta elementet i matrisen (kallad k) som inte täcks av en av linjerna i steg 3 väljs.

Värdet på k dras från alla element som inte täcks av rader. Därefter läggs värdet på ka till alla element som täcks av skärningspunkten mellan två rader.

Objekt som täcks av en enda rad lämnas som de är. När du har utfört detta steg återgår du till steg 3.

Optimal allokering

Efter att algoritmen har stoppats i steg 3 väljs en uppsättning nollor så att varje rad och varje kolumn endast har en noll valt.

Om det inte finns en enda noll i denna rad eller kolumn i denna urvalsprocess, kommer en av dessa nollor att väljas. De återstående nollorna i den kolumnen eller raden tas bort, vilket också upprepas för de andra uppgifterna.

Om det inte finns en enda nolltilldelning finns det flera lösningar. Kostnaden kommer dock att förbli densamma för olika uppdragsuppsättningar.

Alla dummy rader eller kolumner som har lagts till tas bort. De nollor som valts i den här slutliga matrisen motsvarar således den ideala uppgiften som krävs i den ursprungliga matrisen.

Exempel

Låt oss överväga ett företag där det finns fyra aktiviteter (A1, A2, A3, A4) som måste utföras av fyra arbetare (T1, T2, T3, T4). En aktivitet måste tilldelas per arbetare.

Följande matris visar kostnaden för att tilldela en viss arbetare till en viss aktivitet. Målet är att minimera den totala kostnaden för uppgiften som består av dessa fyra aktiviteter.

Steg 1: subtrahera minima för varje rad

Du börjar med att subtrahera elementet med minimivärdet i varje rad från de andra elementen i den raden. Till exempel är det minsta elementet i den första raden 69. Därför dras 69 från varje element i den första raden. Den resulterande matrisen är:

Steg 2: subtrahera minima från varje kolumn

På samma sätt subtraheras elementet med minimivärdet för varje kolumn från de andra elementen i den kolumnen, vilket erhåller följande matris:

Steg 3: täck alla nollor med ett minimum antal rader

Nu kommer vi att bestämma det minsta antalet rader (horisontellt eller vertikalt) som krävs för att täcka alla nollor i matrisen. Alla nollor kan täckas med tre rader:

Eftersom antalet rader som krävs är tre och det är mindre än storleken på matrisen (n = 4) fortsätter vi med steg 4.

Steg 4: skapa extra nollor

Det minsta elementet som inte täcks av raderna väljs, vars värde är 6. Detta värde subtraheras från alla element som inte täcks och samma värde läggs till alla element som täcks av skärningspunkten mellan två rader. Detta resulterar i följande matris:

Som anges i den ungerska metoden måste steg tre utföras igen.

Steg 3 (upprepa)

Återigen bestäms det minsta antalet rader som krävs för att täcka alla nollor i matrisen. Den här gången krävs fyra rader:

Eftersom antalet rader som krävs är 4, lika stor som matrisen (n = 4), har vi en optimal fördelning mellan nollorna i matrisen. Därför stannar algoritmen.

Optimal allokering

Som metoden indikerar, motsvarar valet av följande nollor en optimal tilldelning:

Detta val av nollor motsvarar följande optimal fördelning i den ursprungliga kostnadsmatrisen:

Därför måste arbetare 1 utföra aktivitet 3, arbetare 2, aktivitet 2, arbetare 3, aktivitet 1 och arbetare 4 måste utföra aktivitet 4. Den totala kostnaden för detta optimala uppdrag är 69 + 37 + 11 + 23 = 140.

referenser

1. Ungersk algoritm (2019). Den ungerska algoritmen. Hämtad från: Hungarianalgorithm.com.
2. Studie (2019). Använda den ungerska algoritmen för att lösa tilldelningsproblem. Hämtad från: study.com.
3. Wisdom Jobs (2018). Ungersk metod för att lösa uppdragsproblem - kvantitativa tekniker för hantering. Hämtad från: wisjobs.com.
4. Geeks for Geeks (2019). Ungerns algoritm för tilldelningsproblem. Hämtad från: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Ungerns maximala matchande algoritm. Lysande. Hämtad från: brilliant.org.