- Hvad er den ungarske metode?
- Trin 1: Træk minima fra hver række
- Trin 2: Træk minimumsniveauet fra hver kolonne
- Trin 3: dæk alle nuller med et minimum antal linjer
- Trin 4: Opret ekstra nuller
- Optimal allokering
- Eksempel
- Trin 1: Træk minima fra hver række
- Trin 2: Træk minimumsniveauet fra hver kolonne
- Trin 3: dæk alle nuller med et minimum antal linjer
- Trin 4: Opret ekstra nuller
- Trin 3 (gentag)
- Optimal allokering
- Referencer
Den ungarske metode er en algoritme, der bruges i allokeringsproblemer, når du vil minimere omkostningerne. Det vil sige, det bruges til at finde mindstepriserne ved at tildele flere personer til forskellige aktiviteter baseret på de mindst omkostninger. Hver aktivitet skal tildeles en anden person.
Et allokeringsproblem er en speciel type lineært programmeringsproblem, hvor målet er at minimere omkostningerne eller tiden for at udføre et antal job af flere personer.
Kilde: pixabay.com
En af de vigtige egenskaber ved tildelingsproblemet er, at kun et job (eller arbejdstager) er tildelt en maskine (eller et projekt).
Denne metode blev udviklet af den ungarske matematiker D. Konig. Af denne grund er det kendt som den ungarske metode til tildelingsproblemer. Det er også kendt som Kuhn-Munkres allokeringsalgoritme.
Ethvert tildelingsproblem kan let løses ved anvendelse af denne metode, der består af to faser:
- Med den første faser rækkereduktioner og søjlereduktioner udføres.
- I den anden fase optimeres løsningen på iterativ basis.
Hvad er den ungarske metode?
Den ungarske metode består af fire trin. De første to trin udføres kun én gang, mens trin 3 og 4 gentages, indtil der findes en optimal allokering.
En firkantet matrix af rækkefølge n efter n betragtes som inputdata, der kun skal indeholde ikke-negative elementer.
For et givet problem, hvis antallet af rækker i matrixen ikke er lig med antallet af kolonner, skal der tilføjes en dummy-række eller en dummy-søjle, afhængigt af tilfældet. Tildelingsomkostninger for disse dummyceller allokeres altid som nul.
Trin 1: Træk minima fra hver række
For hver række i arrayet vælges og trækkes elementet med den laveste værdi fra hvert element i den række.
Trin 2: Træk minimumsniveauet fra hver kolonne
Tilsvarende vælges elementet med den laveste værdi for hver kolonne og trækkes fra hvert element i den kolonne.
Trin 3: dæk alle nuller med et minimum antal linjer
Alle nuller i matrixen, der er resultatet af trin 2, skal dækkes ved hjælp af et minimum antal vandrette og lodrette linjer, enten ved rækker eller kolonner.
Hvis der er påkrævet i alt n linjer for at dække alle nuller, hvor n er lig med størrelsen n gange n af matrixen, vil der være en optimal fordeling mellem nulene, og derfor stopper algoritmen.
Ellers, hvis der kræves mindre end n linjer for at dække alle nuller i matrixen, skal du fortsætte til trin 4.
Trin 4: Opret ekstra nuller
Det mindste element i matrixen (kaldet k), der ikke er dækket af en af linjerne foretaget i trin 3, vælges.
Værdien af k trækkes fra alle elementer, der ikke er dækket af linjer. Derefter føjes værdien af ka til alle elementerne, der er dækket af skæringspunktet mellem to linjer.
Genstande, der er dækket af en enkelt linje, bliver liggende. Når du har udført dette trin, vender du tilbage til trin 3.
Optimal allokering
Når algoritmen er stoppet i trin 3, vælges et sæt nuller, således at hver række og hver kolonne kun har valgt ét nul.
Hvis der i denne valgproces ikke er et enkelt nul i en række eller kolonne, vælges en af disse nuller. De resterende nuller i den kolonne eller række fjernes og gentager det samme for de andre opgaver også.
Hvis der ikke er en enkelt nul-tildeling, er der flere løsninger. Omkostningerne vil dog forblive de samme for forskellige sæt af opgaver.
Eventuelle dummy rækker eller kolonner, der er tilføjet, fjernes. De nuller, der er valgt i denne endelige matrix, svarer således til den ideelle tildeling, der kræves i den originale matrix.
Eksempel
Lad os overveje et firma, hvor der er fire aktiviteter (A1, A2, A3, A4), der skal udføres af fire arbejdstagere (T1, T2, T3, T4). En aktivitet skal tildeles pr. Arbejdstager.
Følgende matrix viser omkostningerne ved at tildele en bestemt arbejdstager til en bestemt aktivitet. Målet er at minimere de samlede omkostninger ved den opgave, der består af disse fire aktiviteter.
Trin 1: Træk minima fra hver række
Du starter med at subtrahere elementet med minimumsværdien i hver række fra de andre elementer i den række. For eksempel er det mindste element i den første række 69. Derfor trækkes 69 fra hvert element i den første række. Den resulterende matrix er:
Trin 2: Træk minimumsniveauet fra hver kolonne
På samme måde trækkes elementet med minimumsværdien for hver kolonne fra de andre elementer i den kolonne, hvilket opnår følgende matrix:
Trin 3: dæk alle nuller med et minimum antal linjer
Nu bestemmer vi det minimale antal linjer (vandret eller lodret), der kræves for at dække alle nuller i matrixen. Alle nuller kan dækkes ved hjælp af 3 linjer:
Da antallet af krævede linjer er tre og det er mindre end matrixens størrelse (n = 4), fortsætter vi med trin 4.
Trin 4: Opret ekstra nuller
Det mindste element, der ikke er dækket af linjerne, vælges, hvis værdi er 6. Denne værdi trækkes fra alle de elementer, der ikke er dækket, og denne samme værdi tilføjes til alle elementer, der er dækket af krydset mellem to linjer. Dette resulterer i følgende matrix:
Som angivet i den ungarske metode skal trin tre udføres igen.
Trin 3 (gentag)
Igen bestemmes det minimale antal linjer, der kræves for at dække alle nuller i matrixen. Denne gang kræves der fire linjer:
Da antallet af krævede linjer er 4, lig med størrelsen på matrixen (n = 4), har vi en optimal fordeling mellem nulerne i matrixen. Derfor stopper algoritmen.
Optimal allokering
Som metoden indikerer, svarer valget af følgende nuller til en optimal tildeling:
Dette valg af nuller svarer til følgende optimale allokering i den originale omkostningsmatrix:
Derfor skal arbejdstager 1 udføre aktivitet 3, arbejdstager 2, aktivitet 2, arbejder 3, aktivitet 1 og arbejdstager 4 skal udføre aktivitet 4. De samlede omkostninger ved denne optimale opgave er 69 + 37 + 11 + 23 = 140.
Referencer
- Ungarsk algoritme (2019). Den ungarske algoritme. Hentet fra: hungarianalgorithm.com.
- Undersøgelse (2019). Brug af den ungarske algoritme til at løse tildelingsproblemer. Taget fra: study.com.
- Visdomsjob (2018). Ungarsk metode til løsning af tildelingsproblem - kvantitative teknikker til styring. Taget fra: wisjobs.com.
- Geeks for Geeks (2019). Ungarsk algoritme til tildelingsproblem. Taget fra: geeksforgeeks.org.
- Karleigh Moore, Nathan Landman (2019). Ungarsk maksimal matchende algoritme. Strålende. Taget fra: brilliant.org.