CdSINFORMATICA
Codice029AA
CFU6
PeriodoPrimo semestre
LinguaItaliano
| Moduli | Settore/i | Tipo | Ore | Docente/i | |
| RICERCA OPERATIVA | MAT/09 | LEZIONI | 48 |
|
Il corso presenta gli strumenti necessari alla costruzione e alla risoluzione di modelli analitici di ottimizzazione per problemi reali, tipicamente di gestione, di allocazione delle risorse e di logistica. Verranno illustrate le proprietà teoriche ed alcune delle principali tecniche algoritmiche per la soluzione di tre grandi classi di problemi di ottimizzazione: problemi di flusso su reti, di programmazione lineare e di programmazione lineare intera.
The course introduces tools for building and solving analytic optimization models for real problems in areas such as management, resource allocation and logistics. The main theoretical properties and solution methods will be shown for three large classes of optimization problems: network flow, linear and integer linear programming.
- Logica elementare: connettivi logici, proposizioni, principio di induzione, metodi di dimostrazione
- Spazi vettoriali: spazi, semispazi, vettori, combinazioni lineari, indipendenza lineare, basi, coordinate
- Geometria del piano e dello spazio tridimensionale: sottospazi affini, equazione di rette, piani e semispazi
- Prodotto scalare euclideo, ortogonalità
- Matrici: operazioni con le matrici, determinante, invertibilità
- Concetto di funzione, funzioni lineari (ed affini)
- Sistemi lineari di equazioni e loro risoluzione
- Cosa è un algoritmo
- Complessità di un algoritmo
- Classi P e NP
- Strutture dati: fila, pila, deque, code di priorità, heap
- Grafi: nodi, archi, alberi, cammini, cicli
- Grafi: rappresentazione e visite (DFS e BFS)
- Alberi: rappresentazioni e visite
- Ricerca dei punti di massimo e minimo di funzioni di una variabile
0. Introduzione (2 ore)
- Problemi decisionali e problemi di ottimizzazione
- Classi di problemi ed esempi
- Modelli e loro formulazione (6 ore)
- Tipi di variabili: quantitative, logiche, continue, discrete
- Formulazione di vincoli
- Formulazione della funzione obiettivo
- Grafi e Reti di flusso (18 ore)
- Modello generale dei problemi di flusso
- Alberi, cammini e tagli, visite di grafi e alberi
- Il problema dei cammini minimi
- Il problema dell'albero di copertura di costo minimo
- Il problema del flusso massimo
- Il problema del flusso di costo minimo
- Programmazione Lineare (14 ore)
- Geometria della programmazione lineare e teorema fondamentale
- Dualità e scarti complementari
- Basi: complementarità, degenericità ed ottimalità
- Algoritmi del simplesso primale e duale
- Programmazione Lineare Intera (8 ore)
- Metodi poliedrali: tagli ed algoritmo di Gomory
- Metodi enumerativi: l'algoritmo "Branch&Bound"
- Implementazioni ad-hoc per i problemi dello zaino e del commesso viaggiatore
Introduction (2 hours)
- Decision-making problems and optimization
- Classification of problems and examples
- Models and formulations (6 hours)
- Kinds of variables: quantitative, logic, continuous, discrete
- Constraint formulation
- Formulation of objective functions
- Graphs and network flows (18 hours)
- General model for network flow problems
- Trees, paths and cuts, search procedures for graphs and trees
- Shortest path problems
- Minimum spanning trees
- Maximum flow
- Minimum cost problem
- Linear Programming (14 hours)
- Geometry of linear programming and fundamental theorem
- Duality and complementarity slackness
- Basis: complementarity, degeneracy and optimality
- Primal and dual simplex algorithms
- Integer Linear Programming (8 hours)
- Polyedral methods: Gomory cuts and algorithm
- Enumeration methods: Branch&Bound algorithm
- Ad-hoc implementations for knapsack and traveling salesman problems
Testo di riferimento
- G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G. Scutellà, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa (PDF)
Altri testi di consultazione
- R.K. Ahuja, T.L. Magnanti, J. Orlin, Network flows. Theory, algorithms and applications, Prentice Hall, 1993
- M. Pappalardo, M. Passacantando, Ricerca operativa, Pisa University Press, 2012
- P. Serafini, Ottimizzazione, Zanichelli, 2000
- C. Vercellis, Modelli e decisioni, Progetto Leonardo, 1999
- C. Vercellis, Ottimizzazione. Teoria, metodi, applicazioni, McGraw Hill, 2008
Lecture notes
- G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G. Scutellà, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa (PDF) - in Italian
Further references
- R.K. Ahuja, T.L. Magnanti, J. Orlin, Network flows. Theory, algorithms and applications, Prentice Hall, 1993
- M. Pappalardo, M. Passacantando, Ricerca operativa, Pisa University Press, 2012 (in Italian)
- P. Serafini, Ottimizzazione, Zanichelli, 2000 (in Italian)
- C. Vercellis, Modelli e decisioni, Progetto Leonardo, 1999 (in Italian)
- C. Vercellis, Ottimizzazione. Teoria, metodi, applicazioni, McGraw Hill, 2008 (in Italian)
Le prove d'esame si articolano in un test preliminare a distanza più un'interrogazione orale in presenza. Il test preliminare consiste in una serie di domande a risposta sia chiusa sia aperta. Prima del suo inizio verrà comunicato il numero minimo di risposte esatte per il suo superamento. Il test sarà accessibile su google classroom ai soli studenti iscritti alla prova. La durata del test è 90 minuti, la correzione avverrà immediatamente alla sua conclusione e contestualmente verrà stilato il calendario delle interrogazioni che (generalmente) inizieranno nei giorni successivi. Il test è parte integrante di un esame unitario, pertanto l'interrogazione dovrà essere sostenuta nella stessa sessione (Dicembre-Gennaio, Maggio-Luglio, Settembre) e può essere sostenuta solo se in regola per le prescrizioni previste dal regolamento del corso di studi per sostenere esami del secondo anno. La validità del test è limitata alla medesima sessione.
Sono esonerati dal test preliminare coloro che hanno superato le prove in itinere/prove di verifica intermedia (nel seguito denominate "compitini"), che si svolgeranno con le stesse modalità del test preliminare. La durata di ciascun compitino varia da 60 a 90 minuti secondo l'entità della prova e sarà comunicata prima dell'inizio della stessa. Gli studenti, che sono stati esonerati dal test preliminare a seguito di valutazione positiva dei compitini, possono svolgere la prova orale in uno dei primi due appelli. La consegna di un test successivo ai compitini comporta la rinuncia all'esonoro eventualmente già ottenuto.
Written exam followed by an oral interview