Questo sito utilizza cookie di terze parti per inviarti pubblicità in linea con le tue preferenze. Se vuoi saperne di più clicca QUI 
Chiudendo questo banner, scorrendo questa pagina, cliccando su un link o proseguendo la navigazione in altra maniera, acconsenti all'uso dei cookie. OK

Metodi di assegnazione ottima ed applicazioni

Ricerca Operativa: Metodi di assegnazione ottima ed applicazioni

Mostra/Nascondi contenuto.
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).

Tesi di Laurea

Facoltà: Scienze Statistiche

Autore: Magda Muccioli Contatta »

Composta da 142 pagine.

 

Questa tesi ha raggiunto 581 click dal 20/03/2004.

Disponibile in PDF, la consultazione è esclusivamente in formato digitale.