Ungersk metod vad som består, exempel

han Ungersk metod Det ä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 minsta kostnad genom att tilldela flera personer till olika aktiviteter baserat på den lägsta kostnaden. Varje aktivitet måste tilldelas en annan person.

Ett uppdragsproblem är en speciell typ av linjärt programmeringsproblem, där målet är att minimera kostnaden eller tiden för att slutföra en mängd arbete av flera personer.

Källa: Pixabay.com

En av de viktiga egenskaperna hos tilldelningsproblemet är att endast ett arbete (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 Kuhn-Munkres-uppdragsalgoritm.

Alla tilldelningsproblem kan enkelt lösas genom att tillämpa denna metod som består av två faser:

- Med den första fasen finns minskningar av rader och kolumnreduktioner.

- I den andra fasen är lösningen på en iterativ bas optimerad.

[TOC]

Vad är den ungerska metoden?

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

Det betraktas som inträdesfakta till en fyrkantig matris av ordning n av n, 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 fiktiv rad eller en fiktiv kolumn läggas till, beroende på fallet. Uppdragskostnader för dessa fiktiva celler tilldelas alltid som noll.

Steg 1: Subtrahera minsta av varje rad

För varje rad i matrisen väljs elementet med det lägsta värdet och subtraktionerna för varje element i den raden.

Kan tjäna dig: vad är den nuvarande tillgången? (Med exempel)

Steg 2: Subtrahera minsta av varje kolumn

På liknande sätt väljs elementet med det lägsta värdet för varje kolumn och subtraherar det från varje element i den kolumnen.

Steg 3: Täck alla nollor med ett minimalt antal rader

Alla nollor måste täckas i matrisen till följd av steg 2 med hjälp av ett minimalt antal horisontella och vertikala linjer, antingen med rader eller kolumner.

Om en total linjer krävs för att täcka alla nollor, att vara n lika med storleken n per n i matrisen, kommer det att finnas en optimal tilldelning mellan nollorna och därför stannar algoritmen.

Annars, om mindre av linjer krävs för att täcka alla nollor i matrisen, fortsätter den med steg 4.

Steg 4: Skapa ytterligare nollor

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

Värdet på k för alla element som inte täcks av linjer dras bort. Därefter läggs värdet på k till alla element som täcks av skärningspunkten mellan två rader.

De element som täcks av en enda linje lämnas som de är. Efter att ha utfört detta steg återvänder du till steg 3.

Optimal uppdrag

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

Om det inte finns någon enda noll i denna valprocess i rad eller kolumn kommer en av dessa nollor att väljas. De återstående nollorna elimineras i den kolumnen eller raden och upprepar samma för de andra uppdragen också.

Det kan tjäna dig: makrolokalisering

Om det inte finns en enda fördelning av nollor betyder det att det finns flera lösningar. Kostnaden kommer dock att förbli densamma för de olika tilldelningsuppsättningarna.

Varje fiktiv rad eller kolumn som har lagts till elimineras. De nollor som valts i denna slutliga matris motsvarar den ideala tilldelningen som krävs i den ursprungliga matrisen.

Exempel

Tänk på ett företag där det finns fyra aktiviteter (A1, A2, A3, A4) som måste genomföras av fyra arbetare (T1, T2, T3, T4). En aktivitet per arbetare måste tilldelas.

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

Steg 1: Subtrahera minsta av varje rad

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

Steg 2: Subtrahera minsta av varje kolumn

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

Steg 3: Täck alla nollor med ett minimalt antal rader

Nu kommer det minsta antalet linjer (horisontella eller vertikala) att fastställas som krävs för att täcka alla nollor i matrisen. Alla nollor kan täckas med 3 linjer:

Eftersom antalet obligatoriska linjer är tre och är mindre än storleken på matrisen (n = 4) fortsätter det med steg 4.

Kan tjäna dig: projektledning: vad är, faser, mål, exempel

Steg 4: Skapa ytterligare nollor

Det lägsta elementet som inte täcks av linjerna väljs, vars värde är 6. Detta värde på alla icke -täckta element subtraheras och samma värde läggs till alla element som täcks av skärningspunkten mellan två linjer. Detta resulterar i följande matris:

Som anges i den ungerska metoden måste steget nummer tre genomföras igen.

Steg 3 (repetition)

Å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 linjer som krävs är 4, lika med storleken på matrisen (n = 4), finns det ett optimalt tilldelning mellan nollor i matrisen. Därför stannar algoritmen.

Optimal uppdrag

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

Detta urval av nollor motsvarar följande optimala fördelning i den ursprungliga kostnadsmatrisen:

Därför måste arbetaren 1 genomföra aktivitet 3, arbetaren 2, aktiviteten 2, arbetaren 3, aktiviteten 1 och arbetaren 4 måste genomföra aktiviteten 4. Den totala kostnaden för denna optimala tilldelning är 69+37+11+23 = 140.

Referenser

1. Ungern algoritm (2019). Ungern algoritmen. Taget från: ungerianalgoritm.com.
2. Study (2019). Använda ungerns algoritm för att lösa uppdragsproblem. Taget från: studie.com.
3. Wisdom Jobs (2018). Ungern metod för att lösa uppdragsproblem - kvantitativa tekniker för hantering. Taget från: Wisdomjobs.com.
4. Geeks for Geeks (2019). Ungern algoritm för uppdragsproblem. Taget från: GeeksForgeeks.org.
5. Karleight Moore, Nathan Landman (2019). Ungern maximal matchande algoritm. Lysande. Taget från: lysande.org.