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.
- 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
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
- Introduzione all'algoritmo del simplesso su reti
- 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
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
Prova scritta seguita da una prova orale. Sono ammessi alla prova orale solo gli studenti che hanno superato la prova scritta. Sono esonerati dalla prova scritta coloro che hanno superato le due prove in itinere/prove di verifica intermedia (nel seguito denominate "compitini"). Sono ammessi al secondo compitino soltanto gli studenti che hanno superato il primo.
Per sostenere la prova scritta dell'esame, inclusi i compitini, è necessario iscriversi entro le date indicate su esami.unipi.it.In genere la scadenza per le iscrizioni è fissata 48 ore prima della prova. In caso di mancata iscrizione da parte di uno o più studenti non è possibile garantire la loro partecipazione alla prova.
Durante la prova scritta non è possibile consultare libri o appunti.
La prova orale viene effettuata nella stessa sessione (Gennaio-Febbraio, Giugno-Luglio, Settembre) della prova scritta secondo un calendario di possibili date comunicato durante il compito e pubblicato contemporaneamente sulla pagina web. La consegna di una prova scritta successiva a quella già superata comporta la rinuncia alla prova precedentemente sostenuta con esito positivo.
Gli studenti che sono stati esonerati dalla prova scritta a seguito di valutazione positiva dei compitini possono svolgere la prova orale in uno dei primi due appelli. La consegna di una prova scritta successiva ai compitini comporta la rinuncia all'esonoro eventualmente già ottenuto.