Mađarska metoda je algoritam koji omogućuje minimaliziranje troškova u optimizacijskom problemu koji se temelji na linearnom programiranju.
Cilj mađarske metode je pronaći minimalne troškove skupa zadataka koje moraju izvršiti najprikladniji ljudi.
Koristi linearno programiranje (PL) za izvođenje niza koraka koji se mogu automatizirati. Dakle, alati poput statističkog softvera R (između ostalih) imaju nekoliko vrlo korisnih paketa za ove probleme optimizacije.
Podrijetlo mađarske metode
Njegov je tvorac bio mađarski matematičar (otuda i ime) Harold W. Kuhn 1955. Drugi matematičar, James Munkres, revidirao ga je 1957. Ovom evolucijom dobio je i druga imena poput Munkresovog ili Kuhn-Munkresovog algoritma za raspodjelu.
S druge strane, ova metoda ima presedan kod dva autora, Dénesa Königa i Jenő Egerváry, i Židova i Mađara. Prvi je razvio teoriju grafova na kojoj se temelji ovaj algoritam. Drugi je generalizirao Königov teorem i omogućio Kuhnu da razvije metodu.
Koraci mađarske metode
Koraci koje treba slijediti omogućuju provođenje mađarske metode na jednostavan način pomoću proračunske tablice. Uz to, ova shema koju prikazujemo omogućit će nam da na globalni način vidimo proces koji ćemo detaljno razviti u posljednjem primjeru.
- Kao preliminarne korake morate dodijeliti ljude (retke) nizu projekata (stupce). Uz to, potrebno je izračunati različite troškove svakog projekta, ovisno o tome tko ga izvodi, i izgraditi matricu (C) s tim informacijama.
- U matrici (C) tražimo minimalnu vrijednost svakog retka. Oduzimamo to od svih elemenata u redu i izvodimo istu operaciju sa stupcima. Pojavit će se nova matrica (C`) s rezultatima prethodnih operacija.
- Dalje, kreiramo «grafikon jednakosti», koji nam omogućuje odabir zadataka i projekata s najnižim troškovima. Optimum bi bili oni elementi čiji je rezultat bio nula. Ako je istina da ne postoji element s nultom vrijednošću dodijeljenom više od jednog retka, algoritam završava.
- U suprotnom, mora se izvršiti novi zadatak. Izrađuje se nova matrica na koju se primjenjuje niz modifikacija, kao što ćemo vidjeti u primjeru. Stvaramo grafikon i nastavljamo sve dok ne dobijemo matricu koja ima najmanje jednu nulu u svakom retku i na pozicijama koje se ne ponavljaju.
- Ovim informacijama već imamo dodijeljene ljude i projekte (nule) koji optimiziraju problem. Ako je zadatak već dodijeljen u prethodnom retku, u sljedećem će se odbaciti. Da bismo izračunali minimalni trošak zbrajamo troškove početne matrice koji se pojavljuju na položaju tih nula.
Primjer mađarske metode
Pogledajmo jednostavan primjer mađarske metode. Zamislimo da imamo troje radnika i oni moraju biti raspoređeni u tri projekta. Izrađujemo početnu matricu (C) i vrijednosti troškova u svakoj ćeliji. Za to morate koristiti podatke dostupne u tvrtki. Jednom kad sve ovo započnemo započinjemo proces. Proračunska tablica može vam pomoći.
Izračunavamo minimume svakog retka i oduzimamo ih od elemenata tog retka i činimo isto sa stupcima (koraci 1 i 2). U rezultirajućoj matrici (C`) crtamo crte na takav način da pokrivaju sve nule i da se međusobno sijeku (korak 3). Vidimo da postoje dva retka, ali najveća vrijednost broja redaka ili stupaca je tri. Moramo nastaviti.
Sada odabiremo najmanji od nepokrivenih brojeva, u ovom primjeru to su dva (tamnoplava). Oduzimamo ga od prethodnih i dodajemo onima koji se nalaze na mjestu gdje se linije sijeku. U našem slučaju to su još dvije (E3, T1). Preostala nam je nova matrica (korak 4). Precrtamo linije i brojimo. Postoje tri retka, jednaka broju redova ili stupaca. Algoritam je gotov.
Počinjemo s retkom ili stupcem s najmanje nula (E1, T1). Ako je zadatak već dodijeljen, ne može se preraspodijeliti, na primjer, s E2 ne možete koristiti prvu nulu T1, jer je ovaj zadatak dodijeljen E1. Ukupni trošak, prema mađarskoj metodi, bit će zbroj troškova izvorne matrice (korak 1) koja se nalazi na istom položaju kao i odabrane nule (korak 5).