Problemă generalizată de atribuire

În matematică aplicată , o problemă de atribuire generalizată este înțeleasă ca o problemă de optimizare combinatorie , care este o generalizare a problemei de atribuire , în care mulțimea de executanți are o dimensiune care nu este neapărat egală cu dimensiunea setului de locuri de muncă. În acest caz, executantul poate fi desemnat să execute orice lucrare (nu neapărat o singură lucrare, ca în problema de atribuire). Atunci când atribuiți un executant să execute lucrări, sunt stabilite două valori - costurile și veniturile. Fiecare interpret are un anumit buget, astfel încât suma tuturor costurilor nu trebuie să depășească acest buget. Este necesar să se găsească o astfel de încadrare a artiștilor executanți pentru a presta munca pentru a maximiza veniturile.

Ocazii speciale

În cazul în care bugetele executanților și toate costurile muncii sunt egale cu 1, problema se transformă în problema de potrivire maximă .

Dacă prețurile și veniturile pentru toate sarcinile sunt egale, problema se reduce la un rucsac multiplicativ .

Dacă există un singur agent, problema se reduce la problema rucsacului .

Definiție

Există n locuri de muncă și m performeri . Fiecare interpret are un buget . Pentru fiecare pereche de interpret și muncă, sunt date venitul și ponderea . Soluția este un subset de locuri de muncă U și o distribuție a locurilor de muncă din U între performeri. Decizia este acceptabilă dacă valoarea costurilor pentru munca atribuită interpretului nu depășește bugetul . Venitul din decizie este suma tuturor veniturilor tuturor repartizărilor de muncă-executor. $x_{1},\dots,x_{n)$ $b_{1},\dots,b_{m)$ $b_{i}$ $w_{i}$ $b_{i}$ $x_{j}$ $p_{i,j}$ $w_{i,j}$ $b_{i}$ $w_{i}$

Din punct de vedere matematic, problema de atribuire generalizată poate fi formulată după cum urmează:

maximiza

\sum _{i=1}^{m}\sum _{j=1}^{n}p_{ij}x_{ij}.

supus ;

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

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

;

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

;

Problema generalizată de atribuire este NP-hard și chiar APX-hard .

Fleischer, Gomans, Mirokni și Sviridenko au propus un algoritm de căutare locală combinatorie cu aproximare și un algoritm bazat pe programare liniară cu aproximare [1] . $(2+\varepsilon )$ $({\frac {e}{e-1}}+\varepsilon )$

Aproximarea este cea mai cunoscută aproximare a problemei de atribuire generalizată. $({\frac {e}{e-1}}+\epsilon )$

Algoritmul de aproximare Greedy

Folosind problema de atribuire -algoritm de aproximare, se poate crea o ( ) -aproximare pentru problema de atribuire generalizată în maniera unui algoritm lacom folosind conceptul de venit rezidual. Algoritmul creează în mod iterativ o secvență preliminară în care se presupune că trebuie să atribuie lucru executantului la iterație . Alegerea interpretului poate fi modificată ulterior, atunci când atribuiți lucrări altor interpreți. Venitul rămas din muncă pentru executant este , dacă lucrarea nu este dată altui executant și - dacă lucrarea este dată executantului . $\alfa$ $\alpha +1$ $j$ $B j}$ $B j}$ $x_{i}$ $B j}$ $p_{{ij}}$ $x_{i}$ $p_{ij}$ $p_{ik)$ $b_{k}$

Oficial:

Folosiți vector pentru preselecție și în acest vector $T$

T[i]=j

înseamnă că trebuie să atribuie un executant lucrării ,

x_{i}

B j}

T[i]=-1

înseamnă că nimeni nu a fost repartizat la locul de muncă.

x_{i}

Venitul rămas pe iterație este notat cu , unde $j$ $Pijamale}$

P_{j}[i]=p_{ij)

dacă nu este selectat niciun loc de muncă (adică )

x_{i}

T[i]=-1

P_{j}[i]=p_{ij}-p_{ik)

, dacă lucrarea ar trebui să fie dată interpretului (adică ).

x_{i}

b_{k}

T[i]=k

Deci algoritmul arată astfel:

Valori inițiale atribuite pentru toți

T[i]=-1

i=1\ldots n

Pentru toată lumea , faceți:

j=1...m

Un algoritm de aproximare este utilizat pentru a obține distribuția muncii pentru antreprenor folosind funcția venit rezidual . Sunt indicate lucrările selectate .

B j}

Pijamale}

S_j

Corectat folosind , adică pentru toți .

T

S_j

T[i]=j

i\in S_{j}

sfârşitul ciclului

Vezi și

Problemă de atribuire

Note

↑ L. Fleischer, MX Goemans, VS Mirrokni și M. Sviridenko. Algoritmi strânși de aproximare pentru probleme generale maxime de atribuire. În SODA'06: Proc

Link -uri

Reuven Cohen, Liran Katzir și Danny Raz, „O aproximare eficientă pentru problema generalizată de atribuire” , scrisori de procesare a informațiilor, vol. 100, numărul 4, pp. 162–166, noiembrie 2006.
Lisa Fleischer, Michel X. Goemans, Vahab S. Mirrokni și Maxim Sviridenko, „Tight Approximation Algorithms for Maximum General Assignment Problems” , SODA 2006, pp. 611–620.
Hans Kellerer, Ulrich Pferschy, David Pisinger, Probleme la rucsac , 2005. Springer Verlag ISBN 3-540-40286-1