Ricerca Operativa B

Per sostenere l'esame e' necessario aver superato gli esami di Algoritmica e Laboratorio (008AA) e Matematica Discreta (006AA).

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.

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.

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.

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.

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

Prova scritta seguita da una prova orale. Sono ammessi alla prova orale solamente gli studenti che hanno superato la prova scritta. Sono esonerati dalla prova scritta gli studenti che hanno superato entrambe le verifiche intermedie.