UNKARIN MENETELMÄ: MISTÄ SE KOOSTUU, ESIMERKKI - DUDAS - 2025

Unkarin menetelmä on algoritmi, jota käytetään kohdentamisongelmat kun haluavat minimoida kustannukset. Toisin sanoen sitä käytetään pienimpien kustannusten löytämiseen osoittamalla useita ihmisiä erilaisiin toimintoihin vähiten kustannusten perusteella. Jokainen toiminta on osoitettava eri henkilölle.

Allokointiongelma on erityyppinen lineaarinen ohjelmointiongelma, jonka tavoitteena on minimoida useiden ihmisten töiden suorittamisen kustannukset tai aika.

Lähde: pixabay.com

Yksi allokointiongelman tärkeistä ominaisuuksista on, että koneelle (tai projektille) osoitetaan vain yksi työ (tai työntekijä).

Tämän menetelmän on kehittänyt unkarilainen matemaatikko D. Konig. Tästä syystä se tunnetaan unkarilaisena menetelmänä tehtäväongelmiin. Se tunnetaan myös nimellä Kuhn-Munkres allokaatioalgoritmi.

Mikä tahansa allokaatio-ongelma voidaan helposti ratkaista käyttämällä tätä menetelmää, joka koostuu kahdesta vaiheesta:

- Ensimmäisessä vaiheessa rivinvähennykset ja pylväspelkistykset suoritetaan.

- Toisessa vaiheessa ratkaisu optimoidaan iteratiivisesti.

Mikä on unkarilainen menetelmä?

Unkarin menetelmä koostuu neljästä vaiheesta. Kaksi ensimmäistä vaihetta suoritetaan vain kerran, kun taas vaiheet 3 ja 4 toistetaan, kunnes optimaalinen allokaatio löytyy.

Neliön n: n neliömatriisia pidetään syöttötiedona, jonka tulee sisältää vain ei-negatiivisia elementtejä.

Tietyn ongelman tapauksessa, jos matriisin rivien lukumäärä ei ole yhtä suuri kuin sarakkeiden lukumäärä, tapauskohtaisesti on lisättävä nuken rivi tai tyhjä sarake. Näiden tyhjien solujen allokointikustannukset jaetaan aina nollaksi.

Vaihe 1: vähennä kunkin rivin minimit

Jokaiselle taulukon riville valitaan alimman arvon omaava elementti, joka vähennetään jokaisesta rivin elementistä.

Vaihe 2: vähennä minimivaatimukset jokaisesta sarakkeesta

Samoin kohde, jolla on alhaisin arvo, valitaan jokaiselle sarakkeelle ja vähennetään jokaisesta kyseisen sarakkeen kohdasta.

Vaihe 3: peitä kaikki nollat ​​minimillä riveillä

Kaikki matriisin vaiheesta 2 saadut nollat ​​on peitettävä käyttämällä vähimmäismäärää vaaka- ja pystysuoria viivoja joko riveillä tai sarakkeilla.

Jos kaikkien nullien peittämiseksi vaaditaan yhteensä n riviä, joissa n on yhtä suuri kuin matriisin koko n kertaa n, nollavälien välillä on optimaalinen jako, ja siksi algoritmi pysähtyy.

Muussa tapauksessa, jos kaikkien taulukossa olevien nollakuvien kattamiseksi tarvitaan vähemmän kuin n riviä, jatka vaiheeseen 4.

Vaihe 4: luo ylimääräisiä nollia

Matriisin pienin elementti (nimeltään k), jota ei peitä yksi vaiheessa 3 tehdyistä viivoista, valitaan.

K-arvo vähennetään kaikista elementeistä, joita viivat eivät kata. Myöhemmin ka-arvo lisätään kaikkiin elementteihin, joita kahden viivan leikkaus peittää.

Kohteet, jotka on katettu yhdellä rivillä, jätetään sellaisenaan. Suoritettuaan tämän vaiheen palaat vaiheeseen 3.

Optimaalinen allokaatio

Kun algoritmi on pysäytetty vaiheessa 3, valitaan nollajoukko siten, että jokaisessa rivissä ja jokaisessa sarakkeessa on valittu vain yksi nolla.

Jos tässä valintaprosessissa ei ole yhtä nollaa rivissä tai sarakkeessa, valitaan yksi näistä noloista. Tuon sarakkeen tai rivin jäljellä olevat nollat ​​poistetaan, toistaen samat myös muille tehtäville.

Jos ei ole yhtä nollamääritystä, ratkaisuja on useita. Kustannukset pysyvät kuitenkin samoina erilaisille toimeksiannoille.

Kaikki lisätyt tyhjät rivit tai sarakkeet poistetaan. Tässä lopullisessa matriisissa valitut nollat ​​vastaavat siis alkuperäisessä matriisissa vaadittua ihanteellista määritystä.

esimerkki

Tarkastellaan yritystä, jossa on neljä toimintaa (A1, A2, A3, A4), jotka neljän työntekijän on suoritettava (T1, T2, T3, T4). Yksi toiminta on osoitettava työntekijää kohden.

Seuraava matriisi näyttää tietyn työntekijän tietylle toiminnalle osoittamisen kustannukset. Tavoitteena on minimoida näistä neljästä toiminnasta koostuvan tehtävän kokonaiskustannukset.

Vaihe 1: vähennä kunkin rivin minimit

Aloitat vähentämällä elementin minimiarvolla jokaisessa rivissä kyseisen rivin muista elementeistä. Esimerkiksi ensimmäisen rivin pienin elementti on 69. Siksi 69 vähennetään jokaisesta ensimmäisen rivin elementistä. Tuloksena oleva matriisi on:

Vaihe 2: vähennä minimivaatimukset jokaisesta sarakkeesta

Samalla tavalla elementti, jolla on kunkin sarakkeen minimiarvo, vähennetään sarakkeen muista elementeistä, jolloin saadaan seuraava matriisi:

Vaihe 3: peitä kaikki nollat ​​minimillä riveillä

Nyt määritetään vähimmäisrivimäärä linjoja (vaaka- tai pystysuoria), joita tarvitaan kaikkien matriisin nolla-alueiden peittämiseksi. Kaikki nollat ​​voidaan peittää käyttämällä 3 riviä:

Koska vaadittavien rivien lukumäärä on kolme ja se on pienempi kuin matriisin koko (n = 4), jatkamme vaiheeseen 4.

Vaihe 4: luo ylimääräisiä nollia

Valitaan pienin elementti, jota rivit eivät kata, jonka arvo on 6. Tämä arvo vähennetään kaikista kattelemattomista elementeistä ja sama arvo lisätään kaikkiin elementteihin, joita kahden viivan leikkaus kattaa. Tuloksena on seuraava matriisi:

Kuten Unkarin menetelmässä todetaan, vaihe 3 on suoritettava uudelleen.

Vaihe 3 (toista)

Jälleen määritetään rivien vähimmäismäärä, joka tarvitaan kaikkien matriisin nollakatteiden peittämiseen. Tällä kertaa vaaditaan neljä riviä:

Koska vaadittavien rivien lukumäärä on 4, yhtä suuri kuin matriisin koko (n = 4), meillä on optimaalinen jakauma matriisin nollia välillä. Siksi algoritmi pysähtyy.

Optimaalinen allokaatio

Kuten menetelmä osoittaa, seuraavista noloista tehty valinta vastaa optimaalista määritystä:

Tämä nollavalinta vastaa seuraavaa optimaalista allokaatiota alkuperäisessä kustannusmatriisissa:

Siksi työntekijän 1 on suoritettava aktiviteetti 3, työntekijän 2, aktiviteetin 2, työntekijän 3, toiminnan 1 ja työntekijän 4 suoritettava aktiviteetti 4. Tämän optimaalisen toimeksiannon kokonaiskustannukset ovat 69 + 37 + 11 + 23 = 140.

Viitteet

1. Unkarin algoritmi (2019). Unkarin algoritmi. Otettu: hungarianalgorithm.com.
2. Tutkimus (2019). Unkarin algoritmin käyttö tehtäväongelmien ratkaisemiseksi. Otettu: study.com.
3. Viisauden työpaikat (2018). Unkarilainen menetelmä tehtäväongelman ratkaisemiseksi - kvantitatiiviset tekniikat johtamiseen. Ostettu: wisdomjobs.com.
4. Geekit Geekeille (2019). Unkarilainen algoritmi tehtäväongelmaan. Ostettu: geeksforgeeks.org.
5. Karleigh Moore, Nathan Landman (2019). Unkarin enimmäissovitusalgoritmi. Loistava. Ostettu: brilliant.org.