Unkarilainen menetelmä on algoritmi, jonka avulla voidaan minimoida kustannukset lineaariseen ohjelmointiin perustuvassa optimointiongelmassa.
Unkarilaisen menetelmän tarkoituksena on löytää vähimmäiskustannukset joukosta tehtäviä, jotka on suoritettava sopivimmille ihmisille.
Se käyttää lineaarista ohjelmointia (PL) automatisoitavien vaiheiden suorittamiseen. Siten työkaluilla, kuten tilasto-ohjelmisto R (muun muassa), on useita erittäin hyödyllisiä paketteja näihin optimointiongelmiin.
Unkarilaisen menetelmän alkuperä
Sen luoja oli unkarilainen matemaatikko (tästä nimi) Harold W. Kuhn vuonna 1955. Toinen matemaatikko, James Munkres, tarkisti sen vuonna 1957. Tämän evoluution myötä se on saanut muita nimiä, kuten Munkres- tai Kuhn-Munkres-allokointialgoritmin.
Toisaalta tällä menetelmällä on ennakkotapaus kahdessa kirjoittajassa, Dénes König ja Jenő Egerváry, sekä juutalaisissa että unkarilaisissa. Ensimmäinen kehitti graafiteorian, johon tämä algoritmi perustuu. Toinen yleisti Königin lauseen ja antoi Kuhnille mahdollisuuden kehittää menetelmää.
Unkarin menetelmän vaiheet
Seuraavat vaiheet mahdollistavat unkarilaisen menetelmän toteuttamisen yksinkertaisella tavalla laskentataulukon avulla. Tämän osoittamamme järjestelmän avulla voimme lisäksi nähdä prosessin, jonka kehitämme yksityiskohtaisesti viimeisessä esimerkissä.
- Alustavina vaiheina sinun on määritettävä ihmiset (rivit) projektisarjaan (sarakkeet). Lisäksi on tarpeen laskea kunkin projektin erilaiset kustannukset sen mukaan, kuka sen toteuttaa, ja rakentaa matriisi (C) näillä tiedoilla.
- Etsimme matriisista (C) kunkin rivin vähimmäisarvoa. Vähennämme tämän rivin kaikista elementeistä ja teemme saman toiminnon sarakkeiden kanssa. Uusi matriisi (C`) ilmestyy edellisten operaatioiden tuloksiin.
- Seuraavaksi luodaan «tasa-arvokaavio», jonka avulla voimme valita alhaisimpien tehtävien ja projektien. Optimaaliset olisivat ne elementit, joiden tulos olisi nolla. Jos on totta, että ei ole elementtiä, jonka nolla-arvo olisi määritetty useammalle kuin yhdelle riville, algoritmi päättyy.
- Muussa tapauksessa on tehtävä uusi tehtävä. Tehdään uusi matriisi, johon sovelletaan sarjaa modifikaatioita, kuten näemme esimerkissä. Luomme kaavion uudelleen ja jatkamme, kunnes meillä on matriisi, jossa on vähintään yksi nolla kullakin rivillä ja toistumattomissa paikoissa.
- Tämän tiedon avulla meillä on jo määritetyt ihmiset ja projektit (nollat), jotka optimoivat ongelman. Jos tehtävä on jo määritetty edelliselle riville, se hylätään seuraavalla. Vähimmäiskustannusten laskemiseksi lisätään näiden nollien sijasta näkyvät alkumatriisin kustannukset.
Esimerkki unkarilaisesta menetelmästä
Katsotaanpa yksinkertaista esimerkkiä unkarilaisesta menetelmästä. Kuvitellaan, että meillä on kolme työntekijää ja heidät on osoitettava kolmeen projektiin. Luomme alkumatriisin (C) ja kustannusarvot kuhunkin soluun. Tätä varten sinun on käytettävä yrityksessä saatavilla olevia tietoja. Kun meillä on kaikki tämä, aloitamme prosessin. Laskentataulukko voi auttaa.
Laskemme kunkin rivin minimiarvot ja vähennämme ne kyseisen rivin elementeistä ja teemme samoin sarakkeiden kanssa (vaiheet 1 ja 2). Tuloksena olevassa matriisissa (C`) piirrämme viivoja siten, että ne peittävät kaikki nollat ja leikkaavat puolestaan toisiaan (vaihe 3). Rivejä on kaksi, mutta rivien tai sarakkeiden lukumäärän suurin arvo on kolme. Meidän on jatkettava.
Nyt valitsemme pienimmän paljastamattomista numeroista, tässä esimerkissä se on kaksi (tummansininen). Vähennämme sen edellisistä ja lisätään niihin, jotka sijaitsevat viivojen leikkauspisteessä. Meidän tapauksessamme se on vielä kaksi (E3, T1). Meille jää uusi matriisi (vaihe 4). Piirrämme viivat uudelleen ja laskemme. Rivejä on kolme, sama kuin rivien tai sarakkeiden määrä. Algoritmi on valmis.
Aloitetaan rivillä tai sarakkeella, jolla on vähiten nollia (E1, T1). Jos tehtävä on jo määritetty, sitä ei voida määrittää uudelleen, esimerkiksi E2: n kanssa et voi käyttää T1: n ensimmäistä nollaa, koska tämä tehtävä on osoitettu E1: lle. Kokonaiskustannukset ovat unkarilaisessa menetelmässä alkuperäisen matriisin (vaihe 1) kustannusten summa, joka sijaitsee samassa paikassa kuin valitut nollat (vaihe 5).