Scheda programma d'esame
RICERCA OPERATIVA
MASSIMO PAPPALARDO
Anno accademico2017/18
CdSINFORMATICA
Codice029AA
CFU6
PeriodoPrimo semestre
LinguaItaliano

ModuliSettoreTipoOreDocente/i
RICERCA OPERATIVAMAT/09LEZIONI48
MASSIMO PAPPALARDO unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

Il corso si prefigge l'obiettivo di guidare lo studente nella formulazione di modelli matematici per problemi di ottimizzazione lineare (discreta e continua) a risorse limitate, e di illustrare tecniche algoritmiche per la loro risoluzione.

Lo studente acquisirà competenze che gli permetteranno di formulare modelli di ottimizzazione lineare continua e discreta, compresi quelli di flusso su reti. Apprenderà inoltre proprietà matematiche che lo condurranno alla progettazione di approcci algoritmici di base per due importanti classi di problemi di ottimizzazione: problemi di flusso su rete e programmazione lineare.

Knowledge

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 and the most relevant implementation details (complexity, data structures, ...) of the solution algorithms for two important classes of "easy" problems (network flows and linear programming); furthermore, she/he will be able to construct formulations using the most useful formalism in practice, that of Integer Linear Programming.

Modalità di verifica delle conoscenze

L'esame scritto ed orale ha lo scopo di verificare che lo studente conosca le principali tecniche algoritmiche presentate durante il corso; conosca le motivazioni teoriche che rendono corretti gli algoritmi e che sappia formulare problemi di ottimizzazione con struttura non troppo articolata.

Assessment criteria of knowledge

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 solving exercises 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. The oral exam will in any case cover all the theoretical and algorithmic material of the course.

Capacità

Lo studente sarà in grado di formulare modelli matematici per alcuni problemi applicativi, e risolvere problemi di flusso su rete e problemi di programmazione lineare.

Skills

The student will be able to formulate mathematical methods for some linear optimization problems continuous or discrete including those described on networks and graphs.

Comportamenti

Lo studente acquisirà non solo competenze ma anche capacità critiche che, sia a livello modellistico che algoritmico, risulteranno rilevanti in svariati ambiti lavorativi, sia a livello progettuale che implementativo.

Behaviors

The student will acquire critical capacities both for mathematical models and linear optimization algorithms.

Prerequisiti (conoscenze iniziali)

Fondamenti di Algebra Lineare e di Algoritmica.

Prerequisites

Fundamentals of linear algebra and algorithms.

Indicazioni metodologiche

Il corso è concepito per lezioni frontali e studio individuale.

La frequenza seppur non obbligatoria, è fortemente consigliata.

Teaching methods

Delivery: face to face

Learning activities:

  • attending lectures
  • individual study

Attendance: Advised

Teaching methods:

  • Lectures
Programma (contenuti dell'insegnamento)

Formulazione di problemi di ottimizzazione: dati, variabili, vincoli. Problemi di produzione, di trasporto, di assegnamento. Variabili discrete e continue. Modelli standard per software esistenti. Programmazione Lineare. Soluzioni ammissibili ed ottime. Poledri e loro rappresentazione geometrica e matriciale. Teorema fondamentale della PL. Soluzioni di base e vertici. Teoria della dualità e test di ottimalità. Algoritmo del simplesso primale. Algoritmo del simplesso duale. Il caso delle variabili intere e binarie. Le valutazioni superiori ed inferiori. Algoritmi "greedy". Il metodo dei piani di taglio. Piani di taglio di Gomory.

Problemi su reti. Cammini minimi, flusso massimo, flusso di costo minimo. Matrici di incidenza, capacità, costi, bilanci. Alberi di copertura e basi. Poliedro dei flussi. Flussi di base su reti non capacitate e capacitate. La tecnica della tripartizione degli archi. Problema dei potenziali. Potenziali di base. Teorema di Bellman. Algoritmo del simplesso su reti non capacitate; algoritmo del simplesso su reti capacitate. L'algoritmo di Ford-Fulkerson.

Il metodo del "Branch and Bound". Il problema dello zaino ed il problema del "commesso viaggiatore". Cenni di complessità computazionale. 

Syllabus

The course will cover the following material: = - Linear Programs: definitions, geometrical and algebraic properties = duality theory = the primal and dual simplex algorithm - Network Flow problems and algorithms: = Maximum Flows = Min-Cost Flows - Integer Linear Programs: = Cutting plane methods = "Branch and Bound"

Bibliografia e materiale didattico
  • M.Pappalardo-M.Passacantando, Ricerca Operativa, Casa Editrice Pisa University Press.
  • F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli.
Bibliography

Pappalardo M., Passacantando M., “Ricerca Operativa”, Pisa University Press.

F.S. Hillier, G.J. Lieberman, "Introduzione alla ricerca operativa", Franco Angeli.

Modalità d'esame

Prova scritta e prova orale. Sono esonerati dalla prova scritta gli studenti che hanno superato entrambe le verifiche intermedie

Assessment methods

Written and oral examination.

Ultimo aggiornamento 14/07/2017 10:13