Metodi di assegnazione ottima ed applicazioni

Introduzione Nel mondo delle applicazioni economiche e industriali, spesso s’incontrano problemi d’elevata complessità computazionale; in altre parole, problemi che richiedono un numero di passi eccessivamente elevato per essere risolti per via computazionale. Per questo motivo, necessitiamo d’algoritmi efficienti (più veloci) in grado di produrre una soluzione accettabile in tempi ragionevoli. Si suppone che, un algoritmo, all’aumentare della complessità computazionale, richieda un tempo d’esecuzione proporzionale alla complessità stessa.. Esiste una classe di problemi chiamata NP-completa (Nondeterministic Polynomial), la quale definisce la frontiera fra trattabili ed intrattabili computazionalmente: i primi sono caratterizzati da una complessità di tipo polinomiale, i secondi, invece, da una complessità maggiore di quella polinomiale. Un esempio di problema intrattabile computazionalmente è quello che può essere risolto almeno in tempo esponenziale, in altre parole, in 2 n passi. I problemi che appartengono alla classe NP sono problemi che possono essere risolti in tempo polinomiale attraverso algoritmi non deterministici in grado, almeno a livello statistico, di ottenere un’efficienza superiore a quella “di caso peggiore”. L’importanza di questa classe deriva dal fatto che è possibile dimostrare che se un problema NP-completo è risolvibile in tempo polinomiale, allora tutti i problemi NP-completi lo sono. La teoria della NP-completezza, quindi, ci fornisce un insieme di tecniche che ci permette di mostrare che, se un dato problema è hard, come un ampio numero d'altri che sono riconosciuti come tali, il problema in questione risulta NP-completo e quindi, equivalente a tutti gli altri. E’ necessario introdurre questa classe di problemi, poiché, in questa mia esposizione sarà trattato un problema di tale tipo: il Problema dell’Assegnamento Quadratico (QAP).