Rezolvarea problemei numirii prin metoda maghiară. Un exemplu.
Sarcină: Rezolvați problema numirilor la maxim.
Nu vom da nici o condiție verbală, pot fi diferite, de exemplu "sunt angajați 6 candidați pentru 6 posturi vacante și au primit evaluări corespunzătoare în interviu pentru fiecare post vacant, recrutează candidați pentru șase posturi vacante astfel încât scorul total al candidaților să fie maxim" sau "șase mașini efectuează șase locuri de muncă în timpul specificat în tabel, fac un plan de producție ...". Presupunem că matricea (plata, timpul, etc.) este înaintea noastră și este necesară rezolvarea problemei de atribuire a metodei maghiare la un maxim, adică selectați o celulă pe rând și pe coloană, astfel încât suma să fie maximă.
soluţie:
Pasul 1:
Notă: primul pas este necesar doar pentru a rezolva problema la maxim, dacă aveți nevoie să o rezolvați pentru un minim, apoi săriți-o.
Transformăm matricea, înlocuind fiecare element al matricei cu diferența dintre elementul maxim al acestei linii și elementul însuși.
Este necesar să se obțină zerouri în fiecare rând și în fiecare coloană. În coloanele a treia, a cincea și a șasea nu există niciun zer, scăpăm din elementele acestor coloane elementul minim al coloanei corespunzătoare.
Am obținut o matrice în care fiecare rând și fiecare coloană au zero. Scopul nostru este de a marca o celulă în fiecare rând și fiecare coloană, astfel încât acestea să fie zero. În această matrice numai primele patru rânduri și coloane îndeplinesc această cerință. Marcați celulele potrivite cu un cadru.
Notați ca o "linie nemulțumită", a 5-a, în care nu am putut nota un astfel de zero și a doua coloană, conține zero în linia a cincea. Dar a doua coloană conține, de asemenea, zero în prima linie, notează-l ca fiind "nefericit". Prima linie de zerouri nu mai conține; procesul de marcare a liniilor neplăcute sa încheiat și am primit o situație numită "strangulare".
În tabel vom marca rândurile și coloanele neplăcute cu asteriscuri, iar numărul de lângă asterisc va însemna ordinea marcajului (pentru o mai bună înțelegere a procesului).
Selectați elementul minim în rândurile marcate în afara rândurilor marcate. Acesta este 3, care se află în a cincea coloană și a cincea coloană.
Extrageți acest element din rândurile marcate și adăugați-l în coloanele care rezultă.
Efectuați acțiunile, rețineți că acum puteți marca un zero în al cincilea rând și în a cincea coloană.
Nu este suficient zero în linia a șasea. Rețineți că este nefericită, are zero în prima coloană, o marchează ca nemulțumită, ea, la rândul ei, conține zero în a doua linie, notează-o, dar nu conține mai multe zerouri, procesul de marcare este legal.
Selectăm elementul minim în rândurile marcate în afara coloanelor marcate. Acesta este elementul 2 în rândul al șaselea și în a șasea coloană. Extrageți cei doi de la cea de-a doua și a șasea și apoi adăugați-o în prima coloană.
Să realizăm acțiunile. Rețineți că acum putem nota încă zero.
Am obținut o matrice cu șase zerouri, câte unul în fiecare rând și coloană, prin urmare, pot fi făcute misiuni (distribuția lucrărilor etc.) de-a lungul matricei:
Iar costul (raționalitatea, timpul de lucru etc.) al unei astfel de desemnări va fi:
Articole similare
Trimiteți-le prietenilor: