Problemă de atribuire

Problemele de atribuire (sau problemele de atribuire ) sunt acele probleme de cercetare operațională în care trebuie să atribuiți diferite sarcini într-un mod optim.

Problema de atribuire este considerată o problemă ușoară, chiar dacă este o problemă combinatorie și, în general, astfel de probleme sunt NP-hard , adică dificil de rezolvat. Cu toate acestea, aceasta este una dintre problemele particulare care se bucură de proprietatea integralității și, de fapt, nu este altceva decât o problemă particulară a fluxului de cost minim .

Aceasta este o problemă de importanță fundamentală în optimizarea combinatorie, deoarece se găsește adesea în structura unor probleme mai complexe: adică problemele de aplicație sunt adesea o problemă de atribuire cu constrângeri suplimentare. În acest fel - prin așa-numitele tehnici de relaxare - algoritmii studiați pentru această problemă pot fi folosiți pentru a rezolva problema inițială.

Formulare

O problemă de atribuire este definită pe un grafic bipartit sau un grafic $G=(N,A)$ ${\ displaystyle G = (N, A)}$ ${\ displaystyle G = (N, A)}$ unde este $N=N_{1}\cup N_{2}$ ${\ displaystyle N = N_ {1} \ cup N_ {2}}$ ${\ displaystyle N = N_ {1} \ cup N_ {2}}$ Și $A\subseteq N_{1}\times N_{2}$ ${\ displaystyle A \ subseteq N_ {1} \ times N_ {2}}$ ${\ displaystyle A \ subseteq N_ {1} \ times N_ {2}}$ . La fiecare arc $(i,j)\in A$ ${\ displaystyle (i, j) \ în A}$ ${\ displaystyle (i, j) \ în A}$ este asociat un cost $c_{i,j}$ ${\ displaystyle c_ {i, j}}$ ${\ displaystyle c_ {i, j}}$ ; doriți să găsiți cel mai mic cost alocat; acesta este întregul $B\subseteq A$ ${\ displaystyle B \ subseteq A}$ $B \ subseteq A$ astfel încât

$B={\mbox{argmin}}\{C(A^{'}):A^{'}\subset A,\quad \forall i\in N_{1}:\,\exists j\in N_{2}:\quad (i,j)\in A^{'}\forall j\in N_{2}:\,\exists i\in N_{1}:\quad (i,j)\in A^{'}\}$ ${\ displaystyle B = {\ mbox {argmin}} \ {C (A ^ {'}): A ^ {'} \ subset A, \ quad \ forall i \ în N_ {1}: \, \ există j \ în N_ {2}: \ quad (i, j) \ în A ^ {'} \ forall j \ în N_ {2}: \, \ există i \ în N_ {1}: \ quad (i, j) \ în A ^ {'} \}}$ ${\ displaystyle B = {\ mbox {argmin}} \ {C (A ^ {'}): A ^ {'} \ subset A, \ quad \ forall i \ în N_ {1}: \, \ există j \ în N_ {2}: \ quad (i, j) \ în A ^ {'} \ forall j \ în N_ {2}: \, \ există i \ în N_ {1}: \ quad (i, j) \ în A ^ {'} \}}$ ,

Și $C(A^{'})=\sum _{(i,j)\in A^{'}}c_{i,j}$ ${\ displaystyle C (A ^ {'}) = \ sum _ {(i, j) \ in A ^ {'}} c_ {i, j}}$ ${\ displaystyle C (A ^ {'}) = \ sum _ {(i, j) \ in A ^ {'}} c_ {i, j}}$ .

Următoarea este una dintre formulările posibile din programarea liniară :

$\min \sum _{(i,j)\in A}c_{i,j}x_{i,j}$ ${\ displaystyle \ min \ sum _ {(i, j) \ în A} c_ {i, j} x_ {i, j}}$ ${\ displaystyle \ min \ sum _ {(i, j) \ în A} c_ {i, j} x_ {i, j}}$
astfel încât:
$\sum _{(i,j)\in A}x_{i,j}=1$ ${\ displaystyle \ sum _ {(i, j) \ in A} x_ {i, j} = 1}$ ${\ displaystyle \ sum _ {(i, j) \ in A} x_ {i, j} = 1}$	$\forall i\in N_{1}$ ${\ displaystyle \ forall i \ în N_ {1}}$ ${\ displaystyle \ forall i \ în N_ {1}}$
$\sum _{(i,j)\in A}x_{i,j}=1$ ${\ displaystyle \ sum _ {(i, j) \ in A} x_ {i, j} = 1}$ ${\ displaystyle \ sum _ {(i, j) \ in A} x_ {i, j} = 1}$	$\forall j\in N_{2}$ ${\ displaystyle \ forall j \ în N_ {2}}$ ${\ displaystyle \ forall j \ în N_ {2}}$
$x_{i,j}\in {0,1}$ ${\ displaystyle x_ {i, j} \ în {0,1}}$ ${\ displaystyle x_ {i, j} \ în {0,1}}$	$\forall (i,j)\in A$ ${\ displaystyle \ forall (i, j) \ în A}$ ${\ displaystyle \ forall (i, j) \ în A}$

Prin urmare, problema apare ca o problemă de programare liniară întreagă ; cu toate acestea, poate fi redefinită ca o problemă a fluxului de cost minim (care poate fi rezolvată prin relaxare continuă și, prin urmare, în programarea liniară ). Prin urmare, nu este surprinzător faptul că, deși aceasta este o problemă combinatorie, aceasta poate fi rezolvată în timp polinomial .

Rezoluție tipică

Problema de bază este de a găsi o repartizare între activități (producători) - resurse (clienți) la cel mai mic cost.

Probleme de atribuire a cercetării operaționale.png

Mai întâi trebuie să creăm un tabel care să raporteze costurile între activități și resurse. Indicăm cu A1, A2, A3, A4, ..., $A_{n}$ ${\ displaystyle A_ {n}}$ $A_ {n}$ activități și cu R1, R2, R3, R4, ..., $R_{n}$ ${\ displaystyle R_ {n}}$ $R_ {n}$ resurse. În celelalte casete indicăm costul fiecărei misiuni (referitor la o anumită resursă și la o anumită activitate).

	A1	A2	A3	A4
R1	5	8	3	4
R2	11	12	18	13
R3	7	7	20	20
R4	10	9	9	8

Primul pas constă în scăderea din fiecare rând a valorii sale minime (numită, de fapt, minimă a rândului). În practică, luând în considerare rândul relativ la R1, căutăm valoarea minimă a acelui rând, adică 3 și o scădem din fiecare casetă întotdeauna relativă la primul rând. La fel se procedează și cu celelalte rânduri, scăzând 11 din al doilea, 7 din al treilea și 8 din ultimul, obținând un nou tabel.

	A1	A2	A3	A4
R1	2	5	0	1
R2	0	1	7	2
R3	0	0	13	13
R4	2	1	1	0

Din acest ultim tabel obținut considerăm casetele care conțin valoare (cost) zero și încercăm, pe baza acestora, să atribuim o activitate fiecărei resurse astfel încât costul (raportat la acest ultim tabel) să fie zero.

În cazul nostru putem considera problema încheiată deoarece este posibil să atribuim fiecare coloană A unui rând R păstrând costul relativ zero. Dacă nu ar fi fost cazul, am fi procedat, în mod similar, cu scăderea valorii minime a coloanei (a se vedea exemplul următor). Practic:

\left.{\begin{array}{l}A3-R1\\A1-R2\\A2-R3\\A4-R4\end{array}}\right\}{\text{costi relativi all'ultima tabella}}=0

{\ displaystyle \ left. {\ begin {array} {l} A3-R1 \\ A1-R2 \\ A2-R3 \\ A4-R4 \ end {array}} \ right \} {\ text {costuri legate de 'ultimul tabel}} = 0}

{\ displaystyle \ left. {\ begin {array} {l} A3-R1 \\ A1-R2 \\ A2-R3 \\ A4-R4 \ end {array}} \ right \} {\ text {costuri legate de 'ultimul tabel}} = 0}

Notă: Nu am atribuit A1-R3, altfel nu am mai fi putut atribui A1-R2.

Pentru a găsi costul real legat de această sarcină, trebuie să luăm în considerare și tabelul de pornire cu costurile aferente (păstrând întotdeauna sarcinile tocmai găsite). Prin urmare, obținem:

\left.{\begin{array}{l}A3-R1\Rightarrow {\text{costo}}=3\\A1-R2\Rightarrow {\text{costo}}=11\\A2-R3\Rightarrow {\text{costo}}=7\\A4-R4\Rightarrow {\text{costo}}=8\end{array}}\right\}{\text{costi effettivi (relativi alla prima tabella)}}

{\ displaystyle \ left. {\ begin {array} {l} A3-R1 \ Rightarrow {\ text {cost}} = 3 \\ A1-R2 \ Rightarrow {\ text {cost}} = 11 \\ A2-R3 \ Rightarrow {\ text {cost}} = 7 \\ A4-R4 \ Rightarrow {\ text {cost}} = 8 \ end {array}} \ right \} {\ text {costuri reale (relativ la primul tabel) }}}

{\ displaystyle \ left. {\ begin {array} {l} A3-R1 \ Rightarrow {\ text {cost}} = 3 \\ A1-R2 \ Rightarrow {\ text {cost}} = 11 \\ A2-R3 \ Rightarrow {\ text {cost}} = 7 \\ A4-R4 \ Rightarrow {\ text {cost}} = 8 \ end {array}} \ right \} {\ text {costuri reale (relativ la primul tabel) }}}

Evident, costul total al misiunii este dat de suma costurilor parțiale tocmai găsite: $C=3+11+7+8=29$ ${\ displaystyle C = 3 + 11 + 7 + 8 = 29}$ ${\ displaystyle C = 3 + 11 + 7 + 8 = 29}$

Exemplu rezolvat

Masa de pornire:

	A1	A2	A3	A4
R1	4	2	2	3
R2	5	6	4	7
R3	8	11	13	9
R4	1	2	3	4

Al doilea tabel obținut prin scăderea minimului rândului:

	A1	A2	A3	A4
R1	2	0	0	1
R2	1	2	0	3
R3	0	3	5	1
R4	0	1	2	3

Cu acest tabel este imposibil să atribuiți o resursă (R) coloanei A4 deoarece nu există valori nule în ea. Apoi continuăm cu o reducere pe coloane.

Al treilea tabel obținut prin scăderea minimului coloanei:

	A1	A2	A3	A4
R1	2	0	0	0
R2	1	2	0	2
R3	0	3	5	0
R4	0	1	2	2

Alocarea rezultată:

{\begin{aligned}A3-R2\to 4+\\A1-R4\to 1+\\A4-R3\to 9+\\A2-R1\to 2=\\\hline {\text{costo}}_{\text{tot}}\Rightarrow 16\end{aligned}}

{\ displaystyle {\ begin {align} A3-R2 \ to 4 + \\ A1-R4 \ to 1 + \\ A4-R3 \ to 9 + \\ A2-R1 \ to 2 = \\\ hline {\ text {cost}} _ {\ text {tot}} \ Rightarrow 16 \ end {align}}}

{\ displaystyle {\ begin {align} A3-R2 \ to 4 + \\ A1-R4 \ to 1 + \\ A4-R3 \ to 9 + \\ A2-R1 \ to 2 = \\\ hline {\ text {cost}} _ {\ text {tot}} \ Rightarrow 16 \ end {align}}}

Prin urmare, costul total al acestei misiuni este $16$ ${\ displaystyle 16}$ $16$ .

Controlul autorității	LCCN ( EN ) sh00004835