Politecnico di Torino | |||||||||||||||||
Anno Accademico 2017/18 | |||||||||||||||||
01QNKOA, 01QNKJM, 01QNKLI, 01QNKLM, 01QNKLN, 01QNKLP, 01QNKLS, 01QNKLX, 01QNKLZ, 01QNKMA, 01QNKMB, 01QNKMC, 01QNKMH, 01QNKMK, 01QNKMN, 01QNKMO, 01QNKMQ, 01QNKNX, 01QNKOD, 01QNKPC, 01QNKPN, 01QNKPW Ottimizzazione per il problem solving |
|||||||||||||||||
Corso di Laurea in Ingegneria Informatica - Torino Corso di Laurea in Ingegneria Meccanica (Mechanical Engineering) - Torino Corso di Laurea in Ingegneria Dell'Autoveicolo (Automotive Engineering) - Torino Espandi... |
|||||||||||||||||
|
|||||||||||||||||
|
|||||||||||||||||
Presentazione
Il corso di Ottimizzazione per il Problem Solving permette di affrontare e risolvere una vasta gamma di problemi di decisione propri dell’ingegneria o di altri settori del mondo reale: informatica, telecomunicazioni, industria manifatturiera, trasporti, logistica, economia, management, finanza, energia, terziario ed altri ancora.
L’ottimizzazione richiede la modellazione del problema allo studio, cioè la costruzione di un modello matematico, sufficientemente rappresentativo del problema stesso, costituito dalle variabili del problema e da un obiettivo da perseguire nel rispetto di opportuni vincoli. Questo modello viene quindi risolto mediante opportuni algoritmi e solver di ottimizzazione. |
Risultati di apprendimento attesi
Conoscenze che l’insegnamento si propone di trasmettere agli studenti:
gli studenti approfondiranno la teoria, i metodi e gli algoritmi per la risoluzione di problemi di ottimizzazione lineare continua (cioè, dove le variabili sono continue), di flussi su reti e, in parte, di ottimizzazione lineare intera (cioè, dove le variabili sono intere). Abilità che l’insegnamento si propone di trasmettere agli studenti: gli studenti svilupperanno l’abilità di costruire, dato un problema reale, un corrispondente ed adeguato modello matematico e risolverlo mediante opportuni algoritmi e solver di ottimizzazione. |
Prerequisiti / Conoscenze pregresse
Non sono richiesti prerequisiti. Le uniche conoscenze pregresse sono quelle già acquisite nei corsi di base.
|
Programma
1. Ottimizzazione lineare continua: problemi e modelli, metodo del simplesso e derivati, dualità (40% del corso).
2. Flussi su reti: concetti fondamentali di teoria dei grafi, ricerca di un albero ricoprente di costo minimo, problema dei trasporti, problema della ricerca di cammino minimo, problema del flusso di costo minimo, problema del massimo flusso (50% del corso). 3. Cenni di ottimizzazione lineare intera (ad es. problemi di progettazione di reti, localizzazione di servizi, analisi di dati, instradamento di traffico): metodi esatti (Branch and Bound) e metodi euristici (algoritmi greedy, Tabu Search, Simulated Annealing, Algoritmi Genetici) (10% del corso). |
Organizzazione dell'insegnamento
L’insegnamento integra opportunamente ore di lezione ed ore di esercitazioni, nella misura di circa 60% e 40% del corso, rispettivamente. Le esercitazioni vengono svolte in aula e seguono gli argomenti delle lezioni. Nel laboratorio LADISPE ttp://www.ladispe.polito.it/ sono a disposizione degli studenti i migliori solver di ottimizzazione esistenti sul mercato per risolvere problemi reali, anche di grandi dimensioni. Vengono fornite in aula le istruzioni per il loro uso. Non sono comunque richieste particolari competenze di programmazione.
|
Testi richiesti o raccomandati: letture, dispense, altro materiale didattico
Testi utilizzati per l’insegnamento:
R. Tadei, F. Della Croce, Elementi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2010. M. Ghirardi, A. Grosso, G. Perboli, Esercizi di Ricerca Operativa, Progetto Leonardo, Editrice Esculapio, Bologna, 2009. Altro materiale didattico, assieme ad esempi di esami precedenti, è disponibile sul portale della didattica. Testi consigliati per approfondimenti: H. P. Williams, Model building in Mathematical Programming, 4th ed., Wiley, 1999. H. P. Williams, Logic and Integer Programming, Springer, 2009. |
Criteri, regole e procedure per l'esame
L'esame è costituito da una prova scritta. Agli studenti vengono sottoposte da quattro a sei domande, di carattere sia teorico sia applicativo. La prima domanda, di particolare importanza, consiste nello scrivere, per un dato problema reale, un corrispondente modello matematico di ottimizzazione lineare che lo rappresenti opportunamente (si veda parte 1 del Programma).
|
Orario delle lezioni |
Statistiche superamento esami |
|