Problema di assegnazione

I problemi di assegnazione (o problemi di assegnamento) sono quei problemi di ricerca operativa in cui bisogna assegnare diverse attività in maniera ottimale.

Il problema di assegnazione è considerato un problema facile, anche se è un problema combinatorio e generalmente tali problemi sono NP-hard, cioè difficili da risolvere. Tuttavia questo è uno dei particolari problemi che godono della proprietà di integralità e difatti altro non è che un particolare problema del flusso di costo minimo.

Questo è un problema di fondamentale importanza in ottimizzazione combinatoria poiché spesso si ritrova nella struttura di problemi più complessi: ovvero spesso i problemi applicativi sono un problema di assegnamento con dei vincoli aggiuntivi. In questo modo - tramite le cosiddette tecniche di rilassamento - si possono utilizzare gli algoritmi studiati per questo problema per risolvere il problema originario.

Formulazione

Un problema di assegnazione è definito su di un grafo bipartito ovvero un grafo $G=(N,A)$ dove $N=N_{1}\cup N_{2}$ e $A\subseteq N_{1}\times N_{2}$. Ad ogni arco $(i,j)\in A$ è associato un costo $c_{i,j}$; si vuole trovare l'assegnamento di costo minimo; ovvero l'insieme $B\subseteq A$ tale che

$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^{'}\}$,

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

La seguente è una delle possibili formulazioni in Programmazione lineare:

$\min \sum _{(i,j)\in A}c_{i,j}x_{i,j}$
tale che:
$\sum _{(i,j)\in A}x_{i,j}=1$	$\forall i\in N_{1}$
$\sum _{(i,j)\in A}x_{i,j}=1$	$\forall j\in N_{2}$
$x_{i,j}\in {0,1}$	$\forall (i,j)\in A$

Il problema si presenta, quindi, come un problema di Programmazione lineare intera; tuttavia è possibile ridefinirlo come un problema del flusso di costo minimo (che è risolvibile tramite rilassamento continuo e, quindi, in Programmazione lineare). Non stupisce, perciò, il fatto che, pur essendo questo un problema combinatorio è risolvibile in tempo polinomiale.

Risoluzione tipica

Il problema di base è quello di trovare un'assegnazione tra attività (produttori) – risorse (clienti) al costo minimo.

Per prima cosa dobbiamo realizzare una tabella che metta in relazione i costi tra le attività e le risorse. Indichiamo con A1, A2, A3, A4, …, $A_{n}$ le attività e con R1, R2, R3, R4, …, $R_{n}$ le risorse. All'interno delle altre caselle indichiamo il costo di ogni assegnazione (relativa ad una specifica risorsa e ad una specifica attività).

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

Il primo passo consiste nel sottrarre ad ogni riga il suo valore minimo (chiamato, appunto, minimo di riga). In pratica, considerando la riga relativa ad R1, si cerca il valore minimo di quella riga, ovvero 3, e lo si sottrae ad ogni casella sempre relativa alla prima riga. Lo stesso si fa con le altre righe, si sottrae 11 dalla seconda, 7 dalla terza e 8 dall'ultima ottenendo una nuova tabella.

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

Da questa ultima tabella ottenuta si considerano le caselle contenenti valore (costo) zero si cerca, in base a queste, di assegnare ad ogni risorsa un'attività in modo che il costo (relativo a questa ultima tabella) sia zero.

Nel nostro caso possiamo considerare concluso il problema perché è possibile assegnare ogni colonna A ad una riga R mantenendo nullo il costo relativo. Se così non fosse stato avremmo proceduto, in modo analogo, con la sottrazione del minimo valore di colonna (vedi esempio seguente). In pratica:

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

Nota: Non abbiamo assegnato A1-R3 altrimenti non avremmo più potuto assegnare A1-R2.

Per trovare il reale costo relativo a questa assegnazione dobbiamo andare a considerare anche la tabella di partenza con i relativi costi (mantenendo sempre le assegnazioni appena trovate). Otteniamo quindi:

$\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)}}$

Ovviamente il costo totale della assegnazione è dato dalla somma dei costi parziali appena trovati: $C=3+11+7+8=29$

Esempio risolto

Tabella di partenza:

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

Seconda tabella ottenuta sottraendo il minimo di riga:

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

Con questa tabella è impossibile assegnare una risorsa (R) alla colonna A4 in quanto non vi sono valori nulli al suo interno. Si procede quindi con una riduzione per colonne.

Terza tabella ottenuta sottraendo il minimo di colonna:

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

Assegnazione risultante:

${\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}}$

Il costo totale di questa assegnazione è dunque $16$.

Controllo di autorità	LCCN (EN) sh00004835 · J9U (EN, HE) 987007290944005171