MADŽARSKA METODA: IZ ČESA SESTOJI, NA PRIMER - DUDE - 2026

Madžarski metoda je algoritem, ki se uporablja v težave dodelitve, če želite zmanjšati stroške. To pomeni, da se uporablja za iskanje najnižjih stroškov z dodeljevanjem več ljudi različnim dejavnostim na podlagi najmanjših stroškov. Vsaka dejavnost mora biti dodeljena drugi osebi.

Problem z dodelitvijo je posebna vrsta problema linearnega programiranja, kjer je cilj zmanjšati stroške ali čas dokončanja številnih delovnih mest s strani več ljudi.

Vir: pixabay.com

Ena od pomembnih značilnosti težave z dodelitvijo je, da je stroju (ali projektu) dodeljeno samo eno delovno mesto (ali delavec).

To metodo je razvil madžarski matematik D. Konig. Zaradi tega je poznana kot madžarska metoda za težave pri dodeljevanju. Znan je tudi kot algoritem za dodeljevanje Kuhn-Munkres.

Vsak problem z dodelitvijo je mogoče enostavno rešiti z uporabo te metode, ki je sestavljena iz dveh faz:

- V prvi fazi se izvajajo zmanjšanja in zmanjšanja stolpcev.

- V drugi fazi se rešitev optimizira na iterativni osnovi.

Kakšna je madžarska metoda?

Madžarska metoda je sestavljena iz štirih korakov. Prva dva koraka se izvedeta samo enkrat, koraka 3 in 4 pa se ponavljata, dokler ne najdemo optimalne razporeditve.

Kot vhodni podatek se šteje kvadratna matrica reda n po n, ki mora vsebovati samo negativne elemente.

Če je za določeno težavo število vrstic v matrici enako številu stolpcev, je treba dodati vrstico ali preskusni stolpec, odvisno od primera. Stroški dodelitve za te navidezne celice se vedno dodelijo kot nič.

1. korak: odštejte najmanjše vrednosti vsake vrstice

Za vsako vrstico v polju se izbere element z najnižjo vrednostjo in odšteje od vsakega elementa v tej vrstici.

2. korak: odštejte najmanjše vrednosti iz vsakega stolpca

Podobno je za vsak stolpec izbran element z najnižjo vrednostjo in odštet od vsake postavke v tem stolpcu.

3. korak: vse ničle prekrijte z minimalnim številom vrstic

Vse ničle v matriki, ki izhajajo iz koraka 2, morajo biti zajete z minimalnim številom vodoravnih in navpičnih črt, bodisi z vrsticami ali stolpci.

Če je za pokrivanje vseh ničel potrebnih skupaj n vrstic, kjer je n enak velikosti n krat n matrice, dobimo optimalno razporeditev med ničle in zato se algoritem ustavi.

V nasprotnem primeru, če potrebujete manj kot n vrstic, da pokrijete vse ničle v matriki, nadaljujte s korakom 4.

4. korak: ustvarite dodatne ničle

Izbran je najmanjši element matrike (imenovan k), ki ga ne pokriva nobena od vrstic v koraku 3.

Vrednost k se odšteje od vseh elementov, ki niso pokriti s črtami. Kasneje se vrednost ka doda vsem elementom, ki jih pokriva presečišče dveh vrstic.

Elementi, ki jih pokriva ena sama vrstica, ostanejo takšni, kot so. Po izvedbi tega koraka se vrnete na korak 3.

Optimalna razporeditev

Ko se algoritem ustavi v koraku 3, se izbere niz ničel, tako da ima vsaka vrstica in vsak stolpec izbrano samo eno ničlo.

Če v tem izbirnem postopku ni ene same ničle v vrstici ali stolpcu, bo izbrana ena od teh ničel. Preostale ničle v tem stolpcu ali vrstici so odstranjene, ponavljajo pa se enako tudi za druge naloge.

Če ni enotnega ničelnega dodeljevanja, obstaja več rešitev. Vendar bodo stroški ostali enaki za različne sklope nalog.

Morebitne vrstice ali stolpci, ki so bili dodani, se odstranijo. Izbrane ničle v tej končni matrici ustrezajo idealni dodelitvi, ki jo zahteva originalna matrica.

Primer

Razmislimo o podjetju, v katerem so štiri dejavnosti (A1, A2, A3, A4), ki jih morajo izvajati štirje delavci (T1, T2, T3, T4). Na delavca mora biti dodeljena ena dejavnost.

Naslednja matrica prikazuje stroške pripisovanja določenemu delavcu določeni dejavnosti. Cilj je zmanjšati skupne stroške naloge, sestavljene iz teh štirih dejavnosti.

1. korak: odštejte najmanjše vrednosti vsake vrstice

Začnete z odštevanjem elementa z najmanjšo vrednostjo v vsaki vrstici od ostalih elementov v tej vrstici. Na primer, najmanjši element v prvi vrstici je 69. Zato se od vsakega elementa v prvi vrstici odšteje 69. Nastala matrica je:

2. korak: odštejte najmanjše vrednosti iz vsakega stolpca

Na enak način se element od najmanjše vrednosti vsakega stolpca odšteje od drugih elementov tega stolpca, pri čemer dobimo naslednjo matrico:

3. korak: vse ničle prekrijte z minimalnim številom vrstic

Zdaj bomo določili najmanjše število vrstic (vodoravnih ali navpičnih), ki so potrebne za pokrivanje vseh ničel v matriki. Vse ničle je mogoče pokriti s tremi vrsticami:

Ker je število potrebnih vrstic tri in je manjše od velikosti matrike (n = 4), nadaljujemo s korakom 4.

4. korak: ustvarite dodatne ničle

Izbran je najmanjši element, ki ga črte ne zajemajo, katerih vrednost je 6. Ta vrednost se odšteje od vseh elementov, ki niso zajeti, in enaka vrednost se doda vsem elementom, ki jih pokriva presečišče dveh vrstic. Rezultat je naslednja matrika:

Kot je navedeno v madžarski metodi, je treba ponovno opraviti tretji korak.

3. korak (ponovite)

Ponovno je določeno minimalno število vrstic, ki so potrebne za pokrivanje vseh ničel v matriki. Tokrat so potrebne štiri vrstice:

Ker je število potrebnih vrstic 4, je enako velikosti matrike (n = 4), imamo optimalno razporeditev med ničle v matriki. Zato se algoritem ustavi.

Optimalna razporeditev

Kot kaže metoda, izbira naslednjih ničel ustreza optimalni dodelitvi:

Ta izbor ničel ustreza naslednji optimalni razporeditvi v prvotni matriki stroškov:

Zato mora delavec 1 opravljati dejavnost 3, delavec 2, dejavnost 2, delavec 3, dejavnost 1, delavec 4 pa opravljati dejavnost 4. Skupni stroški te optimalne naloge znašajo 69 + 37 + 11 + 23 = 140.

Reference

1. Madžarski algoritem (2019). Madžarski algoritem. Vzeto iz: Hungarianalgorithm.com.
2. Študija (2019). Uporaba madžarskega algoritma za reševanje problemov. Vzeto iz: study.com.
3. Wisdom Jobs (2018). Madžarska metoda reševanja problema dodeljevanja - kvantitativne tehnike upravljanja. Vzeto iz: wisdomjobs.com.
4. Geeks za Geeks (2019). Madžarski algoritem za problem dodelitve. Izvedeno iz: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Madžarski najvišji ujemajoči se algoritem. Briljantno. Izvedeno iz: bril.org.