Problema di assegnazione: differenze tra le versioni

Versione delle 19:47, 25 apr 2012

Versione attuale delle 21:00, 15 lug 2019

(14 versioni intermedie di 10 utenti non mostrate)

Riga 1:

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, essoanche infattise è un problema combinatorio e generalmente questitali problemi sono [[Classi di complessità P e NP|NP-Hardhard]], cioè

difficili da risolvere. Tuttavia questo è uno dei particolari problemi che godono della

[[Ricerca_operativa#Proprietà di integralità|proprietà di integralità]] e difatti altro non è che un particolare [[problema didel flusso di costo minimo]].

Questo è un problema di fondamentale importanza in [[Ottimizzazioneottimizzazione Combinatoriacombinatoria]] 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

[[Ricerca operativa#Rilassamenti ed euristiche|tecniche di rilassamento]] - si possono utilizzare gli algoritmi studiati per questo problema per risolvere il problema originario.

Riga 36:

|}

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 [[Classi di complessità P e NP|tempo polinomiale]].

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 combinatorio è risolvibile in [[Classi di complessità P e NP|tempo polinomiale]].

==Risoluzione tipica==

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

[[Immagine:Ricerca_operativa_problemi_assegnazione.png|center]]

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, …, <math>A_n</math> le attività e con R1, R2, R3, R4, …, <math>R_n</math> le risorse. All’internoAll'interno delle altre caselle indichiamo il costo di ogni assegnazione (relativa ad una specifica risorsa e ad una specifica attività).

{| border=0 cellspacing=5

Riga 81 ⟶ 77:

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’ultimadall'ultima ottenendo una nuova tabella.

{| border=0 cellspacing=5

!

Riga 113 ⟶ 109:

| '''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à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.

Riga 119 ⟶ 115:

In pratica:

<div align="center"><math>\left.\begin{array}{l}A3-R1\\A1-R2\\A2-R3\\A4-R4\end{array}\right\}\text{costi relativi all'ultima tabella}=0</math></centerdiv>

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

Riga 126 ⟶ 122:

Otteniamo quindi:

<div align="center"><math>\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)}</math></centerdiv>

Ovviamente il costo totale della assegnazione è dato dalla somma dei costi parziali appena trovati:

Riga 232 ⟶ 228:

Assegnazione risultante:

<div align="center"><math>\begin{align}A3-R2\to 4+\\A1-R4\to 1+\\A4-R3\to 9+\\A2-R1\to 2=\\\hline\text{costo}_{\text{tot}}\Rightarrow 16\end{align}</math></centerdiv>

Il costo totale di questa assegnazione è dunque <math>16</math>.

{{Controllo di autorità}}

[[es:Problema de la asignación]]

[[fr:Problème d'affectation]]

[[zh:任务分配问题]]

[[en:Assignment problem]]

[[Categoria:Ricerca operativa]]

[[Categoria:Problemi risolvibili in tempo polinomiale]]