Problema di assegnazione

Da Wikipedia, l'enciclopedia libera.

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, esso infatti è un problema combinatorio e generalmente questi 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 di 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.

[modifica] 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 di 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 combinatiorio è risolvibile in tempo polinomiale.

[modifica] 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	15	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:

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:

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

[modifica] 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: