ECTS - University of Pisa
| Modules | Area | Type | Hours | Teacher(s) | |
| 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 sistemi reali, con particolare riferimento ai modelli di ottimizzazione, ed alla loro soluzione algoritmica.
Verranno presentate le proprietà matematiche alla base di alcune delle principali tecniche algoritmiche per la soluzione di tre grandi classi di problemi di ottimizzazione, in ordine cresciente di difficoltà: problemi di cammino e flusso su reti, problemi di programmazione lineare, e problemi di ottimizzazione combinatoria. Verranno 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 discusse le problematiche 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 tecniche ed esempi applicativi che consentano allo studente di acquisire la capacità di modellare autonomamente i problemi con gli 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, and will be able to construct formulations using 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.
Prova scritta seguita da una prova orale.
Written and 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.
Prova scritta seguita da una prova orale.
Written and oral exam.
Per iscriversi all'esame (comprese le prove scritte) è necessario aver verbalizzato gli esami di Algebra Lineare ed Analisi Matematica II. Come richiesto dal CCS, il controllo su queste propedeuticità sarà stretto e senza eccezioni.
To be admitted to the written exam it is strictly necessary to have passed the exams of Algebra Lineare and Analisi Matematica II. No exceptions will be done.
Nessuno.
None.
Il corso è concettualmente prerequisito per il corso di Ricerca Operativa II alla Laurea Magistrale.
The course is conceptually a prerequisite of the course of Ricerca Operativa II (Laurea Magistrale).
Lezioni frontali, con esercitazioni.
Delivery: face to face
Learning activities:
Attendance: Advised
Teaching methods:
Problemi e Modelli (4 ore)
Grafi e Reti di flusso (18 ore)
Programmazione Lineare (18 ore)
Ottimizzazione Combinatoria (20 ore)
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
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
F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli, Milano (1999)
Contattare il docente.
Contact the teacher.
Prova scritta, eventualmente seguita da una prova orale.
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.
Per iscriversi all'esame è parimenti necessario aver verbalizzato gli esami di Algebra Lineare ed Analisi Matematica II. Come richiesto dal CCS, il controllo su queste propedeuticità sarà stretto e senza eccezioni.
Durante la prova scritta non è possibile consultare libri o appunti.
Superata la prova scritta con un voto di almeno 18/30, lo studente può chiedere la verbalizzazione immediata dell'esame. Il voto verbalizzato sarà quello dello scritto a meno che esso non sia superiore ai 27/30, nel qual caso il voto verbalizzato sarà comunque 27/30; per ottenere un voto superiore a 27/30 lo studente deve necessariamente sostenere la prova orale. Lo studente può decidere liberamente se accettare come valutazione finale il punteggio conseguente alla prova scritta, secondo la regola sopra descritta, sapendo che a seconda dell'esito della prova orale la valutazione finale potrebbe anche risultare inferiore a quella dello scritto, e l'esame potrebbe anche non essere superato.
La prova orale viene effettuata nello stesso appello della prova scritta, normalmente nei giorni immediatamente successivi alla pubblicazione dei risultati della prova scritta stessa. Salvo deroghe concordate esplicitamente col docente, e solamente per gravi motivi, il non presentarsi all'orale o alla verbalizzazione del voto corrisponde alla rinuncia al voto medesimo, con la conseguente necessità di ripetere lo scritto.
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:
Further information:
The written exam usually consists in 6 exercises (3 hours) covering all the material of the course, i.e., the algorithmic aspects, the modeling aspects, and the theoretical aspects. Upon a receiving a sufficient grade at the written exam, the student can ask to be spared to oral one and have the course registered with the vote she/he obtained at the written exam. The exception is if the student has had a vote higher than 27/30; in this case the course can be registered with 27/30. All students who have received a sufficient grade at the written exam can, if they want, undertake the oral exam for a chance of getting a higher grade. However, the oral exam may result in a final grade which is lower than that of the written exam, and even to the student being asked to repeat the exam.Written and oral exam.
È possibile organizzare stage aziendali relativi ai contenuti del corso.
It is possible to organize industrial internships relative to the course contents.
