Ottimizzazione Combinatoria

Crediti

Propedeuticità

Nessuna.

Modalità dell’esame

Colloquio finale.

Obiettivi
formativi

Questo insegnamento si prefigge quale obiettivo principale l’introduzione degli studenti all’uso dei modelli di programmazione matematica con particolare attenzione rivolta ai modelli di ottimizzazione a variabili intere corrispondenti a problemi di decisione computazionalmente intrattabili ed alle loro applicazioni nei campi della logistica, dei servizi e della produzione industriale.

Contenuti

Introduzione ai problemi di ottimizzazione combinatoria e ai problemi in forma di riconoscimento. Classi di complessità P, NP, NP-hard e NP-completi. Classificazione dei metodi risolutivi (metodi esatti, metodi di approssimazione e metodi euristici). Algoritmi euristici e meta-euristici: Simulated Annealing; Tabù Search; Algoritmi Genetici; GRASP; Algoritmi di Ricerca Locale. Il problema del Commesso Viaggiatore (TSP). Problemi di distribuzione (Vehicle Routing).

Anno Accademico
2018/2019

Docente: Paola FESTA.

Semestre: secondo.

Ottimizzazione Combinatoria