CdSMATEMATICA
Codice072AA
CFU6
PeriodoPrimo semestre
LinguaItaliano
| Moduli | Settore/i | Tipo | Ore | Docente/i | |
| RICERCA OPERATIVA | MAT/09 | LEZIONI | 60 |
|
Lo scopo del corso è quello di fornire una panoramica (per quanto necessariamente ristretta) sui principali aspetti teorici e pratici inerenti alla costruzione di modelli matematici di ottimizzazione di sistemi reali, ed alla loro soluzione algoritmica. Il corso fornisce agli studenti la conoscenza delle proprietà matematiche alla base di alcune delle principali tecniche algoritmiche per la soluzione di tre grandi classi di problemi di ottimizzazione: problemi di programmazione lineare, problemi di cammino e flusso su reti, e problemi di ottimizzazione combinatoria. Vengono in particolare discusse le proprietà che rendono alcuni di questi problemi "facili" ed altri "difficili", e l'impatto che esse hanno sugli algoritmi risolutivi disponibili. Verranno inoltre introdotte alcune tecniche relative alla costruzione di modelli matematici che coniughino (per quanto più possibile) la rispondenza del modello alla situazione reale rappresentata con la risolubilità computazionale dello stesso, fornendo esempi applicativi che consentano allo studente di acquisire la capacità di modellare autonomamente i problemi con strumenti che attualmente sono considerati tra i migliori in pratica.
The course will introduce the student to the main tools and techniques of Operations Research, the discipline of formulating and solving mathematical models corresponding to finding the "best possible" solutions to decision problems. At the end of the course the student will have a basic knowledge of the main issues arising when creating a mathematical model that need be practically solved in "reasonable" time, which is usually a nontrivial task in that most optimization problem are inherently "hard". In particular the student will know the mathematical foundations of the solution algorithms for two important classes of "easy" problems (network flows and linear programming) as well as of the main exact and approximate solution methods of "hard" ones. The issue of what properties make a problem "easy", or not, is discussed, with particular emphasis on its impact on solution algorithms. Furthermore, some techniques are illustrated for construct formulationsof real-world optimization problems using what is currently considered the most useful formalism in practice, that of Integer Linear Programming.
Prova scritta seguita da una prova orale.
Written and oral exam.
Risolvere piccole istanze di problemi di ottimizzazione delle classi studiate nel corso applicando gli algoritmi noti e comprendendone in profondità il comportamento. Scrivere autonomamente modelli di ottimizzazione (in particolare, di Programmazione Lineare Intera) di semplici problemi proposti.
Solving small instances of optimization problems of the classes studied in the course applying the known algorithms and understanding in details the behavior. Autonomously writing optimization models (in particular, Integer Linear Programming ones) of simple problems.
Tutte le capacità verranno verificate durante la prova scritta e quella orale.
All skills will be tested during both the written and the oral exam.
Analizzare algoritmi complessi con rigore analitico, comprendendone i principi di funzionamento in modo da poterne eventualmente proporre modifiche e produrne implementazioni efficienti. Sviluppare in modo creativo modelli matematici che, pur partendo da un numero ristretto di strutture di base, siano in grado di esprimere moltissimi problemi di interesse pratico.
Rigorously anayzing complex algorithms, fully understanding their basic principles in such a way as to be able to propose modifications or produce efficient implementations. Creatively developing mathematical models that, despite being composed out of a small number of basic structures, be capable of expressing very many problems of practical interest.
Tutte i comportamenti verranno verificati durante la prova scritta e quella orale.
All behaviors will be tested during both the written and the oral exam.
Sono consigliate conoscenze di base di analisi, geometria ed algebra lineare. Si assume una conoscenza di base dei concetti di algoritmo e di analisi della complessità.
Basic knowledge of analysis, geometry, linar algebra, the concept of algorithm and complexity analysis.
Lezioni frontali, con esercitazioni. La partecipazione alle lezioni è consigliata ma non strettamente necessaria, dato il materiale disponibile per il corso (dispense, esercizi d'esame con svolgimento).
Delivery: face to face
Learning activities:
- attending lectures
- participation in discussions
- individual study
Attendance: Advised, not necessary.
Teaching methods:
- Lectures
-
Problemi e Modelli (4 ore)
- Il processo decisionale
- Esempi di problemi ottimizzazione
- Definizioni generali
-
Programmazione Lineare (20 ore)
- Geometria della Programmazione Lineare
- Algoritmo del simplesso primale
- Teoria matematica della dualità
- Algoritmo del simplesso duale
- Riottimizzazione ed analisi parametrica
- Cenni sull'ottimizzazione nonlineare
-
Grafi e Reti di flusso (16 ore)
- Flusso di costo minimo
- Cammini di costo minimo
- Flusso massimo
- Problemi di accoppiamento
-
Ottimizzazione Combinatoria (20 ore)
- Ottimizzazione Combinatoria e Programmazione Lineare Intera
- Tecniche di modellazione per la PLI
- Dimostrazioni di ottimalità
- Algoritmi euristici
- Tecniche di rilassamento
- Algoritmi enumerativi
The course will cover the following material:
- Decision and optimization problems:
= the decision process and optimization problems
= complexity of decision problems
= modeling techniques
- Linear Programs:
= definitions, geometrical and algebraic properties
= the primal simplex algorithm
= duality and the dual simplex algorithm
= sensitivity analysis and reoptimization
- Network Flow problems and algorithms:
= Shortest Paths
= Maximum Flows
= Min-Cost Flows
- Integer Linear Programs: expressive power and complexity
- Solution algorithms for Integer Linear Programs
= heuristics
= relaxations
= implicit enumeration
-
F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli, Milano (1999)
-
Massimo Pappalardo, Mauro Passacantando "Ricerca Operativa", Plus, 2010
-
F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli, Milano (1999)
-
Massimo Pappalardo, Mauro Passacantando "Ricerca Operativa", Plus, 2010
Contattare il docente.
Contact the teacher.
Prova scritta seguita da una prova orale. Sono esonerati dalla prova scritta coloro che hanno superato i due compitini.
I contenuti dell'esame sono quelli del corso dell'anno accademico a cui si riferisce l'appello, anche per gli studenti che avessero seguito il corso in anni precedenti.
Per sostenere l'esame è necessario iscriversi attraverso gli opportuni moduli web entro le date indicate sui moduli stessi. L'iscrizione è necessaria anche per i compitini, con la stessa modalità.
Durante la prova scritta non è possibile consultare libri o appunti.
La prova orale viene effettuata nello stesso appello della prova scritta, normalmente nei giorni immediatamente successivi a quelli della pubblicazione dei risultati della prova scritta stessa.
Gli studenti che sono stati esonerati dalla prova scritta a seguito di valutazione positiva dei compitini devono iscriversi in uno dei primi due appelli dopo il termine del corso per sostenere l'esame orale. È gradito che gli studenti si iscrivano, con la solita modalità, all'appello nel quale intendono sostenere la prova orale specificando "solo orale" nelle note. Gli studenti hanno la facoltà di rinunciare al voto ottenuto dai compitini semplicemente consegnando una delle due prove scritte successive, o non presentandosi a nessuno dei due orali corrispondenti.
The written and oral exam aim at verifying that the student has understood the main algorithmic techniques presented during the course, their theoretical foundations, and she/he is capable of formulating mathematical models of simple fragments of reality with at least a basic understanding of the impact of the modeling choices on the difficulty of the resulting optimization problem.
Methods:
- Final oral exam
- Final written exam
Further information:
The written exam usually consists in 6 exercises (3 hours) covering all the material of the course, and in particular (but not exclusively) the algorithmic aspects. A sufficient (or almost so) written exam is a prerequisite to the oral exam; it is only waived for student successfully passing the two in-course tests (4 exercises, 2 hours each). The oral exam will in any case cover all the theoretical and algorithmic material of the course.