VENGRŲ METODAS: KĄ JIS SUDARO, PAVYZDYS - DUDAS - 2025

Vengrų metodas yra algoritmas, kuris naudojamas paskirstymo problemas, kai norite sumažinti išlaidas. Tai yra, jis naudojamas norint rasti mažiausią kainą, paskiriant kelis žmones įvairioms veikloms, pagrįstoms mažiausiomis sąnaudomis. Kiekviena veikla turi būti paskirta skirtingam asmeniui.

Paskirstymo problema yra speciali linijinio programavimo problemos rūšis, kurios tikslas yra sumažinti išlaidas ar laiką, reikalingą keliems darbams atlikti keliems žmonėms.

Šaltinis: pixabay.com

Viena iš svarbių paskirstymo problemos savybių yra ta, kad mašinai (ar projektui) priskiriama tik viena užduotis (arba darbuotojas).

Šį metodą sukūrė vengrų matematikas D. Konigas. Dėl šios priežasties jis žinomas kaip vengrų metodas, skirtas užduotims spręsti. Jis taip pat žinomas kaip Kuhn-Munkres paskirstymo algoritmas.

Bet kurią paskirstymo problemą galima lengvai išspręsti taikant šį dviejų etapų metodą:

- Atlikus pirmąjį etapą, mažinamos eilės ir stulpeliai.

- Antrame etape sprendimas optimizuojamas iteraciniu pagrindu.

Koks yra vengriškas metodas?

Vengrų metodas susideda iš keturių pakopų. Pirmieji du veiksmai vykdomi tik vieną kartą, o 3 ir 4 žingsniai kartojami tol, kol randamas optimalus paskirstymas.

N eilės kvadratinė matrica n pagal n yra laikoma įvesties duomenimis, kuriuose turi būti tik neigiami elementai.

Esant konkrečiai problemai, jei eilučių skaičius matricoje nėra lygus stulpelių skaičiui, atsižvelgiant į atvejį, reikia pridėti tuščią eilutę arba tuščią stulpelį. Tų manekenų paskirstymo išlaidos visada paskirstomos kaip nulis.

1 žingsnis: atimkite kiekvienos eilutės minimumus

Kiekvienai masyvo eilutei pasirenkamas mažiausias reikšmes turintis elementas ir atimamas iš kiekvieno tos eilutės elemento.

2 žingsnis: atimkite minimalius dydžius iš kiekvieno stulpelio

Panašiai elementas, kurio vertė yra mažiausia, pasirenkamas kiekvienam stulpeliui ir atimamas iš kiekvieno elemento tame stulpelyje.

3 žingsnis: užrašykite visus nulius su minimaliu eilučių skaičiumi

Visi matricos nuliai, gauti atlikus 2 veiksmą, turi būti uždengti minimaliu horizontalių ir vertikalių linijų skaičiumi - eilutėmis arba stulpeliais.

Jei iš viso nulių padengti reikia n eilučių, kai n yra lygus matricos n dydžiui n ir n, tada gaunamas optimalus nulių paskirstymas, todėl algoritmas sustos.

Priešingu atveju, jei reikia mažiau nei n eilučių, kad būtų uždengti visi nuliai masyve, pereikite prie 4 veiksmo.

4 žingsnis: sukurkite papildomus nulius

Pasirinktas mažiausias matricos elementas (vadinamas k), kurio neapima viena iš 3 žingsnyje padarytų linijų.

K reikšmė atimama iš visų elementų, kurių neapima linijos. Vėliau ka vertė pridedama prie visų elementų, kuriuos dengia dviejų linijų sankirta.

Elementai, apdengti viena eilute, paliekami tokie, kokie yra. Atlikę šį veiksmą, grįšite prie 3 veiksmo.

Optimalus paskirstymas

Sustabdžius algoritmą 3 veiksme, pasirenkamas toks nulis, kad kiekvienoje eilutėje ir stulpelyje būtų pasirinktas tik vienas nulis.

Jei šiame atrankos procese eilutėje ar stulpelyje nėra nė vieno nulio, bus pasirinktas vienas iš tų nulių. Likę toje skiltyje ar eilutėje esantys nuliai yra pašalinti, pakartodami tą patį ir kitoms užduotims.

Jei nėra vieno nulinio priskyrimo, yra keli sprendimai. Tačiau skirtingų užduočių rinkinių kaina išliks ta pati.

Visos pridėtos netikros eilutės ar stulpeliai pašalinami. Taigi šioje galutinėje matricoje pasirinkti nuliai atitinka idealųjį priskyrimą, kurio reikalaujama pradinėje matricoje.

Pavyzdys

Panagrinėkime įmonę, kurioje yra keturios veiklos (A1, A2, A3, A4), kurias turi vykdyti keturi darbuotojai (T1, T2, T3, T4). Vienam darbuotojui turi būti priskirta viena veikla.

Ši matrica parodo tam tikro darbuotojo priskyrimo tam tikrai veiklai išlaidas. Tikslas yra sumažinti visas užduoties, kurią sudaro šios keturios veiklos, išlaidas.

1 žingsnis: atimkite kiekvienos eilutės minimumus

Pradėsite iš kitų tos eilutės elementų atimdami elementą, kurio kiekvienos eilutės vertė yra mažiausia. Pavyzdžiui, mažiausias pirmosios eilutės elementas yra 69. Todėl 69 yra atimamas iš kiekvieno pirmosios eilės elemento. Gauta matrica yra:

2 žingsnis: atimkite minimalius dydžius iš kiekvieno stulpelio

Tuo pačiu būdu elementas, turintis mažiausią kiekvieno stulpelio vertę, yra atimamas iš kitų tos stulpelio elementų, gaunant tokią matricą:

3 žingsnis: užrašykite visus nulius su minimaliu eilučių skaičiumi

Dabar mes nustatysime minimalų eilučių (horizontalių ar vertikalių) skaičių, reikalingą padengti visus nulis nubraižytus matricoje. Visi nuliai gali būti uždengti naudojant 3 eilutes:

Kadangi reikiamų eilučių skaičius yra trys ir jis yra mažesnis už matricos dydį (n = 4), tęsiame 4 žingsnį.

4 žingsnis: sukurkite papildomus nulius

Pasirinktas mažiausias linijų neapimtas elementas, kurio vertė yra 6. Ši vertė yra atimama iš visų neapimtų elementų, o ta pati vertė pridedama prie visų elementų, kuriuos apima dviejų linijų sankirta. Tai lemia tokią matricą:

Kaip nurodyta vengrų metode, reikia dar kartą atlikti trečiąjį veiksmą.

3 veiksmas (pakartokite)

Vėl nustatomas mažiausias linijų skaičius, reikalingas visoms nulio dalims matricoje uždengti. Šį kartą būtinos keturios eilutės:

Kadangi reikiamų eilučių skaičius yra 4, lygus matricos dydžiui (n = 4), mes turime optimalų paskirstymą tarp nulio matricoje. Todėl algoritmas sustoja.

Optimalus paskirstymas

Kaip rodo metodas, šių nulių parinkimas atitinka optimalų priskyrimą:

Šis nulių pasirinkimas atitinka šį optimalų paskirstymą pradinėje išlaidų matricoje:

Todėl 1 darbuotojas privalo vykdyti 3, 2 darbuotojas, 2 veikla, 3 darbuotojas, 1 veikla ir 4 darbuotojas turi atlikti 4 užduotį. Bendros šios optimalios užduoties išlaidos yra 69 + 37 +. 11 + 23 = 140.

Nuorodos

1. Vengrijos algoritmas (2019). Vengrijos algoritmas. Paimta iš: hungarianalgorithm.com.
2. Tyrimas (2019 m.). Vengrijos algoritmo naudojimas užduotims spręsti. Paimta iš: study.com.
3. Išminties darbai (2018). Vengrijos metodas užduoties uždaviniui spręsti - kiekybiniai vadybos metodai. Paimta iš: wisdomjobs.com.
4. Geeks už Geeksą (2019). Vengrijos užduoties uždavinio algoritmas. Paimta iš: geeksforgeeks.org.
5. Karleigh Moore, Nathanas Landmanas (2019). Vengrijos maksimalus atitikimo algoritmas. Nuostabus. Paimta iš: brilliant.org.