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 presents the necessary tools for the construction and resolution of optimization models for real problems (management, resource allocation and logistics problems, etc.). The theoretical properties and some of the main algorithmic techniques for the solution of three classes of optimization problems will be illustrated: network flow problems, linear programming problems and integer linear programming problems.
Per l'accertamento delle conoscenze saranno svolte delle prove in itinere.
Ongoing assessment to monitor academic progress will be carried out.
Lo studente sarà in grado di analizzare, modellizzare e sviluppare algoritmi risolutivi per problemi di flusso su reti, problemi di programmazione lineare e di programmazione lineare intera.
The student will be able to analyse, model and develop solving algorithms for netwrok flow problems, linear programming problems and integer linear programming problems.
Durante le sessioni di esercitazioni saranno svolti esercizi per modellizzare e risolvere problemi di flusso su reti, di programmazione lineare e di programmazione lineare intera.
Exercises to model and solve network flow problems, linear programming problems and integer linear programming problems will be conducted during the tutorial sessions.
Lo studente potrà sviluppare capacità critiche, sia a livello modellistico che algoritmico, per affrontare problemi di ottimizzazione del mondo reale, che risulteranno rilevanti in svariati ambiti lavorativi, sia a livello progettuale che implementativo.
The student will be able to develop critical modelling and algorithmic skills on real-world optimization problems, which will be relevant to several work areas, both at design and implementation level.
Durante le sessioni di esercitazioni saranno valutate le capacità critiche dello studente per affrontare problemi di ottimizzazione del mondo reale.
During the tutorial sessions, the student's critical skills in dealing with real-world optimization problems will be assessed.
- 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
- Boolean logic: operators, propositions, induction principle, proof methods
- Vector spaces: spaces, semi-spaces, vectors, linear combinations, linear independence, bases, coordinates
- Geometry of the two and three-dimensional spaces: affine subspaces, equations of lines, planes and half-spaces
- Euclidean product, orthogonality
- Matrices: operations with the matrices, determinant, invertibility
- Affine and linear functions
- Linear systems of equations and their resolution
- What is an Algorithm
- Complexity of an algorithm
- Classes P and NP
- Data structures: row, stack, deque, priority queues, heap
- Graphs: nodes, arcs, trees, paths, cycles
- Graphs: representation and visits (DFS and BFS)
- Trees: representations and visits
- Maximum and minimum points for functions of one variable
Modalità: lezioni frontali, con l'aiuto di slide, e sessioni di esercitazioni.
Sito di elearning del corso: download di materiali didattici, pubblicazione di test per esercizi a casa (con relative soluzioni).
Attività di apprendimento: partecipazione alle lezioni e studio individuale.
Frequenza: consigliata
Delivery: Frontal lessons, with the help of transparencies, exercise sessions.
Course elearning site: download teaching materials, publication of tests for home exercises.
Learning activities: attending lectures, individual study.
Attendance: Advised
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 (16 ore)
- Modello generale dei problemi di flusso
- Alberi, cammini e tagli, visite di grafi e alberi
- Il problema dei cammini minimi
- Il problema del flusso massimo
- Il problema del flusso di costo minimo
- Il problema dell'albero di copertura di costo minimo
Programmazione Lineare (16 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 and optimization problems
- Classes of problems and examples
Optimization models (6 hours)
- Variables: quantitative, logical, continuous, discrete
- Constraints formulation
- Objective function formulation
Graphs and network flows (16 hours)
- General model for network flow problems
- Trees, paths and cuts, graph search
- Shortest path problem
- Maximum flow problem
- Minimum cost flow problem
- Minimum spanning tree problem
Linear Programming (16 hours)
- Geometry and fundamental theorem of LP
- Duality and complementary slackness conditions
- Bases: complementarity, degeneracy and optimality
- Primal and dual simplex algorithms
Integer Linear Programming (8 hours)
- Polyhedral methods: Gomory cuts
- Enumeration methods: the "Branch & Bound" method
- Ad-hoc implementations of the "Branch & Bound" method for the knapsack problem and the travelling salesman problem
Testo di riferimento:
- M. Pappalardo, M. Passacantando, Ricerca Operativa, Pisa University Press, 2012. (Errata corrige)
Altri testi consigliati:
- R.K. Ahuja, T.L. Magnanti, J. Orlin, Network flows. Theory, algorithms and applications, Prentice Hall, 1993
- G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G. Scutellà, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa
- F.S. Hillier, G.J. Lieberman, Ricerca Operativa - Fondamenti, McGraw-Hill, 2010
- F. Schoen, Modelli di ottimizzazione per le decisioni, Esculapio, 2006
- C. Vercellis, Ottimizzazione. Teoria, metodi, applicazioni, McGraw Hill, 2008
Main textbook:
- M. Pappalardo, M. Passacantando, Ricerca Operativa, Pisa University Press, 2012. (Errata corrige)
Further textbooks:
- R.K. Ahuja, T.L. Magnanti, J. Orlin, Network flows. Theory, algorithms and applications, Prentice Hall, 1993
- G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M. G. Scutellà, Appunti di Ricerca Operativa, SEU - Servizio Editoriale Universitario di Pisa
- F.S. Hillier, G.J. Lieberman, Ricerca Operativa - Fondamenti, McGraw-Hill, 2010
- F. Schoen, Modelli di ottimizzazione per le decisioni, Esculapio, 2006
- 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.
The exam is made up of one written test and one oral test. Only students who have passed the written test are admitted to the oral test. Exempted from the written test are those who have passed the two intermediate tests. Only those students who have passed the first intermediate test are admitted to the second intermediate test.
In order to partecipate to the written tests it is necessary to register by the deadlines indicated on exams.unipi.it. If one or more students do not register, it is not possible to guarantee their participation in the test.
During the written test it is not possible to consult books or notes.
The oral test is carried out in the same session (January-February, June-July, September) of the written test according to a calendar of possible dates communicated during the test and published simultaneously on the web page. The delivery of a written test after the one already passed involves the renunciation of the test previously passed with positive results.
Students who have been exempted from the written test following a positive evaluation of the tasks can take the oral test in one of the first two appeals. The delivery of a written test after the tasks involves the waiver of any exemption already obtained.