Ricerca Operativa B

Antonio Frangioni      Tel. 0502212789

Per sostenere l'esame e' necessario aver superato gli esami di Algoritmica e Laboratorio (008AA) e Matematica Discreta (006AA). Sarebbe opportuno, inoltre, aver superato l'esame di Analisi Matematica (005AA).

Il corso si prefigge l'obiettivo di guidare lo studente nella formulazione di modelli matematici per rilevanti problemi applicativi, e di illustrare tecniche algoritmiche, per alcune famiglie base di problemi di ottimizzazione, a partire da proprietà teoriche caratterizzanti tali famiglie (i problemi di flusso su rete ed i problemi di programmazione lineare).

Conoscenze. Lo studente acquisirà competenze che gli permetteranno di formulare significativi modelli di ottimizzazione, prevalentemente modelli di flusso su rete e modelli di ottimizzazione, ma anche modelli di programmazione lineare intera. 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.

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

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.

Il corso presenta gli strumenti necessari alla definizione e alla risoluzione di modelli analitici di ottimizzazione per problemi reali, tipicamente di gestione, di allocazione delle risorse e di logistica. Verranno introdotte proprietà teoriche ed alcune delle principali tecniche algoritmiche per la risoluzione di due grandi famiglie di problemi di ottimizzazione: i problemi di flusso su rete ed i problemi di programmazione lineare.

This is a basic Operations Research course. It presents the general concept of mathematical model, focusing on optimization problems, recalls complexity results about "hard" and "easy" problems, then presents in some detail efficient algorithms for some important classes of "easy" optimization problems such as path and flow problems on graphs and linear programs. These are the basic tools for constructing algorithms for "hard" problems, in particular general Mixed-Integer Programming ones; the course shows that very many practical problems in management, allocation of resources and logistics can be formulated as MIPs, although it does not directly present solution algorithms for them.

1. Introduzione (2 ore)

   • Problemi decisionali, problemi di ottimizzazione ed esistenza
   • Classi di problemi: alcuni esempi.

2. Grafi e Reti di flusso (18 ore)

   • Un modello generale per i problemi di flusso su rete
   • Il problema dei cammini minimi
   • Il problema del flusso massimo
   • Il problema del flusso di costo minimo
     
   • Problemi di accoppiamento

3. Programmazione Lineare (18 ore)

   • Modelli di Programmazione Lineare e loro interpretazione geometrica
   • Teoria della dualità
   • Algoritmo del Simplesso Primale e sua interpretazione geometrica
   • Algoritmo del Simplesso Duale e sua interpretazione geometrica
   • Riottimizzazione ed analisi parametrica
     

4. Programmazione Lineare Intera (10 ore)

   • Tipi di variabili: logiche, continue, discrete
   • Formulazioni di vincoli
   • Formulazioni della funzione obiettivo
   • Esempi di problemi reali.

Prova scritta seguita da una prova orale. Sono ammessi alla prova orale solamente gli studenti che hanno superato la prova scritta (con votazione pari almeno a "quasi sufficiente"). Sono esonerati dalla prova scritta gli studenti che hanno superato entrambe le verifiche intermedie.