Vengrų metodas yra algoritmas, leidžiantis sumažinti sąnaudas optimizavimo problemoje, pagrįstoje tiesiniu programavimu.
Vengrijos metodo tikslas yra rasti mažiausią užduočių, kurias turi atlikti tinkamiausi žmonės, rinkinį.
Jis naudoja linijinį programavimą (PL), kad atliktų veiksmus, kuriuos galima automatizuoti. Taigi tokie įrankiai kaip statistinė programinė įranga R (be kita ko) turi keletą labai naudingų paketų šioms optimizavimo problemoms spręsti.
Vengrijos metodo kilmė
Jo kūrėjas buvo Vengrijos matematikas (taigi ir jo vardas) Haroldas W. Kuhnas 1955 m. Kitas matematikas Jamesas Munkresas jį pataisė 1957 m. Su šia evoliucija jis gavo kitus pavadinimus, tokius kaip Munkres arba Kuhn-Munkres paskirstymo algoritmas.
Kita vertus, šis metodas turi dviejų žydų ir vengrų autorių - Dénes König ir Jenő Egerváry - precedentą. Pirmasis sukūrė grafikų teoriją, kuria grindžiamas šis algoritmas. Antrasis apibendrino Königo teoremą ir leido Kuhnui sukurti metodą.
Vengrijos metodo žingsniai
Veiksmai, kuriuos reikia atlikti, leidžia paprastu būdu atlikti Vengrijos metodą naudojant skaičiuoklę. Be to, ši schema, kurią mes parodysime, leis mums globaliai pamatyti procesą, kurį mes išsamiai plėtosime paskutiniame pavyzdyje.
- Kaip išankstinius veiksmus turite priskirti žmones (eilutes) prie projektų (stulpelių) serijos. Be to, reikia apskaičiuoti skirtingas kiekvieno projekto išlaidas, atsižvelgiant į tai, kas jį vykdo, ir su šia informacija susikurti matricą (C).
- Matricoje (C) ieškome minimalios kiekvienos eilutės vertės. Tai atimame iš visų eilutės elementų ir atliekame tą pačią operaciją su stulpeliais. Bus rodoma nauja matrica (C`) su ankstesnių operacijų rezultatais.
- Tada sukursime «lygybės grafiką», kuris leidžia mums pasirinkti užduotis ir projektus su mažiausiomis sąnaudomis. Optimaliausia būtų tie elementai, kurių rezultatas būtų lygus nuliui. Jei tiesa, kad nėra elemento, kurio nulinė vertė būtų priskirta daugiau nei vienai eilutei, algoritmas baigiasi.
- Priešingu atveju reikia atlikti naują užduotį. Padaroma nauja matrica, kuriai taikoma modifikacijų serija, kaip matysime pavyzdyje. Atkuriame grafiką ir tęsiame tol, kol turime matricą, kurios kiekvienoje eilutėje yra bent vienas nulis ir nesikartojančiose pozicijose.
- Turėdami šią informaciją jau turime priskirtus žmones ir projektus (nulius), kurie optimizuoja problemą. Jei užduotis jau priskirta ankstesnėje eilutėje, ji atmetama kitoje. Norėdami apskaičiuoti mažiausią kainą, pridedame pradinės matricos sąnaudas, kurios atsiranda šių nulių padėtyje.
Vengrijos metodo pavyzdys
Pažvelkime į paprastą Vengrijos metodo pavyzdį. Įsivaizduokime, kad turime tris darbuotojus ir juos reikia skirti trims projektams. Kiekvienoje ląstelėje sukuriame pradinę matricą (C) ir sąnaudų vertes. Tam turite naudoti įmonėje esančią informaciją. Kai visa tai turėsime, mes pradėsime procesą. Padėti gali skaičiuoklė.
Apskaičiuojame kiekvienos eilutės minimumus ir atimame juos iš tos eilutės elementų ir darome tą patį su stulpeliais (1 ir 2 žingsniai). Gautoje matricoje (C`) brėžiame linijas taip, kad jos apimtų visus nulius ir savo ruožtu susikertų viena kitą (3 žingsnis). Matome, kad yra dvi eilutės, tačiau didžiausia eilučių ar stulpelių skaičiaus vertė yra trys. Turime tęsti.
Dabar mes pasirenkame mažiausią iš neuždengtų skaičių, šiame pavyzdyje tai du (tamsiai mėlyni). Atimame jį iš ankstesnių ir pridedame prie tų, kurie yra tiesių susikirtimo vietoje. Mūsų atveju tai dar du (E3, T1). Mums lieka nauja matrica (4 žingsnis). Piešiame linijas ir skaičiuojame. Yra trys eilutės, tokios pačios kaip eilučių ar stulpelių skaičius. Algoritmas baigtas.
Mes pradedame nuo eilutės ar stulpelio, kuriame yra mažiausiai nulių (E1, T1). Jei užduotis jau priskirta, jos negalima iš naujo priskirti, pavyzdžiui, naudojant E2, negalite naudoti pirmojo T1 nulio, nes ši užduotis buvo priskirta E1. Bendra kaina Vengrijos metodu bus pradinės matricos (1 žingsnis), esančios toje pačioje padėtyje kaip ir pasirinktos nulio, išlaidų suma (5 žingsnis).