Madžarska metoda je algoritem, ki omogoča zmanjšanje stroškov pri optimizacijskem problemu, ki temelji na linearnem programiranju.
Cilj madžarske metode je najti minimalne stroške sklopa nalog, ki jih morajo opraviti najprimernejši ljudje.
Uporablja linearno programiranje (PL) za izvajanje vrste korakov, ki jih je mogoče avtomatizirati. Tako imajo orodja, kot je statistična programska oprema R (med drugim), nekaj zelo uporabnih paketov za te optimizacijske probleme.
Izvor madžarske metode
Njegov ustvarjalec je bil madžarski matematik (od tod tudi ime) Harold W. Kuhn leta 1955. Drugi matematik, James Munkres, ga je revidiral leta 1957. S tem razvojem je dobil druga imena, kot sta Munkres ali Kuhn-Munkresov algoritem za dodeljevanje.
Po drugi strani pa ima ta metoda precedens pri dveh avtorjih, Dénesu Königu in Jenő Egerváryju, tako Judov kot Madžarov. Prvi je razvil teorijo grafov, na kateri temelji ta algoritem. Drugi je posplošil Königov izrek in Kuhnu omogočil razvoj metode.
Koraki madžarske metode
Koraki, ki jih je treba upoštevati, omogočajo izvedbo madžarske metode na preprost način s pomočjo preglednice. Poleg tega nam bo ta shema, ki jo prikazujemo, omogočila, da na globalni način vidimo proces, ki ga bomo podrobno razvili v zadnjem primeru.
- Kot predhodni korak morate dodeliti ljudi (vrstice) vrsti projektov (stolpce). Poleg tega je treba izračunati različne stroške posameznega projekta, odvisno od tega, kdo ga izvaja, in zgraditi matriko (C) s temi podatki.
- V matriki (C) iščemo najmanjšo vrednost vsake vrstice. To odštejemo od vseh elementov v vrstici in izvedemo enako operacijo s stolpci. Pojavila se bo nova matrica (C`) z rezultati prejšnjih operacij.
- Nato izdelamo «graf enakovrednosti», ki nam omogoča izbiro nalog in projektov z najnižjimi stroški. Optimalno bi bili tisti elementi, katerih rezultat je bil nič. Če je res, da ni elementa z ničelno vrednostjo, dodeljeno več kot eni vrstici, se algoritem konča.
- V nasprotnem primeru je treba določiti novo nalogo. Narejena je nova matrica, na katero je uporabljena vrsta sprememb, kot bomo videli v primeru. Ustvarimo graf in nadaljujemo, dokler ne dobimo matrike, ki ima v vsaki vrstici in v ponavljajočih se položajih vsaj eno ničlo.
- S temi informacijami že imamo dodeljene ljudi in projekte (ničle), ki optimizirajo težavo. Če je naloga že dodeljena v prejšnji vrstici, jo v naslednji zavržemo. Za izračun minimalnih stroškov dodamo stroške začetne matrice, ki se pojavijo na položaju teh ničel.
Primer madžarske metode
Oglejmo si preprost primer madžarske metode. Predstavljajmo si, da imamo tri delavce in jih je treba razporediti v tri projekte. V vsaki celici ustvarimo začetno matrico (C) in vrednosti stroškov. Za to morate uporabiti informacije, ki so na voljo v podjetju. Ko imamo vse to, začnemo postopek. Preglednica vam lahko pomaga.
Izračunamo minimume vsake vrstice in jih odštejemo od elementov te vrstice ter storimo enako s stolpci (koraka 1 in 2). V nastalo matrico (C`) narišemo črte tako, da pokrivajo vse ničle in se nato sekajo (korak 3). Vidimo, da sta dve vrstici, vendar je največja vrednost števila vrstic ali stolpcev tri. Moramo nadaljevati.
Zdaj izberemo najmanjše izmed nepokritih številk, v tem primeru je dve (temno modra). Odštejemo ga od prejšnjih in dodajamo tistim, ki se nahajajo tam, kjer se črte sekajo. V našem primeru gre za še dve (E3, T1). Preostala nam je nova matrica (korak 4). Prerisujemo črte in štejemo. Obstajajo tri vrstice, enako številu vrstic ali stolpcev. Algoritem je končan.
Začnemo z vrstico ali stolpcem z najmanj ničlami (E1, T1). Če je naloga že dodeljena, je ni mogoče dodeliti, na primer pri E2 ne morete uporabiti prve ničle T1, ker je bila ta naloga dodeljena E1. Skupni stroški bodo po madžarski metodi vsota stroškov prvotne matrike (1. korak), ki se nahaja na istem položaju kot izbrane ničle (5. korak).