Modules | Area | Type | Hours | Teacher(s) | |
RICERCA OPERATIVA | MAT/09 | LEZIONI | 60 |
|
Il corso presenta gli strumenti necessari alla definizione e alla risoluzione di modelli analitici di ottimizzazione per problemi reali, tipicamente di gestione e allocazione di risorse, con enfasi su applicazioni nei settori dell’elettronica e delle telecomunicazioni. Verranno introdotte proprietà teoriche ed alcune delle principali tecniche algoritmiche per la risoluzione di tre grandi famiglie di problemi di ottimizzazione: i problemi di programmazione lineare, i problemi di flusso su rete e i problemi di programmazione lineare intera.
The course will introduce the student to the main properties and algorithmic approaches of Operations Research, the discipline aiming at formulating and solving mathematical models corresponding to decision problems stated in an optimization form. At the end of the course the student will have a basic knowledge of the main issues arising when stating a mathematical model that needs to be efficiently solved. In particular, the student will know the mathematical foundations and some relevant solution algorithms for two important classes of "easy" problems, that is Network Flow problems and linear programming. Furthermore, she/he will be able to formulate "hard" optimization problems via Integer Linear Programming, and to solve them by exploiting some relevant mathematical properties of this class of problems
Prova scritta eventualmente seguita da una prova orale.
The written and the oral exam (when performed) 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 model.
Methods:
Further information:
The written exam is mandatory, and it usually consists of 5 exercises (3 hours) covering all the topics of the course. A sufficient (or almost so) written exam is a prerequisite to the oral exam. Anyway, students may accept the grade obtained with the only written exam, under the condition that grades greater than 27 will be decreased to 27. Also the oral exam, if performed, will cover all the topics of the course.
Delivery: face to face
Learning activities:
Attendance: Advised
Teaching methods:
Problemi e modelli (4 ore)
Programmazione Lineare (PL) (20 ore)
Problemi di flusso su rete (16 ore)
Programmazione Lineare Intera (PLI) (20 ore)
The course will cover the following topics: - Decision and optimization problems - Linear Programming: definitions, geometrical and algebraic properties, duality theory, the primal and the dual simplex algorithm, sensitivity analysis and reoptimization - Network Flow problems: Shortest Paths (theory and algorithms), Maximum Flow (theory and algorithms), Mininimum Cost Flow (theory and algorithms) - Integer Linear Programming: basic modelling techniques, relaxation techniques, exact algorithms, heuristic algorithms
Appunti di Ricerca Operativa, prove d'esame (con e senza svolgimento): disponibili sulla pagina web del corso.
The complete course material is freely distributed at http://didawiki.cli.di.unipi.it/doku.php/ingegneria/ricercaoperativa1/start
Prova scritta eventualmente seguita da una prova orale.
http://didawiki.cli.di.unipi.it/doku.php/ingegneria/ricercaoperativa1/start