Ricerca operativa C

Maria Grazia Scutellà      Tel. 0502212771

1. AA001 Analisi Matematica

2. AA005 Algebra

3. AA006 Algoritmica

Fornire allo studente le conoscenze di base relative alla modellistica, ai problemi di flusso su rete e alla Programmazione Lineare.

Il corso si propone di fornire allo studente gli strumenti di base per:

analizzare problemi reali, tipicamente di gestione, di allocazione delle risorse e di logistica, individuandone le caratteristiche principali per fornire una sua modellazione mediante strumenti logico/matematici;

studiare le proprietà di alcuni problemi di ottimizzazione su rete e descrivere ed utilizzare alcuni algoritmi risolutivi;

conoscere le proprietà teoriche della programmazione lineare, derivando da esse gli schemi algoritmici del simplesso primale e del simplesso duale.

The aim of the course is to provide basic knowledge to model real life management, resource allocation and logistics problems, and to formulate and solve network flow and linear programming problems.
Specifically, problem analysis and mathematical formulation, network flow algorithms and linear programming simplex approaches will be presented.

1. Problemi e modelli (12 ore)
   • La Ricerca Operativa: formulazione e risoluzione di problemi.
   • Problemi decisionali, problemi di ottimizzazione e di esistenza.
   • Uso di variabili (logiche, discrete, continue, a valori prefissati, ...).
   • Formalizzazione di relazioni e vincoli (relazioni logiche, assegnazione di elementi, selezione di sottoinsiemi, vincoli di soglia, ...).
   • Rappresentazione di funzioni (funzioni con carico fisso, funzioni lineari a tratti, funzioni di soglia, ...).

2. Grafi e reti di flusso (12 ore)
   • Introduzione ai problemi di flusso su rete.
   • Algoritmi di visita di un grafo.
   • Il problema dell'albero dei cammini minimi: proprietà e algoritmi.
   • Il problema dell'albero di copertura ottimo: proprietà e algoritmi.
   • Il problema del flusso massimo: proprietà e algoritmi.

3. Programmazione Lineare (18 ore)
   • Coppie di problemi duali e relazioni tra problema primale e problema duale.
   • Geometria della programmazione lineare.
   • Vincoli attivi e non attivi, direzioni, direzioni ammissibili e/o di crescita; lemma di Farkas.
   • Teoria matematica della dualità; teorema forte della dualità e teorema degli scarti complementari.
   • Basi complementari, considerazioni geometriche; algoritmi del simplesso primale e del simplesso duale.
   • Tecniche della programmazione lineare per problemi di flusso.
   • Riottimizzazione ed analisi parametrica.

1. G. Bigi, A. Frangioni, G. Gallo, S. Pallottino, M.G. Scutellà, Appunti del corso.
2. F.S. Hillier, G.J. Lieberman, "Introduction to Operations Research", McGraw Hill (1990).
3. R.K. Ahuja, T.L. Magnanti, J.B. Orlin, "Network Flows: theory, algorithms, and applications", Prentice-Hall (1993).

Scritto e orale.