MAĐARSKA METODA: OD ČEGA SE SASTOJI, PRIMJERICE - DUDÁS - 2025

Mađarski način je algoritam koji se koristi u problemima raspodjele kada želite smanjiti troškove. Odnosno, koristi se za pronalaženje minimalnog troška dodjeljivanjem više ljudi različitim aktivnostima na temelju najmanjeg troška. Svaka aktivnost mora biti dodijeljena drugoj osobi.

Problem raspodjele je posebna vrsta problema linearnog programiranja, gdje je cilj svesti na najmanju moguću mjeru trošak ili vrijeme obavljanja određenog broja poslova.

Izvor: pixabay.com

Jedna od važnih karakteristika problema raspodjele je ta što je samo jedan posao (ili radnik) dodijeljen stroju (ili projektu).

Ovu je metodu razvio mađarski matematičar D. Konig. Iz tog razloga je poznata kao mađarska metoda za probleme s dodjelom. Poznat je i kao algoritam raspodjele Kuhn-Munkres.

Bilo koji problem s dodjelom može se lako riješiti primjenom ove metode koja se sastoji od dvije faze:

- S prvom reduzom provode se redukcije i redukcije stupaca.

- U drugoj fazi rješenje se optimizira na iterativnoj osnovi.

Koja je mađarska metoda?

Mađarska metoda sastoji se od četiri koraka. Prva dva koraka izvršavaju se samo jednom, dok se koraci 3 i 4 ponavljaju sve dok se ne nađe optimalna raspodjela.

Kvadratna matrica reda n prema n smatra se ulaznim podacima koji moraju sadržavati samo negativne elemente.

Za zadani problem, ako broj redova u matrici nije jednak broju stupaca, ovisno o slučaju treba dodati lučni redak ili oblik lutke. Troškovi raspodjele tih luđačkih ćelija uvijek se dodjeljuju kao nula.

1. korak: oduzmite minimale svakog retka

Za svaki red u nizu odabire se element s najnižom vrijednošću i oduzima od svakog elementa u tom retku.

2. korak: oduzmite minimum iz svakog stupca

Slično tome, stavka s najnižom vrijednošću odabrana je za svaki stupac i oduzima se od svake stavke u tom stupcu.

Korak 3: prekrijte sve nule s minimalnim brojem linija

Sve nule u matrici koje proizlaze iz koraka 2 moraju biti prekrivene minimalnim brojem vodoravnih i vertikalnih linija bilo redaka ili stupaca.

Ako je potrebno ukupno n redaka da pokriju sve nule, gdje je n jednak veličini n puta n matrice, doći će do optimalne raspodjele između nula i zbog toga se algoritam zaustavlja.

Inače, ako je potrebno manje od n redaka da biste prekrili sve nulte u nizu, prijeđite na korak 4.

4. korak: stvorite dodatne nule

Odabran je najmanji element matrice (zvan k) koji nije pokriven niti jednom linijom izvedenom u koraku 3.

Vrijednost k oduzima se od svih elemenata koji nisu obuhvaćeni linijama. Nakon toga, vrijednost ka dodaje se svim elementima koji su prekriveni sjecištem dviju linija.

Stavke koje su pokrivene jednim redom ostaju onakve kakve jesu. Nakon izvođenja ovog koraka vraćate se na korak 3.

Optimalna raspodjela

Nakon zaustavljanja algoritma u koraku 3, odabire se skup nula tako da je za svaki red i svaki stupac odabrana samo jedna nula.

Ako u ovom postupku odabira nema niti jedne nule u retku ili stupcu, tada će se odabrati jedna od tih nula. Preostale nule u tom stupcu ili retku uklanjaju se, ponavljajući isto kao i za ostale zadatke.

Ako ne postoji pojedinačni nulti raspored, postoji više rješenja. Međutim, trošak će ostati isti za različite skupove poslova.

Uklanjaju se svi dodani redovi ili stupci. Nulte odabrane u ovoj završnoj matrici tako odgovaraju idealnom zadatku koji se traži u izvornoj matrici.

Primjer

Razmotrimo tvrtku u kojoj postoje četiri djelatnosti (A1, A2, A3, A4) koje moraju obavljati četiri radnika (T1, T2, T3, T4). Po jednoj radnici mora se dodijeliti jedna aktivnost.

Sljedeća matrica prikazuje troškove pridruživanja određenog radnika određenoj aktivnosti. Cilj je minimizirati ukupni trošak zadatka koji se sastoji od ove četiri aktivnosti.

1. korak: oduzmite minimale svakog retka

Započinjete oduzimanjem elementa s minimalnom vrijednošću u svakom retku od ostalih elemenata u tom retku. Na primjer, najmanji element u prvom redu je 69. Stoga se od svakog elementa u prvom redu oduzima 69. Rezultirajuća matrica je:

2. korak: oduzmite minimum iz svakog stupca

Na isti se način element s minimalnom vrijednošću svakog stupca oduzima od ostalih elemenata tog stupca dobivajući sljedeću matricu:

Korak 3: prekrijte sve nule s minimalnim brojem linija

Sada ćemo odrediti minimalni broj linija (vodoravnih ili vertikalnih) koji su potrebni da pokriju sve nule u matrici. Sve se nule mogu prekrivati ​​pomoću 3 retka:

Budući da je potreban broj linija tri i manji je od veličine matrice (n = 4), nastavljamo s korakom 4.

4. korak: stvorite dodatne nule

Odabran je najmanji element koji nije obuhvaćen crtama, čija je vrijednost 6. Ova se vrijednost oduzima od svih elemenata koji nisu obuhvaćeni i ta ista vrijednost dodaje se svim elementima obuhvaćenim sjecištem dviju linija. Rezultat je sljedeća matrica:

Kao što je naznačeno u mađarskoj metodi, treći korak mora biti izveden ponovno.

3. korak (ponovite)

Ponovo se utvrđuje minimalni broj redaka potreban za pokrivanje svih nula u matrici. Ovog puta su potrebna četiri retka:

Budući da je potreban broj linija 4, jednak je veličini matrice (n = 4), imamo optimalnu raspodjelu između nula u matrici. Stoga se algoritam zaustavlja.

Optimalna raspodjela

Kao što pokazuje metoda, odabir sljedećih nula odgovara optimalnom zadatku:

Ovaj izbor nula odgovara sljedećoj optimalnoj raspodjeli u izvornoj matrici troškova:

Dakle, radnik 1 mora obavljati aktivnost 3, radnik 2, aktivnost 2, radnik 3, aktivnost 1, a radnik 4 mora obavljati aktivnost 4. Ukupni trošak ovog optimalnog zadatka je 69 + 37 + 11 + 23 = 140.

Reference

1. Mađarski algoritam (2019). Mađarski algoritam. Preuzeto sa: Hungarianalgorithm.com.
2. Studija (2019). Pomoću mađarskog algoritma za rješavanje problema zadataka. Preuzeto sa: study.com.
3. Wisdom Jobs (2018). Mađarska metoda rješavanja problema dodjele - kvantitativne tehnike upravljanja. Preuzeto sa: wisdomjobs.com.
4. Geeks za Geeks (2019). Mađarski algoritam za problem zadatka. Preuzeto sa: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Mađarski algoritam maksimalnog podudaranja. Sjajan. Preuzeto sa: briljant.org.