Problema atribuirii numărului minim de executori

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 15 august 2017; verificările necesită 6 modificări .

În matematica aplicată , sarcina de a atribui un număr minim de executanți este înțeleasă ca o problemă de optimizare combinatorie care generalizează problema acoperirii unei mulțimi și este similară în formulare cu problema de atribuire .

În această problemă, setul de muncitori are o dimensiune nu neapărat egală cu dimensiunea setului de locuri de muncă. În acest caz, un executant poate fi desemnat să execute mai multe lucrări în același timp și pentru fiecare job îi este alocat un singur executor. Există un buget total pentru execuția tuturor activităților, care este constrângerea de atribuire. Este necesar să se găsească o astfel de numire a artiștilor interpreți sau executanți pentru efectuarea lucrărilor astfel încât numărul de artiști interpreți sau executanți implicați în executarea lucrărilor să fie minim și să nu depășească bugetul alocat pentru întregul complex de lucrări.

Definiție

Există n interpreți și m locuri de muncă. Pentru fiecare pereche de interpret și lucrare, se indică costul executării lucrării . Există un buget general pentru realizarea întregului complex de lucrări. Soluția este un subset de executanți U și repartizarea sarcinilor executanților din U între joburi. Decizia este acceptabilă dacă sunt desemnați executanți pentru toate lucrările și valoarea costurilor pentru aceasta nu depășește bugetul . Este necesar să se minimizeze numărul de interpreți alocați ( L ). Cu alte cuvinte, este necesar să se aleagă setul minim (din punct de vedere al puterii) de interpreți care împreună pot executa toată munca. $w_{i,j}$ $w$ $w$

Problema poate fi rezolvată împărțind-o în două probleme:

Selectarea numărului minim de interpreți care împreună vor putea finaliza toate lucrările și vor îndeplini bugetul . Această problemă este NP-grea din moment ce este o generalizare a problemei de acoperire a multimii NP-complete . $w$
Numire într-un grup selectat de interpreți pentru muncă.

Din punct de vedere matematic, problema atribuirii numărului minim de interpreți poate fi formulată astfel [1] :

minimiza

L=\mid U\mid =\sum _{i=1}^{n}\max _{j=1}^{m}x_{ij)

supusă

\sum _{i=1}^{n}\sum _{j=1}^{m}w_{ij}x_{ij}\leq w.

\sum _{i=1}^{n}x_{ij}=1\qquad j=1,\ldots ,m

;

x_{ij}\in \{0,1\}\qquad i=1,\ldots, n,\quad j=1,\ldots,m

În această setare, funcția obiectiv a problemei este neliniară, ceea ce nu vă permite să găsiți direct soluția optimă folosind metode exacte de programare liniară , inclusiv metoda simplex . Totuși, sarcina poate fi liniarizată prin includerea unor variabile suplimentare , arătând faptul selecției în grupul executantului , . De asemenea, trebuie să legați variabile și . Apoi funcția obiectiv va lua forma $y_{i)$ $i$ $y_{i}\in \{0,1\}\qquad i=1,\ldots ,n$ $y_{i)$ $x_{ij}$

minimiza .

L=\mid U\mid =\sum _{i=1}^{n}y_{i)

Conexiunea variabilelor poate fi specificată prin următoarea condiție:

y_{i}\leq \sum _{j=1}^{m}x_{ij}\leq my_{i}\qquad i=1,\ldots ,n

Algoritmi aproximativi

Pentru rezolvarea rapidă a problemelor de dimensiuni mari, este indicat să folosiți algoritmi aproximativi: algoritmul numărului maxim de elemente minime (MCME) și algoritmul numărului maxim de elemente admisibile (MCDE) [2] .

Vezi și

Note

↑ Kataev A.V., Kataeva T.M., Kozhenko Ya.V. Kataev A. V., Kataeva T. M., Kozhenko Ya. V. Optimizarea dimensiunii echipei de proiect: instrumente economice și matematice // Competitivitate în lumea globală: economie, știință, tehnologie. 2016. - Nr. 8-3 (22). – p. 101-104
↑ Kataev A.V., Kataeva T.M. Management de proiect bazat pe o rețea dinamică de parteneri: monografie. - Rostov-pe-Don - Taganrog: Editura Universității Federale de Sud, 2017. - 125 p.